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 [github.com] 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?
@martin I've been writing Rust for 5 years and professionally for 2 years, I've seen a linked list outside of some very specific use cases.
Yes, Rust Linked List are very limited and you will most likely fight the borrow checker.
Are you sure you need a linked list? In most cases a Vec will be more efficient, and you won't have as many borrow checking issue.
If the order of elements doesn't matter, you can even use Vec::swap_remove for O(1) removal of elements.
@sgued [pouet.chapril.org] I don't want to use Vec because:
- I don't want the collection to hog more memory than it actually needs.
- I want to be able to cheaply extend the collection
- I want to be able to cheaply remove items from arbitrary locations within the collection
@martin LinkedList will likely use more memory. Each LinkedList element needs:
2 additional pointers,
Additional metadata for the allocation (size depends on the allocator)
Pushing an element to a vec is faster than to a LinkedList because it doesn't always need to allocate..
Removing from arbitrary locations can be done through swap_remove. But even remove is likely to be faster than linked list due to not needing to reallocate.
@sgued [pouet.chapril.org] I cannot use swap_remove because the ordering in the list matters. My use case: friends.mbober.de/display/b22e…
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 @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).