Hacker News Reader

Comment by readams | Hacker News Reader

Linked lists are great. But they have the problem that, almost always, whatever problem you're trying to solve would be better done with a regular resizable vector.

This includes problems that they should be great for, like insert into the middle or the front.

The reason is that in practice the way computers actually work is that there is an enormous time penalty for jumping around randomly in memory, and it's large enough that it's often worth paying a O(lg n) cost to switch to something that will be contiguous in memory and allow the CPU to prefetch data.

There are exceptions when you really should use an actual linked list, but your default should be a vector and not a linked list.

View on HN

The first week into my prior job, I had to fix an in-production bug involving quadratic vector growth that was tipping over servers. The vector implementation guaranteed too much, namely consecutive memory layout (which wasn't needed, and if we had needed it, it would have been a mistake).

Decomposing that vector into recursive subvectors solved the problem. Going from a few tens of millions of elements in a single contiguous vector (with consequent -- and bad -- heap fragmentation!) to nested vectors with a few thousand elements each brought us back online again.

Which is to say: Vectors are nice. Lists are nice. Use appropriate data structures for your scale, watch your semantic dependencies, and don't get hung up on dogma.

The VList paper - which I archived at http://trout.me.uk/lisp/vlist.pdf to avoid having to google the bloody thing every time - is an interesting hybrid.

Thank you for that. That's a concept I remembered reading about, but I couldn't remember the name and had no way to find it again.

trout.me.uk/lisp/ and trout.me.uk/gc/ are both basically archives of "stuff I knew I'd suffer that problem with" and it's a pleasure every time the contents come in handy for people who aren't me.

Also back when I was still pretending to be a mathematician I used both GWBASIC and UBASIC for assorted purposes so thank -you- for the nostalgia kick.

Thanks for referring to the article. Great read!

http://trout.me.uk/lisp/ and http://trout.me.uk/gc/ are both "selected stuff I knew I'd have trouble finding again later" and I wish you great joy of them.

Still sad that John Shutt (creator of 'kernel lisp') passed away while I was still procrastinating dropping him an email - I think the only other 'thank you' I've most regretted not sending in time was to Terry Pratchett.

Regarding section 4.1 and 8 in this paper, it uses several software implementations of MSB and gives a performance comparison between the VList and RAOTS from which it was derived. It doesn't utilize hardware instructions which can improve the MSB calculation and eliminate branches (eg, clz/lzcnt or bsr). It's worth having another look at RAOTS using an optimized MSB which will leverage instructions available in modern hardware, and see how its performance compares to the VList.

https://cs.uwaterloo.ca/~imunro/cs840/ResizableArrays.pdf

Thank you!

Added to my /lisp/ directory for when I inevitably realise I've forgotten where I saw it :D

Correct me if I'm wrong, but it sounds like you're describing an Unrolled Linked List [1]? If so, neat!

[1]: https://en.wikipedia.org/wiki/Unrolled_linked_list

Another name for that is "B* tree". Or anyway a thing with similar performance characteristics.

Right, though we didn't need full tree semantics (just fast random access and an append that didn't spool up the fans on the servers).

I would hate to have to do a full balanced b-tree on short notice. (We also had rather terrible extra requirements that made using an off-the-shelf thing from, say, the STL work in our environment).

simple vector implementations will do a full realloc and recopy when you run out of space. so O(1) amortized but O(N) every so often.

another implementation strategy, at the cost of using some extra memory, is to allocate the new space, but only copy over a bit at a time, each time a new element is added -- so every add is still O(1). no long pauses.

(well, assuming the memory alloc is still fast. which i think it should be in practice? tho i'm not super familiar w/ that stuff.)

just curious, do you think that solution would have worked for your situation too?

That's exactly the strategy that was tipping over. Once you start resizing vectors of tens of megabytes, it's kind of over.

You can start playing games by accelerating capacity allocation when a vector rapidly starts growing extremely large. This doesn't solve the problem that vectors sometimes guarantee too much for what you need.

Ah thanks, I didn't read closely enough the first time.

For a simple and readable implementation of a Python btree see this:

https://github.com/samsquire/btree

I tried to keep the implementation as simple as I could.

also what a deque (C++) does

True... except in MSVC. std::deque in MSVC is cursed.

Targeting MSVC, use boost::deque or something, instead. Boost containers are generally fairly good, although they are more or less unmaintained nowadays. (E.g., boost::unordered_map::reserve doesn't work.) Or, like many of us, ignore performance on MS targets because anybody who cares about performances is running something else.

Why?

https://github.com/AcademySoftwareFoundation/openvdb/issues/...

Longer answer is that the size of the "blocks" is limited to 512 bytes or one element, whichever is larger. So unless your elements are really tiny, it is strictly a pessimization.

Many of the STL containers in MSVC are incredibly cursed. Even std::vector is implemented in such a weird way, that you can't debug it easily with any debugger other than Visual Studio. And it's incredibly slow on Debug mode, up to the point that it's unusable... (Because of these reasons I just switched to using my own Vector<T> class recently)

I think there's a very good reason why old gamedevs who were stuck with developing on Windows largely ignored the STL and made their own containers / utility functions: MSVC's STL was just awful.

I always wondered why we weren’t allowed to use the STL in the Windows division in the 00’s. This probably explains it.

There was a lot of BS, as well. It is impossible to tease out which was what.

> Many of the STL containers in MSVC are incredibly cursed. Even std::vector is implemented in such a weird way, that you can't debug it easily with any debugger other than Visual Studio. And it's incredibly slow on Debug mode, up to the point that it's unusable... (Because of these reasons I just switched to using my own Vector<T> class recently)

Here's a link to an old HN discussion that offers some insight on the performance of MSVC's STL in debug.

https://news.ycombinator.com/item?id=18939260

The "cursed" keyword hand-waves over the problem and suggests it originates in the acritical propagation of ignorant beliefs. Sometimes clarifying these is just a Google search away.

Yes, I know that already. And good luck with dealing all the linker/ABI issues from changing that setting.

> ignore performance on MS targets because anybody who cares about performances is running something else.

That's a strange take. Surely games still represent a significant chunk of the demand for C++ developers that need to care about performance?

Thus, "many". Game coders would not be among those.

If your elements are in the millions than a tree might be better, depending on what you do. If you traverse the whole thing often then vector is best, but at a million a tree will do a search for element faster despite the cache misses.

I don't know where the line is, but in general you are probably not close to that line so default go vector. However as your point is, sometimes you are over that line.

And if you really need it you can even do both tree and vector simultaneously - just make sure both consist of pointers only so you avoid update/sync issues.

You can, but probably shouldn't. The pointers means a cache miss when you follow it. Putting everything in the vector is the point, otherwise the map is potentially faster

If you have to do a binary search in a million elements you'll have cache misses anyways

Sure, ln cache misses. With a linear search through pointers you have n cache misses.

Ironically, if you weren't using huge pages, the operating system was already doing this for you anyway, and your contiguous segments weren't contiguous.

This does suggest functionality that the OS should provide: let the program remap memory somewhere else in its address space to obtain a larger contiguous chunk of addresses without copying data. This wouldn't help much if you have direct pointers, but I think e.g. Java has a layer of indirection that would let it benefit from remapping to grow ArrayLists. I don't know if things already work this way. It should make speculative fetches easier for the processor since now it understands what you're doing via the memory map.

Edit: taking this idea a little further is actually fascinating: use the type system to separate objects into pools based on type, and instead of pointers, use indexes into your pool. You can move the pool for free to grow/shrink it. I think you could even do this with pointers and full hardware acceleration today if you used the high bits to tag pointers with their types and used remapping at the hypervisor level to move the pools (so the address in the application level doesn't change). You could do some crazy stuff if the application could coordinate multiple levels of virtual memory.

OSes do already provide this ability: mmap.

Maybe I'm just not seeing it, but I don't see how mmap let's you remap an existing address to a new one? Looks like there is a mremap on Linux in any case.

Or, you can map new space onto the end of an existing mapping, at a slightly greater cost of keeping track. Mremap is usually better.

If you want to stick to mmap, you can do it by creating a file which doesn’t have any actual disk backing (one way to do this is with POSIX shm_open), and handling all memory allocations by mmapping parts of that file rather than mapping true anonymous memory. Then, ‘remapping’ an address to a new one is a matter of calling mmap again with the same file offset. Unlike mremap, this allows mapping the same memory at different addresses simultaneously, which can be useful for some purposes.

/dev/hugepages/ is a good place to put this if you have enough control over the host.

That sounds like a lot of work unless you absolutely have to have a contiguous allocation of every element.

If you don't need that, you can get "O(1.1)" access and nice heap behavior with an indirection or two, and the implementation is likely to be lots more portable and standards-friendly than if you also dragged in a bunch of OS mmap() semantics (which tend to have exciting, platform-dependent misfeatures).

Also, I would have to reach for the mmap() man page. I have malloc() right in front of me. :-)

Right, the ability to relocate a chunk of memory to a new virtual address (with more capacity at the end) without doing a physical copy would be an interesting way to solve the problem.

I don't know if anyone has done research on integrating data structures and OS functionality in this way. Interesting idea.

We needed to get things running again rather quickly, though :-)

Some game engine developers have certainly used this idea, to prevent any reallocations when the dynamic array needs to be resized. Such as:

https://ruby0x1.github.io/machinery_blog_archive/post/virtua...

Some ECS implementations use this to reduce the overhead of dynamic arrays, as well as ensuring pointer stability of the items stored. For example entt:

https://skypjack.github.io/2021-06-12-ecs-baf-part-11/

And here's a library implementing a resizable, pointer-stable vector using virtual memory functionality from the OS:

https://github.com/mknejp/vmcontainer

End of page allocation has been a real life-saver. I have it rigged up to the core allocators of the game engine I work with, so you can switch it with a cmdline switch; if you suspect an overwrite, you switch on the EOP allocator ( using more memory temporarily ), and bang, you get a segfault where you went off the end / used-after-free.

Linux has mremap() for this. macOS has vm_remap(). Not sure about other operating systems.

You can certainly allocate memory at controlled addresses using mmap or VirtualAlloc.

But you should not play virtual memory games at runtime in an application that you expect to be scalable. Unmapping memory or changing its permissions requires propagating the change to all threads in the process. On x86, the performance impact is dramatic. On ARM64, it’s not as bad but it’s still there.

Also, even 64 bits can go fast when you start using high bits, separate pools for different purposes, etc.

I somehow misread your comment the first time through and thought you were suggesting the ability to ask the OS: "Hey, I'm a pointer, is there anything in front of my block of memory, if so can you move it elsewhere so that I can expand?" This would of course be a pretty silly idea but it would be funny to give the OS folks a whole new class of use-after bugs to worry about.

Edit: Let's call it "memoveouttamyway"

Isn't that `realloc`? At the allocator level rather than OS level, but still.

glibc realloc(3) does this on Linux, by way of mremap(2) with MREMAP_MAYMOVE [1]. (Just confirmed on my local machine using strace(1).)

Unfortunately, libstdc++ does not (to my knowledge) use realloc(3) or mremap(2) for vector resize, nor could it in many situations due to the semantics of C++.

[1] https://github.com/bminor/glibc/blob/15a94e6668a6d7c5697e805...

This sounds like you need a log structured merge tree.

My Forman always would tell me KISS - (keep it simple stupid), maybe there is another single word for just solve the problem at hand silly - j,s,p,a,h,s - doesn’t really roll off the tongue the same way…

Nobody has mentioned immutability yet - linked lists are easily used as one of the simplest immutable persistent data structures. Your definition of "better" appears to be solely about keeping the CPU burning, but if CPU isn't the bottleneck, I prefer "immutable linked list" over "clone a vector many times" merely on aesthetic and reason-ability grounds.

Or you could go the Clojure route and do the tree-style immutable vectors where the cost is log32(N) for most operations, small enough in all the relevant operations, and you get the amazing usability of immutable data structures that are performant enough in most cases.

How does that scale down to small sequences of under ten items?

an array is used for the last 1-32 elements of the vector (the "tail") so there would be no trie at all, just the tail

cons cells are a local maximum.

often they're sufficiently maximal.

Well, of course if a solution is "cloning a vector many times" then arguably you're using the vectors wrong - in which case it's totally appropriate to find a different data structure (or a better way to use vectors, if possible).

In C where using the simplest data structures is valuable, you’d likely do much better by upgrading your programming language to something that offers a better data structure. If you’re using a higher level language where you can abstract details about your sequence data structure, I think there’s very little benefit to using the simplest data structure and you should instead have widely used libraries that offer a good immutable sequence type, e.g. RRB trees.

One exception is ML style languages where singly linked lists get a big syntax advantage (Haskell only half counts because most of its lists are really just iterators). I think this was, in hindsight, a mistake for a widely used language. It’s also a source of pointless pain for learners (eg I don’t think there’s much benefit to people having to write lots of silly tail-recursive functions or learning that you have to build your list backwards and then reverse it). Another exception would be some lisps where lists are everywhere and the cons-cell nature of them makes it hard to change.

It's surprising people are arguing about this. That fact alone shows that lots of developers don't understand the relationship between L1/L2 cache, data access patterns, and how prefetching works.

That makes sense, given how abstract things have gotten. Decades ago there was an article that showed the penalty for non-linear data access was massive. That was before speculative access, branch prediction and cache prefetching were standard features. The performance hit today would be even more (except presumably for machines that have implemented the speculative execution security mitigations).

As with any such subject, it's worth discussing the details but probably not the generalities really (except perhaps in the whimsical style of antirez).

You're right to point out that given the performance characteristics of most modern CPUs, accessing memory linerally is optimum. But it doesn't necessarily follow that all collection data structures should be stored as a vector. Consider a collection traversed very slowly relative to the overall computation. There may not be any cache win if the line's always evicted by the time you come back to it.

I’ve always wondered about whether you could have your cake and eat it too with linked lists where nodes are allocated in contiguous blocks of N nodes. So, the normal case of traversing the next pointer is not a discontinuous memory access.

That's quite likely to happen to a linked list when using a compacting GC (such as Java's or C#'s generational garbage collectors) (assuming the elements of the list are only reachable from the preceding element, not from many other places as well).

That depends on the GC’s traversal strategy, I think. If you assume that linked lists are implemented as in lisps (a pair of pointers), then if you traverse the head pointer before the tail pointer, the compacting GC will tend to spread the linked list out over time.

It’s hard for me to blame developers for their misaligned mental models since, as you yourself point out, the relationship between your mental model of the hardware’s behavior and what it actually does is complex and not really obvious. Mitigations etc means that the hardware you bought might totally change its behavior in the future. If all you can rely on is time measurements, it doesn’t explain that the software you wrote last year is now eg 40% slower due to bug mitigations. I think it’s easier to expect developers to put in the effort once they’re empowered with powerful tools to explain how the software gets mapped onto the hardware.

I think tools that result in greater transparency at lower levels will probably emerge, something like a compiler-generated dynamic analysis + pre-flight checklist hybrid. But since it’s so low-level, it might actually affect results, which may be a problem. I think intel vtune seems interesting in that regard.

Well, ideally your programming language (and its standard library) should provide you with basic data structures that are cache oblivious (or optimized for your arrangements cache). So programmers wouldn't need to worry.

The fact is that in 95+% of cases, the performance doesn't matter at all, and a linked list is fine.

The only problem is that use cases evolve, and what was fine suddenly isn't, anymore.

I think the argument of locality and linearity and cache hits is valid, but specific for one access pattern: reading items in order and adding to the tail. If that's what your code ends up doing most of the time, then an array wins over a linked list hands down.

As soon as you start adding or deleting items in the middle, the game changes because the data you need to move is not contained in the cache anymore (except for small arrays).

I can even imagine a workflow that uses both data structures: an app could build up a linked list with the data it reads from an external file, for example, where they can be scattered and not in order; when the file is finally closed, the data are considered read-only and rearranged into an array for the remaining part of the execution.

So don't dismiss linked lists as inefficient "a priori", which is exactly what antirez claims in the article.

That analysis is lacking. Linked lists turn out to be inferior to arrays for essentially any access pattern, at least when the linked list can be assumed to be randomly stored and not accidentally sorted.

Say you want to add an element in the middle of an N-element ll/array.

For the linked list, this means you need to do 2 * N/2 memory reads (read value, read next pointer), which will mean on average N/2 cache misses, to reach the element at index N/2. Then you'll do O(1) operations to add your new element. So, overall you've done O(N) operations and incurred O(N) cache misses.

For an array, there are two cases:

1. In the happy case, you'll be able to re-alloc the array in-place, and then you'll have to move N/2 elements one to the left to make room for your new element. You'll incur one cache miss to read the start of the array, and one cache miss to read the middle of the array, and one cache miss for realloc() to check if there is enough space. The move itself will not incur any more cache misses, since your memory access pattern is very predictable. So, overall you've done O(N) operations, but incurred only O(1) cache misses - a clear win over the linked list case.

2. Unfortunately, sometimes there is no more room to expand the array in place, and you actually have to move the entire array to a new place. Here you'll have to move N elements instead of N/2, but you'll still incur only 1 cache miss for the same reason as above. Given the massive difference between a cache miss and a memory access, doing N operations with 1 cache miss should easily be faster than doing N/2 operations with N/2 cache misses.

The only access patterns where the linked list should be expected to have an advantage are cases where you are adding elements very close to an element which you already have "in hand" (e.g. at the head, or at the tail if you also keep a pointer to the tale, or to the current element if you're traversing the list while modifying it). In those cases, the linked list would need O(1) operations and cache misses, while the array would need O(N) operations and O(1) cache misses, so it would start to lose out.

> The only access patterns where the linked list should be expected to have an advantage are...

Exactly my point: such access patterns exist.

> It's surprising people are arguing about this. That fact alone shows that lots of developers don't understand the relationship between L1/L2 cache, data access patterns, and how prefetching works.

Your misconception lies in the assumption that the only conceivable use case is iterating over a preallocated data structure to do read-only operations.

Once you add real world usages, with CRUD operations involving memory allocations/reallocations then your misconception about cache crumbles, and you start to understand why "people are arguing over this".

Which misconceptions? Messy memory allocations hurt lists even more.

You're expanding the scope of the problem. In real life nobody is pulling shit off of a database and stuffing it into a linked list. And if they are the performance will still be worse because each list will be allocated. Even if you do your own malloc you will blow cache with a linked list, because as time goes on your locality will be blown out. Iterating over a linked list will be worse as well.

In fact, on modern architectures it may be faster to iterate over arrays just to take advantage of l2/l3 behaviors.

I often write code destined to run on a microcontroller, and linked lists are great for avoiding dynamic memory. It's nice to be able to statically or transiently allocate storage without having to bound the size of anything.

Of course, the same unintuitive tradeoffs tend to apply even if there isn't much caching to worry about. A trivial linear iteration is often faster than a more elaborate algorithm when the input is small.

Carmack is a fan of this approach. Allocate some reasonably large number as your design constraint and if you start approaching it that is a time to ask why and is this data structure still reasonable here

A memory-constrained microcontroller is actually one of the valid exceptions to the rule.

Well, yes, and a lot of people treat kernel development as if they were developing for a constrained microcontroller. I don't think this is even a bad thing, we want the kernel to be as lean as possible because every page and cycle the kernel burns is one that users don't get to use.

I suppose a more important reason is the "not have to bound anything" part. OS kernels almost definition don't know how many objects will be created. Implementing queues as vectors of pointers will require dynamic allocation and/or introduce many more failure points when going out of resources. With linked lists, once you have an object you can always append it to a linked-list queue.

This is a memory vs. time tradeoff. And the time cost gets worse as the machine gets bigger.

Designing for embedded is not the same thing as being lean.

It's also an area where the costs are a lot less significant either: a cortex m4 and below often doesn't have a cache (at least for RAM: flash often has a cache and predictive lookup, but the perfomance difference is small enough that the cache can basically render executing code from flash as identical to RAM), and the RAM is about as fast as the processor, so random access and sequential access are pretty similar performance wise. (And with the speed of modern microcontroller cores the size of the data is rarely even an issue: most STM32s can iterate through their entire RAM in under a millisecond).

That said, in my embedded work I still rarely find a linked list to be a useful data structure (but I know FreeRTOS, which I use a lot, uses them extremely heavily internally).

That‘s why the Amiga OS (Exec) used linked lists as its primary data structure. It was one of the first micro computer operating systems using dynamic memory mapping (i.e. no fixed addresses for OS calls and data structures) and supported multi tasking. Any object you received from Exec basically was a pointer to a list node. And, yes, the Amiga‘s biggest problem was memory fragmentation and leakage because unreachable linked list nodes would be starting to accumulate whenever working with a buggy program.

> regular resizable vector

At gross complexity / fragmentation / to your memory allocator.

Linked Lists are definitely easier to use if you're ever in a position where you're writing your own malloc(). The infrastructure needed to cleanly resize arrays (and also: the pointers all going bad as you do so) has a lot of faults IMO.

EDIT: In particular, linked lists have a fixed size, so their malloc() hand-written implementation is extremely simple.

Doubling the vector size each time it needs to be enlarged takes care of fragmentation/memory overhead, in practice. Or preallocating if you know the rough size.

It does take some discipline to avoid the storage of pointers, but once you get used to that it’s quite fine.

Source: I work on VPP, which uses vectors quite extensively.

Usually you want a smaller growth factor than that to allow for more reuse. (Also: what’s VPP?)

I use doubling because it’s simple to reason about and hard to screw up the math.

What kind of growth factors heuristics worked for you the best ?

VPP: rather fast user mode dataplane. https://fd.io/ is the “marketing” site. https://wiki.fd.io/view/VPP is the “less flashy” dev wiki.

The optimal growth factor is the golden ratio (1.6), in practice many vectors use a growth factor of 1.5.

The reason for not going above the golden ratio is that it prevents any previously allocated memory from ever being reused. If you are always doubling the size of your vector, then it is never possible to reclaim/reuse any previously allocated memory (for that vector) which means every time your vector grows you are causing more and more memory fragmentation, as opposed to using a growth factor of 1.5 which results in memory compaction.

Why does that happen when doubling size? I don’t understand

Sure we can go over both cases:

Case 1: Growth factor of 2 and an initial size of 10 bytes.

Start with an initial allocation of 10 bytes of memory.

On growth allocate 20 bytes and release the 10 bytes, leaving a hole 10 bytes.

On growth allocate 40 bytes and release the 20 bytes, the hole in memory is now 30 bytes large (the initial 10 byte hole + the new 20 byte hole).

On growth allocate 80 bytes and release the 40 bytes, the hole is now 60 bytes.

On growth allocate 160 bytes and release the 80 bytes, the hole is now 140 bytes.

So on so forth... using this strategy it is never possible for the dynamic array to reclaim the hole it left behind in memory.

Case 2: Growth factor of 1.5 and an initial size of 10 bytes.

Start with an initial allocation of 10 bytes of memory. On growth allocate 15 bytes and release the 10 bytes, leaving a hole 10 bytes.

On growth allocate 22 bytes and release the 15 bytes, the hole in memory is now 25 bytes large (the initial 10 byte hole + the new 15 byte hole).

On growth allocate 33 bytes and release the 22 bytes, the hole is now 47 bytes.

On growth allocate 50 bytes and release the 33 bytes, the hole is now 80 bytes.

On growth reuse 75 bytes from the hole in memory left over from previous growths, the hole is now 5 bytes.

With a growth factor of 1.5 (or anything less than the golden ratio), the hole grows up to a point and then shrinks, grows and shrinks, allowing the dynamic array to reuse memory from past allocations.

With a growth factor of 2, the hole in memory continues to grow and grow and grow.

This appears to assume that there will be no intervening allocations that are allowed to use the same region of memory, since otherwise your "hole" will be very discontiguous.

But if that is the case, then why are you releasing memory? That's just costing you time moving the data. With a doubling mechanism:

Start with an initial allocation of 10 bytes of memory.

On growth allocate another 10, and don't copy anything, leaving no hole at all.

On growth allocate another 20, and don't copy anything, leaving no hole at all.

etc.

In what scenario would the growth factor of 1.5 actually help? If you're restricting the allocation API to only malloc then you can't grow the size of your allocation and what you said might make sense as something the allocator could take advantage of internally. But realloc exists, and will hopefully try to extend an existing allocation if possible. (If your earlier allocation was fairly small, then the allocator might have put it in an arena for fixed-size allocations so it won't be possible to merge two of them, but once things get big they generally get their own VMA area. Obviously totally dependent on the allocator implementation, and there are many.)

99.9% of the time, each allocation leaves a separate hole. Your goal is to enable other allocations to use those holes without further splitting them, not to get your ever-growing vector to reuse memory.

I usually use doubling, but I just recently landed a patch to expand by a factor of 8 instead, which sped up a microbenchmark (of constructing a JSON string, fwiw) by 50%.

Someone saw in a profile that we were spending a lot of time in realloc in a task that involved building a string in contiguous memory. But the final string was realloc'd down to its actual size, so it was safe to get a lot more aggressive with the growth to avoid copying. The overhead was only temporary. It turns out that powers of 8 get big fast, so there are now many fewer copies and the few that happen are copying a small portion of the overall data, before a final octupling that provided mostly unused space that didn't cost much.

Know your problem, I guess?

Very interesting. And indeed, especially being adjacent with the very interesting “golden ratio” comment, this shows that there is more than one definition of “best” dependent on the task, and that one always needs to verify their hunch by actual profiling.

good to know vpp is still alive. always interesting work coming out of it, and it never seemed to take off.

There are quite a few sizable businesses (hundreds of MUSD) built on it / depending on it, that I know of :)

out of curiosity, is it mostly Cisco still funding it? what are the advantages over dpdk? mostly TCP?

The funding - I believe organizationally it has now grown into https://lfnetworking.org/about/members/ and fd.io is just one of the projects.

Contributions-wise to VPP: varies from time to time. On my very recent memory there were sizable IPSec acceleration patches from folks at Intel. There is a fair few one off bugfixes coming from smaller users who scratch their own itch. Pim van Pelt [0] has contributed/improved a few very cool and sizable features (Linux control plane integration, VPP yaml configurator [1])

As for difference with DPDK - does it do L3 routing? NAT ? MAP ? MPLS ? DHCP ? VPP can do all of this, and of course it’s just off top of my memory…

https://docs.fd.io/vpp/22.10/aboutvpp/featurelist.html is the autogenerated feature list based on the “claimed official features” that are tracked via YAML files in the source code.

[0] https://ipng.ch/s/articles/2021/08/12/vpp-1.html [1] https://lists.fd.io/g/vpp-dev/topic/feedback_on_a_tool_vppcf...

or if you can't guarantee allocations will succeed and need to handle that case. in that case you can just have the object that's part of the list have its list element data contained within itself. (aka an intrusive list)

More complexity than allocating/deallocating a struct for each link in the list?

And the solution to "pointers to elements of a vector going bad" is don't save pointers to elements of a vector.

Here is a performance graph on removing items from a vector vs list - slightly old (2017) https://github.com/dtrebilco/Taren/blob/master/Articles/iter...

From the article https://github.com/dtrebilco/Taren/blob/master/Articles/Eras...

That is removing an item at N index, right? (that's why it talking about iterators?) Linked lists are only fast at append/pop with the first node.

>> This includes problems that they should be great for, like insert into the middle or the front.

How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from?

>> your default be a vector and not a linked list

The default should be to understand the problem.

I think by “middle” they mean “at the current position” not at an arbitrary position in the middle when starting from HEAD

> How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from?

Both an array and a linked list are O(n) for adding in the middle. In an array, you finding the middle element is O(1), then moving the rest of the array is O(n) [you have to move n/2 elements]. In a linked list, finding the middle element is O(n) [you have to traverse n/2 elements], but adding it is O(1).

So, asymptotically there is no difference. In practice though, the linked list traversal will cause O(n) cache misses to reach the middle element (since we are traversing random memory), while the array move will only incur O(1) cache misses (since we are accessing memory in order) - so, the array will actually win in practice.

Edit: Note that I also don't know where the GP got the O(lg n).

It seems that the case where it is necessary to find the exact middle element and insert something wouldn't be very common but OK, I'll humor this use case. Let's assume that the list is huge and inserting at the middle is the only thing we do. Just maintain a pointer to the middle element and insert there: O(1) for find and insert. If it is necessary to add/remove at other places in the list, it is possible to maintain a doubly linked list and move the middle pointer back and forth accordingly (still O(1)).

I suppose if the LL like structure is mostly read only with rare inserts, not that big and holds simple data types or structs and often needs to be read sequentially then an array/vector/list would be better than a regular LL but then it is obvious that an array is better anyway.

It's poor guidance to tell people that the vector is the "go to" when you need a LL. Sad actually that this poor guidance has been upvoted by so many people such that it is the top comment, all in the name of some FUD about cache misses.

Let's take the case where we need to add to any element of the structure, with uniform probability.

For an array, this means we'll have to move N elements if we need to add at the beginning, N/2 if exactly in the middle, or 0 if at the end. Either way, we'll need to re-size the array, which has some chance of requiring N copies anyway - say, half the time. So, on average, we'll perform 3N/4 moves per element added, requiring 1 cache miss every time.

For a (doubly-)linked list, this means we'll have to traverse 0 elements if we want to add right before Head, 0 if we want to add right after Tail, and worse case we'll need to traverse N/2 nodes if right in the middle - so, we'll have to do on average N/4 traversals per element added. Each of the nodes traversed will generally be a cache miss, so N/4 cache misses. So, the Linked List will indeed be require a third the number of operations on average, but many times more cache misses, so should be expected to lose. If you store the middle pointer as well, you'll again half the number of operations for the list, but that still won't cover the amount of time wasted on cache misses.

Of course, if the distribution is not uniform and is in fact skewed near a predictable element of the linked list, at some level of skewed-ness vs cache speed advantage, the Linked List will overtake the array.

Note that linked lists also have other advantages - for example, they can be used as in the Linux kernel to store the same object in multiple different lists without any copying and without extra pointer indirections (at a small cost of one extra pointer in the object per list it could be a member of). They are also easier to pack into a small address space that has to be dynamically allocated (since you don't require a large contiguous block).

A good balance is a tree with about a cache line's worth of values at each node. It degrades to a vector for small N, gets the pre-fetching / branch prediction benefit for medium N, but doesn't require fully contiguous memory for large N. It also tends to do fairly well on common mutation patterns (insertions and deletions) by avoiding large copies.

If you want lock-free atomic data structures there are lots of variations (like AVL trees) that can be used as the underlying storage and just like mentioned above it tends to work well for most use cases and access patterns.

If N is fairly small and/or you allocate most of your linked list around the same time it may not matter which is why measuring your actual program with real-world data and access patterns is so important. eg if in production logging or other malloc traffic ends up making your linked list nodes spread out in memory perf is not going to match what you tested at your desk.

Often an algorithm can operate on an entire cache line's worth of data before main memory can chase down a single pointer. Modern CPUs hide that with prediction but even if the address prediction is 100% accurate if the result is a pointer loading chain you run out of pre-fetch slots pretty fast.

To give concrete numbers if DRAM is not busy refreshing and there is no bus contention or inter-core contention then we might get 60-100ns access times all told. If we have a 3Ghz CPU then that's 300 cycles waiting around doing nothing... for each pointer that needs to be dereferenced. For a vector after the first 300 cycle hit the rest would be free - following nodes are in the cache line and address prediction will pre-fetch subsequent cache lines as well, allowing pre-fetching to stream data ahead of when it is needed.

Understanding, and even sympathizing, with the machine's toil re: vectors vs manual linked list can separate a good engineer from a great one. We learn linked lists, assembly, and even machine code in Computer Science majors so that we know what's happening under the hood and can more easily surmise the runtime effects.

All of these are indeed important, and will eventually (one hopes) result in the student realizing that linked lists are to be avoided because of their poor mechanical sympathy resulting from their awful cache locality.

Valid uses for a linked list are extremely niche. Yes, you can name some, and I can name several valid uses for bloom filters. Just because a simple linked list is easy to implement does not mean it should be used, any more than bubble sort should be used for its simplicity.

Wait why do linked lists have bad cache locality? It depends on how your heap is set up. For example, you could have an allocator that gives relatively good locality by having high granularity and only bailing out if say your LL gets super long (so if your lists are usually short, they could have awesome locality)

If you are in that place, you're probably using a linked list over small statically allocated memory, but you still need random ordering and fast remove or reorder.

That only works if you allocate lists all at once and never modify them.

If there are any other allocations taking place at the same time -- say, allocations from other threads, or for other data you had to create while building the list, that locality is shot. Same goes if you insert more elements to the list later, or if you perform an operation which changes its order (like sorting it).

> That only works if you allocate lists all at once and never modify them.

You can reorder and modify the contents of the list without losing locality.

I mean, if you modify the contents of the list nodes in place, sure. But at that point, you're just doing an array with extra steps.

Changing any of the pointers, however, will make memory prefetch much less efficient. CPUs like linear memory access patterns; they're easy to predict. Chasing pointers is much less predictable, even if the pointers are all to the same region of memory.

It might still be cheaper than copying the values if they’re large.

That doesn't seem to make much sense to me. LL are useful in cases where you deal with changing lists, where you'd be forced to allocate and deallocate memory often. If you know before hand the exact or approximate size of the list and it's contents you can store that continuously in memory with greater cache locality because you're not storing pointers in addition to data. Seems to me the use case of LL is perhaps as ill suited for cache locality as the structure itself

They’re also useful when you want to cheaply reorder nodes without copying the elements.

True. You could implement that using an array of structs where each struct contains indexes of the array to link other structures. instead of memory pointers, since they are 8 bytes in 64-bit applications. This way you get the nice properties of both linked lists and continuously allocated arrays

If your list is short then you won't have a problem. But if your list is long then traversing it can be a major problem.

For example, if your list item is page aligned like the task_struct in the Linux kernel, rescheduling the next process could traverse the process list. The process list links will be at the same page offset and associate with a restricted set of the L1/L2/L3 caches lines and thrash from memory. Worse, the TLB will thrash as well. This was actually the case for Linux until about 2000.

https://www.usenix.org/legacy/publications/library/proceedin...

http://trout.me.uk/lisp/vlist.pdf

An order book in electronic trading.

It is not too large (a few thousand of entries usually), but it needs to be accessed and modified extremely fast. There can be insertions and deletions anywhere, but it is strongly biased towards front. It is ordered by price, either ascending or descending.

Various “ordered queue” implementations are usually a poor fit, as there are many insertions and deletions in the middle, and they need to avoid any additional latency. The same goes to vectors. Red-black trees etc. are too complex (and slow) for such a small size.

So we start with a humble linked list, and optimize it (unrolled, skip search etc). But we respect linked lists, they work.

> Understanding, and even sympathizing, with the machine's toil re: vectors vs manual linked list can separate a good engineer from a great one.

I think your parent's point is that if you're a C++ programmer, recognizing that vectors outperform other data structures for most use cases is what separates a good engineer from a great one. Often even for things that require lookup (i.e. vector outperforming a set).

During code reviews, a senior C++ programmer in my company (formerly sat in the C++ standards committee) would always demand benchmarks from the developer if they used anything else. In most cases, using representative real world data, they discovered that vectors outperformed even when the theoretical complexity of the other data structure was better.

A great engineer knows the limitation of theory.

Of course, my comment is only regarding C++. No guarantees that vectors are great in other languages.

> [V]ectors outperform other data structures ... even for things that require lookup (i.e. vector outperforming a set)

This is something I've heard before (not often benchmarked) and it makes intuitive sense, and sometimes I've also told it to myself in order to not feel bad for writing O(n) where n is always small.

But somehow, reading this snippet, I'm reminded that the vector does not maintain the semantic reminder that it's used in a key/value use case. So it has me thinking there should be a map/hashtable/dictionary interface that's really just a vector with linear lookup.

Then I think, hmm, maybe the standard containers should just do that. Maybe the authors of those should have some heuristic of "when to get fancy".

I think the cases where lookup is faster for a linearly scanned vector is where the hash computation overhead is greater than a linear scan. Assuming you have a good hash implementation, that should be true only for a small number of entries, where you need to determine "small" by measuring.

I think it's about locality and quickness of compare.

So if you have a small data structure and/or large cache, and the key is not complicated.

Even if the key is cheap, that it isn't in cache means that vector will be faster just because we avoid the cache miss of loading the value into memory.

Std::find_if works great if you want to treat a vector like a map. Plus you can have different keys if that is useful for your problem (look up employee by name, id, or address?)

These are flat_map, flat_set, flat_hash_map, etc ...

See: https://en.cppreference.com/w/cpp/header/flat_map

I believe that flat_map and flat_set at least are sorted, so that binary_search/lower_bound can be used for lookups.

Linear search generally does outperform for small collections though (it’s better for caches and the branch predictor).

C++23! The future is here.

> Often even for things that require lookup (i.e. vector outperforming a set)

I am always uncomfortable using higher algorithmic complexity. Sure, for small data sets, the vector will outperform the set, but it may not stay small forever. I may waste a millisecond now, but at least, I won't waste an hour if the user decides to use 100x the amount of data I initially considered. And using much more data than expected is a very common thing. It is a robustness thing more than optimization.

If you want both, there are staged algorithms, a typical example is a sort algorithm that goes insertion -> quicksort -> mergesort. Insertion sort is O(N^2), but it is great for small arrays, quicksort is O(N log N) on average but may become O(N^2) in some cases, and mergesort is guaranteed O(N log N) and parallelizable, but it is also the slowest for small arrays. For lists, that would be a list of vectors.

I like the staging idea, but curiously I haven't seen any papers investigating this.

Obviously, there is an overhead cost of the staging itself, which hits the use case for small data, and there is the question "From what data size onwards to use what algorithm?".

For example, I just had a look at sort in Clang's STL implementation, which seems to set a boundary at N=1000. Since the number is a multiple of 10, it looks like it might be arbitrarily picked, in any case there is no paper references in the comments to back it up.

Are people aware of formal studies that explore whether it is worth the trouble to inspect data structure and then to dispatch to different algorithms based on the findings?

You're saying you think there's still optimization to be done re. the N=1000 constant?

Other than that, I'd suggest that big O complexity is already telling you that the inspection is worth it. Assuming inspection of an array is constant.

> Sure, for small data sets, the vector will outperform the set, but it may not stay small forever.

In over 90% of SW applications written in C++, there is little to no uncertainty on the size of the data set. Most applications are written for a very specific purpose, with fairly well known needs.

If my data set is size N, and I can benchmark and show the vector outperforms the theoretical option up to, say, 20N, it's a safe choice to go with vector. Doing these analyses is engineering.

In any case, it's almost trivial to swap out the vector with other options when needed, if you plan for it.

I hope that senior engineer is also the one person, who will refactor things, if ever there are more elements in any of those vectors, making linear search slower than an actual set or other data structure. Oh and of course that senior engineer will also hopefully be the one monitoring the lengths of all those vectors in production.

> vectors, making linear search slower

The standard library gives you plenty of tools to maintain and search in a sorted vector. Often enough still faster than maps.

> Oh and of course that senior engineer will also hopefully be the one monitoring the lengths of all those vectors in production.

Doesn't a std::map have more space overhead than a vector?

I believe he was referring to the number of elements in a vector, to know when to swap with a different data structure - not the size in bytes.

But to your point - I once needed to do a key/value lookup for a large data set, and so of course I used a map. Then I ran out of RAM (had 80GB of it too!). So I switched to a vector and pre-sorted it and used binary_search for lookups (data set was static - populate once and the rest of the codebase didn't modify it). And of course, the RAM consumption was less than half that of the map.

Just describe your sorted list as "a balanced binary tree with implicit child links" and then you get credit for being fast, space-efficient, and using fancy data structure.

I learned to love linked lists as soon as I discovered that I can just store them in vectors to get the performance of guaranteed contiguous memory:

  // LinkedListItem[k]: item[k], prev[k], next[k]
  std::vector<T> item;
  std::vector<uint> prev;
  std::vector<uint> next;

Similar is used in transparency rendering with per-pixel linked-lists.

Interesting idea but how does C++ guarantee contiguous memory for a vector? I just don’t see how a data structure with an arbitrary, dynamic size can also reside in a contiguous range of address space.

When the array is resized, it’s moved to a new contiguous block of memory: everything is copied or moved over. See: https://stackoverflow.com/questions/8261037/what-happen-to-p...

Simple, you just allocate a bigger contiguous chunk of memory and copy the entire vector over when the current chunk maxes out.

the size of a c++ object is fixed at compile-time

The performance of vectors comes from iterating through them and letting the cpu prefetch items before you need them. Random access in a vector doesn’t really get you that if the vector is larger than your L1/L2 caches, which linked lists would be in anyway if you used them recently enough.

I think a lot of graph edits are a nightmare to perform with an adjacency list, and a breeze when you just edit linked pointers.

Imagine the Euler Operators on a manifold (ie a 3D mesh) or on a planar graph, but on a vector instead of on a DCEL.

That works if the data that you want to put in the sequence is copyable (doesn't have "identity"), or if you can arrange so that it gets created in the right spot from the start and you can always choose the iteration order to be sequential in memory. For many more complex structures, that is not the case.

Could you give an example of a data that is uncopyable ? A struct witj self-referential pointers ?

If the data is relatively big buffers, you really do not want to copy them. Your memory bandwidth will thank you, and performance will vastly increase. Cache locality will be good anyway since you're referring to long blocks.

This kind of data structure often has a buffer + associated metadata. If the metadata+pointer fits into 1-2 cache lines, storing it in a vector can give be win vs. storing the next/prev pointers next to data + metadata.

In any case, there is always only one authoritative answer: “perf top”. :)

It's about the meaning, not the raw bits. I might be able to duplicate your signature, but that doesn't mean I can sign documents for you.

Example: Any object shared among multiple lists or other data structures at the same time, or directly pointed to by other objects, such that any of those views must reach the same cheaply mutable state. This includes objects in the object-oriented programing (OOP) model, actors in the actor model, and file objects in a kernel which are in multiple lists.

For those you have to store object pointers in the vector, instead of copies of the objects. That works and is often done, but it defeats or reduces the cache locality perfornance improvement which motivates using a vector in the first place.

On an in-order CPU an intrusive list (pointers inside the objects) can be traversed faster than a vector or B-tree of object pointers, though a non-intrusive list (list of nodes containing object pointers) won't be faster. On an out-order CPU with heavy speculative execution it is less clear cut because the vector allows successive objects to be dereferenced speculatively in parallel to a limited extent, while this is not possible traversing an intrusive list.

If the list is going to be traversed looking for objects based on some filter criterion such as flags or a number comparison, based on non-mutable state (or where it's ok for mutation to be expensive), traversal can be sped up by storing criterion data in the vector alongside the pointers, or in a second vector, to avoid dereferencing every touched object pointer during traversal.

Linked list are indeed great for secondary traversal orders (or for subsets).

But I don't understand your comments re in-order CPUs: vectors will be faster there too as they avoid the load-load dependency. Most modern inorder CPUs are still superscalar and fully pipelined.

For example, an std::mutex is uncopyable, and even immovable.

While I generally agree with you, I have had multiple occasions where amortized O(1) was unacceptable, whereas the overhead of linked lists was ok.

You can make dynamic arrays have worst case O(1) at the cost of some extra overhead.

Copy the array on every append? :)

That would not be O(1), but O(n) per insert.

> almost always, whatever problem you're trying to solve would be better done with a regular resizable vector

Resizing a vector brings the whole of it into cache, potentially dragging all of it all the way from actual RAM. Prepending an entry brings nothing into cache.

Cache is king.

So use an array deque if you need O(1) prepending.

Resizing the array in the array dequeue brings the entire thing into cache. That's a disaster.

It's a disaster but it's an amortized O(1) disaster.

It's far from a disaster because the best way to deal with a list is still to use a contiguous array.

Allocation isn't free. You have to do it sometime and doing it all in bulk is going to have the same consequences as just one small allocation anyway. If you are mapping new pages into main memory, making system calls or looping through a heap structure, you're not only affecting the data cache but also the TLB while also pointer chasing.

Making a list out of an allocation for every element is performance suicide on modern computers. Even the amortized resizing of an array is done at the speed of memory bandwidth because of the prefetcher. Thinking that is some sort of performance hindrance is absurd because it outweighs the alternative by orders of magnitude. If there really are hard limits on the time every insertion can take, then the solution needs to be links of large chunks of memory to still minimize allocations on every element.

Obviously the compromise is to use a linked list, but preallocate a contiguous block of memory to hold all your linked list nodes. Like an array of linked list nodes, each with a pointer to the array index of the next node.

Then you just need to double the size of that block of memory and copy all the nodes to the new block whenever it fills up.

Hmm, but you’d probably end up needing some kind of a list of free blocks of space within that array to deal with fragmentation… you’d need another linked list to store those blocks in.

If only there was some sort of system that could take care of all that allocation and freeing of memory for you?

It looks like you are conflating a linked list with a heap. Once you have an array/vector for your node list the unused memory can be a list itself, each index pointing to the next free index. You just need the next free index to get memory and you point to the current free index when you free a node. You don't need to manage the memory further than that.

That's amortized O(1), not WCET O(1). For transformational systems they're equivalent, for reactive systems they aren't.

> Resizing a vector brings the whole of it into cache

I don’t do low level code on modern systems; is there not a way to just blit chunks of memory around without a CPU looping it’s way through word by word carrying out MOVQ instructions which do a full RAM read/write?

If you’re streaming data out of memory to a PCIe bus or something, that wouldn’t go via cpu cache, right? There’s some kind of DMA model, so there’s something in the system architecture that allows memory access to be done off-CPU (I vaguely think of this as being what the northbridge was for in the old school x86 architecture but I’m fuzzy on the details?).

Mechanical copying of byte arrays feels like something a CPU should be able to outsource (precisely because you don’t want to pollute your cache with that data)

Not in architectures I've seen or maybe I'm missing the instructions to do it? Even if there were and you can bypass the CPU, hauling data out of RAM is still going to take a long time.

> maybe I'm missing the instructions to do it?

Yes, they’re called “non-temporal” load and store instructions. AFAIK most memcpy implementations will automatically use non-temporal access when copying blocks larger than a certain threshold, precisely to avoid destroying the cache during bulk copies.

Additionally, a well-optimized memcpy implementation (e.g. making good use of prefetch hints) should not suffer too much from RAM latency and be able to pretty much max out the bandwidth available to the CPU core.

You're thinking of like MOVNTDQA? Those still have to reach into RAM - that's still double-digits nanoseconds away and still creates a stall in the processor at n complexity!! No thanks? I can allocate a new linked list node with memory guaranteed already entirely in cache (except for TLA failure.)

> be able to pretty much max out the bandwidth available to the CPU core

Why max out a slow link at n complexity when you can just avoid doing that entirely and use a linked list?

Surely you know the answer, if you're analyzing at this level of detail?

It's because spending 1 millisecond per X operations doing vector moves is preferable to spending 20 milliseconds per X operations stalling on list links.

If you set a good vector size from the start, the moves will be rare to nonexistent. Or you could reserve some address space and never have to move the data.

In the ideal case (and assuming a vector large enough that it spans many pages), you would actually be able to work with the OS's virtual memory manager to re-allocate and move only the page that contains the address you want to write to, while all other pages can stay untouched. But there is quite a bit of careful work to do to implement something like this and make sure you are not invalidating pointers or even internal malloc() data structures.

Sure, prepending or adding at the end(assuming you're keeping a tail pointer, which is easy and common) are basically the only cases where a linked list can beat an array.

Yeah, and we deliberately prepend because that doesn't involve writing to a field in a node which may not be in cache. It's the consumer's job to reverse the list if they ever actually need it.

That depends on the number of elements and the size of the payload data. Both approaches can be combined by using a linked list of arrays.

Yes.

There is a reason why it's hard to create either a bare linked list or a bare array on modern language. It's because both are bad extremes, and the optimum algorithm is almost always some combination of them.

Compacting garbage collectors put linked lists into nearby memory.

Even if memory was packed by a GC, linked lists still have to pay the cost of allocating and garbage collecting every cell of memory individually. I doubt a GC would solve linked lists’ woes.

Do you have some benchmarks demonstrating your claim?

Erlang GC is pretty good, plus there are some nice highly local allocators

Be that as it may, it'll still take a benchmark to convince me.

There are also prefetch instructions. I listened to https://www.youtube.com/watch?v=SetLtBH43_U recently (transcript: https://signalsandthreads.com/memory-management/), part of it talked about some work in OCaml's GC.

> ...each individual memory request that’s not in cache still has to wait the full 300 cycles. But if we can get 10 of them going at the same time, then we can be hitting a new cache line every 30 cycles. I mean, that’s not as good as getting one every 16 cycles, but it’s close. You’re actually able to get to a reasonable fraction of the raw memory bandwidth of the machine while just traversing randomly over this huge one gigabyte heap

https://github.com/ocaml/ocaml/pull/10195 shows the change adding prefetching to the marking phase (https://github.com/ocaml/ocaml/pull/9934 was done earlier for sweeping). There are some benchmarks in the thread/linked from the thread.

I don't have a benchmark, but it's important to remember that GCs only scan live objects, and they always have to scan all live objects; while allocation is normally an extremely simple instruction (bump the memory pointer). It's true though that scanning a live linked list would be expected to be slower than scanning a live array (though some optimized scanning strategies may be possible).

Overall I couldn't tell what the impact on overall performance would be, but I can tell you for sure that de-allocating an N-element linked list or array are both O(1) operations for a copying garbage collector (which are the most common kinds of compacting GCs), since they simply will never reach nor copy any of the elements.

Will they? I don't think they reorder live objects relative to each other, so any object allocated between two nodes would still end up between those nodes after the GC ran.

It is very possible for a compacting garbage collector to reorder live objects.

It might or might not. Commonly, not.

Disagreeing with other answers here, but usually they will, and not because the authors tried to make it happen. It's just sort of the default behavior.

A copying collector has to trace through the whole graph to find everything reachable. The tracing order is usually going to be depth first. (It's the easiest to code if you're using recursion and therefore maintaining state with the runtime's stack, but even with an explicit stack you'll want to push and pop the end for locality.) Which means that objects arranged into a linked list will be visited in list order, and you generally copy as you visit an object for the first time. So... reordering live objects relative to each other "just happens". Even if it's a doubly-linked list, since the back pointers have already been visited and so don't matter.

This is less true if your objects have a lot of other pointers in them. But that's just saying that if your object graph isn't a list, then it won't end up laid out in list order. It'll still end up in DFS order according to the true graph.

I wish the word vector didn’t have so many different uses in science and engineering.

if you can replace linked list with vector then you don't need a linked list and the two shouldn't be compared as it is almost always obvious when you need one over the other. Link lists are used in areas when there is a relationship between nodes like a list of running processes. one of the frequent operations is to remove a node from whatever position it's in and add it on either side.

Right. Like there are so many algorithms that I shudder to think about how you'd implement them without linked lists. Like...how about a buddy allocator? Sure you could use a vector for each but you'd be copy and resizing huge swathes of memory constantly for very little gain. Use the right tool for the job!

The thing is, the cost of copying memory is essentially the same as the cost of reading it, and linked lists force you to keep re-reading the same memory over and over (assuming random access).

Adding an element in the middle of an array vs the middle of a linked list actually has the same asymptotic complexity (O(n)), but far better cache impact for the array (since moving a contiguous block of n/2 elements should only incur 1 cache miss, while reading n/2 randomly distributed nodes of the list will incur on average something like n/4 cache misses). Adding closer to the beginning of the linked list is faster, but adding close to the end of the vector is faster still, so overall with random access, the vector should win.

I think you missed the point here. You don't use link lists when you are going to walk the list and insert in the middle or some random place. The only time you end up walking a link list in typical scenarios is when you want to print them out or some unimportant operation.

Link list is used to hold relationship between nodes and when you are operating on that node the common patterns are remove and add it to another list, or re-add it on either side. Take a look at bsd or linux source for inspiration. A process struct has more than dozen member variables of node* type because the object ends up being in several lists like sched, signal queue, child threads etc.

what makes you think that list operations make the CPU jump randomly in memory and that implementors of, say, Lisp systems haven't optimized memory management for linked lists? A modern GC provides features generations, areas, copying and compacting.

One a Lisp Machine from the 80s/90s the system saves a type sorted and locality optimized memory image, from which it later boots the Lisp system. Additionally to the typical GC optimizations (incl. integration with the paging system) it also provided CDR coding, which allocates lists as continuous memory. The GC also creates those CRD coded lists. CDR coding fell out of fashion in modern Lisp implementations, because the space and time savings aren't that great to justify the more complex implementation.

If you're iterating, sure, use a vector. If you're pulling from a queue and doing a lot of processing, maybe an RPC -- does the ~70ns memory latency hit really matter that much? Probably not.

Why impose that latency if you don't need to? It costs me nothing to reach for a vector instead.

Costs you a dynamic memory allocation, code overhead and higher memory use. There are good reasons why std::array and plain arrays exist. Vectors are for when your data is unbounded, which is actually a risk most of the time. For truly big data, you want a special structure anyway.

Without extra work you can’t use a vector like a queue, and a circular buffer doesn’t necessarily support all types and/or preserve iterators on insert. Could use a deque, a blocked linked list. But IMO list is fine if it’s not clearly a bottleneck.

If you're pulling from a queue use a ring buffer.

Sometimes. Depends on whether you are filling in a data buffer or trying to send an already calculated data buffer.

A standard ring buffer does copies/fill. A ring buffer of pointers has similar performance characteristics to a linked list.

OT but does anyone know a general purpose ring buffer implementation for Java?

LMAX disruptor: https://lmax-exchange.github.io/disruptor/user-guide/index.h...

It's used by log4j2 and several other java libraries and is quite solid. You can use it in blocking or polling modes, so it's quite generic depending on your latency requirements.

Unfortunately log4j2 is no longer a shining example of good engineering, if you're trying to sell something...

I'd prefer saying LMAX is / was used as the core of high frequency trading applications.

One data structure I recently found myself wanting is a tree-based "array", with O(log n) access by index / insertion anywhere / deletion anywhere.

Kinda weird how rare it seems to be.

That sounds like a pretty run-of-the-mill balanced binary tree? Rust has a BTreeMap: https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...

Inserting into an array increments the indexes of all subsequent values. How would a regular BTree emulate that behavior?

It would rebalance on insert with O(log N) performance but chunky constant factor, keeping the ordering so access by index is also O(log N) with low constant factor...

Which is why usually you would use a red-black tree rather than a BTree, as it has much lower constant for insertion and access by index. However higher for traversal in order.

That does sound useful, although I'm having some trouble thinking of what for exactly. :-)

And indeed, I don't recall seeing something like that. At a first glance O(log n) seems easy to do in the average case, but perhaps not in the worst case.

I suppose it's quite similar to the idea of Bagwell's persistent data structures[1] — those are particularly useful for lock free coding and with a high enough branching factor could be not as much overhead as a linked list or just plain copying.

[1] https://hypirion.com/musings/understanding-persistent-vector...

Well, doesn’t the “index” need to be stored in the tree itself for this to work? If so, the tree just represents an ordered map. (Changing indexes after deletion or insertion would be a problem, though.)

https://stackoverflow.com/a/837911 disregard the O(1) discussion.

An underlying problem here is that we have come to favor computers that scales out the Von Neumann architecture with more cache coherent cores and more memory. If we take the path of hardware that implements smaller Von Neumann scales, and rather partitions smaller sets of cores and memory into actors that communicate with memssages we would get lower memory latency and less penalty from random access patterns.

> Linked lists are great. But they have the problem that, almost always, whatever problem you're trying to solve would be better done with a regular resizable vector.

One important exemption is when you want your datastructure to be persistent.

See https://en.wikipedia.org/wiki/Persistent_data_structure

But for many applications there are also better persistant data structures than linked lists around.

Isn't linked list the fundamental data structure for LISP? The sweet memory of cons() this and cdr() that are all backed by linked list?

So, two things. One: 1980s machines don't have the memory access performance you see today. If N list chase operations takes the same time as N sequential reads then the linked list has the nice properties you were probably taught in school and actual in-memory representation of a linked list is a good choice. On today's machines that list chase might incur a sizeable cache stall, making it thousands or even tens of thousands of times slower.

Two: Lisp doesn't actually care whether there are literally linked lists behind everything. Today you would use a different data structure reflecting the hardware you have.

Not only today, since the mid-70's, yet somehow many keep thinking List only has lists.

> 1980s machines don't have the memory access performance you see today

They had similar problems. CPU with tiny caches <-> caches <-> expensive RAM in the range from 500kbytes to a few MB <-> virtual memory paging to slow disks.

For example a typical Lisp Machine might have had 20 MB RAM. But the Lisp image it ran was probably already much larger. Thus paging spaces upwards from 60 megabytes were not uncommon. I had a Lisp Machine with 40 MB RAM and have used > 200 MB paging space. Disks were very slow. Were are talking about ESDI (2.5 Mbyte/sec or less) interfaces or later 5-10 Mbyte/sec SCSI 1 and 2.

I had a 600MB ESDI disk inside a 1 MIPS Lisp Machine with 8 Megawords RAM of 36bit memory + 8 bit ECC.

Thus locality plaid an extremely large role for usable performance. In the early days machines had to be rebooted when they ran out of memory, since a garbage collection could take a long time. Rebooting a machine was just a few minutes. Doing a full GC over 200 MB virtual memory could take half an hour.

When I was making a new Lisp image (called a world), the size was upwards 50MB. 100 MB was common. A special command ran for roughly 30 minutes and reordered the objects in main memory to improve locality. The another command saved the image - which took also tens of minutes.

A big breakthrough in usability came with the introduction of the Ephemeral Garbage Collector, which only touched RAM and took care of the short lived objects, with some hardware support to identify and track RAM pages with changed content.

Features back then were:

* cdr coded lists which were allocated like vectors

* lots of other data structures like vectors, n-dimensional arrays, hashtables, records, objects, ...

* an ephemeral garbage collector with hardware support tracking changes in RAM pages

* incremental garbage collection

* a copying/compacting generational garbage collector with type sorted memory regions

* cooperation between the garbage collector and the virtual memory pager

* various manual or semi-manual memory management facilities

* incremental memory image saves

The main reason to develop Lisp Machines in the end 70s was to get Lisp development off of time-shared computers (with limited shared RAM and virtual memory) onto single user workstations, where RAM and virtual memory is not shared between different users.

The same problem appeared then on UNIX machines, where Lisp systems often were among the most memory hungry programs -> thus they needed lots of RAM, which was expensive. Thus a lot of virtual memory was used. But access to Lisp objects in virtual memory was much slower than Lisp objects in RAM. It took many years to have competitive GCs on those machines.

When RAM got more affordable and larger, things improved.

Cons can build a tree, though it can certainly build a list.

(a1 (b1 (c1 c2 c3) b2 (c4 c5)) a2 a3) is a tree.

No, only if you are speaking about the first implementations of LISP until LISP 1.5 and similar timeframe.

By the time Xerox, MIT, TI started delving into Lisp machines, the language had already gotten support for stack allocation, value types, arrays, structures (records).

Same applies to its big brother Scheme.

This is only a problem with implementation of linked lists. The article talks about how linked lists are conceptual. They make a nice data structure to work with in code. But several ways could easily be conceived of that optimize them so that elements are adjacent to each other.

Has there been any work on nudging the allocator towards putting all the nodes on the linked list on the same page? Or close together in memory more generally (to leverage the L1 & L2 caches)

If you're allocating the entire linked list at once, that may well happen in practice. Otherwise, there is no good way it can happen automatically; but, compacting GCs will usually do this for you (assuming that the list elements are only reachable from the previous element).

Interesting thanks!

Assuming rust or other systems language.

Linked lists are optimal for head access; not random access. For random access, yes a vector would be better.

I've always wondered why GSAP and CreateJS both rely on linked lists for sequencing animations

> almost always

As any generalization this one too is, of course, incorrect.

Outside of the realm of academia, the need to keep data pieces in several containers at the same time, with no heap operations on insertion or removal and O(1) removal is very common, especially in the kernel space and embedded contexts. The only option that fits the bill - you guessed it - are the linked lists.

Note that this (and the article) describes an intrusive linked list. Extrusive linked lists (like you might see in a class library or CS 101 project), where the node structure is heap-allocated separately from the data that it points to, have very few practical advantages over vectors, which is why standard libraries are increasingly defaulting to vectors even when the class is named "list".

Is there a difference between intrusive and extrusive list when the member type is a struct (value type)?

Yes. An intrusive list puts the pointers to next & prev in the struct itself. IntrusiveList<Member>::iterator is a Member*, then member->next points to another Member*. An extrusive list puts the pointers in a separate node structure, which then has a pointer to the actual member type. ExtrusiveList<Member>::iterator is a ExtrusiveListNode<Member>*, node->next points to another ExtrusiveListNode*, and you access the actual Member* with node->data. Basically it's a double indirection.

The advantage of extrusive linked lists is that you don't need to modify the data layout of Member at all. All the linked list manipulation happens on ListNodes, which have a pointer to the actual member, which can be accessed with just a cast. That's why they're so well-suited to class libraries: you can easily write a generic ExtrusiveLinkedList that works with any data that can be represented with a pointer, hide all the traversal (and the existence of individual ExtrusiveListNodes) in accessor functions, and present a simple API with no codegen or modifications to Member.

The advantages of intrusive linked lists are 1) performance 2) no heap allocations 3) easy traversal when given a Member*. It's only a single indirection rather than a double, and usually that indirection is necessary anyway to avoid copies. Insertion and deletion are just pointer manipulation; you don't need to allocate new space for the nodes. Oftentimes your functions will take Member* anyway, and it's nice not to take or traverse the container if you just need to peek at the next element coming up.

The point of this subthread is that intrusive linked lists have very clear use cases in the kernel & embedded spaces, where these advantages are often critical. Extrusive linked lists, however, have very few advantages over vectors (which also require heap allocation but are more cache & locality friendly). In a common business app responding to user input, the difference between O(1) amortized and O(1) is negligible; you can eat the occasional pause for a vector resizing, because the user isn't going to care about a few milliseconds. They both require heap allocation. The vector will give you much faster traversal, because subsequent reads all hit cache. The vector takes less memory (1 pointer per element, with a max of 50% overhead, while an extrusive doubly-linked list is 3 pointers per element). There's just little reason to use an extrusive linked list because the use-cases where intrusive linked lists are not better are precisely the same ones where vectors are better.

As any generalization this one too is, of course, incorrect.

In the real world of application development when choosing between Vector and LinkedList the answer is almost always Vector. There are, of course, certain problems where LinkedList is always the correct answer.

However for all problem that have chosen either Vector or LinkedList as their container of choice a super majority should choose Vector.

There are essentially no vectors in most of the embedded world, including RTOS. Why would you need that many extra copies of data?

Coopies are not free. Not in terms of stack, neither in terms of memory or its bandwidth. Both of which are in demand there.

For an example, look into how most of Zephyr RTOS is implemented. It's mostly intrusive lists (called queues there for some reason, but they support iteration) or ring buffers (msgq or mpsc_pbuf or pipe). For bigger systems you can use red-black trees.

There is no vector data structure, you can allocate a block from the heap and manage its size manually, but it's rarely done as most sizes are static and many data structures are preallocated by the bootloader or loaded directly from flash memory. Cache locality of these is of course possible to manipulate manually by use of memory sections.

A list does not copy by default, which is an extremely important performance characteristic. And it does not require overallocation like a vector of pointers, plus has a fast remove, especially at head or tail.

Extra copies, huh?

Feel free to replace the term “Vector” with “Contiguous Memory”. The relevant distinction in this conversation is “contiguous vs node pointers”. Embedded loves contiguous blocks.

A dynamic array copies memory if it regrows, inserts, removes. The cost of that operation depends on numerous factors. But it doesn’t result in “extra copies” laying around.

Oh wait maybe you mean array operations perform extra copies, not that they persist. In which case it comes down to which is more expensive: memcpy some bytes or cache inefficient pointer traversal.

It depends! But most problems for most programs are MUCH faster if they avoid LinkedList. Many people, especially new programmers, radically underestimate the penalty of pointer chasing.

> Embedded loves contiguous blocks.

Quite the opposite. When you have no dynamic allocations, vectors are out of the question, while pool of nodes is fine and sound.

And quite often you can't copy elements from one place to another in embedded or operating systems, since many consumers can store a pointer to this element. Of course this could be solved by usage of vector of pointers, but this completely ruins the ``cache locality'' argument.

> As any generalization this one too is, of course, incorrect.

His statement wasn't a generalization to repeating this back does not make sense.

Also, when in doubt, do a quick benchmark with different implementation.

by vector you mean regular js arrays?

Broadly yes, C++‘s vector is the equivalent of JS arrays.

But the javascript array type is much more complicated. It intelligently changes its internal structure based on how you use it - which is pretty wild.

nsarray (objective-c) also does something similar

https://news.ycombinator.com/item?id=2413656 (sadly the article link is dead)

Would you mind elaborating on js arrays intelligently changing their internal structure based on use? My background is only JS/Python and have never touched C++ so I don’t have the context of how these differ.

A c++ vector internally uses an array - which is a chunk of memory where each item is just in the next spot in memory in sequential order. Eg, the array [1,2,3] might have 1 at memory address 100, 2 at memory address 101 and 3 at memory address 102. Given an array index, you can figure out where a value is stored in memory pretty trivially.

When the array fills up, vector will allocate a fresh array (thats bigger - often 2x bigger) and copy everything over. This is slow - because it has to copy everything. But much faster than you think.

So thats how C++'s vector (and Rust's Vec) work.

Javascript implementations (like v8) can swap out the implementation behind the scenes based on how you're using your array. The API is always the same - but the way the array works in memory will be different based on whatever is fastest given the way you're using your array. (V8 doesn't know ahead of time what sort of data will be in your array or what you're using it for, so it guesses then changes things up if it guesses wrong).

Here's a blog post talking about some of the internal details in V8:

https://itnext.io/v8-deep-dives-understanding-array-internal...

The actual implementation is much more complex than this blog post suggests. (I think they also optimize based on push/pop vs shift/unshift vs other stuff).

Thanks for taking the time to write that up–I appreciate the explanation.

My only adjacent knowledge here was when I checked the V8 implementation of the `sort` method on the array prototype and saw it changes the sorting algorithm used based on array length (IIRC insertion sort for length < 10 and merge sort otherwise).

Thanks for the V8 resource as well.

I recommend James Micken’s JavaScript talk on this matter: https://m.youtube.com/watch?t=3m10s&v=D5xh0ZIEUOE

(Time stamped to the beginning of the arrays section)

Modern CPUs detect patterns of pointer chasing common in linked list use and prefetch to cache just fine. Your comment would have been valid a decade or more ago.

And plenty of use cases are much better with linked lists than resizable vectors. Eg: queues.

RAM latency is huge. No amount of prefetching can fix that. If anything, prefetching works better with arrays as RAM reads multiple bytes at once.

Queues are best implemented with a pow2 cyclic array, and you have a free deque, too.

A ring-buffer based queue is mostly better than a linked list but it is not necessarily the best. The typical STL deque implementation [1], with all its complexity, is usually faster than a ring buffer.

[1] https://stackoverflow.com/questions/6292332/what-really-is-a...

I think there's more to cache locality than prefetching. In an array, consecutive elements will be usually be adjacent in physical memory (excepting page boundaries ), so each cache line load where a cache line is larger than the array element will "overfetch" into the next element. This should mean fewer total cache loads and thus more efficient use of memory bandwidth for situations where it is constrained (such as walking a list).

Then again, if you have control over allocations you can prefetch whole chunks of data to which the list refers making this point moot.

Often lists refer to arrays or sections of memory. The performance loss if any appears in bigger structures where you do want to have explicit control anyway.

For most use cases a ring buffer either with or without a maximum length will do much better as a queue than a linked list will.

There are some niche use cases where linked lists are good. Lock-free queues are one, and another big set of use cases is where you need hard O(1) insert even with a high constant factor, not amortized O(1).

High-performance SPSC queues are always implemented with an array.

If you need hard O(1) insert you can usually just allocate an array much bigger than you will need. The combination of hard performance requirements and willingness to wait for an allocator all the time is unusual.

The place I see linked lists pop up the mosts are when implementing LRU caches. You need a linked hashmap of sorts where the hashmap gives O(1) lookup to the linked list node in question, and then you can extract that node and move it to the head of the queue in O(1) as well.

This is a special case of where they also appear: linked hashmap implementations, where you want a hashmap that has a consistent iteration order.

I’ve seen them show up in lots of situations through intrusive lists, which I think is the general form of the example you’re giving.

Intrusive lists are used in the Linux kernel, in physics engines (eg Chipmunk2d) and game engines. The way Redis uses them for TTL expiry follows the same pattern.

Having linked nodes of a hashmap, is just that - I'd not call it a linked list. You can do moving median with a binary tree and linked nodes, too.

>where you need hard O(1) insert even with a high constant factor

You will need a truly concurrent memory allocator for that, too... or if you are just the kernel (one of the reasons the linux kernel can benefit from linked lists)

Overall, allocating new objects/memory is not guaranteed O(1).

There are a lot of factors involved, but given a limited number of cache lines that can be stored in low level cache, I would think there'd be at least some performance penalty for prefetching from non-linear blocks of memory vs the inherent spatial locality in an array/vector, if only because it'd cause more old cache to be evicted.

Or the opposite, prefetching a whole vector when you just need one item, evicting more than needed unnecessarily.

There is a reason why non-embedded CPUs have sizable L2 caches now.

Queues are generally implemented with with a vector of pointers to vectors. Nicely diagrammed here https://stackoverflow.com/questions/6292332/what-really-is-a... Ring buffers also work better than linked lists

is Erlang and JDK general enough for you? Oh, both use linked lists,

https://github.com/erlang/otp/blob/master/lib/stdlib/src/que... https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...

why would your refer LinkedBlockingQueue? You have ArrayBlockingQueue, too. ArrayDeque is just better than LinkedList.

Even if your linked list is backed by an array and all the elements are right next to each other, computing some cheap function of the elements of a linked list is incredibly slow compared to the alternative because of the unnecessary and very long dependency chain.

Vectors are basically perfect for queues.

I'm going to call you out on this one, because it's a bold claim, and I'd love to see an explanation and some perf numbers.

For example, I'm wondering how the CPU knows what the next item in the list to prefetch it. Unlike the next item in an array, list items could be pointing anywhere in process memory.

Also, what counts as a modern CPU in this context? Are we talking latest generation desktop CPUs from Intel, or anything after Core 2 Duo? How about mobile devices with ARM CPUs? Would those just be ignored?

Is there a benchmark?

Feast your eyes on the "Intel® 64 and IA-32 Architectures Optimization Reference Manual": https://cdrdv2-public.intel.com/671488/248966_software_optim... (newer link, as requested by one of the child comments)

It details the prefetchers, how they work, what patterns they recognize (section 3.7)

My benchmarks say you’re wrong.

https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...

You're joking right?

"I made an extra test that wraps matrix4x4 in std::unique_ptr."

And that is your test? One piece of code? Not even presenting disassembly? Who the hell knows what your compiler wrought in response to your "std::unique_ptr" and "matrix4x4" ?

Sorry for my ignorance – linked list matching the performance of vector is something new to me. I would like to learn more. The best way to prove your point is to show us a benchmark. However, I couldn't find one with a quick google search.

Well I’ve provided 1 benchmark to your 0. I’d say I’m ahead.

My code benchmark is actually far more pre-fetch friendly than a LinkedList because it can prefetch more than one “node” at a time. In a LinkedList you can’t prefetch N+1 and N+2 at the same time because N+2 is dependent on the result of N+1.

I’m always open to learning new things. Modern compiler magic is deep and dark. If sometimes a compiler magically makes it fast and sometimes slow that’d be quite interesting! If you have any concrete examples I’d love to read them.

It doesn’t claim linked lists are fast. And it doesn’t have any benchmarking data.

Actually the only reference to linked lists I see is in the prefetcher section (3.7.3), where it explicitly recommends that consecutive items are stored in a single 4kb cache line or in consecutive cache lines. They give a positive code example using an array, like other commenters are suggesting.

It's a link to a document on architectures well over a decade old - the most recent mentioned is the original Core architecture (from 2008). Honestly, based on your first comment I thought you were implying something about content dependent prefetch or other techniques that I am familiar in the academic literature but unaware of ever being used in mainstream hardware.

> Organize the data so consecutive accesses can usually be found in the same 4-KByte page. > • Access the data in constant strides forward or backward IP Prefetcher. 3-72

> Method 2: >• Organize the data in consecutive lines. > • Access the data in increasing addresses, in sequential cache lines.

Nothing new here that contradicts the GPs skepticism. Certainly not enough evidence for you to be a dick.

yup, was link to old a document with same title. updated. thanks.

Ok, but the hardware data prefetch functionality seems basically unchanged:

"Characteristics of the hardware prefetcher are: • It requires some regularity in the data access patterns. — If a data access pattern has constant stride, hardware prefetching is effective if the access stride is less than half of the trigger distance of hardware prefetcher. — If the access stride is not constant, the automatic hardware prefetcher can mask memory latency if the strides of two successive cache misses are less than the trigger threshold distance (small- stride memory traffic). — The automatic hardware prefetcher is most effective if the strides of two successive cache misses remain less than the trigger threshold distance and close to 64 bytes."

Prefetching just one element ahead does fuck-all when ram is 100x slower than cache especially if you need to precharge and activate a new row which is always the case when you're spraying tiny objects all over the place.

So don't spray tiny objects around. :) Keep them nicely tucked away in an arena.

Vectors actually tend to create a spray of tiny objects... As opposed to a true dynamic array which has limitations in resize. If you're lucky, they will keep a single dynamic array per vector. You're usually not this lucky with bigger data.

If you never free your objects, you may as well use an array anyway - it'll be much more simple. And if you use an arena with an object pool, you're back in cache miss territory.

Vectors only "create a spray of tiny objects" if you have a vector-of-references or something like that. And even then, reading data requires 2 reads from memory (1 to read the pointer in the vector, and another to read the object). Finding item N in a linked list will require N reads (since you need to read each item before the target). Yes, resizing a vector is O(n). But every time I measure memcpy, it always goes faster than I expect.

If you disagree, try to prove it with code. At least one of us will learn something that way.

This is a great document that will absolutely confirm, in a number of ways, that linked lists are going to be terrible for prefetching.

That depends more on what they link to. Not prefetching a worthless list of pointers when you could prefetch data instead is typically faster. Prefetchers have limited capabilities and capacity for loads.

The prefetcher doesn't even have to get involved for linear sequences, it would only get involved after a cache miss threshold is met. The fastest and simplest prefetcher, L1, is stream based and will work great for sequential data.

Google for Intel hardware prefetcher and you'll turn up some info.

Re: benchmarks. Not likely exactly what you're looking for, but the GigaUpdates Per Second benchmark (https://en.wikipedia.org/wiki/Giga-updates_per_second) is sort of the most-pathological-case of pointer jumping where the jumps are random. Prefetchers don't do well with that (for obvious reasons) - they tend to work best when there is some pattern to the accesses. Linked data structures often live somewhere in between - they may start with good, regular stride patterns, but then over time as elements are added and moved around, it turns into a tangle of spaghetti.

Edit: I should add more. While prefetchers do exist in hardware, they're a bit of a murky subject. Sometimes they speed things up, sometimes they do so bad they slow everything down. They can be very workload dependent. And to top it off, hardware vendors can sometimes be a bit opaque when explaining what their prefetching hardware actually does well on. It's probably safest to not assume your hardware will help you when it comes to tangled pointer jumping code, and if you can avoid it via a different data structure it's probably good to do so. That said, other data structures may entail other tradeoffs - better cache usage for lookups, but potentially more expensive insertions. As usual with data structures, its a game of balancing tradeoffs.

I don't buy this.

https://www.youtube.com/watch?v=WDIkqP4JbkE

Prefetching in CPUs predates this talk.

https://www.youtube.com/watch?v=Nz9SiF0QVKY

That talk is 2018.

Cache prefetching works best for linear accesses like with a vector, not for random pointer lookups. Prefetchers are also going to have an extra harder time with double indirection since they're unable to see which value is going to be fed to the lea.

Prefetching is also expensive in and of itself, the CPU doesn't do it unless you're already incurring cache hits. This makes cache misses even worse. There are also multiple prefetchers in the CPU and the L1 prefetcher is very basic and is only going to help with contiguous accesses. Your allocator might be doing some nice things for you that let the one of the L2 prefetchers help, I would expect that you'll see better L2 performance due to prefetching.

If you have an example of a linked list being as fast as a vector for iteration, please do show it.

... I didn't say it was for random pointer lookups. That's the pathological case that was the primary reason the Cray X-MT (formerly Tera MTA) was invented. As I said, when you have pointers with some regularity (hence my reference to regular or patterned striding), then you may get some benefit of prefetching when you're not just dealing with linear contiguous access. The "may" is important there - whether you do or don't get it is workload / data dependent. As I also said, more likely than not over time the data structure will lose regularity as pointers get re-wired, and the benefits of prefetching go out the window.

I'm not sure what you "don't buy" - I didn't say definitively that prefetching does or does not always help. Sometimes it does, and when it does, it's highly dependent on the regularity of the way the pointers cause you to stride through memory. I even basically agreed with you -- to quote me, "It's probably safest to not assume your hardware will help you when it comes to tangled pointer jumping code". You appear to want to argue for some reason.

how do linked lists fit the regularity requirement? the only regularity in this pattern of access is the offset at which the next address to fetch is stored. this seems like a nontrivial amount of logic and state for the prefetcher to keep track of, unlike something like base * scale + offset when e.g. traversing a 2d array.

It is more complex for hardware to keep track of for sure. It's been a feature of high performance cores for more than a decade though. Kernels tend to be based off of linked lists, so it's a massive win typically.

A bunch of people keep saying this with no substantiation - the best we saw was a link to the latest Intel optimization manual that quite specifically refutes this claim. I even quoted it upthread.

Do you have anything substantial to add to that?

I'm sure CPUs will try their best to optimize these usage patterns. But I suspect vector / array based approaches will still always outcompete linked lists in actual benchmarks.

Thats always been my experience of them.

Linked lists still show up in the kernel, in redis, in game engines and so on because you can't build fast intrusive collections using arrays.

Making linked lists "as fast as we can make them" doesn't mean they're competitive with a vector.

Look, people who are excited about this and just want to learn are asking for proof. You can't just make a claim like "it's been a feature of high performance for more a decade" and provide 0 evidence for the claim, because it's not common knowledge and explicitly contradicts what is commonly taught.

I can time how long it takes to iterate through an array and show that it is faster than iterating through a linked list with the same number of elements.

Now, what optimization would I have to impleemnt to end up with a program that iterates through this linked list faster than the equivalent array?

> As I said, when you have pointers with some regularity (hence my reference to regular or patterned striding), then you may get some benefit of prefetching when you're not just dealing with linear contiguous access.

I would need a source to believe this. The only way I can imagine this working is that the L2 prefetcher might incidentally work well with your allocator - your allocator might try to hand out more or less colocated or evenly strided data.

> I'm not sure what you "don't buy"

This statement, primarily:

> Modern CPUs detect patterns of pointer chasing common in linked list use and prefetch to cache just fine

To me, this statement reads as:

1. Prefetchers in CPUs can prefetch data by examining loads that have yet to be executed

2. That they do this well, or at least that's how I read "just fine"

To my knowledge neither of those is true.

> You appear to want to argue for some reason.

I'm not trying to argue at all, I'm trying to learn. What you're saying does not sound right to be but it would be extremely interesting to me if I learned that CPUs are doing something that I'm not aware of.

If you're actually saying that an allocator may end up striding allocations such that the prefetcher can reliably predict where to load next, sure I'll buy that, at least for L2. That's a fine thing to say, it just isn't what I took away from your initial statement, which is what I wanted to drill into because, again, it would be very interesting to me.

Sorry if I'm coming off as argumentative, I was rushing that previous comment, which isn't really fair to put on you. I genuinely just am curious and if this is a case of miscommunication, no worries at all. I'd just be remiss if I didn't try to suss out if I'm wrong.

Apple's M1 has a data dependent prefetcher (superset form of pointer chase prefetcher), as discovered by the researchers behind the Augury paper [1]. They discuss how it works, how and when it activates, as well as a couple other cool details which should more than answer your curiosity. They don't have benchmarks for performance, but these sorts of prefetchers do exist (and possible in hardware you're using right now!).

[1] https://www.prefetchers.info/augury.pdf

The prefetcher described in the paper implemented in the M1 is nowhere near a prefetcher that would be able to prefetched linked-list nodes.

> We tested for the existence of four DMPs: both single- and two-level versions of pointer-chasing and indirection-based DMPs (Section IV). Our findings show the existence of a single-level pointer-chasing DMP....

When activated, the prefetcher described will also issue loads for pointers in a contiguous array of pointers. In particular, the pointer/addresses are already known by the core (because they themselves were presumably prefetched far ahead of time by the stream/stride prefetcher), so the core knows which addresses to prefetch. But in a linked-list, the address of the next node is not known by the core until after the node is retrieved from memory. I.e. there is an additional data dependency, and it takes a round trip to memory to resolve that data dependency.

It's the difference between prefetching B's in

  A0  A1  A2  A3  A4
  v   v   v   v   v
  B0  B1  B2  B3  B4

and prefetching B, C, D, E in

  A -> B -> C -> D -> E

The former is much easier to do than the latter as 1) the A's are easy to prefetch, and 2) the B's can be fetched in parallel. In the second, the core has to wait until B resolves before it can fetch C, and it has to wait until C resolves before it can fetch D, etc.

I have some experience using/modifying linked-list benchmarks (https://github.com/google/multichase) specifically to test memory latency.

It is extremely difficult, maybe impossible, to design a prefetcher that can predict the next cacheline(s) to prefetch while traversing in a linked-list. I am not aware of a single CPU that can do this consistently. For instance, if you run multichase (a linked-list chaser) on GCP servers, you generally get the expected memory latency (~70-100ns, depending on the platform).

Why let the CPU guess when you can tell it what you want? (Prefetch a small arena of objects linked to by the list.)

Even with a perfect prefercher a linked list would still be slower to iterate than a vector as it is inherently serial (unless your CPU does address prediction and I don't think any CPU does).

Reply on news.ycombinator.com