The true cost of linked lists

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).

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.

[1] https://isocpp.org/blog/2014/12/efficiency-with-algorithms-p...

For example you could count only non-cached memory accesses on a particular model cpu. See "Idealized Cache Model" from https://en.m.wikipedia.org/wiki/Cache-oblivious_algorithm for example.

This is part of algorithms analysis that a lot of developers skip: these are just tools, there's many models available to use with them, or if you want to, just use wall-clock, with all of the pain that comes with that.

Everyone seems to forget this. It's more a measure of how an algorithm will scale rather than performance.

https://github.com/sio2project/sio2jail/blob/master/src/perf...

No, it only assumes that there is a constant factor between the fastest and slowest "operations". It does not matter that one instruction can take a thousand times more cycles than another, if you have n² fast instructions and n slow ones, the running time will still be dominated by the n² fast ones for large n.

> Big-O assumes that only asymptotic behavior matters.

Yes, and this is the only simplification that it does.

This is a big misconception about "Big-O". It does not "assume" anything. It's just not what people think it is.

It's an asymptotic upper bound on counting something. In sorting algorithms you count the number of comparisons expressed as a function of collection size. In collection insertion algorithms on some underlying data structure, it's counting some not-very-clearly-defined atomic operations that are being executed when inserting an element.

Where the assumptions come from is if you start using the notation to give performance comparisons and also start assuming things about Big-O that are just not true. But that has nothing to do with "Big-O".

There is a family of symbols, called the Landau symbols, of which Big-O is only one. There is a lot of misuse of the symbol and in many cases what people actually mean is Theta(N) or Omega(N).

Initially, prefer to task CPU over memory allocation. Crufty allocation generally will always have a real negative impact felt by the end-user. A low memory footprint is always a win, while going for a (theoretical) fast running time may be effort wasted.

1. A small computation that you perform many, many times.

2. A very, very large computation.

For #2, big-O can still generally tell most of the story. (Example: 100 insertions in the middle of a list with a billion elements.) For #1, big-O almost irrelevant, and benchmarking is key. (Example: a billion insertions into the middle of length-100 lists.) So knowing which situation you're in is important.

As you go up the scale the Big-O values are almost always dominant. It's very rare to see a situation where you would choose the algorithm with the higher value.

However, when two algorithms have the same Big-O there can still be a big difference in performance, especially in the face of how a cache influences things.

(There are cases where the memory accesses are so important that they can make the "bad" approach better. A while back I did some time testing and found the Sieve of Eratosthenes inferior to brute force because of all the cache misses.)

Well I did have a CS teacher that said that O(log n) is basically O(1) because in practice, n usually will fit it in a 32bit and log n then is 32 at most :D

It might have been said in jest in part but really it's not that far fetched.

You'll get a similar reaction to if you try to show people who won money on crypto art or tesla that they are lucky early members of a pyramid scheme.

And the usual argument is, "well, it's understood..." which is a terrible argument because the whole notion of ignoring constant factor C is that it's supposed to go to the noise floor as n approaches infinity. So if you're going to claim that we didn't mean n approaches infinity, we meant "n fits into a CPU word and the data set fits into memory" then you're trying to have it both ways and that's pure nonsense.

If you want a better overview of algorithms for practical reasons, you can use o(), O(), average case and ammortised complexity, or just provide histograms of runtimes for algorithms you're comparing.

Only it's not enough. When you benchmark an O(N^2) algo may seem fine but then three years later the data has changed and is now an order of magnitude larger. So you need not only know your data, you also need to spend time thinking about how large it can become.

Functionally, though, I would describe this algorithm as O(N). It's just a straight up linear scan of the problem space. It's unbounded, with a worst case of O(Infinity) and no upper limit on what searched can be, but it's functionally O(N) regardless.

O(1) needs to basically be something like a hash key/pointer to memory address to get the result you're looking for. It will not increase linearly as the problem space increases, whereas your first example increases exactly linearly.

Mixing real-machine finitude with big-O theory often gives unexpected or unhelpful results. Once in an interview I argued that since hash tables have a finite number of buckets, at large enough scale they really have O(n) worse-case performance. That didn't go over very well. :-)

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.

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.

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.

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.

However, in my limited experience with such things I have always found myself needing both walking around and a big-picture list of items. Thus I have always implemented such things as a list of elements and storing indexes rather than pointers.

i thought that was the point of linked lists: O(1) insertion & deletion.

For example you have a list of points that define a linestring, and have to make sure that no two points are further apart than some value. It's really simple to iterate over linked list, insert a midpoint into the list, stay at the same step and redo the calculations(because p0-midpoint can still be longer than some value).

But other than that i don't think i had to do many random inserts/removals in non-DB contexts.

one of the benefits of a linkedlist is having the ability to remove an element from a list in O(1) by having reference to an item that is stored in the list. This is allowed since a linked list node can remve itself in constant time. This is a common pattern in linked lists used in C code for example.

javas linkedlists don't allow for this benefit. since in java you have to perform a search for the node to be removed and pay a O(n) penalty on a O(1) operation.

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.

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-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.

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)

Tsk tsk. A critical rule for flame wars that also applies to mere discussions among common folk is that you should avoid using absolute terms, as it gives your opponent an easy opening. Instead, couch your statements in vague and wishy washy terms like 'usually' and 'often'.

This also helps when your opponent produces a valid counterexample - you can petulantly retreat to safer ground while grumbling about how of course there are occasional exceptions and then, if you wish, you can sidetrack the argument into a debate about how often it really happens. From there you can feign boredom and exit, think up a snarky, mic-drop conclusion, etc.

- As taught in Raised on the streets of BBSs and USENET

ArrayLists grow by allocating a new buffer whose size is a multiple of the current size. This means that as the buffer size gets bigger, the reallocations become less frequent.

The end result is that appending to an ArrayList has constant time amortized complexity, even though it will periodically do increasingly large copies.

https://en.wikipedia.org/wiki/Amortized_analysis

I bombed an interview once because my interviewers didn't understand amortized analysis and I wasn't able to get them to understand it.

The ArrayList will be a nice flat chunk of memory... of pointers to the data, so you'll have to do a lookup for each element anyway. The LinkedList will have two lookups still, but it's not an order of magnitude anymore. Now it's more of a tradeoff between bit slower reads / bit faster updates.

You maybe want something like a linked array, but it's staggeringly difficult to find a scenario where a Java LinkedList or c++ std::list is ever the optimal choice. You should pretty much always start with an ArrayList or std::vector and go from there if/when it ever turns out to be a hotspot in benchmarks or profiling

That being said, the cases where a linked list is better than an array are very low these days.

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.

They're also more useful on microcontrollers where there's no cache, no prefetcher, etc. Less code needed for the data structure means more free space for business logic, and there's no performance penalty for bad cache locality on a system without any cache. Also a hash table has to hash each input, which is a significant amount of work for many microcontrollers.

  ListNode* a = new ListNode('A');
  ListNode* b = new ListNode('B');
  ListNode* c = new ListNode('C');
  a.next = b;
  b.next = c;

This is a linked list with the same shape as the list above, but with completely different performance characteristics:

  int* data = new int[3];
  data[0] = 'A';
  data[1] = 'B';
  data[2] = 'C';

  int* links = new int[3];
  links[0] = 1;
  links[1] = 2;
  links[2] = -1;

Yes, and constant time insertions/deletions in the middle of the list, assuming you know the address ahead of time.

This makes them great as backing queues in an LRU cache: given some key/value pairs, have a linked list whose nodes map to each key. Additions to the K/V store gets appended to the LL. This lets you easily remove the oldest n elements in the K/V store, by traversing from the head of the LL. It also lets you efficiently remove arbitrary elements from the K/V store, if you store the addresses of each LL node as values in the K/V, since deletions in the middle of the LL are constant time.

>yet I see them employed in various places all the time

I agree, however, that most LL applications (like the one I just mentioned) are fairly niche. LLs are overused because they’re dead simple to implement and commonly taught in intro CS classes.

This also technically applies to lockless data structures for some high performance code too. But those tend to be much much more tightly tuned for performance and the specific CPU they are intended to run on.

Inserting an element in middle is probably only legit use but it is kinda rare to have large enough data that you frequently insert in mid

When the use case requires insertion/removal from the middle of the list. An LRU cache is about the most common use case I've run across. (The "LRU" part requires it to often bump an item to the end of the list, so LL's excel here, as we can shift the element's position in the list in O(1) time. An LRU structure would normally pair the LL with a HashMap, which maps the cached item to its LL entry, so that we've also got a O(1) search into the LL, and don't hit the problem in the article.)

> yet I see them employed in various places all the time, by competent engineers who are definitely aware of their limitations.

I see them employed very, very rarely. Vectors¹ are by far more common in every codebase I've ever worked on. (And should be one's default, IMO, if all you need is a container of stuff that you're going to iterate over, which is the usual case, for the reasons in the article.)

¹ignoring cases where a hash(map|set) is required; then our codebase uses that, b/c that's what's needed.

Your question is more accurate than you realize! Because the answer is... the past.

Up until about the 486/50MHz era, CPUs and memory were attached to each other; one CPU cycle was approximately equal to one memory access. I don't mean that you could reach out to RAM in exactly one cycle and get a value, there were still some CPU caches and other considerations, but it was much closer to that ideal than on modern systems. And if you go back in time even farther, that actually was the case (Commodore 64, for instance).

(I don't know if there was ever a "true" 486/66 system, but I remember that as the CPU/clock speed where the CPU finally and definitively detached from RAM speed because that was generally a double-clocked 486/33 from the RAM's perspective. I can't quite remember the marketing term that was used. It's a dead term now because everything works that way.)

In those circumstances, traversing a linked list was not necessarily that much more expensive than a vector, and you could win on the other things a linked list can do faster than a vector, like insert in the middle, especially an insert in the middle when you were traversing the list anyhow. You could also win on a linked list containing a relatively large value organized just by pointers; a sort on the linked list manipulating just the pointers could win versus a sort that was trying to move around larger values constantly during the sort. And so on.

When memory accesses aren't hundreds and hundreds of CPU cycles, when your hardware doesn't have prefecting implemented, when your pointers aren't 64bits wide, when you aren't on modern systems essentially designed to make vector-based access go zoom, linked lists make a lot more sense.

This is how they got embedded in curricula so hard that they are taught to this day. They used to be a very important data structure. Now they're an antipattern. It happened gradually, though, and it doesn't help that linked lists are just about the easiest non-trivial data structure to teach and I'm not sure they could get removed from the standard curriculum for that reason alone.

"One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?"

Another problem linked lists have is that if you know that's what you're going to do, you can build vector-based solutions to that problem that work just fine. Vector-based stacks, for instance, are trivial, and O(1)-amortized for push and pop, which is good enough in practice. (A bit more care is needed than an only-growing vector but IIRC it can be done.) You need not just something linked lists are better at, but some bizarre cocktail of all the things they're just barely better at, and you still need to construct a win out of the combo. It's nearly impossible. Not quite impossible. I assume without looking that the Linux kernel still has some linked lists for good reason, as I'm sure if they could win on performance by removing them they would. But very hard.

[0]: https://www.systemverilog.io/ddr4-basics

The point is, it doesn't matter if you know the length of the list, you still have to examine all the elements.

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.

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.

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.

You can have a 2x difference in main memory performance between machines these days.

The very first, biggest impact performance metric is the algorithm used — anything besides that will be meaningless given a bad algorithm.