4 ms·

If objects know where they are, why do you need sorted ordering? If you need sorted ordering, it sounds like you're (regularly!) iterating over it. But iteratin

If objects know where they are, why do you need sorted ordering? If you need sorted ordering, it sounds like you're (regularly!) iterating over it. But iterating over a linked list is incredibly slow. This is where Big-O just really doesn't have a strong relationship with performance. Iterating over a linked-list is O(N), same as a vec. But in the real world it's nowhere close to as fast. So then if you're not regularly iterating over it a bag implemented with a vec is likely a better option. Then just have a bool that tracks if it's sorted or not, and in the (relatively) rare case you need sorted traversal just sort() it first.

xigoi 5y ago
Ordered is not the same thing as sorted. If you do swap-removals, there's no way to sort the array back into the original order unless you also keep track of insertion time, which adds memory overhead.
- kllrnohj 5y ago
  Storing pointers in a linked list also adds memory overhead, too. Insertion time in nanoseconds is only 8 bytes - same as a single pointer on 64-bits. So half the memory usage as a doubly linked list.
josephg 5y ago
You can get the best of both worlds - fast iteration and fast insert speed - by using a tree. Essentially use a b-tree as a list, and in internal nodes count the number of items contained in each child. Inserts traverse down the tree to find the insert position, insert there and then traverse back up the tree updating indexes. Each leaf should contain a small array of items, and when inserting you can memmove the existing items to to make space. Tuning the size of that array lets you balance the cost of memcpy vs the cost of pointer indirection & allocations on insert. The whole construction ends up extremely efficient in practice for this kind of thing, since you get log(n) indexed lookup and log(n) insert time. I don’t know why they aren’t used more.
- kllrnohj 5y ago
  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).

xigoi 5y ago

Ordered is not the same thing as sorted. If you do swap-removals, there's no way to sort the array back into the original order unless you also keep track of insertion time, which adds memory overhead.

kllrnohj 5y ago
Storing pointers in a linked list also adds memory overhead, too. Insertion time in nanoseconds is only 8 bytes - same as a single pointer on 64-bits. So half the memory usage as a doubly linked list.

josephg 5y ago

You can get the best of both worlds - fast iteration and fast insert speed - by using a tree. Essentially use a b-tree as a list, and in internal nodes count the number of items contained in each child. Inserts traverse down the tree to find the insert position, insert there and then traverse back up the tree updating indexes. Each leaf should contain a small array of items, and when inserting you can memmove the existing items to to make space. Tuning the size of that array lets you balance the cost of memcpy vs the cost of pointer indirection & allocations on insert. The whole construction ends up extremely efficient in practice for this kind of thing, since you get log(n) indexed lookup and log(n) insert time. I don’t know why they aren’t used more.

kllrnohj 5y ago
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).