9 ms·

Trees don't give you fast iteration, though. You still end up with lots of pointer chases during iteration. The lookup is algorithmically fast, but it's even fa

Trees don't give you fast iteration, though. You still end up with lots of pointer chases during iteration. The lookup is algorithmically fast, but it's even faster on the more CPU-friendly hashset/hashmap. You can do what you describe without the tree by also having your linked list instead contain small arrays of items instead of individual items, but you then lose the property that you can stably point at an item in the list across inserts. And both then suffer from the problem that finding the element to remove (or insert at) is no longer O(1) as a result. Not as bad on the tree, of course, but you're into the realm of you really need to benchmark a specific implementation of the idea & outline the specific constraints to see if it really beats just the good ol' vector and/or hashmap.

TheCoelacanth 5y ago
B-trees[1] are pretty fast to iterate through as long as the branching factor is fairly large. If the branching factor is 100, you would only need to chase one pointer every 100 nodes (and in practice, even larger branching factors are common). They wouldn't be used so heavily in filesystems and databases if they were slow to iterate through. [1] https://en.wikipedia.org/wiki/B%2B_tree https://en.wikipedia.org/wiki/B%2B_tree
josephg 5y ago
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).

TheCoelacanth 5y ago

B-trees[1] are pretty fast to iterate through as long as the branching factor is fairly large. If the branching factor is 100, you would only need to chase one pointer every 100 nodes (and in practice, even larger branching factors are common). They wouldn't be used so heavily in filesystems and databases if they were slow to iterate through. [1] https://en.wikipedia.org/wiki/B%2B_tree https://en.wikipedia.org/wiki/B%2B_tree

josephg 5y ago

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).