[delecti]

I fee like anyone who was surprised that algorithmic complexity isn't everything, probably didn't totally understand it. The assumptions (like ignoring constants) are straight out of calculus limits. That (+10000) on the end doesn't mean anything if you're sorting an infinite list, but it means a lot if you're sorting 15 (or in your case 500) entries.

[twawaaay]

Well, it actually is kinda worse (or better, depends how you look at it).

It is not necessarily +10000, it can also be something like x5000.

Because CPUs really, really, really like working short, simple, predictable loops that traverse data in a simple pattern and hate when it is interrupted with something like dereferencing a pointer or looking up a missing page.

So your super complex and super intelligent algorithm might actually be only good on paper but doing more harm to your TLB cache, prefetcher, branch predictor, instruction pipeline, memory density, etc.

So there is this fun question:

"You are generating k random 64 bit integers. Each time you generate the integer, you have to insert it in a sorted collection. You implement two versions of the algorithm, one with a singly-linked list and one with a flat array. In both cases you are not allowed to cheat by using any external storage (indexes, caches, fingers, etc.)

The question: in your estimation, both algorithms being implemented optimally, what magnitude k needs to be for the linked list to start being more efficient than array list."

The fun part of this question is that the answer is: NEVER.

[simiones]

> The fun part of this question is that the answer is: NEVER.

Are you claiming that it is faster in practice to insert an element at the beginning of an array with 1G items, than it is to insert it at the beginning of a linked list with 1G items?

Or that, on average, the time spent traversing the linked list (assuming an average number of cache misses) the time taken to move all elements in the array one to the right?

I am certain the first item will not be true, and the second may or may not be true depending on many many other details (e.g., in a language with a compacting GC, the linked list elements will often be stored approximately like in the array case, and you may not pay too high a cost for cache misses).

[twawaaay]

> Are you claiming that it is faster in practice to insert an element at the beginning of an array with 1G items, than it is to insert it at the beginning of a linked list with 1G items?

You missed that insertion point is selected at random and must be found as part of the operation. But in practice if you know data will be inserted preferentially at the wrong end -- you can just easily reverse the data structure to make insertions prefer the better end.

> I am certain the first item will not be true

I am used to it. Everybody gets it wrong until they spend some time thinking about it, get it explained and/or run a real life test.

Hint: think about the cost of iterating over half of the linked list versus performing binary search over the array AND moving half of it.

The cost of binary search goes to negligible pretty fast and cost of moving 8 bytes of memory is always going to be lower than the cost of iterating over one entry (16 bytes) of linked list. And you have statistically equal number of both assuming you are selecting values at random with equal chance for each 64 integer to be next choice.

CPU can be moving a lot of bytes at the same time but it has to dereference the pointer before it can get to perform comparison before it can dereference the next pointer...

Actual algorithmic complexity of both algorithms is exactly the same. But an array is much more efficient (instructions per item).

[kmonsen]

You are right and this is will know, but not only for the reason you state. Cache locality is so much better on an array/vector compared to linked list and that is really important.

[twawaaay]

Good point. Cache locality is another important reason that I should have mentioned. I have not run tests, but it may possibly be the most important reason of them all.

In many linked data structures you can mitigate a lot of this problem. For example, in the past I have used contiguous arrays where I would allocate linked elements, then I would try to exploit how the elements are produced to get them placed one after another, if possible.

When data is produced randomly you can try to create "buckets", where each bucket is backed by an array and attempts to keep consecutive elements relatively close to each other. You could then try to rewrite those buckets in a way that gets amortised. Or you can just straight write it as if it was an array of sorted linked list elements where on each delete or insert you have to move some of the elements, but you only need to reorganise one bucket and not others.

All a bit cumbersome and at the end of it you are still wasting at least half of the cache on pointers.

[kmonsen]

Here is a video by Bjarne himself explaining this: https://youtu.be/YQs6IC-vgmo

Note there is a use case for linked list, inserting/deleting one or few items once in a while. But in general you can just use vector for anything that is not a leetcode problem.

[jasonwatkinspdx]

A fun related thing I first learned about years ago due to a Dr Dobbs article: some strided access patterns are FAR worse than random access patterns. This is because certain strides hit the worst case behavior of limited associativity caches, dramatically reducing the effective cache size.

[simiones]

> The cost of binary search goes to negligible pretty fast and cost of moving 8 bytes of memory is always going to be lower than the cost of iterating over one entry (16 bytes) of linked list. And you have statistically equal number of both assuming you are selecting values at random with equal chance for each 64 integer to be next choice.

That makes a lot of sense, thank you for the more detailed explanation.

[jwilk]

I think you misunderstood the question.

If you insert an element at the beginning, there's no list iteration cost.

[twawaaay]

Please, read the question.

It stipulates that elements are selected at random.

You select k integers at random.

Some of them might be inserted faster into linked list, but when you average it over k integers you will still be slower because inserting into array will be faster, on average.

Just think what happens if the integer is inserted at the END of the list (same probability...) You need to slowly iterate over entire linked list. While you quickly land at the result with a binary search on an array and then pay almost no cost inserting it there.

If you think about it, ON AVERAGE, you have to search through half of the list (if you are linked list) or move half of the array (if you are an array).

[jwilk]

The parts of simiones's message you quoted are not about the average case. They are about the corner case when an item would be added the beginning, meaning the linked list has the biggest advantage.

[layer8]

Well, there is one case where a linked list may be faster: when due to memory fragmentation you are unable to allocate contiguous k elements (hence efficiency would drop to zero) but you would still able to allocate k nodes (or k/n nodes with n elements each). It can therefore make sense to use a linked list of arrays with some sensible limit on the array size (e.g. in the gigabyte range). As long as a smaller number of elements is used, the linked list will only have one node and degenerate to the array solution.

[twawaaay]

If that was on a very old operating system (think MS-DOS?)

On new operating systems process address space is pieced together independently from physical space. So you can have contiguous, multi-GB array even if you don't have contiguous, multi-GB physical region.

As you read/write your virtual address space the CPU detects that there is no TLB mapping and interrupts into operating system which behind the scenes finds a page, returns the mapping and continues as if nothing ever happened.

This is why a process nowadays can allocate any amount of memory -- more than there is physical memory on the machine. It only starts grinding to a halt when you actually try to use it all. (This actually is one of my interview questions -- Can a process allocate more memory than is physically available on the machine? Why does it work?)