22 ms·

The true cost of linked lists

251 points by karroum 4y ago

gus_massa 4y ago
It would be nice to show the data in the tables as graphics too, perhaps log-log so it's easier to see all the points. In the first table: Benchmark Time CPU Iterations ------------------------------------------------------------- BM_ListFind/8 2824 ns 2825 ns 247103 [...] BM_ListFind/8192 3758778 ns 3758624 ns 204 [...] the last column makes no sense. Is that an error sorting the data or I'm misunderstanding what it mean?
- karroum 4y ago
  I agree plots would be nicer (maybe I'll add them) regarding the last column it's the number of iterations, google benchmark will make less iterations if individual iterations take more time.
  - gus_massa 4y ago
    Now it makes sense.
- Izkata 4y ago
  The benchmark is time-limited, looks like to about 0.75 seconds (= time * iterations). It ran the test that many times in that duration, each iteration taking on average the amount in the time/cpu column.
szastamasta 4y ago
I’ve done similar benchmarks some time ago for Java with exactly same conclusions. Due to the way CPUs reads and caches memory the only case for linked lists is doing a lot of in the middle inserts and deletes while iterating the list. Array copying is really optimized on current hardware.
- marginalia_nu 4y ago
  The redeeming factor (IMO) is that LinkedList implements a lot of useful interfaces: List, Queue AND Deque. If you are doing something like a graph traversal algorithm, breadth-first search or some relative, it's sometimes a justifiable choice for storing nodes-to-be-explored. ArrayDeque is marginally faster, but honestly not by much.
  - sitkack 4y ago
    Solve the problem using the best tools available. Then make it fast. Most CSmen over focus on runtime performance.
- chii 4y ago
  > the only case for linked lists is doing a lot of in the middle inserts and deletes i thought that was the point of linked lists: O(1) insertion & deletion.
  - lionkor 4y ago
    Yes, but only after finding the element which is O(n) worst case
    - adwn 4y ago
      In intrusively linked lists (the one usually used in kernels), you typically already have a pointer to the object, and therefore, to its next/prev pointers. For example, removing a task from the scheduler's RUN list and appending to the WAITING list is O(1), because you already have a pointer to the task, because the system's architecture is structured in such a way that you don't have to traverse the RUN list to find the pointer to the task's entry.
      - gpderetta 4y ago
        Exactly. Linked lists work well for secondary ordering of elements.
Const-me 4y ago
About the search benchmark, caches alone do not explain 2 orders of magnitude difference. It's also the prefetcher. CPU cores have a special functional block which observes addresses of cache lines requested from memory, detects sequential access pattern, and when detected pre-loads data into caches (including L1d) in advance. The RAM access pattern of std::vector search benchmark is an awesome use case for that thing.
MattPalmer1086 4y ago
Yes, cache misses are a big factor in algorithm speed. I've been working on some search algorithms recently. It's actually faster to read more bytes, as long as they're close, and make a better quality shift based on that rather than reading fewer bytes and making a less informed decision. The cost of reading bytes close by is negligible.
- extrapickles 4y ago
  Most storage media (DRAM[0], SSD, etc) do reads by pages anyways, so processing other bytes in that page is fast as they have already been fetched. [0]: https://www.systemverilog.io/ddr4-basics https://www.systemverilog.io/ddr4-basics
omginternets 4y ago
When are linked lists actually good? Everything I read about them suggests they have rotten performance, yet I see them employed in various places all the time, by competent engineers who are definitely aware of their limitations. One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?
- superdimwit 4y ago
  One nice property is their stable addressing. A linked list element won't move once allocated.
  - chii 4y ago
    > A linked list element won't move once allocated. only pertains to languages like C. In a virtual machine language like java, this isn't a property that can exist (there's no such thing as an address - at least as far as the language is concerned).
    - ziml77 4y ago
      A reference in Java can essentially be thought of as a pointer into a virtual address space. The JVM can move around the location of an object in the system's actual memory, but as far as anything holding reference is concerned nothing has changed.
      - recursive 4y ago
        And a reference to an object that's in an array won't be invalidated if that object is moving around the array or even removed entirely. It's still a C concern.
- di4na 4y ago
  Anytime you do something that is immutable with probable change somewhere inside that is not easy to handle with far mor complex datastructure. In particular linked list are great for heterogeneous cells type. Vectors and arrays have the problem of needing contiguous memory. If an inner cell can have different size, or worse change it mid work, things get ugly really fast.
rurban 4y ago
he should really tested against a deque too, not the two extremes only.
- codesnik 4y ago
  then he should test it against ringbuffers, IMHO.
  - rurban 4y ago
    ringbuffers are just needed for concurrent access or tiny/static ram/kernels. his tests are just simple ordinary perf tests for the cost of pointer chasing. That's why deques were invented, to give you the best of both. Similar to a B-Tree.
quadcore 4y ago
Thats right. Though in reality, programs behave in a complex way. You rarely have to insert something in the middle of a list in practice. You rarely do random behaviors, at least in my field. Let me explain. In the game industry, we use contiguous-allocated intrusive free list memory pools. For enemies or projectiles as an example. Those things live and die (they are removed from the free list and inserted in the "live" list or put back in the free list when they die) in such a way the locality is kept good. Admitedly I dont have sources nor benchmarks and never did. But its obvious it at least invalidates author's point in the sense that benchmarks gota be done in real life programs.
- devit 4y ago
  Linked lists only perform poorly if you iterate them, or otherwise access multiple items at once. If you use them as a single-linked free list they are faster than a vector since you only need to fetch a cache line for the object rather than a cacheline for the object and one for the vector storing free objects.
- pornel 4y ago
  Even this doesn't give you optimal locality. Objects in the same pool are closer than if they were randomly fragmented from a global allocator, but if you're accessing them in the list order, you're not accessing adjacent addresses to take advantage of memory prefetch. If the pool is large, it may not even fit in the cache. When performance needs to be maximized, games switch to entity component systems and switch from arrays-of-structs to structs-of-arrays. This enables processing all objects as a vector, linearly from start to end, and often without needing to fetch any irrelevant bytes that aren't processed in a given pass. This sometimes also helps utilize SIMD for data spanning more than one entity, which you can't do when using linked lists.
urthor 4y ago
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vecto... From 2012. std::deque does very well. Suspect the difference is fairly anaemic. Usually if you're choosing data structures, you pick a "good enough choice," (any of the three). Or, if it matters, you pull out your profiler and pick the "exact" right one.
kzrdude 4y ago
Linked lists are often used as a "secondary" structure, i.e intrusively linked lists of objects that whose main references come from elsewhere. Just wondering, are there any alternative solutions to those kinds of cases?
- thinkharderdev 4y ago
  Wouldn't that just be a vector of pointers?
  - deleted 4y ago
    [deleted]
- kzrdude 4y ago
  Self-answer but in Linux the "XArray" has been developed and maybe that can be an actual answer to my question: https://www.kernel.org/doc/html/latest/core-api/xarray.html https://www.kernel.org/doc/html/latest/core-api/xarray.html
jleyank 4y ago
I did not see whether there is a noticeable (or even measured) effect vs load on the cpu. I would thing that cache misses increase with load as multiple processes compete for the memory resources. Perhaps modern machines can schedule around this but it should still be tested. Or, perhaps, this is saying (again) that one should code then tune? Pick data structures that facilitate the design you’re trying for rather than for theoretical elegance? Chips are cheap while developers are not, and having a cleaner, saner design is a win. Unless your software price per core is so high that people won’t license more.
- matthews2 4y ago
  How do you define load on the CPU? It may use less power as it is spending more time stalled, waiting for memory. But it could be still using as much time as the OS scheduler is willing to give it.
deleted 4y ago
[deleted]
nraynaud 4y ago
Geometry/topology is very often presented as soup of pointers, (think of doubly connected edge list, Quad-edge, etc.) I have personnally always implemented these with pointers, because it's at the tip of my skills and that's how they are presented on the internet ; but I'm curious to know if people more confortable with topologies and meshes use a different memory representation.
- Const-me 4y ago
  I usually keeping these things as indexed meshes: std::vector<Vector3> for positions, and std::vector<std::array<uint32_t,3>> for the triangles. As a nice side effect, the representation is compatible with GPUs, matches VRAM layout of the vertex/index buffers. For some simple algorithms which need adjacency information, that’s everything needed. For instance, to compute per-vertex normals, nothing else is required, create an std::vector for the per-vertex accumulators, and iterate over the triangles. For complicated algorithms which need adjacency information, I build special indices over the same data. To find triangles connected to specific triangle, a hash map with uint64_t keys (two sorted uint32_t vertex IDs in the lower/upper half of the integer) and a structure of two uint32_t values (triangle IDs, good meshes are guaranteed to have exactly 2 triangles for each edge, with opposite winding directions). To find triangles by vertex, a multimap from uint32_t vertex to uint32_t triangle. For algorithms which need to modify these meshes, sometimes I generate new meshes instead of modifying old ones. Other times I replace erased elements with special values (like UINT_MAX for integer indices), append new elements to the end of the vectors, and when the algorithm is complete I re-index the mesh while removing unused vertices/triangles.
- ordu 4y ago
  I think, that they presented on Internet as a soup of pointers, because it is the obvious and general way to do it. Other ways like connectivity matrix are less general: if you have a lot of nodes, and by several orders of magnitude less then N^2 edges, then the most of matrix elements will be empty. Moreover it is not obvious way, you need to explain it also on top of your goal to explain what you are explaining about geometry/topology. So if you tried to do it you'd spend all the allotted time talking about pros and cons of different representations of topology. I believe that if someone tried to talk about topology while using Rust as a language for sample code, he/she would use some other representation, because a soup of pointers is a PITA in Rust. It is easier to claim that we will be using a connectivity matrix, or a Vec of edges, and to explain how it works, than to juggle with pointers.
SAI_Peregrinus 4y ago
Big-O notation relies on several simplifying assumptions which are wrong in practice. It's not useless, but it's for analyzing algorithmic complexity, not for analyzing algorithmic performance. Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been. Some instructions take more cycles than others. Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes. Etc, etc. An algorithm's complexity is loosely correlated with its performance, but the two are not identical.
- magicalhippo 4y ago
  Indeed. I do think knowing about big-O and keeping it in mind is important though. Yes this loop is fast now with my 1000 items, but what if the input grows to 100000 or more? Keeping it in mind can also help you avoid accidentally writing O(n^2) loops or worse. More than once I've been unsure about the complexity of a library call, so I check the code and it's say O(n) rather than O(1), potentially turning my own O(n) into a O(n^2).
- TchoBeer 4y ago
  >Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior. >Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes. This is definitely something to keep in mind when analyzing algorithms, but that does not imply asymptotic complexity is not useful when analyzing performance. There are other measures (e.g. how an algorithm performs on a random small input, or maybe your domain is restricted somewhat) and sometimes those measures areore useful than big O, but big O remains useful, it just is not the end all be all.
  - inetknght 4y ago
    > Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior. This assumption is demonstrably broken if the first multiplication is a cache miss but the other multiplications then aren't -- an easy example is when the other two multiplications have data on the same cache line as the first multiplication's data.
metadaemon 4y ago
The only linked lists I’ve used in production would be Java’s LinkedHashMap for preservation of insertion order. https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/LinkedHashMap.html https://docs.oracle.com/en/java/javase/16/docs/api/java.base...
robmccoll 4y ago
Yeah, we should teach this to undergrads. If you want high performance for a dynamic list, you end up making a lot of tradeoffs with tricks like: - Use blocks of multiple elements per actual list element that fit your cache line size. Blocks also have the benefit of potentially allowing SIMD processing of your data. - Allocate blocks out of a vector or some other structure that reduces your actual number of allocation calls. Maintain a free list threaded through this vector. - Tombstone list elements in their blocks on removal instead of repacking the entire list. This allows for fast deletions and fast insertions at specific locations (in that you can always insert a new block between existing blocks containing only a single element or get lucky and re-use a tombstoned slot). Note that most of these optimizations trade some memory efficiency for speed. This is a common theme in optimization. Using more memory, but using it more intelligently such that you are potentially accessing less of it and accessing it sequentially where possible.
idealmedtech 4y ago
I find it's best to write readable, straightforward code at first, and when performance really matters, benchmark to find places where you can eke out the percentage points that matter. Premature optimization can waste valuable hours when you don't know what how production workloads will stress your application.
- LorenPechtel 4y ago
  This. I always write for readability and only pay attention to performance when it's something that's going to be repeated often and it matters on the big-O scale. Optimizing beyond that should only be done with the profiler to guide you.
continuational 4y ago
This article makes the classic mistake of assuming linked list = mutable doubly linked list. Immutable, singly linked lists (aka cons lists) are a different beast entirely, and don't benchmark well in languages with heap fragmentation issues.
- gumby 4y ago
  And cdr-coded lists, or sublists, can have vastly improved cache performance, especially when you have a transporting GC.
  - bjoli 4y ago
    Does any implementation updated in the last 25 years use CDR coding??
    - gumby 4y ago
      I don't know -- most implementations on popular architectures only have two (low order) bits for tagging due to alignment issues, so there may not be room. Might be easier in the case of a RISC V with the tagging extension. Also it would be possible to implement such an approach in a C++ list container where you don't need boxing (the content type is known).
      - hayley-patton 4y ago
        On a 64-bit machine where everything is aligned to two words (like SBCL), you get 4 bits for tags.
- Const-me 4y ago
  > don't benchmark well in languages with heap fragmentation issues. Microsoft has solved most of these issues on Windows, couple decades ago. The feature was introduced in WinXP, and enabled by default in Vista and all newer versions: https://docs.microsoft.com/en-us/windows/win32/memory/low-fragmentation-heap https://docs.microsoft.com/en-us/windows/win32/memory/low-fr... I’m not an expert in Linux but I would be surprised if Linux didn’t do the same. RAM costs have plummeted. The losses from RAM usage overhead of LFH became insignificant compared to the issues caused by the fragmentation.
Sebb767 4y ago
This is a common misunderstanding of computational complexity: It does not measure runtime, but how runtime changes depending on the input. Take the following two algorithms to find the square root of an int: result=None for i in 0...INT_MAX if i*i==searched result=i return i and for i in 0...searched if i*i==searched return i The first algorithm is O(1), the second is O(sqrt(searched)). Despite this, the second will clearly be faster in actual execution time. However, if your number range changes from 0-100 to 100,000,000-250,000,000 , the former will still take the same time while the latter will take a lot longer. Now, in this example, this is quite obvious, but in the real world, you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity - it was never designed to perfectly measure or predict execution speed. This is also the reason constants are dropped in the notation. For real world performance, benchmarking is the key. Computers are very complex beasts and there are a lot of potential speedups or slowdowns you might never think of - memory bank order, thermal throttling and compiler optimizability can drastically change the results, just to name a few. Computational complexity is totally fine as an angle to find new possible optimizations, but in the end, you need to compare it to the other approaches and see what actually works. [0] https://news.ycombinator.com/item?id=21743424 https://news.ycombinator.com/item?id=21743424
- mining 4y ago
  I would probably argue that either the first algorithm is incorrect (because searched can be larger than INT_MAX) or the complexity of the second algorithm is bound both by O(searched) (or sqrt(searched), if implemented with more vigour) and O(1) (because the value of 'searched' is bound by a constant).
  - Sebb767 4y ago
    I explicitly wrote > to find the square root of an int: so the value can't exceed INT_MAX :) Overall, I know the two algorithms aren't perfect, but they're a simple minimal example to show the difference between complexity and runtime.
- 4y ago
eof 4y ago
Reminds me of this masterpiece of a rust tutorial; Learning Rust With Entirely Too Many Linked Lists - https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/
fmajid 4y ago
Branch prediction probably also favors the vector, if not as overwhelmingly as the cache locality.
deleted 4y ago
[deleted]
glitchc 4y ago
A linked list is going to be more costly where objects are simple integers and a single array access can load multiple adjacent elements. In practice, list nodes are more often than not complex objects, where loading a single object will flood the cache anyways. Furthermore, the author is masking the true cost of an array resize, which often happens in a running system where a finite array is completely full and needs to be resized to append an additional element. This is the scenario where linked lists are most useful.
- eternalban 4y ago
  You can also simply have a pointer to the value, so a node is just three pointers (prev, val, next) in a fixed sized structure. This gets you 2 nodes / CL. Add a fixed sized hash of value (key) if you want to search the list without chasing the val pointer, and your node still fits in a 64b CL. Pad it with 24b (yes, sacrifice a bit of space for performance gain) and your nodes will cache align. Resize point is fair but we still options here. A segmented approach for very large collections may also help, with tuning knobs of array size / segment. The smallish top level ds maintaining segment ptrs will be super hot and very likely ever present in L2. It really all depends on how many items are involved and how the data needs to be accessed and used.
- gpderetta 4y ago
  Reallocating the backing store for a vector is O(n), exactly like the cost of inserting in the middle, so it doesn't change anything much.
dahart 4y ago
> STL list […] the mallocs cost will still be greater. This is a narrow view of the costs of the STL::list container class, not of linked lists in general. Linked lists are at their best when they are internal storage, meaning the links are part of the class being stored, in order to prevent unnecessary mallocs. STL::list is an external storage container, which automatically compromises some of the potential benefits of a linked list. Linked lists are also best when you don’t malloc to build the list at all, but maintain things already in memory. Linked lists are best used in places where using vectors is impractical or impossible, like the insides of a memory manager. I don’t feel like timing many inserts using STL::list says a lot about linked lists at all, and what it does say is mostly focusing on the wrong things. Definitely use vector when you can, especially if you’re just comparing container classes.
- dundarious 4y ago
  Intrusive lists are better, sure, but pointer-jumping will still throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful. And avoiding pointer-jumping is not an automatic win from using intrusive lists — you still need to allocate/lay out your stack conscientiously. And a very similar argument can be made for bounded arrays as an alternative to std::vector. Also, I only skimmed it, but the article seems to ignore the fact that even for an unbounded/growing array like std::vector, the growth strategy does not free+malloc/realloc on each insertion in practice, as the growth strategy will leave unused capacity for future insertions, and in such cases the cost is just memmove (for simple types at least). Maybe I missed that part, but it seems like an important point worth highlighting.
  - dahart 4y ago
    > pointer-jumping will throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful. Right! Yes, that’s part of my point, STL::list isn’t being careful with cache, or with allocations. Really it just rarely makes sense to even compare STL::list to STL::vector as if they’re otherwise equal choice. Usually the choice is (or should be) driven by constraints, not by which has a slight perf edge, right? Inside a memory manager, use of a vector isn’t usually considered a choice. Maybe it’s possible to build a free page vector, but I think isn’t common, and people usually pay the costs of pointer chasing on the free list because there aren’t practical alternatives. > the <vector> growth strategy does not free+malloc/reallocate on each insertion Yeah very good point. Does STL::list do the same for the container of pointers? I don’t even know, but maybe it can’t, and maybe the primary perf advantage of STL::vector over STL::list is due to vector’s amortized mallocs?
DeathArrow 4y ago
When I was a kid and took programming lessons in high school, they taught us about linked lists,using Pascal or C. Back then, there weren't any list like data structures backed by arrays, like List from C# and Vector from C++. But learning linked lists was a good thing, we also had to learn about pointers and how memory is layed out, so we also knew that sequential access to memory is faster. Also, learning about stack vs heap, CPU caches, made a big difference in how we wrote programs and how we continued to write programs 25 years later. So I think I was lucky starting with Pascal and C, continuing with C++ instead of starting with Python or Javascript.
- LorenPechtel 4y ago
  My general experience with education is that one is well served by knowing things a bit deeper than one actually uses them. Going one more layer down in education makes the stuff you actually do use make much more sense.
PaulHoule 4y ago
I got schooled on this topic a while back. I was arguing in a discussion that ArrayList was always better than LinkedList in Java. Most of the time it is, but note that ArrayList has to occasionally allocate a new array when the list outgrows the array inside it, then copy the list. When the list gets huge, that operation of reallocating and copying gets disruptive as it puts a lot of pressure on the cache, memory allocation system, etc.
- kaba0 4y ago
  I believe it corresponds to the traditionally learnt O(n) lookup, O(1) insertion/deletion of linked lists, whereas the reverse is true of arrays (having to move the items). Though in practice I find that unless you are often deleting elements from the middle, modern CPUs will really prefer copying a huge amount of serial data, so an arraylist may still be faster all around then LinkedLists. (The CPU will recognize you moving values in a given direction and will have the best pipeline it can have)
  - PaulHoule 4y ago
    Most of the time that is right. In fact, there was a revolution in how people write query processing systems in the 2010s where people realized that the performance of a processing pipeline that reads columnar data structures straight through is amazing, particularly if you can use SIMD instructions. On the other hand, pointer chasing often isn't as bad as you think it might be. That is, modern allocator/garbage collectors often end up laying out the parts of a linked list in a predictable way such that access is somewhat strided and the fetcher is reasonably efficient at traversing the list.
    - kllrnohj 4y ago
      > On the other hand, pointer chasing often isn't as bad as you think it might be. It kinda really is, though. In addition to cache line locality, serial access also benefits from being speculatable. The CPU can't very effectively speculate past a pointer chase (and on arm little cores it doesn't even try), so those become pipeline stalls. Even if the pointer happened to be close-ish, it's still going to end up being a stall more often than not. And an allocator / GC is only going to lay out a linked list in any sort of predictable way if the linked list is built up all at once, in which case a linked list is obviously not the right data structure anyway ;)
cesaref 4y ago
It's the usual premature optimisation problem. I'd personally go with whichever data structure makes your code easy to write and comprehend, then profile, then adjust as necessary. 99% of code doesn't need to be efficient, but the maintenance cost tends to relate to the sheer amount of code and it's comprehensibility, and this cost is the one to optimise for, not speed. For the other 1% that you identify with profilers, go with the more optimal data structure, and accept the reduction in clarity and purpose.
- kaba0 4y ago
  I would wager that getting big O complexity right is absolutely not premature optimizations, it is perhaps the only thing one should “optimize” upfront. The very first, biggest impact performance metric is the algorithm used — anything besides that will be meaningless given a bad algorithm.
  - lazide 4y ago
    As with anything ‘it depends’ - if you’re writing CRUD enterprise code that at most will see several hundred objects at a time, but will have to be understood by 100s of cut rate contractors over it’s lifetime? Go for obvious and hard to screw up, over the most efficient algorithm. Of course someone will misappropriate it and use it as the core of some terribly thought out data handling app with billions of items, but at least anyone with a clue will be able to figure out why it’s terrible later. And if no one with a clue is around, then not like there was any better outcome going to happen except by sheer luck anyway.
    - cesaref 4y ago
      Right, and my point is that maintenance is a massive cost which is boring, and often overlooked when talking about the 'cost' of code. Slow code causing excessive CPU load or requiring multiple application servers is one cost, but maintenance is another, and the skill is to understand when it's appropriate for what. My default would be to generate maintainable code first, and worry about performance when it matters, but a knee-jerk 'linked lists are slow so avoid' approach is almost always the wrong way of approaching it. Choose the correct data structure and algorithm for maintainability, then optimise if it's too slow should be the default in my opinion.
s17n 4y ago
See also the classic Bjarne Stroustrup talk: https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo
the_af 4y ago
I don't understand this article at all. The author mentions that: > The theorical complexities are: > For list: O(n) > For vector: O(n) ... but then goes on to compare running times of list vs vector and notices vector is 90 times faster than list for many operations, mulls over cache locality and whatnot. Did he seriously expect O(n) to give him a way to compare running times? Big-O is about asymptotic behavior, not a way to compare running times in milliseconds between two implementations. That is, "how many seconds does this take?" cannot be answered with "oh, it's O(N^2)". The author seems very confused about what he is trying to argue.
- tobiasSoftware 4y ago
  The author isn't confused, rather that is the point he is making. Often schools teach you to only focus on the big O and ignore the constant multiplier. Those same schools then teach vectors and linked lists as the two main data structures. They talk about the cases where one has an obvious strength over the other, such as inserting into the middle, or using an index to access an element in the middle. However, they tend to skim over scenarios where the big O notation is the same but one has an advantage due to the constant multiplier, leading many students to come away with the impression that big O notation is all that matters.
  - the_af 4y ago
    > Often schools teach you to only focus on the big O and ignore the constant multiplier That's news to me. Which schools teach you that? Where I studied CS, algorithmic complexity and Big-O was taught in Graph Theory (Discrete Maths), and no attempt was made to imply it was about run time in milliseconds. The problem might be that there's plenty of self-taught programmers writing blogs that talk about Big-O without understanding what it means, and people who "learn" about it from said blogs. There's no theoretical mismatch with reality here. The only confusion might lie in the minds of self-taught programmers.
    - xpe 4y ago
      Fair points. Still, statistically, it is useful to recognize the empirical (but imperfect) correlation between Big-O and run time. One does not have to be confused to know this. Rather, one would be lacking perspective to not recognize that there is a connection. This connection is important if you want to be empirical validation of an algorithm on a particular computer. I just want to point out that your comment could easily be perceived as a ding against self-taught programmers. Many self-taught programmers (which I will define as ones that have not had a formal CS degree) read extensively. Many use their intrinsic motivation to really dive in. Also, many are successful. Bill Gates is one example. Yes, there are programmers of all kinds that have a tendency to write sloppy blog posts, to make overconfident and inaccurate statements, to forget things they've read, to hack their way around, and so on. There may even be a statistical correlation between self-taught programmers and such behavior. But I'd suggest we points out those behaviors when they are a problem rather than make assumptions about their educational backgrounds.
Thomashuet 4y ago
The claim is that vectors perform better than lists even in a case where the theoretical complexity is in favor of the list: insertion in the middle. However the complexity of insertion in the middle is O(n) for both vectors and lists so the demonstration falls apart. A scenario where the complexity is different would be to copy and modify the first element: O(1) for lists and O(n) for vectors.
- gpderetta 4y ago
  Insertion in a linked list is not O(n) though.
  - sliken 4y ago
    The post mentions inserting in the middle of the list. Sort of, do you assume you found the right node already, then it's O(1). If not, it's O(n/2).
    - gpderetta 4y ago
      Inserting in the middle of the list is still O(1). It doesn't make sense to include finding the insertion position in the insert cost as there are many ways to do that (for example you might have a separate hashed or ordered index, or simply have a pointer to the node by other means). Also, pedantically O(n/2) is the same as O(n).
deleted 4y ago
[deleted]
moron4hire 4y ago
The point of learning about linked lists is not to actually, you know, write a linked list. For one reason, your language of choice probably already has one, but also, in the process of learning about linked lists, you're supposed to also learn about their drawbacks[0]. No, the point is that there are a lot of linked-list-like things in the world, so knowing about how to work with linked lists helps you work with those things when you encounter them. [0] Seems there are a lot of problems that stem form Comp Sci students skimming the syllabus and not actually reading the material.
Chio 4y ago
This reminds me of an old paper [1] that discuss the performance characteristics of different array layouts for searching in particular. The conclusion is heavily based on the number of cache misses and branch predictor misses that binary search has for different array layouts. Doesn't have much practical application unfortunately since there is almost zero support for things like eytzinger layout in most standard libraries and sorting an array with a eytzinger layout is a bit harder than a non-decreasing layout. [1] "ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING", Paul-Virak Khuong and Pat Morin, https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf
dekhn 4y ago
I've been curious about this since I first learned about lists- my first "real data structure" (not provided by C). It took me a long time to wrap my head around them, but once i did... I was armed for a whole range of other more complicated data structures. That said, throughout my career, the number of times I've used an actual linked list (always double-linked and mutable) is quite small, as I had already found that vector was much faster for small operations (lists under 100 integral items), because, well, Intel optimized for people like me.
tobiasSoftware 4y ago
This article doesn't go over my favorite reason why Linked Lists are bad. Their main use case is that you can insert into the middle in constant time, right? Well, how do you find the insertion point? If your answer is anything algebraic, then I've got bad news for you: inserting into the middle might be constant time, but getting to the insertion point will be linear time. Really, the only use case for linked lists is if direct pointers to elements are cached somewhere, and in that case you are probably using a map anyway. IMO linked lists should be replaced with an ordered map for this reason.
- LorenPechtel 4y ago
  If you have an unordered list finding the spot is linear time anyway. That being said, the cases where a linked list is better than an array are very low these days.
deleted 4y ago
[deleted]
cycomanic 4y ago
As a side note I really wish people would stop putting the result tables instead of otting the results. The mental complexity of processing the results in table format is orders of magnitude higher, while one needs to go through every line and parse the number one to understand the main point it could be seen with a single glance if it was a plot. This gets even worse on mobile which wraps the output lines, like its the case here.
corysama 4y ago
I would use this as an interview question just to see if the person had ever been taught or given any thought to memory caches. "How much slower is it to iterate through a linked list vs. an array?" I mostly interviewed fresh-from-school grads. The most common answer I got was: 2x.
- LorenPechtel 4y ago
  I wouldn't consider this a good question because it changes with technology. Rather, ask about the factors that influence it. You can have a 2x difference in main memory performance between machines these days.
  - corysama 4y ago
    I wasn't looking for an exact answer. Just an something that indicated they were aware of caches at all. When asked to go into detail about their estimate, people who guessed 2x would start counting arithmetic operations.
deleted 4y ago
[deleted]
uvdn7 4y ago
There is this philosophy about software that it needs to be redesigned if the workload scales by 10x. The same applies here. When we are studying a topic, context (scale in particular in this case) matters a lot. Just like our physical world, and how classic mechanics and quantum mechanics are so different.
pphysch 4y ago
Question for PL implementation folks: How practical is it to implement a keyword/type that (portably) represents the L1/L2/LN cache size? Suppose I am implementing an algorithm or data structure and I really don't care what the $BLOCK_SIZE is, as long as it fits reasonably nicely in one of the lower caches as a sane default. It would be nice if I could do this with a magic keyword rather than hardcoding a default (1KiB) and forcing the end user to tune runtime params according to their hardware. Bonus if this can be used for static/stack allocations too.
- 0xffff2 4y ago
  For compiled languages, you would only every be able to do this for code compiled specifically for the target machine. I wonder if there are numbers out there for what percentage of code that applies to in the real world? My naive assumption is that it's a single digit percentage.
- kllrnohj 4y ago
  The `cpuid` instruction would tell you things like cache line size (and can enumerate cache topology). But you're then paying a cost for the value not being known at compile time, so you'd need to weigh the tradeoffs that may result from that.
travisgriggs 4y ago
It would be interesting to see how this translates to the newer Arm/M1 type processor. My experience with timing wisdom over the years is that things that are slow at one point (because of things like cache misses, etc), shift over time. I find I have to frequently recalibrate my expectations of "whats fastest".
- throwaway894345 4y ago
  Genuine question: why would ARM/M1 make cache misses more infrequent / faster (or does it just make cache hits slower relative to cache misses)? Have cache misses ever been fast relative to cache misses such that you would have to rebalance performance expectations/intuition?
  - travisgriggs 4y ago
    To be honest, I don't know. But I do know that the speed at which memory moves can alter the game when using traditional based "intel" optimization wisdom.
zelphirkalt 4y ago
Finding the last element in a vector is initially given as theoretical complecity O(n) -- What? In any language I used, a vector would have information about how long it is and that would be used to get an index (length - 1) and the access is constant O(1). Not sure what kind of vectors are assumed in the article.
- dreamcompiler 4y ago
  I had the same reaction. The only O(n) case I can think of is C's zero-delimited strings. But does anybody even still use these things nowadays?
  - TingPing 4y ago
    Millions of C projects, yes.
- bhuber 4y ago
  On any sort of list structure, a "find" operation generally means searching the list in order for an element that satisfies a predicate, usually equality to a given value. The article could be more clear about this, but in this context finding the last element in a list means calling find() on a list where only the last element of the list matches the predicate. This is almost the worst case scenario (the worst case being no elements in the list match). If you read the code in the article, you can see it's using https://www.cplusplus.com/reference/algorithm/find/ https://www.cplusplus.com/reference/algorithm/find/ to find an element in the list of value 1, after inserting that as the last element in the list. The point is, it doesn't matter if you know the length of the list, you still have to examine all the elements.
karmakaze 4y ago
TL;DR - Let me introduce spatial locality and cache.
deleted 4y ago
[deleted]
hamstergene 4y ago
I once found code that used vector instead of list, and the author had a benchmark exactly like this to defend it. Except that, the benchmark was storing ints but our production code stored std::function closures. Changing the benchmark to store a simple struct with two shared_ptrs invalidated it, showing that list outperforms vector on as little as 4 elements for head&middle insertions. I think all blog articles about CPU caches could use to repeat their benchmarks on something that hides a function call (move constructor), an atomic write, and an allocation, just to demonstrate how tight the boundaries are. What is good about sticking with fundamental computer science is that it provides pretty strong guarantee about what can and cannot happen, while hand-written optimizations are fragile. Even if optimization does work today, one year later the next maintainer may alter data types, or production data volumes may change, and the optimization will start doing the opposite.
stjohnswarts 4y ago
In all these years of c/c++ linked lists have never been my bottleneck... It's always good to know of such things though and keep them in mind.
AtNightWeCode 4y ago
I don’t think I have seen a linked list used in production code in the last +10 years. Maybe there are some cases where it may be practical from a design perspective. Many langs have a list collection that one is supposed to use instead.
yes_really 4y ago
> The theoretical complexities are: > - For list: O(n) > - For vector: O(n) > Surprisingly enough, the vector version is almost 90 times faster than the list version for 8K. How can we explain this big difference? That does not contradict the theoretical complexities at all. The article didn't show any "practical" complexities contradicting the theoretical ones. I do not mean to offend, but it looks like the author doesn't even understand what the O() notation means. The notation does not imply that all O(n) functions take the same amount of time. Multiple functions can scale linearly and still be different. In fact O(n) = O(1,000,000*n).
MatthiasWandel 4y ago
Why don't I like linked lists? Cause they are complete disarray :) Ok, not a great pun, but I have always used arrays when possible, even for stuff that needs inserting. I just assume I won't have a million elements to shuffle.
nikonyrh 4y ago
It still bothers me that hash-maps are advertised as O(1) lookups, regardless whether their size is 1 kb, 1 Mb, 1 Gb or 1 Tb. This just isn't true based on several benchmarks. So given that this is the case, using immutable data structures with O(log n) performance isn't "any" different than using the mutable ones.

251 points by karroum 4y ago

It would be nice to show the data in the tables as graphics too, perhaps log-log so it's easier to see all the points. In the first table: Benchmark Time CPU Iterations ------------------------------------------------------------- BM_ListFind/8 2824 ns 2825 ns 247103 [...] BM_ListFind/8192 3758778 ns 3758624 ns 204 [...] the last column makes no sense. Is that an error sorting the data or I'm misunderstanding what it mean?

karroum 4y ago
I agree plots would be nicer (maybe I'll add them) regarding the last column it's the number of iterations, google benchmark will make less iterations if individual iterations take more time.
- gus_massa 4y ago
  Now it makes sense.
Izkata 4y ago
The benchmark is time-limited, looks like to about 0.75 seconds (= time * iterations). It ran the test that many times in that duration, each iteration taking on average the amount in the time/cpu column.

szastamasta 4y ago

I’ve done similar benchmarks some time ago for Java with exactly same conclusions. Due to the way CPUs reads and caches memory the only case for linked lists is doing a lot of in the middle inserts and deletes while iterating the list. Array copying is really optimized on current hardware.

marginalia_nu 4y ago
The redeeming factor (IMO) is that LinkedList implements a lot of useful interfaces: List, Queue AND Deque. If you are doing something like a graph traversal algorithm, breadth-first search or some relative, it's sometimes a justifiable choice for storing nodes-to-be-explored. ArrayDeque is marginally faster, but honestly not by much.
- sitkack 4y ago
  Solve the problem using the best tools available. Then make it fast. Most CSmen over focus on runtime performance.
chii 4y ago
> the only case for linked lists is doing a lot of in the middle inserts and deletes i thought that was the point of linked lists: O(1) insertion & deletion.
- lionkor 4y ago
  Yes, but only after finding the element which is O(n) worst case
  - adwn 4y ago
    In intrusively linked lists (the one usually used in kernels), you typically already have a pointer to the object, and therefore, to its next/prev pointers. For example, removing a task from the scheduler's RUN list and appending to the WAITING list is O(1), because you already have a pointer to the task, because the system's architecture is structured in such a way that you don't have to traverse the RUN list to find the pointer to the task's entry.
    - gpderetta 4y ago
      Exactly. Linked lists work well for secondary ordering of elements.

Const-me 4y ago

About the search benchmark, caches alone do not explain 2 orders of magnitude difference. It's also the prefetcher. CPU cores have a special functional block which observes addresses of cache lines requested from memory, detects sequential access pattern, and when detected pre-loads data into caches (including L1d) in advance. The RAM access pattern of std::vector search benchmark is an awesome use case for that thing.

MattPalmer1086 4y ago

Yes, cache misses are a big factor in algorithm speed. I've been working on some search algorithms recently. It's actually faster to read more bytes, as long as they're close, and make a better quality shift based on that rather than reading fewer bytes and making a less informed decision. The cost of reading bytes close by is negligible.

extrapickles 4y ago
Most storage media (DRAM[0], SSD, etc) do reads by pages anyways, so processing other bytes in that page is fast as they have already been fetched. [0]: https://www.systemverilog.io/ddr4-basics https://www.systemverilog.io/ddr4-basics

omginternets 4y ago

When are linked lists actually good? Everything I read about them suggests they have rotten performance, yet I see them employed in various places all the time, by competent engineers who are definitely aware of their limitations. One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?

superdimwit 4y ago
One nice property is their stable addressing. A linked list element won't move once allocated.
- chii 4y ago
  > A linked list element won't move once allocated. only pertains to languages like C. In a virtual machine language like java, this isn't a property that can exist (there's no such thing as an address - at least as far as the language is concerned).
  - ziml77 4y ago
    A reference in Java can essentially be thought of as a pointer into a virtual address space. The JVM can move around the location of an object in the system's actual memory, but as far as anything holding reference is concerned nothing has changed.
    - recursive 4y ago
      And a reference to an object that's in an array won't be invalidated if that object is moving around the array or even removed entirely. It's still a C concern.
di4na 4y ago
Anytime you do something that is immutable with probable change somewhere inside that is not easy to handle with far mor complex datastructure. In particular linked list are great for heterogeneous cells type. Vectors and arrays have the problem of needing contiguous memory. If an inner cell can have different size, or worse change it mid work, things get ugly really fast.

rurban 4y ago

he should really tested against a deque too, not the two extremes only.

codesnik 4y ago
then he should test it against ringbuffers, IMHO.
- rurban 4y ago
  ringbuffers are just needed for concurrent access or tiny/static ram/kernels. his tests are just simple ordinary perf tests for the cost of pointer chasing. That's why deques were invented, to give you the best of both. Similar to a B-Tree.

quadcore 4y ago

Thats right. Though in reality, programs behave in a complex way. You rarely have to insert something in the middle of a list in practice. You rarely do random behaviors, at least in my field. Let me explain. In the game industry, we use contiguous-allocated intrusive free list memory pools. For enemies or projectiles as an example. Those things live and die (they are removed from the free list and inserted in the "live" list or put back in the free list when they die) in such a way the locality is kept good. Admitedly I dont have sources nor benchmarks and never did. But its obvious it at least invalidates author's point in the sense that benchmarks gota be done in real life programs.

devit 4y ago
Linked lists only perform poorly if you iterate them, or otherwise access multiple items at once. If you use them as a single-linked free list they are faster than a vector since you only need to fetch a cache line for the object rather than a cacheline for the object and one for the vector storing free objects.
pornel 4y ago
Even this doesn't give you optimal locality. Objects in the same pool are closer than if they were randomly fragmented from a global allocator, but if you're accessing them in the list order, you're not accessing adjacent addresses to take advantage of memory prefetch. If the pool is large, it may not even fit in the cache. When performance needs to be maximized, games switch to entity component systems and switch from arrays-of-structs to structs-of-arrays. This enables processing all objects as a vector, linearly from start to end, and often without needing to fetch any irrelevant bytes that aren't processed in a given pass. This sometimes also helps utilize SIMD for data spanning more than one entity, which you can't do when using linked lists.

urthor 4y ago

https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vecto... From 2012. std::deque does very well. Suspect the difference is fairly anaemic. Usually if you're choosing data structures, you pick a "good enough choice," (any of the three). Or, if it matters, you pull out your profiler and pick the "exact" right one.

kzrdude 4y ago

Linked lists are often used as a "secondary" structure, i.e intrusively linked lists of objects that whose main references come from elsewhere. Just wondering, are there any alternative solutions to those kinds of cases?

thinkharderdev 4y ago
Wouldn't that just be a vector of pointers?
- deleted 4y ago
  [deleted]
kzrdude 4y ago
Self-answer but in Linux the "XArray" has been developed and maybe that can be an actual answer to my question: https://www.kernel.org/doc/html/latest/core-api/xarray.html https://www.kernel.org/doc/html/latest/core-api/xarray.html

jleyank 4y ago

I did not see whether there is a noticeable (or even measured) effect vs load on the cpu. I would thing that cache misses increase with load as multiple processes compete for the memory resources. Perhaps modern machines can schedule around this but it should still be tested. Or, perhaps, this is saying (again) that one should code then tune? Pick data structures that facilitate the design you’re trying for rather than for theoretical elegance? Chips are cheap while developers are not, and having a cleaner, saner design is a win. Unless your software price per core is so high that people won’t license more.

matthews2 4y ago
How do you define load on the CPU? It may use less power as it is spending more time stalled, waiting for memory. But it could be still using as much time as the OS scheduler is willing to give it.

deleted 4y ago

[deleted]

nraynaud 4y ago

Geometry/topology is very often presented as soup of pointers, (think of doubly connected edge list, Quad-edge, etc.) I have personnally always implemented these with pointers, because it's at the tip of my skills and that's how they are presented on the internet ; but I'm curious to know if people more confortable with topologies and meshes use a different memory representation.

Const-me 4y ago
I usually keeping these things as indexed meshes: std::vector<Vector3> for positions, and std::vector<std::array<uint32_t,3>> for the triangles. As a nice side effect, the representation is compatible with GPUs, matches VRAM layout of the vertex/index buffers. For some simple algorithms which need adjacency information, that’s everything needed. For instance, to compute per-vertex normals, nothing else is required, create an std::vector for the per-vertex accumulators, and iterate over the triangles. For complicated algorithms which need adjacency information, I build special indices over the same data. To find triangles connected to specific triangle, a hash map with uint64_t keys (two sorted uint32_t vertex IDs in the lower/upper half of the integer) and a structure of two uint32_t values (triangle IDs, good meshes are guaranteed to have exactly 2 triangles for each edge, with opposite winding directions). To find triangles by vertex, a multimap from uint32_t vertex to uint32_t triangle. For algorithms which need to modify these meshes, sometimes I generate new meshes instead of modifying old ones. Other times I replace erased elements with special values (like UINT_MAX for integer indices), append new elements to the end of the vectors, and when the algorithm is complete I re-index the mesh while removing unused vertices/triangles.
ordu 4y ago
I think, that they presented on Internet as a soup of pointers, because it is the obvious and general way to do it. Other ways like connectivity matrix are less general: if you have a lot of nodes, and by several orders of magnitude less then N^2 edges, then the most of matrix elements will be empty. Moreover it is not obvious way, you need to explain it also on top of your goal to explain what you are explaining about geometry/topology. So if you tried to do it you'd spend all the allotted time talking about pros and cons of different representations of topology. I believe that if someone tried to talk about topology while using Rust as a language for sample code, he/she would use some other representation, because a soup of pointers is a PITA in Rust. It is easier to claim that we will be using a connectivity matrix, or a Vec of edges, and to explain how it works, than to juggle with pointers.

SAI_Peregrinus 4y ago

Big-O notation relies on several simplifying assumptions which are wrong in practice. It's not useless, but it's for analyzing algorithmic complexity, not for analyzing algorithmic performance. Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been. Some instructions take more cycles than others. Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes. Etc, etc. An algorithm's complexity is loosely correlated with its performance, but the two are not identical.

magicalhippo 4y ago
Indeed. I do think knowing about big-O and keeping it in mind is important though. Yes this loop is fast now with my 1000 items, but what if the input grows to 100000 or more? Keeping it in mind can also help you avoid accidentally writing O(n^2) loops or worse. More than once I've been unsure about the complexity of a library call, so I check the code and it's say O(n) rather than O(1), potentially turning my own O(n) into a O(n^2).
TchoBeer 4y ago
>Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior. >Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes. This is definitely something to keep in mind when analyzing algorithms, but that does not imply asymptotic complexity is not useful when analyzing performance. There are other measures (e.g. how an algorithm performs on a random small input, or maybe your domain is restricted somewhat) and sometimes those measures areore useful than big O, but big O remains useful, it just is not the end all be all.
- inetknght 4y ago
  > Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior. This assumption is demonstrably broken if the first multiplication is a cache miss but the other multiplications then aren't -- an easy example is when the other two multiplications have data on the same cache line as the first multiplication's data.

metadaemon 4y ago

The only linked lists I’ve used in production would be Java’s LinkedHashMap for preservation of insertion order. https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/LinkedHashMap.html https://docs.oracle.com/en/java/javase/16/docs/api/java.base...

robmccoll 4y ago

Yeah, we should teach this to undergrads. If you want high performance for a dynamic list, you end up making a lot of tradeoffs with tricks like: - Use blocks of multiple elements per actual list element that fit your cache line size. Blocks also have the benefit of potentially allowing SIMD processing of your data. - Allocate blocks out of a vector or some other structure that reduces your actual number of allocation calls. Maintain a free list threaded through this vector. - Tombstone list elements in their blocks on removal instead of repacking the entire list. This allows for fast deletions and fast insertions at specific locations (in that you can always insert a new block between existing blocks containing only a single element or get lucky and re-use a tombstoned slot). Note that most of these optimizations trade some memory efficiency for speed. This is a common theme in optimization. Using more memory, but using it more intelligently such that you are potentially accessing less of it and accessing it sequentially where possible.

idealmedtech 4y ago

I find it's best to write readable, straightforward code at first, and when performance really matters, benchmark to find places where you can eke out the percentage points that matter. Premature optimization can waste valuable hours when you don't know what how production workloads will stress your application.

LorenPechtel 4y ago
This. I always write for readability and only pay attention to performance when it's something that's going to be repeated often and it matters on the big-O scale. Optimizing beyond that should only be done with the profiler to guide you.

continuational 4y ago

This article makes the classic mistake of assuming linked list = mutable doubly linked list. Immutable, singly linked lists (aka cons lists) are a different beast entirely, and don't benchmark well in languages with heap fragmentation issues.

gumby 4y ago
And cdr-coded lists, or sublists, can have vastly improved cache performance, especially when you have a transporting GC.
- bjoli 4y ago
  Does any implementation updated in the last 25 years use CDR coding??
  - gumby 4y ago
    I don't know -- most implementations on popular architectures only have two (low order) bits for tagging due to alignment issues, so there may not be room. Might be easier in the case of a RISC V with the tagging extension. Also it would be possible to implement such an approach in a C++ list container where you don't need boxing (the content type is known).
    - hayley-patton 4y ago
      On a 64-bit machine where everything is aligned to two words (like SBCL), you get 4 bits for tags.
Const-me 4y ago
> don't benchmark well in languages with heap fragmentation issues. Microsoft has solved most of these issues on Windows, couple decades ago. The feature was introduced in WinXP, and enabled by default in Vista and all newer versions: https://docs.microsoft.com/en-us/windows/win32/memory/low-fragmentation-heap https://docs.microsoft.com/en-us/windows/win32/memory/low-fr... I’m not an expert in Linux but I would be surprised if Linux didn’t do the same. RAM costs have plummeted. The losses from RAM usage overhead of LFH became insignificant compared to the issues caused by the fragmentation.

Sebb767 4y ago

This is a common misunderstanding of computational complexity: It does not measure runtime, but how runtime changes depending on the input. Take the following two algorithms to find the square root of an int: result=None for i in 0...INT_MAX if i*i==searched result=i return i and for i in 0...searched if i*i==searched return i The first algorithm is O(1), the second is O(sqrt(searched)). Despite this, the second will clearly be faster in actual execution time. However, if your number range changes from 0-100 to 100,000,000-250,000,000 , the former will still take the same time while the latter will take a lot longer. Now, in this example, this is quite obvious, but in the real world, you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity - it was never designed to perfectly measure or predict execution speed. This is also the reason constants are dropped in the notation. For real world performance, benchmarking is the key. Computers are very complex beasts and there are a lot of potential speedups or slowdowns you might never think of - memory bank order, thermal throttling and compiler optimizability can drastically change the results, just to name a few. Computational complexity is totally fine as an angle to find new possible optimizations, but in the end, you need to compare it to the other approaches and see what actually works. [0] https://news.ycombinator.com/item?id=21743424 https://news.ycombinator.com/item?id=21743424

mining 4y ago
I would probably argue that either the first algorithm is incorrect (because searched can be larger than INT_MAX) or the complexity of the second algorithm is bound both by O(searched) (or sqrt(searched), if implemented with more vigour) and O(1) (because the value of 'searched' is bound by a constant).
- Sebb767 4y ago
  I explicitly wrote > to find the square root of an int: so the value can't exceed INT_MAX :) Overall, I know the two algorithms aren't perfect, but they're a simple minimal example to show the difference between complexity and runtime.
4y ago

eof 4y ago

Reminds me of this masterpiece of a rust tutorial; Learning Rust With Entirely Too Many Linked Lists - https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/

fmajid 4y ago

Branch prediction probably also favors the vector, if not as overwhelmingly as the cache locality.

deleted 4y ago

[deleted]

glitchc 4y ago

A linked list is going to be more costly where objects are simple integers and a single array access can load multiple adjacent elements. In practice, list nodes are more often than not complex objects, where loading a single object will flood the cache anyways. Furthermore, the author is masking the true cost of an array resize, which often happens in a running system where a finite array is completely full and needs to be resized to append an additional element. This is the scenario where linked lists are most useful.

eternalban 4y ago
You can also simply have a pointer to the value, so a node is just three pointers (prev, val, next) in a fixed sized structure. This gets you 2 nodes / CL. Add a fixed sized hash of value (key) if you want to search the list without chasing the val pointer, and your node still fits in a 64b CL. Pad it with 24b (yes, sacrifice a bit of space for performance gain) and your nodes will cache align. Resize point is fair but we still options here. A segmented approach for very large collections may also help, with tuning knobs of array size / segment. The smallish top level ds maintaining segment ptrs will be super hot and very likely ever present in L2. It really all depends on how many items are involved and how the data needs to be accessed and used.
gpderetta 4y ago
Reallocating the backing store for a vector is O(n), exactly like the cost of inserting in the middle, so it doesn't change anything much.

dahart 4y ago

> STL list […] the mallocs cost will still be greater. This is a narrow view of the costs of the STL::list container class, not of linked lists in general. Linked lists are at their best when they are internal storage, meaning the links are part of the class being stored, in order to prevent unnecessary mallocs. STL::list is an external storage container, which automatically compromises some of the potential benefits of a linked list. Linked lists are also best when you don’t malloc to build the list at all, but maintain things already in memory. Linked lists are best used in places where using vectors is impractical or impossible, like the insides of a memory manager. I don’t feel like timing many inserts using STL::list says a lot about linked lists at all, and what it does say is mostly focusing on the wrong things. Definitely use vector when you can, especially if you’re just comparing container classes.

dundarious 4y ago
Intrusive lists are better, sure, but pointer-jumping will still throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful. And avoiding pointer-jumping is not an automatic win from using intrusive lists — you still need to allocate/lay out your stack conscientiously. And a very similar argument can be made for bounded arrays as an alternative to std::vector. Also, I only skimmed it, but the article seems to ignore the fact that even for an unbounded/growing array like std::vector, the growth strategy does not free+malloc/realloc on each insertion in practice, as the growth strategy will leave unused capacity for future insertions, and in such cases the cost is just memmove (for simple types at least). Maybe I missed that part, but it seems like an important point worth highlighting.
- dahart 4y ago
  > pointer-jumping will throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful. Right! Yes, that’s part of my point, STL::list isn’t being careful with cache, or with allocations. Really it just rarely makes sense to even compare STL::list to STL::vector as if they’re otherwise equal choice. Usually the choice is (or should be) driven by constraints, not by which has a slight perf edge, right? Inside a memory manager, use of a vector isn’t usually considered a choice. Maybe it’s possible to build a free page vector, but I think isn’t common, and people usually pay the costs of pointer chasing on the free list because there aren’t practical alternatives. > the <vector> growth strategy does not free+malloc/reallocate on each insertion Yeah very good point. Does STL::list do the same for the container of pointers? I don’t even know, but maybe it can’t, and maybe the primary perf advantage of STL::vector over STL::list is due to vector’s amortized mallocs?

DeathArrow 4y ago

When I was a kid and took programming lessons in high school, they taught us about linked lists,using Pascal or C. Back then, there weren't any list like data structures backed by arrays, like List from C# and Vector from C++. But learning linked lists was a good thing, we also had to learn about pointers and how memory is layed out, so we also knew that sequential access to memory is faster. Also, learning about stack vs heap, CPU caches, made a big difference in how we wrote programs and how we continued to write programs 25 years later. So I think I was lucky starting with Pascal and C, continuing with C++ instead of starting with Python or Javascript.

LorenPechtel 4y ago
My general experience with education is that one is well served by knowing things a bit deeper than one actually uses them. Going one more layer down in education makes the stuff you actually do use make much more sense.

PaulHoule 4y ago

I got schooled on this topic a while back. I was arguing in a discussion that ArrayList was always better than LinkedList in Java. Most of the time it is, but note that ArrayList has to occasionally allocate a new array when the list outgrows the array inside it, then copy the list. When the list gets huge, that operation of reallocating and copying gets disruptive as it puts a lot of pressure on the cache, memory allocation system, etc.

kaba0 4y ago
I believe it corresponds to the traditionally learnt O(n) lookup, O(1) insertion/deletion of linked lists, whereas the reverse is true of arrays (having to move the items). Though in practice I find that unless you are often deleting elements from the middle, modern CPUs will really prefer copying a huge amount of serial data, so an arraylist may still be faster all around then LinkedLists. (The CPU will recognize you moving values in a given direction and will have the best pipeline it can have)
- PaulHoule 4y ago
  Most of the time that is right. In fact, there was a revolution in how people write query processing systems in the 2010s where people realized that the performance of a processing pipeline that reads columnar data structures straight through is amazing, particularly if you can use SIMD instructions. On the other hand, pointer chasing often isn't as bad as you think it might be. That is, modern allocator/garbage collectors often end up laying out the parts of a linked list in a predictable way such that access is somewhat strided and the fetcher is reasonably efficient at traversing the list.
  - kllrnohj 4y ago
    > On the other hand, pointer chasing often isn't as bad as you think it might be. It kinda really is, though. In addition to cache line locality, serial access also benefits from being speculatable. The CPU can't very effectively speculate past a pointer chase (and on arm little cores it doesn't even try), so those become pipeline stalls. Even if the pointer happened to be close-ish, it's still going to end up being a stall more often than not. And an allocator / GC is only going to lay out a linked list in any sort of predictable way if the linked list is built up all at once, in which case a linked list is obviously not the right data structure anyway ;)

cesaref 4y ago

It's the usual premature optimisation problem. I'd personally go with whichever data structure makes your code easy to write and comprehend, then profile, then adjust as necessary. 99% of code doesn't need to be efficient, but the maintenance cost tends to relate to the sheer amount of code and it's comprehensibility, and this cost is the one to optimise for, not speed. For the other 1% that you identify with profilers, go with the more optimal data structure, and accept the reduction in clarity and purpose.

kaba0 4y ago
I would wager that getting big O complexity right is absolutely not premature optimizations, it is perhaps the only thing one should “optimize” upfront. The very first, biggest impact performance metric is the algorithm used — anything besides that will be meaningless given a bad algorithm.
- lazide 4y ago
  As with anything ‘it depends’ - if you’re writing CRUD enterprise code that at most will see several hundred objects at a time, but will have to be understood by 100s of cut rate contractors over it’s lifetime? Go for obvious and hard to screw up, over the most efficient algorithm. Of course someone will misappropriate it and use it as the core of some terribly thought out data handling app with billions of items, but at least anyone with a clue will be able to figure out why it’s terrible later. And if no one with a clue is around, then not like there was any better outcome going to happen except by sheer luck anyway.
  - cesaref 4y ago
    Right, and my point is that maintenance is a massive cost which is boring, and often overlooked when talking about the 'cost' of code. Slow code causing excessive CPU load or requiring multiple application servers is one cost, but maintenance is another, and the skill is to understand when it's appropriate for what. My default would be to generate maintainable code first, and worry about performance when it matters, but a knee-jerk 'linked lists are slow so avoid' approach is almost always the wrong way of approaching it. Choose the correct data structure and algorithm for maintainability, then optimise if it's too slow should be the default in my opinion.

s17n 4y ago

See also the classic Bjarne Stroustrup talk: https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo

the_af 4y ago

I don't understand this article at all. The author mentions that: > The theorical complexities are: > For list: O(n) > For vector: O(n) ... but then goes on to compare running times of list vs vector and notices vector is 90 times faster than list for many operations, mulls over cache locality and whatnot. Did he seriously expect O(n) to give him a way to compare running times? Big-O is about asymptotic behavior, not a way to compare running times in milliseconds between two implementations. That is, "how many seconds does this take?" cannot be answered with "oh, it's O(N^2)". The author seems very confused about what he is trying to argue.

tobiasSoftware 4y ago
The author isn't confused, rather that is the point he is making. Often schools teach you to only focus on the big O and ignore the constant multiplier. Those same schools then teach vectors and linked lists as the two main data structures. They talk about the cases where one has an obvious strength over the other, such as inserting into the middle, or using an index to access an element in the middle. However, they tend to skim over scenarios where the big O notation is the same but one has an advantage due to the constant multiplier, leading many students to come away with the impression that big O notation is all that matters.
- the_af 4y ago
  > Often schools teach you to only focus on the big O and ignore the constant multiplier That's news to me. Which schools teach you that? Where I studied CS, algorithmic complexity and Big-O was taught in Graph Theory (Discrete Maths), and no attempt was made to imply it was about run time in milliseconds. The problem might be that there's plenty of self-taught programmers writing blogs that talk about Big-O without understanding what it means, and people who "learn" about it from said blogs. There's no theoretical mismatch with reality here. The only confusion might lie in the minds of self-taught programmers.
  - xpe 4y ago
    Fair points. Still, statistically, it is useful to recognize the empirical (but imperfect) correlation between Big-O and run time. One does not have to be confused to know this. Rather, one would be lacking perspective to not recognize that there is a connection. This connection is important if you want to be empirical validation of an algorithm on a particular computer. I just want to point out that your comment could easily be perceived as a ding against self-taught programmers. Many self-taught programmers (which I will define as ones that have not had a formal CS degree) read extensively. Many use their intrinsic motivation to really dive in. Also, many are successful. Bill Gates is one example. Yes, there are programmers of all kinds that have a tendency to write sloppy blog posts, to make overconfident and inaccurate statements, to forget things they've read, to hack their way around, and so on. There may even be a statistical correlation between self-taught programmers and such behavior. But I'd suggest we points out those behaviors when they are a problem rather than make assumptions about their educational backgrounds.

Thomashuet 4y ago

The claim is that vectors perform better than lists even in a case where the theoretical complexity is in favor of the list: insertion in the middle. However the complexity of insertion in the middle is O(n) for both vectors and lists so the demonstration falls apart. A scenario where the complexity is different would be to copy and modify the first element: O(1) for lists and O(n) for vectors.

gpderetta 4y ago
Insertion in a linked list is not O(n) though.
- sliken 4y ago
  The post mentions inserting in the middle of the list. Sort of, do you assume you found the right node already, then it's O(1). If not, it's O(n/2).
  - gpderetta 4y ago
    Inserting in the middle of the list is still O(1). It doesn't make sense to include finding the insertion position in the insert cost as there are many ways to do that (for example you might have a separate hashed or ordered index, or simply have a pointer to the node by other means). Also, pedantically O(n/2) is the same as O(n).

deleted 4y ago

[deleted]

moron4hire 4y ago

The point of learning about linked lists is not to actually, you know, write a linked list. For one reason, your language of choice probably already has one, but also, in the process of learning about linked lists, you're supposed to also learn about their drawbacks[0]. No, the point is that there are a lot of linked-list-like things in the world, so knowing about how to work with linked lists helps you work with those things when you encounter them. [0] Seems there are a lot of problems that stem form Comp Sci students skimming the syllabus and not actually reading the material.

Chio 4y ago

This reminds me of an old paper [1] that discuss the performance characteristics of different array layouts for searching in particular. The conclusion is heavily based on the number of cache misses and branch predictor misses that binary search has for different array layouts. Doesn't have much practical application unfortunately since there is almost zero support for things like eytzinger layout in most standard libraries and sorting an array with a eytzinger layout is a bit harder than a non-decreasing layout. [1] "ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING", Paul-Virak Khuong and Pat Morin, https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf

dekhn 4y ago

I've been curious about this since I first learned about lists- my first "real data structure" (not provided by C). It took me a long time to wrap my head around them, but once i did... I was armed for a whole range of other more complicated data structures. That said, throughout my career, the number of times I've used an actual linked list (always double-linked and mutable) is quite small, as I had already found that vector was much faster for small operations (lists under 100 integral items), because, well, Intel optimized for people like me.

tobiasSoftware 4y ago

This article doesn't go over my favorite reason why Linked Lists are bad. Their main use case is that you can insert into the middle in constant time, right? Well, how do you find the insertion point? If your answer is anything algebraic, then I've got bad news for you: inserting into the middle might be constant time, but getting to the insertion point will be linear time. Really, the only use case for linked lists is if direct pointers to elements are cached somewhere, and in that case you are probably using a map anyway. IMO linked lists should be replaced with an ordered map for this reason.

LorenPechtel 4y ago
If you have an unordered list finding the spot is linear time anyway. That being said, the cases where a linked list is better than an array are very low these days.

deleted 4y ago

[deleted]

cycomanic 4y ago

As a side note I really wish people would stop putting the result tables instead of otting the results. The mental complexity of processing the results in table format is orders of magnitude higher, while one needs to go through every line and parse the number one to understand the main point it could be seen with a single glance if it was a plot. This gets even worse on mobile which wraps the output lines, like its the case here.

corysama 4y ago

I would use this as an interview question just to see if the person had ever been taught or given any thought to memory caches. "How much slower is it to iterate through a linked list vs. an array?" I mostly interviewed fresh-from-school grads. The most common answer I got was: 2x.

LorenPechtel 4y ago
I wouldn't consider this a good question because it changes with technology. Rather, ask about the factors that influence it. You can have a 2x difference in main memory performance between machines these days.
- corysama 4y ago
  I wasn't looking for an exact answer. Just an something that indicated they were aware of caches at all. When asked to go into detail about their estimate, people who guessed 2x would start counting arithmetic operations.

deleted 4y ago

[deleted]

uvdn7 4y ago

There is this philosophy about software that it needs to be redesigned if the workload scales by 10x. The same applies here. When we are studying a topic, context (scale in particular in this case) matters a lot. Just like our physical world, and how classic mechanics and quantum mechanics are so different.

pphysch 4y ago

Question for PL implementation folks: How practical is it to implement a keyword/type that (portably) represents the L1/L2/LN cache size? Suppose I am implementing an algorithm or data structure and I really don't care what the $BLOCK_SIZE is, as long as it fits reasonably nicely in one of the lower caches as a sane default. It would be nice if I could do this with a magic keyword rather than hardcoding a default (1KiB) and forcing the end user to tune runtime params according to their hardware. Bonus if this can be used for static/stack allocations too.

0xffff2 4y ago
For compiled languages, you would only every be able to do this for code compiled specifically for the target machine. I wonder if there are numbers out there for what percentage of code that applies to in the real world? My naive assumption is that it's a single digit percentage.
kllrnohj 4y ago
The `cpuid` instruction would tell you things like cache line size (and can enumerate cache topology). But you're then paying a cost for the value not being known at compile time, so you'd need to weigh the tradeoffs that may result from that.

travisgriggs 4y ago

It would be interesting to see how this translates to the newer Arm/M1 type processor. My experience with timing wisdom over the years is that things that are slow at one point (because of things like cache misses, etc), shift over time. I find I have to frequently recalibrate my expectations of "whats fastest".

throwaway894345 4y ago
Genuine question: why would ARM/M1 make cache misses more infrequent / faster (or does it just make cache hits slower relative to cache misses)? Have cache misses ever been fast relative to cache misses such that you would have to rebalance performance expectations/intuition?
- travisgriggs 4y ago
  To be honest, I don't know. But I do know that the speed at which memory moves can alter the game when using traditional based "intel" optimization wisdom.

zelphirkalt 4y ago

Finding the last element in a vector is initially given as theoretical complecity O(n) -- What? In any language I used, a vector would have information about how long it is and that would be used to get an index (length - 1) and the access is constant O(1). Not sure what kind of vectors are assumed in the article.

dreamcompiler 4y ago
I had the same reaction. The only O(n) case I can think of is C's zero-delimited strings. But does anybody even still use these things nowadays?
- TingPing 4y ago
  Millions of C projects, yes.
bhuber 4y ago
On any sort of list structure, a "find" operation generally means searching the list in order for an element that satisfies a predicate, usually equality to a given value. The article could be more clear about this, but in this context finding the last element in a list means calling find() on a list where only the last element of the list matches the predicate. This is almost the worst case scenario (the worst case being no elements in the list match). If you read the code in the article, you can see it's using https://www.cplusplus.com/reference/algorithm/find/ https://www.cplusplus.com/reference/algorithm/find/ to find an element in the list of value 1, after inserting that as the last element in the list. The point is, it doesn't matter if you know the length of the list, you still have to examine all the elements.

karmakaze 4y ago

TL;DR - Let me introduce spatial locality and cache.

deleted 4y ago

[deleted]

hamstergene 4y ago

I once found code that used vector instead of list, and the author had a benchmark exactly like this to defend it. Except that, the benchmark was storing ints but our production code stored std::function closures. Changing the benchmark to store a simple struct with two shared_ptrs invalidated it, showing that list outperforms vector on as little as 4 elements for head&middle insertions. I think all blog articles about CPU caches could use to repeat their benchmarks on something that hides a function call (move constructor), an atomic write, and an allocation, just to demonstrate how tight the boundaries are. What is good about sticking with fundamental computer science is that it provides pretty strong guarantee about what can and cannot happen, while hand-written optimizations are fragile. Even if optimization does work today, one year later the next maintainer may alter data types, or production data volumes may change, and the optimization will start doing the opposite.

stjohnswarts 4y ago

In all these years of c/c++ linked lists have never been my bottleneck... It's always good to know of such things though and keep them in mind.

AtNightWeCode 4y ago

I don’t think I have seen a linked list used in production code in the last +10 years. Maybe there are some cases where it may be practical from a design perspective. Many langs have a list collection that one is supposed to use instead.

yes_really 4y ago

> The theoretical complexities are: > - For list: O(n) > - For vector: O(n) > Surprisingly enough, the vector version is almost 90 times faster than the list version for 8K. How can we explain this big difference? That does not contradict the theoretical complexities at all. The article didn't show any "practical" complexities contradicting the theoretical ones. I do not mean to offend, but it looks like the author doesn't even understand what the O() notation means. The notation does not imply that all O(n) functions take the same amount of time. Multiple functions can scale linearly and still be different. In fact O(n) = O(1,000,000*n).

MatthiasWandel 4y ago

Why don't I like linked lists? Cause they are complete disarray :) Ok, not a great pun, but I have always used arrays when possible, even for stuff that needs inserting. I just assume I won't have a million elements to shuffle.

nikonyrh 4y ago

It still bothers me that hash-maps are advertised as O(1) lookups, regardless whether their size is 1 kb, 1 Mb, 1 Gb or 1 Tb. This just isn't true based on several benchmarks. So given that this is the case, using immutable data structures with O(log n) performance isn't "any" different than using the mutable ones.