4 ms·

But then your objects are scattered all over the address space, which means that objects you’re accessing in sequence are unlikely to be in the same cache line,

But then your objects are scattered all over the address space, which means that objects you’re accessing in sequence are unlikely to be in the same cache line, so you pay a cache miss on every single access. Having (maybe?) more efficient malloc/free in exchange for dramatically increasing the cost of accessing your data is not a good trade-off for most access patterns. See Chandler Carruth’s talk from CppCon 2014: https://youtu.be/fHNmRkzxHWs?t=2085 https://youtu.be/fHNmRkzxHWs?t=2085

dragontamer 6y ago
But the entire point of linked lists is to insert in the middle in constant time. 1 -> 2 -> 3 -> 4 Can become... 1 -> 2 -> 2.5 -> 3 -> 4 If you do that with arrays, you need a O(n) memcpy and maybe even a realloc. ----------- Furthermore, linked lists don't even need a malloc routine !!!!!! See Knuth's dancing links (DXL) algorithm. The ability to efficiently add and remove nodes from a linked list (even if that list was statically allocated) can sometimes beat the performance of arrays, because memcpy is just asymptotically slower than insert / remove.
- gameswithgo 6y ago
  Yes, but if you actually measure some scenarios, it is usually overall faster to pay the cost of O(1) copy. This of course depends on how often you insert things into the middle, vs how often you iterate over the collection. But on a modern computer it is surprising how big that ratio needs to be! In Knuths prime this tradeoff didn't really exist, because memory accesses were about at the same speed as executing an instruction, rather than ~200 times slower.
  - dragontamer 6y ago
    Knuth's Dancing Links is originally from 2001, and was first published to book form in Fasicle 6 (2019). Dancing Links seems to have outstanding performance for a generic cover problem, even on modern cache heavy processors. It seems like the static layout of the links benefits greatly from cache locality. Seriously, study the algorithm before hating on it. EDIT: Knuth's original writing style may be "too mathematical" for some. Here's a dumbed down version: https://medium.com/javarevisited/building-a-sudoku-solver-in-java-with-dancing-links-180274b0b6c1 https://medium.com/javarevisited/building-a-sudoku-solver-in... The original Knuth: https://arxiv.org/abs/cs/0011047 https://arxiv.org/abs/cs/0011047 The 2001 code is suboptimal in a few ways compared to the more recent updates. Knuth discusses the updates in Fasicle 6, the cweb source code is: https://www-cs-faculty.stanford.edu/~knuth/programs/dlx1.w https://www-cs-faculty.stanford.edu/~knuth/programs/dlx1.w ------------------- EDIT: But... I hate it when people tell me to read other papers without pointing out the issue. :-) The specific issue is that in Dancing Links: 1 -> 2 -> 3 becomes 1->3, and then later becomes 1 -> 2 -> 3 again. This pattern of insert (and then un-insert at the same place) means that all linked-list operations will execute in L1 cache. Furthermore, Knuth lays out the data such that 1, 2, and 3 are sequential in memory. So the entire process is incredibly cache-efficient and takes advantage of both temporal and spatial locality. (Because 1 usually inserts / removes 2, and because 1 and 2 are always next to each other in memory, you're never leaving L1 cache). As such, all DXL-operations are outstandingly fast. Furthermore, the pattern of insert-uninsert is useful for Exact Cover (which Knuth then used to solve graph coloring, N-Queens, Sudoku, and other NP-complete problems at relatively high speed). No, its not a generic SAT solver, but it does pretty darn good, especially considering how simple the operations are.
- jasode 6y ago
  >, you need a O(1) memcpy I didn't downvote your comments but memcpy is O(n) instead of O(1) : https://stackoverflow.com/questions/362760/how-do-realloc-and-memcpy-work https://stackoverflow.com/questions/362760/how-do-realloc-an... I'll delete this reply if you meant something else.
  - dragontamer 6y ago
    Ah jeez. That's what I get for typing fast. Yeah, I mean O(1) insert / remove for linked lists, and O(n) memcpys (most array insert / remove operations) EDIT: I've edited my post above. I think its correct now. Thanks for pointing out the error.
- eniotna 6y ago
  In most real world problems, you don't really care about keeping a data structure sorted at all time. All you want, is to have it sorted when you're about to do X. So it's generally faster to just have a contiguous chunk, insert at the end, then sort when you need.
  - dragontamer 6y ago
    And ironically, that's when we get into fragmentation issues for arrays! Growing the array from size 8 -> 16 -> 32 -> 64 ... 1024->2048 makes it harder, and harder to find contiguous, exponentially growing chunks. If you have a fragmented memory allocator, you may run out of memory due to fragmentation. In contrast, if each of those elements were a small and constant-sized 8-byte chunk (or 16-byte chunk), then you'd be able to fit that small chunk anywhere. ----------------- Anyway, I agree with you that vector.push_back() is an outstanding methodology on modern systems. But Linked-Lists aren't as bad as people make them out to be.
    - alexhutcheson 6y ago
      What environment are you working in where this is a problem in practice? In tiny embedded devices with very limited memory, you do all your allocation at startup and avoid malloc during runtime, so you’d never run into this. On server, desktop, or even smartphone applications, I’ve never run into cases where “the allocator was unable to get a chunk of memory to complete a vector resize()” is a significant problem. If my vector is going to be a significant fraction of the memory available on the system, I generally know that up-front, and would just call reserve() with a conservative estimate of the upper-found size. That’s pretty rare though - not many problems call for vectors that are 1+ GB in size. For anything that’s not a significant fraction of the system’s available memory, the allocator can generally find you a chunk.
      - dragontamer 6y ago
        I've been experimenting with data-structures on GPUs. 8GBs of RAM to share across 4096 SIMD-cores (well... 64 "compute units" with 64-way SIMD... you know...). But Vega64 runs 4-threads per SIMD-core, so you actually need 16384-SIMD threads before you utilize the processor. (And at occupancy 10, you have 10-threads per hardware thread, or 163840 SIMD-threads total) Anyway, you run out of RAM really, really quickly if you try to give data-structures to each of those SIMD individually. 8GBs RAM / 16384-GPU-threads is 500kB per GPU-thread... 50kB at the theoretical max occupancy 10. Yeah, you want your data-structures to be read-mostly so that your 16384-threads can all be reading the same stuff. But every now and then, you need a per-GPU-thread data-structure. And... well... there's not a lot of per-GPU-thread data available (because you have so many darn threads...) -------- You end up using Linked lists, even though GPU latency is wtf terrible. Like really, really, really bad. If you think a CPU's 50-nanosecond DDR4 access time is slow, try 500ns or even 1000ns for a linked-list "node = node->next" operation on GPUs. And GPUs are in-order too, so no out-of-order latency hiding for you...
- penetraitor69 6y ago
  My understanding is that push/pop from the front/back of linked lists are constant time, but that inserts in the middle necessitate looping through the linked list until you get to the correct index, which is a O(n) operation.
  - dragontamer 6y ago
    > but that inserts in the middle necessitate looping through the linked list until you get to the correct index, which is a O(n) operation. Not if you save the node you are working on. Inserting (when you have a node) is simply: NewNode = malloc(...) or new or something. NewNode.next = node.next node.next = NewNode
    - penetraitor69 6y ago
      Oh, gotcha; I just meant in the general case.

dragontamer 6y ago

But the entire point of linked lists is to insert in the middle in constant time. 1 -> 2 -> 3 -> 4 Can become... 1 -> 2 -> 2.5 -> 3 -> 4 If you do that with arrays, you need a O(n) memcpy and maybe even a realloc. ----------- Furthermore, linked lists don't even need a malloc routine !!!!!! See Knuth's dancing links (DXL) algorithm. The ability to efficiently add and remove nodes from a linked list (even if that list was statically allocated) can sometimes beat the performance of arrays, because memcpy is just asymptotically slower than insert / remove.

gameswithgo 6y ago
Yes, but if you actually measure some scenarios, it is usually overall faster to pay the cost of O(1) copy. This of course depends on how often you insert things into the middle, vs how often you iterate over the collection. But on a modern computer it is surprising how big that ratio needs to be! In Knuths prime this tradeoff didn't really exist, because memory accesses were about at the same speed as executing an instruction, rather than ~200 times slower.
- dragontamer 6y ago
  Knuth's Dancing Links is originally from 2001, and was first published to book form in Fasicle 6 (2019). Dancing Links seems to have outstanding performance for a generic cover problem, even on modern cache heavy processors. It seems like the static layout of the links benefits greatly from cache locality. Seriously, study the algorithm before hating on it. EDIT: Knuth's original writing style may be "too mathematical" for some. Here's a dumbed down version: https://medium.com/javarevisited/building-a-sudoku-solver-in-java-with-dancing-links-180274b0b6c1 https://medium.com/javarevisited/building-a-sudoku-solver-in... The original Knuth: https://arxiv.org/abs/cs/0011047 https://arxiv.org/abs/cs/0011047 The 2001 code is suboptimal in a few ways compared to the more recent updates. Knuth discusses the updates in Fasicle 6, the cweb source code is: https://www-cs-faculty.stanford.edu/~knuth/programs/dlx1.w https://www-cs-faculty.stanford.edu/~knuth/programs/dlx1.w ------------------- EDIT: But... I hate it when people tell me to read other papers without pointing out the issue. :-) The specific issue is that in Dancing Links: 1 -> 2 -> 3 becomes 1->3, and then later becomes 1 -> 2 -> 3 again. This pattern of insert (and then un-insert at the same place) means that all linked-list operations will execute in L1 cache. Furthermore, Knuth lays out the data such that 1, 2, and 3 are sequential in memory. So the entire process is incredibly cache-efficient and takes advantage of both temporal and spatial locality. (Because 1 usually inserts / removes 2, and because 1 and 2 are always next to each other in memory, you're never leaving L1 cache). As such, all DXL-operations are outstandingly fast. Furthermore, the pattern of insert-uninsert is useful for Exact Cover (which Knuth then used to solve graph coloring, N-Queens, Sudoku, and other NP-complete problems at relatively high speed). No, its not a generic SAT solver, but it does pretty darn good, especially considering how simple the operations are.
jasode 6y ago
>, you need a O(1) memcpy I didn't downvote your comments but memcpy is O(n) instead of O(1) : https://stackoverflow.com/questions/362760/how-do-realloc-and-memcpy-work https://stackoverflow.com/questions/362760/how-do-realloc-an... I'll delete this reply if you meant something else.
- dragontamer 6y ago
  Ah jeez. That's what I get for typing fast. Yeah, I mean O(1) insert / remove for linked lists, and O(n) memcpys (most array insert / remove operations) EDIT: I've edited my post above. I think its correct now. Thanks for pointing out the error.
eniotna 6y ago
In most real world problems, you don't really care about keeping a data structure sorted at all time. All you want, is to have it sorted when you're about to do X. So it's generally faster to just have a contiguous chunk, insert at the end, then sort when you need.
- dragontamer 6y ago
  And ironically, that's when we get into fragmentation issues for arrays! Growing the array from size 8 -> 16 -> 32 -> 64 ... 1024->2048 makes it harder, and harder to find contiguous, exponentially growing chunks. If you have a fragmented memory allocator, you may run out of memory due to fragmentation. In contrast, if each of those elements were a small and constant-sized 8-byte chunk (or 16-byte chunk), then you'd be able to fit that small chunk anywhere. ----------------- Anyway, I agree with you that vector.push_back() is an outstanding methodology on modern systems. But Linked-Lists aren't as bad as people make them out to be.
  - alexhutcheson 6y ago
    What environment are you working in where this is a problem in practice? In tiny embedded devices with very limited memory, you do all your allocation at startup and avoid malloc during runtime, so you’d never run into this. On server, desktop, or even smartphone applications, I’ve never run into cases where “the allocator was unable to get a chunk of memory to complete a vector resize()” is a significant problem. If my vector is going to be a significant fraction of the memory available on the system, I generally know that up-front, and would just call reserve() with a conservative estimate of the upper-found size. That’s pretty rare though - not many problems call for vectors that are 1+ GB in size. For anything that’s not a significant fraction of the system’s available memory, the allocator can generally find you a chunk.
    - dragontamer 6y ago
      I've been experimenting with data-structures on GPUs. 8GBs of RAM to share across 4096 SIMD-cores (well... 64 "compute units" with 64-way SIMD... you know...). But Vega64 runs 4-threads per SIMD-core, so you actually need 16384-SIMD threads before you utilize the processor. (And at occupancy 10, you have 10-threads per hardware thread, or 163840 SIMD-threads total) Anyway, you run out of RAM really, really quickly if you try to give data-structures to each of those SIMD individually. 8GBs RAM / 16384-GPU-threads is 500kB per GPU-thread... 50kB at the theoretical max occupancy 10. Yeah, you want your data-structures to be read-mostly so that your 16384-threads can all be reading the same stuff. But every now and then, you need a per-GPU-thread data-structure. And... well... there's not a lot of per-GPU-thread data available (because you have so many darn threads...) -------- You end up using Linked lists, even though GPU latency is wtf terrible. Like really, really, really bad. If you think a CPU's 50-nanosecond DDR4 access time is slow, try 500ns or even 1000ns for a linked-list "node = node->next" operation on GPUs. And GPUs are in-order too, so no out-of-order latency hiding for you...
penetraitor69 6y ago
My understanding is that push/pop from the front/back of linked lists are constant time, but that inserts in the middle necessitate looping through the linked list until you get to the correct index, which is a O(n) operation.
- dragontamer 6y ago
  > but that inserts in the middle necessitate looping through the linked list until you get to the correct index, which is a O(n) operation. Not if you save the node you are working on. Inserting (when you have a node) is simply: NewNode = malloc(...) or new or something. NewNode.next = node.next node.next = NewNode
  - penetraitor69 6y ago
    Oh, gotcha; I just meant in the general case.