Re:Things you can’t do in Rust (and what to do instead)
by josephg on Saturday May 15, 2021 @11:47PM
(#27171046)
Hashmaps don't help at all if what you want is a list - because the items aren't ordered. The point isn't to use a hashmap with incrementing integer keys or something wacky like that. Its to use a b-tree (or a skip list) with all your list items stored in their desired order in the tree. In reality iterating through a b-tree is fast because the depth is small (~5-10), and all the parents stay in CPU cache during the iteration.
Iterating through a b-tree with a large branching factor (and multiple items at each leaf) is significantly faster than iterating through a linked list in practice, because main memory lookups dominate the linked list performance. With a b-tree you only need to do a main memory read after iterating every ~100 items (or whatever the leaf size is). With a linked list as you're describing you need to do it every item. Inserting is still O(1) - the branch size at each leaf is a constant factor. And its a small constant factor (memcpy is faster than you think it is.)
You can make linked lists fast for arbitrary insertions by storing forward pointers that skip more than 1 element, and by storing multiple elements at each leaf. If you do you end up with a skip list - which is a data structure with basically the same performance characteristics as a b-tree but a bit less performance stability.
Linked lists with a single item per node are basically never the appropriate data structure to use for any application. The only time I've seen them used in a sensible way was through clever use of intrusive lists in a physics engine, to avoid allocations & smooth out any spikes in allocator load from reallocating vectors. Even then the justification was bit dubious. Oh, and I've seen them used in JS where its much harder to implement high performance, complex data structures.
Anyway, I highly recommend anyone who's interested actually benchmark some different scenarios. Its remarkable how much of a difference good data structures make. The big insights I've had are that memcpy is way faster than I think it should be, and memory reads are way slower than I think. Vectors do perform well in practice, even with arbitrary inserts because of how fast memcpy is. But that gets beaten out by well written b-trees if you're doing inserting at arbitrary positions quite quickly (usually around when you have about 10k items in my experience).
Iterating through a b-tree with a large branching factor (and multiple items at each leaf) is significantly faster than iterating through a linked list in practice, because main memory lookups dominate the linked list performance. With a b-tree you only need to do a main memory read after iterating every ~100 items (or whatever the leaf size is). With a linked list as you're describing you need to do it every item. Inserting is still O(1) - the branch size at each leaf is a constant factor. And its a small constant factor (memcpy is faster than you think it is.)
You can make linked lists fast for arbitrary insertions by storing forward pointers that skip more than 1 element, and by storing multiple elements at each leaf. If you do you end up with a skip list - which is a data structure with basically the same performance characteristics as a b-tree but a bit less performance stability.
Linked lists with a single item per node are basically never the appropriate data structure to use for any application. The only time I've seen them used in a sensible way was through clever use of intrusive lists in a physics engine, to avoid allocations & smooth out any spikes in allocator load from reallocating vectors. Even then the justification was bit dubious. Oh, and I've seen them used in JS where its much harder to implement high performance, complex data structures.
Anyway, I highly recommend anyone who's interested actually benchmark some different scenarios. Its remarkable how much of a difference good data structures make. The big insights I've had are that memcpy is way faster than I think it should be, and memory reads are way slower than I think. Vectors do perform well in practice, even with arbitrary inserts because of how fast memcpy is. But that gets beaten out by well written b-trees if you're doing inserting at arbitrary positions quite quickly (usually around when you have about 10k items in my experience).