I'm trying to get into #rustlang. I've already rewritten a small program and it was an okay experience but today, I hit something weird.
I have a LinkedList and need to iterate over it and, if I found any item that meets some criteria, I need to remove it from the list.
Using C++ iterators, this would be O(N).
Rust's linked_list has an issue open for more than 4 years (!) to add a remove function to linked lists. But even with that function, you'll need an index of the item to be removed and cannot (as far as I can tell) use the iterator you already have from scanning the list.
So in Rust I would need to spend O(N) to scan the list and an additional O(N) for each item I need removed.
Or is there a faster way to do that?
Tracking Issue for linked_list_remove · Issue #69210 · rust-lang/rust
#68705 adds a method in LinkedList to remove an element at a specified index. The feature gate for the issue is #![feature(linked_list_remove)].GitHub
teilten dies erneut
Ian Douglas Scott
Als Antwort auf Martin • • •Technically that's also O(n) (O(2n) = O(n)).
I don't see much Rust code using `LinkedList`. Probably its more common to just use `Vec`. Which in many cases will end up performing better overall, regardless of language.
Martin
Als Antwort auf Ian Douglas Scott • •brettwitty
Als Antwort auf Martin • • •Martin
Als Antwort auf brettwitty • •brettwitty
Als Antwort auf Martin • • •Martin mag das.
Epic Eric :thinkhappy:
Als Antwort auf Martin • • •Vec in std::vec - Rust
doc.rust-lang.orgEpic Eric :thinkhappy:
Als Antwort auf Epic Eric :thinkhappy: • • •std::collections - Rust
doc.rust-lang.orgMartin
Als Antwort auf Epic Eric :thinkhappy: • •That guide explicitly says I should use a LinkedList when:
Which is exactly why I want to use a linked list.
Vecseems like it would do a lot of unnecessary memory allocation for that.Epic Eric :thinkhappy:
Als Antwort auf Martin • • •Martin
Unbekannter Ursprungsbeitrag • •I don't want to use Vec because:
Martin
Unbekannter Ursprungsbeitrag • •Vec::retaincreate a whole new copy of the collection, i.e. I'll need twice the memory at that point?Martin
Unbekannter Ursprungsbeitrag • •Martin
Als Antwort auf Martin • •BTW what I want to do is a cache that stores a key/value pair (both are strings). When an entry is hit, I want to move it to the front of the list.
When there is no hit, a network request is issued to fetch the value for the key. The key/value pair is then emplaced at the front of the list. If the list is then over the maximum capacity, the item at the back shall be removed.
laund [old account, moved]
Als Antwort auf Martin • • •Martin
Als Antwort auf laund [old account, moved] • •In my experience, LinkedLists are great when the container is growing and shrinking dynamically or when you want to move stuff around within the collection while the rest of the items maintain their order. The downside is expensive random access to elements so list are better suited for use cases where you have to iterate through the collection anyways.
Vectors are better for access to random elements and if you know the size of the collection beforehand. It's also cheaper to insert elements at the end if the vector's current size can hold another element. Inserting elements anywhere other than the end or removing an element that is not at the front or back is ridiculously expensive.
laund [old account, moved]
Als Antwort auf Martin • • •i mean i kinda understand that, i just found it interesting the docs don't state this.
Though i kinda wanna do a benchmark of linked list inserting/removing elements in the middle vs vec = vec.iter().filter(remove_condition).collect() - how many elements do i need to filter out for a Vec to be faster? how much slower is iteration of linked lists?
theres a old benchmark by matklad which inserts random numbers into a sorted vec/list, which requires tons of insertions in the middle, that claims Vec is still far more performant at this.
Vev: 33365 μs
List: 184282 μs
https://github.com/matklad/vec-vs-list
but this was 8 years ago with a different linked list.
GitHub - matklad/vec-vs-list: Compare vector vs linked list in terms of performance
GitHubMartin mag das.
Martin
Unbekannter Ursprungsbeitrag • •I cannot use swap_remove because the ordering in the list matters. My use case: https://friends.mbober.de/display/b22eb8e8-4167-19df-204d-582842795229
As far as I know common C++ vector implementations, they do not release memory when removing an element from the vector unless many elements were removed since reducing the size of a vector means allocating new memory and copying all remaining elements which is quite expensive. I assume Rust's vec does the same. That is what I meant by "hogging" memory.
As I'm also exploring Rust for embedded applications. Performance and memory efficiency matters to me and I was told that Rust is as good as C++ in this regard.
Martin
Unbekannter Ursprungsbeitrag • •laund [old account, moved]
Als Antwort auf Martin • • •@sgued Just a general piece of advice:
Don't confuse "As good as C++ in this regard" with "Works the same way as C++" - while the characteristics can be very similar, the way you'll want to implement things are often quite different.
laund [old account, moved]
Als Antwort auf Martin • • •@sgued You could consider using or taking inspiration from the LRU used by the Servo browser https://github.com/servo/uluru
It uses a fixed size array to store all items, using u16s to create a linked list using the array indices of your items. Since its backed by a constant size array you know exactly how much memory it uses (well, unless your items are heap pointers like Vec, String etc.) - in this case: (your item + 2*u16)*n + 2*u16 which is also going to be more memory efficient than a linked list utilizing pointers on all architectures where u16 < usize
The fact it uses a static array also makes the crate work in no_std environments without an allocator (embedded).
GitHub - servo/uluru: A simple, fast, LRU cache implementation.
GitHubMartin mag das.