4 ms·

>> This includes problems that they should be great for, like insert into the middle or the front. How is a vector good for inserting elements in the middle? T

>> This includes problems that they should be great for, like insert into the middle or the front. How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from? >> your default be a vector and not a linked list The default should be to understand the problem.

llbeansandrice 4y ago
I think by “middle” they mean “at the current position” not at an arbitrary position in the middle when starting from HEAD
tsimionescu 4y ago
> How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from? Both an array and a linked list are O(n) for adding in the middle. In an array, you finding the middle element is O(1), then moving the rest of the array is O(n) [you have to move n/2 elements]. In a linked list, finding the middle element is O(n) [you have to traverse n/2 elements], but adding it is O(1). So, asymptotically there is no difference. In practice though, the linked list traversal will cause O(n) cache misses to reach the middle element (since we are traversing random memory), while the array move will only incur O(1) cache misses (since we are accessing memory in order) - so, the array will actually win in practice. Edit: Note that I also don't know where the GP got the O(lg n).
- osigurdson 4y ago
  It seems that the case where it is necessary to find the exact middle element and insert something wouldn't be very common but OK, I'll humor this use case. Let's assume that the list is huge and inserting at the middle is the only thing we do. Just maintain a pointer to the middle element and insert there: O(1) for find and insert. If it is necessary to add/remove at other places in the list, it is possible to maintain a doubly linked list and move the middle pointer back and forth accordingly (still O(1)). I suppose if the LL like structure is mostly read only with rare inserts, not that big and holds simple data types or structs and often needs to be read sequentially then an array/vector/list would be better than a regular LL but then it is obvious that an array is better anyway. It's poor guidance to tell people that the vector is the "go to" when you need a LL. Sad actually that this poor guidance has been upvoted by so many people such that it is the top comment, all in the name of some FUD about cache misses.
  - tsimionescu 4y ago
    Let's take the case where we need to add to any element of the structure, with uniform probability. For an array, this means we'll have to move N elements if we need to add at the beginning, N/2 if exactly in the middle, or 0 if at the end. Either way, we'll need to re-size the array, which has some chance of requiring N copies anyway - say, half the time. So, on average, we'll perform 3N/4 moves per element added, requiring 1 cache miss every time. For a (doubly-)linked list, this means we'll have to traverse 0 elements if we want to add right before Head, 0 if we want to add right after Tail, and worse case we'll need to traverse N/2 nodes if right in the middle - so, we'll have to do on average N/4 traversals per element added. Each of the nodes traversed will generally be a cache miss, so N/4 cache misses. So, the Linked List will indeed be require a third the number of operations on average, but many times more cache misses, so should be expected to lose. If you store the middle pointer as well, you'll again half the number of operations for the list, but that still won't cover the amount of time wasted on cache misses. Of course, if the distribution is not uniform and is in fact skewed near a predictable element of the linked list, at some level of skewed-ness vs cache speed advantage, the Linked List will overtake the array. Note that linked lists also have other advantages - for example, they can be used as in the Linux kernel to store the same object in multiple different lists without any copying and without extra pointer indirections (at a small cost of one extra pointer in the object per list it could be a member of). They are also easier to pack into a small address space that has to be dynamically allocated (since you don't require a large contiguous block).
xenadu02 4y ago
A good balance is a tree with about a cache line's worth of values at each node. It degrades to a vector for small N, gets the pre-fetching / branch prediction benefit for medium N, but doesn't require fully contiguous memory for large N. It also tends to do fairly well on common mutation patterns (insertions and deletions) by avoiding large copies. If you want lock-free atomic data structures there are lots of variations (like AVL trees) that can be used as the underlying storage and just like mentioned above it tends to work well for most use cases and access patterns. If N is fairly small and/or you allocate most of your linked list around the same time it may not matter which is why measuring your actual program with real-world data and access patterns is so important. eg if in production logging or other malloc traffic ends up making your linked list nodes spread out in memory perf is not going to match what you tested at your desk. Often an algorithm can operate on an entire cache line's worth of data before main memory can chase down a single pointer. Modern CPUs hide that with prediction but even if the address prediction is 100% accurate if the result is a pointer loading chain you run out of pre-fetch slots pretty fast. To give concrete numbers if DRAM is not busy refreshing and there is no bus contention or inter-core contention then we might get 60-100ns access times all told. If we have a 3Ghz CPU then that's 300 cycles waiting around doing nothing... for each pointer that needs to be dereferenced. For a vector after the first 300 cycle hit the rest would be free - following nodes are in the cache line and address prediction will pre-fetch subsequent cache lines as well, allowing pre-fetching to stream data ahead of when it is needed.

llbeansandrice 4y ago

I think by “middle” they mean “at the current position” not at an arbitrary position in the middle when starting from HEAD

tsimionescu 4y ago

> How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from? Both an array and a linked list are O(n) for adding in the middle. In an array, you finding the middle element is O(1), then moving the rest of the array is O(n) [you have to move n/2 elements]. In a linked list, finding the middle element is O(n) [you have to traverse n/2 elements], but adding it is O(1). So, asymptotically there is no difference. In practice though, the linked list traversal will cause O(n) cache misses to reach the middle element (since we are traversing random memory), while the array move will only incur O(1) cache misses (since we are accessing memory in order) - so, the array will actually win in practice. Edit: Note that I also don't know where the GP got the O(lg n).

osigurdson 4y ago
It seems that the case where it is necessary to find the exact middle element and insert something wouldn't be very common but OK, I'll humor this use case. Let's assume that the list is huge and inserting at the middle is the only thing we do. Just maintain a pointer to the middle element and insert there: O(1) for find and insert. If it is necessary to add/remove at other places in the list, it is possible to maintain a doubly linked list and move the middle pointer back and forth accordingly (still O(1)). I suppose if the LL like structure is mostly read only with rare inserts, not that big and holds simple data types or structs and often needs to be read sequentially then an array/vector/list would be better than a regular LL but then it is obvious that an array is better anyway. It's poor guidance to tell people that the vector is the "go to" when you need a LL. Sad actually that this poor guidance has been upvoted by so many people such that it is the top comment, all in the name of some FUD about cache misses.
- tsimionescu 4y ago
  Let's take the case where we need to add to any element of the structure, with uniform probability. For an array, this means we'll have to move N elements if we need to add at the beginning, N/2 if exactly in the middle, or 0 if at the end. Either way, we'll need to re-size the array, which has some chance of requiring N copies anyway - say, half the time. So, on average, we'll perform 3N/4 moves per element added, requiring 1 cache miss every time. For a (doubly-)linked list, this means we'll have to traverse 0 elements if we want to add right before Head, 0 if we want to add right after Tail, and worse case we'll need to traverse N/2 nodes if right in the middle - so, we'll have to do on average N/4 traversals per element added. Each of the nodes traversed will generally be a cache miss, so N/4 cache misses. So, the Linked List will indeed be require a third the number of operations on average, but many times more cache misses, so should be expected to lose. If you store the middle pointer as well, you'll again half the number of operations for the list, but that still won't cover the amount of time wasted on cache misses. Of course, if the distribution is not uniform and is in fact skewed near a predictable element of the linked list, at some level of skewed-ness vs cache speed advantage, the Linked List will overtake the array. Note that linked lists also have other advantages - for example, they can be used as in the Linux kernel to store the same object in multiple different lists without any copying and without extra pointer indirections (at a small cost of one extra pointer in the object per list it could be a member of). They are also easier to pack into a small address space that has to be dynamically allocated (since you don't require a large contiguous block).

xenadu02 4y ago

A good balance is a tree with about a cache line's worth of values at each node. It degrades to a vector for small N, gets the pre-fetching / branch prediction benefit for medium N, but doesn't require fully contiguous memory for large N. It also tends to do fairly well on common mutation patterns (insertions and deletions) by avoiding large copies. If you want lock-free atomic data structures there are lots of variations (like AVL trees) that can be used as the underlying storage and just like mentioned above it tends to work well for most use cases and access patterns. If N is fairly small and/or you allocate most of your linked list around the same time it may not matter which is why measuring your actual program with real-world data and access patterns is so important. eg if in production logging or other malloc traffic ends up making your linked list nodes spread out in memory perf is not going to match what you tested at your desk. Often an algorithm can operate on an entire cache line's worth of data before main memory can chase down a single pointer. Modern CPUs hide that with prediction but even if the address prediction is 100% accurate if the result is a pointer loading chain you run out of pre-fetch slots pretty fast. To give concrete numbers if DRAM is not busy refreshing and there is no bus contention or inter-core contention then we might get 60-100ns access times all told. If we have a 3Ghz CPU then that's 300 cycles waiting around doing nothing... for each pointer that needs to be dereferenced. For a vector after the first 300 cycle hit the rest would be free - following nodes are in the cache line and address prediction will pre-fetch subsequent cache lines as well, allowing pre-fetching to stream data ahead of when it is needed.