9 ms·

Unrelated to the article, but perhaps an interesting fact: as a Java programmer you perhaps know that using the class java.util.LinkedList is almost always wors

Unrelated to the article, but perhaps an interesting fact: as a Java programmer you perhaps know that using the class java.util.LinkedList is almost always worse in than using plain arrays or ArrayList. Even though there are much less allocations, the overhead for maintaining the linked list data structures is immense. And it turns out that computers are pretty fast at allocating memory. But there more optimized implementations of linked lists of course (probably using arrays as well internally (?)).

ansible 6y ago
It is worth remembering that linked lists were invented back in the dawn of computing. This was when systems... often didn't even have cache memory at all. Accessing different RAM values took the same amount of time, and sometimes with a single clock cycle. Fast! So jumping around a (large, for the time) linked list in heap memory wasn't nearly as slow as something comparable today, relative to other data structures.
- mcculley 6y ago
  It is worse in Java. The standard LinkedList class in Java stores references to the data, not the data, in nodes, so there is more pointer chasing.
  - sltkr 6y ago
    This applies equally to ArrayList.
    - mcculley 6y ago
      Yes, but if you can use ArrayList, you can also use an array. If you want to be able to remove an object from the middle without moving objects around, you have no choice other than LinkedList and the extra references.
  - pjmlp 6y ago
    For the time being, value types will eventually fix that. Ironically some of the ideas how to proceed with value types integration were already present in Eiffel, but so are design decisions.
  - xirbeosbwo1234 6y ago
    So do arrays. You can never have an "inline" object. It's always a reference. Java has another problem because each node is an object, though. Every object has (I believe) about 16 bytes of overhead. That will double the size of each node.
- gpderetta 6y ago
  most importantly, those machines were not fully pipelined (if at all) and certainly not capable of out of order execution, so the inherent forced serialization of a linked list traversal was not an issue.
twic 6y ago
There is such a thing as an unrolled linked list, which is a bit like a flat B-tree: https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list They ought to have quite good properties. In particular, if you are appending one element at a time, they never need to copy, but are also quite dense. Iteration is then fast. Feels like it should be useful for buffering and aggregation type jobs. I have never seen one in a library.
- creata 6y ago
  I wonder whether someone's invented a way to take a nice ADT like data List a = Cons a (List a) | Nil and automatically unroll it to fill at least a cache line. That sounds like it'd be a small win for performance, but I don't know.
  - gsg 6y ago
    Yes, this has been done a few times. CDR-coding was a hardware-assisted method of unrolling a Lisp list (complicated somewhat by the need to support mutation of car and cdr) that appeared on Lisp machines, and there's a Appel/Reppy/Shao paper on unrolling linked lists in the context of Standard ML. There's also some interesting work on flattened versions of arbitrary tree structures: https://engineering.purdue.edu/~milind/docs/ecoop17.pdf https://engineering.purdue.edu/~milind/docs/ecoop17.pdf
- winrid 6y ago
  This was actually the correct answer to "build a linked list" interview question I did. They didn't explicitly ask for it to be unrolled, just sounded frustrated that I didn't make a fancy unrolled one. :)
Cthulhu_ 6y ago
This is the thing with algorithms and leetcode and the like; I've got about ten years of professional experience, and in all of my career (CRUD apps, full stack; sounds boring but I've touched many different industries) I've NEVER had to think about what data structure to use. Java's ArrayList was good enough in all cases, as was HashMap. Although one interesting thing, ConcurrentHashMap turned out to be faster in all my (bad) benchmarks. I'm doing Go nowadays, it does not have generics except for its built in lists (arrays/slices) and maps, and that covers 99% of my use cases as well. Anyway, I'll never work at Google or any company that does leetcode interviews because it's so far removed from (my?) reality.
- ALittleLight 6y ago
  I've been leetcoding recently and I feel like most leetcode problems have similar requirements to what you describe vis a vis data structures. I've been focusing on Medium difficulty, maybe it's different on hard, but I've been doing the occasional hard too and not noticed it. The problems mostly seem to be about realizing what algorithm you'll need and implementing it. I actually solved a problem recently that I thought would require a QuadTree, and after implementing one and solving the problem I was proud of myself until I looked at the other solutions and realized I didn't need a QuadTree at all. In my notes I recorded the problem as a likely fail, because if I were the interviewer I'd take unnecessary complexity as a red flag. Part of me, I think, just wanted the chance to implement a QuadTree.
- w1nk 6y ago
  I never enjoy seeing this line of argumentation pop up when we (as the computing industry) discuss practicalities of data structures and algorithm choices. I've got a bit over twice your time in the industry and one of the things that is still very clearly on an upward walk is the size of our N's (think big O) in all of our applications and across all of our data structures. I'm not sure what kinds of applications you're building, but if any of your collections contain on the orders of thousands/10s/100s thousands of items, you really should be considering the impact of how you shape that data for consumption inside your application. You hint at the need to do so, arraylists being good enough until they're not and then hashmaps, etc. I think there is a pretty reasonable line between expecting our engineers and peers to pick proper containers for the data they're consuming without stepping over into purely 'academic' territory. Shutting down the discussions with 'well I've never had to use this' feels a bit icky and not a great way to advance any of the conversation.
exDM69 6y ago
Yes, linked lists have terrible cache behavior and usually the performance of any packed structure with less pointer chasing should beat it. ArrayList, Vector, whatever you call it usually is faster. But computers aren't fast in allocating memory. In particular, they're not predictably fast in allocating memory, as most allocators will have complex internal data structures and may end up having to call the operating system to give fresh pages of unused memory. The best case may be smoking fast, the amortized cost may be decent but the worst case is pretty bad. So when reliable and predictable performance is needed, memory allocations are to be avoided. This is relevant if you're working on (soft) real time applications, say audio, games or so. And linked lists are still mighty fast in addition and removal, joining and splitting. Intrusive linked lists drop one extra pointer chase. In kernel space, there are tons of use cases for linked lists that are never traversed, or at least not traversed in the fast path. Traversal is the slow part, but that's not necessary for a lot of cases where you add something to a list or a set, and remove items one by one. There's no other data structure that beats linked lists when there's only addition, removal, joins and splits, but no traversals. Linked lists are almost always the wrong data structure for the job, but in special niche cases (which are not that rare, at least in kernel space) it's the simplest and most effective.
- pdpi 6y ago
  > Intrusive linked lists drop one extra pointer chase. Template-based lists (in the style of C++ STL) let you have your cake and eat it too in that you still keep the list structure out of your data, but you still get the cache locality of an intrusive list.
  - DSMan195276 6y ago
    I think your typical template-based list is actually a bad example :P Maybe there's something about C++ I don't know, but typically those implementations only allow for adding one list node (via the template wrapping), and also they can't usually take an element from one list and then attach it to another one. Where-as intrusive implementations like the Linux Kernel's allow for any number of list nodes or other data structures to be placed alongside the data, and the elements can be moved onto any list you want without any allocations necessary.
skohan 6y ago
> it turns out that computers are pretty fast at allocating memory Isn't this not the case? My understanding was that 90% of HPC is normally about making sure to avoid as many individual allocations/deallocations possible, because these are massively expensive compared to almost all user-space operations, and lead to cache-inefficient memory layouts, which can slow your code down by like a factor of 200
- chrisseaton 6y ago
  What do you think an allocation involves in a modern language implementation? It's about five machine instructions amortised. Load the allocation pointer, add the object size to it, check it's not got too large, store it. Deallocation though - yes that's slow!
  - joosters 6y ago
    That's the absolute best case for the simplest malloc implementation possible. In the real world, a malloc can involve picking an appropriate zone/arena based upon allocation size & the current thread, obtaining locks, chasing some pointers through its data structures, doing some book-keeping, perhaps even calling up to the OS to increase the process space. Maybe in the very best case it can just shuffle a couple of pointers, but over time it has to do a lot more than that.
    - kragen 6y ago
      Well, chrisseaton did say amortised, not worst-case. He wasn't talking about malloc, which is a C function that indeed cannot be that fast, but about a modern language implementation. Results from some trivial benchmarks are in my comments at https://news.ycombinator.com/item?id=26438596 https://news.ycombinator.com/item?id=26438596 and https://news.ycombinator.com/item?id=26449902 https://news.ycombinator.com/item?id=26449902. You can reason it out from first principles, though. Picking the right arena is done at compile time, and you don't obtain locks or chase pointers on the open-coded fast path. Maybe once every 1024 allocations you have to do all that jazz, which costs you another 128 instructions, 0.125 instructions per allocation. And maybe once very 1024 times you do that, you need to call up to the OS to increase the process space at a cost of about 4096 instructions or so, 0.004 instructions per allocation. So the allocation fast path dominates your amortized allocation performance, even though the cases you're talking about are what dominate your worst-case performance.
karmakaze 6y ago
In Java arrays or ArrayList usually mean 'of references' so don't get the full cache locality benefit until Valhalla ever gets done. For primitive types, there are numerous primitive collection libraries that use primitive values and optionally object references.

ansible 6y ago

It is worth remembering that linked lists were invented back in the dawn of computing. This was when systems... often didn't even have cache memory at all. Accessing different RAM values took the same amount of time, and sometimes with a single clock cycle. Fast! So jumping around a (large, for the time) linked list in heap memory wasn't nearly as slow as something comparable today, relative to other data structures.

mcculley 6y ago
It is worse in Java. The standard LinkedList class in Java stores references to the data, not the data, in nodes, so there is more pointer chasing.
- sltkr 6y ago
  This applies equally to ArrayList.
  - mcculley 6y ago
    Yes, but if you can use ArrayList, you can also use an array. If you want to be able to remove an object from the middle without moving objects around, you have no choice other than LinkedList and the extra references.
- pjmlp 6y ago
  For the time being, value types will eventually fix that. Ironically some of the ideas how to proceed with value types integration were already present in Eiffel, but so are design decisions.
- xirbeosbwo1234 6y ago
  So do arrays. You can never have an "inline" object. It's always a reference. Java has another problem because each node is an object, though. Every object has (I believe) about 16 bytes of overhead. That will double the size of each node.
gpderetta 6y ago
most importantly, those machines were not fully pipelined (if at all) and certainly not capable of out of order execution, so the inherent forced serialization of a linked list traversal was not an issue.

twic 6y ago

There is such a thing as an unrolled linked list, which is a bit like a flat B-tree: https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list They ought to have quite good properties. In particular, if you are appending one element at a time, they never need to copy, but are also quite dense. Iteration is then fast. Feels like it should be useful for buffering and aggregation type jobs. I have never seen one in a library.

creata 6y ago
I wonder whether someone's invented a way to take a nice ADT like data List a = Cons a (List a) | Nil and automatically unroll it to fill at least a cache line. That sounds like it'd be a small win for performance, but I don't know.
- gsg 6y ago
  Yes, this has been done a few times. CDR-coding was a hardware-assisted method of unrolling a Lisp list (complicated somewhat by the need to support mutation of car and cdr) that appeared on Lisp machines, and there's a Appel/Reppy/Shao paper on unrolling linked lists in the context of Standard ML. There's also some interesting work on flattened versions of arbitrary tree structures: https://engineering.purdue.edu/~milind/docs/ecoop17.pdf https://engineering.purdue.edu/~milind/docs/ecoop17.pdf
winrid 6y ago
This was actually the correct answer to "build a linked list" interview question I did. They didn't explicitly ask for it to be unrolled, just sounded frustrated that I didn't make a fancy unrolled one. :)

Cthulhu_ 6y ago

This is the thing with algorithms and leetcode and the like; I've got about ten years of professional experience, and in all of my career (CRUD apps, full stack; sounds boring but I've touched many different industries) I've NEVER had to think about what data structure to use. Java's ArrayList was good enough in all cases, as was HashMap. Although one interesting thing, ConcurrentHashMap turned out to be faster in all my (bad) benchmarks. I'm doing Go nowadays, it does not have generics except for its built in lists (arrays/slices) and maps, and that covers 99% of my use cases as well. Anyway, I'll never work at Google or any company that does leetcode interviews because it's so far removed from (my?) reality.

ALittleLight 6y ago
I've been leetcoding recently and I feel like most leetcode problems have similar requirements to what you describe vis a vis data structures. I've been focusing on Medium difficulty, maybe it's different on hard, but I've been doing the occasional hard too and not noticed it. The problems mostly seem to be about realizing what algorithm you'll need and implementing it. I actually solved a problem recently that I thought would require a QuadTree, and after implementing one and solving the problem I was proud of myself until I looked at the other solutions and realized I didn't need a QuadTree at all. In my notes I recorded the problem as a likely fail, because if I were the interviewer I'd take unnecessary complexity as a red flag. Part of me, I think, just wanted the chance to implement a QuadTree.
w1nk 6y ago
I never enjoy seeing this line of argumentation pop up when we (as the computing industry) discuss practicalities of data structures and algorithm choices. I've got a bit over twice your time in the industry and one of the things that is still very clearly on an upward walk is the size of our N's (think big O) in all of our applications and across all of our data structures. I'm not sure what kinds of applications you're building, but if any of your collections contain on the orders of thousands/10s/100s thousands of items, you really should be considering the impact of how you shape that data for consumption inside your application. You hint at the need to do so, arraylists being good enough until they're not and then hashmaps, etc. I think there is a pretty reasonable line between expecting our engineers and peers to pick proper containers for the data they're consuming without stepping over into purely 'academic' territory. Shutting down the discussions with 'well I've never had to use this' feels a bit icky and not a great way to advance any of the conversation.

exDM69 6y ago

Yes, linked lists have terrible cache behavior and usually the performance of any packed structure with less pointer chasing should beat it. ArrayList, Vector, whatever you call it usually is faster. But computers aren't fast in allocating memory. In particular, they're not predictably fast in allocating memory, as most allocators will have complex internal data structures and may end up having to call the operating system to give fresh pages of unused memory. The best case may be smoking fast, the amortized cost may be decent but the worst case is pretty bad. So when reliable and predictable performance is needed, memory allocations are to be avoided. This is relevant if you're working on (soft) real time applications, say audio, games or so. And linked lists are still mighty fast in addition and removal, joining and splitting. Intrusive linked lists drop one extra pointer chase. In kernel space, there are tons of use cases for linked lists that are never traversed, or at least not traversed in the fast path. Traversal is the slow part, but that's not necessary for a lot of cases where you add something to a list or a set, and remove items one by one. There's no other data structure that beats linked lists when there's only addition, removal, joins and splits, but no traversals. Linked lists are almost always the wrong data structure for the job, but in special niche cases (which are not that rare, at least in kernel space) it's the simplest and most effective.

pdpi 6y ago
> Intrusive linked lists drop one extra pointer chase. Template-based lists (in the style of C++ STL) let you have your cake and eat it too in that you still keep the list structure out of your data, but you still get the cache locality of an intrusive list.
- DSMan195276 6y ago
  I think your typical template-based list is actually a bad example :P Maybe there's something about C++ I don't know, but typically those implementations only allow for adding one list node (via the template wrapping), and also they can't usually take an element from one list and then attach it to another one. Where-as intrusive implementations like the Linux Kernel's allow for any number of list nodes or other data structures to be placed alongside the data, and the elements can be moved onto any list you want without any allocations necessary.

skohan 6y ago

> it turns out that computers are pretty fast at allocating memory Isn't this not the case? My understanding was that 90% of HPC is normally about making sure to avoid as many individual allocations/deallocations possible, because these are massively expensive compared to almost all user-space operations, and lead to cache-inefficient memory layouts, which can slow your code down by like a factor of 200

chrisseaton 6y ago
What do you think an allocation involves in a modern language implementation? It's about five machine instructions amortised. Load the allocation pointer, add the object size to it, check it's not got too large, store it. Deallocation though - yes that's slow!
- joosters 6y ago
  That's the absolute best case for the simplest malloc implementation possible. In the real world, a malloc can involve picking an appropriate zone/arena based upon allocation size & the current thread, obtaining locks, chasing some pointers through its data structures, doing some book-keeping, perhaps even calling up to the OS to increase the process space. Maybe in the very best case it can just shuffle a couple of pointers, but over time it has to do a lot more than that.
  - kragen 6y ago
    Well, chrisseaton did say amortised, not worst-case. He wasn't talking about malloc, which is a C function that indeed cannot be that fast, but about a modern language implementation. Results from some trivial benchmarks are in my comments at https://news.ycombinator.com/item?id=26438596 https://news.ycombinator.com/item?id=26438596 and https://news.ycombinator.com/item?id=26449902 https://news.ycombinator.com/item?id=26449902. You can reason it out from first principles, though. Picking the right arena is done at compile time, and you don't obtain locks or chase pointers on the open-coded fast path. Maybe once every 1024 allocations you have to do all that jazz, which costs you another 128 instructions, 0.125 instructions per allocation. And maybe once very 1024 times you do that, you need to call up to the OS to increase the process space at a cost of about 4096 instructions or so, 0.004 instructions per allocation. So the allocation fast path dominates your amortized allocation performance, even though the cases you're talking about are what dominate your worst-case performance.

karmakaze 6y ago

In Java arrays or ArrayList usually mean 'of references' so don't get the full cache locality benefit until Valhalla ever gets done. For primitive types, there are numerous primitive collection libraries that use primitive values and optionally object references.