In defense of linked lists
antirez.com
antirez.com
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.
And plenty of use cases are much better with linked lists than resizable vectors. Eg: queues.
[1] https://stackoverflow.com/questions/6292332/what-really-is-a...
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.
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).
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.
This is a special case of where they also appear: linked hashmap implementations, where you want a hashmap that has a consistent iteration order.
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.
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 is a reason why non-embedded CPUs have sizable L2 caches now.
https://github.com/erlang/otp/blob/master/lib/stdlib/src/que... https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...
Vectors are basically perfect for queues.
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?
It details the prefetchers, how they work, what patterns they recognize (section 3.7)
https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...
"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" ?
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.
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.
> 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.
"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."
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.
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.
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.
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'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.
Do you have anything substantial to add to that?
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.
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?
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.
> 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
A -> B -> C -> D -> E
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).
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.
Do you have some benchmarks demonstrating your claim?
> ...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.
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.
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.
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.
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.
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.
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.
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.
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.
His statement wasn't a generalization to repeating this back does not make sense.
A standard ring buffer does copies/fill. A ring buffer of pointers has similar performance characteristics to a linked list.
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.
I'd prefer saying LMAX is / was used as the core of high frequency trading applications.
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.
https://news.ycombinator.com/item?id=2413656 (sadly the article link is dead)
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).
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.
(Time stamped to the beginning of the arrays section)
In any case, there is always only one authoritative answer: “perf top”. :)
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.
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.
often they're sufficiently maximal.
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.
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.
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).
You can reorder and modify the contents of the list without losing locality.
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.
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...
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.
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.
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".
So if you have a small data structure and/or large cache, and the key is not complicated.
Linear search generally does outperform for small collections though (it’s better for caches and the branch predictor).
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.
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?
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.
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.
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?
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.
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.
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.
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 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.
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.
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.)
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?
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...
And the solution to "pointers to elements of a vector going bad" is don't save pointers to elements of a vector.
Kinda weird how rare it seems to be.
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.
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.
[1] https://hypirion.com/musings/understanding-persistent-vector...
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.
From the article https://github.com/dtrebilco/Taren/blob/master/Articles/Eras...
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.
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.
(a1 (b1 (c1 c2 c3) b2 (c4 c5)) a2 a3) is a tree.
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.
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.
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.
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.
Added to my /lisp/ directory for when I inevitably realise I've forgotten where I saw it :D
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).
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?
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.
https://github.com/samsquire/btree
I tried to keep the implementation as simple as I could.
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.
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.
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.
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.
That's a strange take. Surely games still represent a significant chunk of the demand for C++ developers that need to care about performance?
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.
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.
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. :-)
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 :-)
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:
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.
Edit: Let's call it "memoveouttamyway"
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...
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.
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.
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?
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)
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.
> 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?
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.
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).
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 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.
The only problem is that use cases evolve, and what was fine suddenly isn't, anymore.
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.
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.
Exactly my point: such access patterns exist.
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".
In fact, on modern architectures it may be faster to iterate over arrays just to take advantage of l2/l3 behaviors.
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.
Designing for embedded is not the same thing as being lean.
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).
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.
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).
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.
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).
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.
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.
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.
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.
// LinkedListItem[k]: item[k], prev[k], next[k]
std::vector<T> item;
std::vector<uint> prev;
std::vector<uint> next;
Linked lists are optimal for head access; not random access. For random access, yes a vector would be better.
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.
The blog post is short, and I think the author covered about everything.
Yeah, linked lists are sometimes appropriate, especially intrusive linked lists (the author called them "embedded" linked lists). The hate they get is a backlash against CS programs that introduce people to them early and don't emphasize enough the reasons you should usually pick something else. If we have to err on one side or the other, I'd rather it be telling people not to use them.
btw:
> Redis can be wrong, but both Redis and the Linux kernel can’t.
Yes, they can, and I'd rather avoid argument from authority altogether.
So I don't think it's a particularly enlightened decision by these projects to use so many lists on their merit, but rather a programming pattern especially common in the C language they use.
I still prefer to evaluate each decision on its merits. Linux has made some great decisions. Also some terrible ones—e.g. fsync semantics [1], attitude to fuzzing. Redis probably has too. They can agree on something and be wrong.
This means that you can do those things under a spin lock or with interrupts masked. You cannot really resize a dynamic array under a tight spinlock, or modify a tree that should be kept balanced.
Another use case is free lists, a list of preallocated structures where you can grab one or put one back quickly under spinlock.
These are some examples of how lists are used in kernel land.
Vecdeque can cheaply pop/push front and end too. Arrays have swap-remove. You may not need to grow if you preallocated a capacity. Freelists can be a stack, or you can choose a data structure that doesn't allocate objects individually so you don't need the freelist in the first place.
Another thing that is C-specific is that most objects are treated as unmovable and their address is their permanent identity. Without language features for prevention of dangling pointers, moves are asking for trouble. This favors linked lists and pointery data structures over contiguous containers and inlined data.
Proof by authority is the worst. Yet, linux kernel can have valid reasons for, but they are intrusive lists with the data having a pointer to the next.
> Yes, they can, and I'd rather avoid argument from authority altogether.
Pretty sure that was a joke, considering the overall light-heartedness of the whole post.
You almost always want to unroll your linked linked lists, so that items are fetched in blocks. But this rarely happens in C because it’s premature optimization in C. In C++ or Rust you can write the code once in a generic data structure and enjoy the benefits to the end of time.
That all said, I think we should still teach them in CS because understanding linked lists is the first step to understanding trees.
One example would be if your thread structure has these embedded pointers, you can easily add/remove a thread to a linked list of threads waiting for some resource without any allocation just by pointer manipulation.
I did it only for compatibility and would still prefer vectors whenever I can use them. Nevertheless, I put some efforts into coming up with a useful and high-performing implementation. To give an example: My `append` function is O(1) and not a poor O(N) version that you rightfully criticized in your tweet.
[1] https://colinfinck.de/posts/nt-list-windows-linked-lists-in-... [2] https://www.youtube.com/watch?v=IxhZIyXOIw8
If you have a standalone linked list data structure, then you can, as long as you have a good means of tracking the lifetime of the data itself.
The same list entry can be moved between several lists using the same type.
If the struct need to be in multiple lists in the same time you can keep multiple list entries in the same struct: https://github.com/freebsd/freebsd-src/blob/69413598d2660054...
If you combine intrusive linking with a pool allocator, you can have decent locality too.
Scrubbing through things quickly is empirically more common, hence the standard advice to use vectors by default.
But yeah, I understand they took the task struct out of the kernel stack now.
Edit: difficult being an understatement, you'd need to solve the halting problem to be able to rewrite any self-referential pointers to stack objects wherever they may be.
An array/stack can be made multithreaded but it is non-trivial to handle the edge-cases. In particular, the ABA problem is rather difficult. I've seen many solutions to it (ex: a synchronization variable that puts the stack into "push-only" mode and then "pop-only" mode. There's no ABA-problem if all threads are pushing!)
However, pushing/popping from a Linked List stack requires no such synchronization at all. Simply compare-and-swap the head (and on failure, try again). Its about as simple as you can get when it comes to atomic / lock free patterns.
It doesn't help with ABA at all, does it? Unless you assume that nodes are immutable and the same pointer is never reused, of course.
Still, that's easily solved: 64-bit version number + 64-bit pointer (or 32-bit version number + 32-bit pointer) for a 128-bit (or 64-bit) compare-and-swap.
All modern CPUs support 128-bit CAS.
EDIT: The version number is incremented by +1 each time. It is unlikely that you'd overflow 64-bit version number and risk an ABA problem, though 32-bits can be overflowed surprisingly quickly in today's computers.
--------
EDIT2: Note: I'm pretty sure (but not 100% sure) that the Head of a linked-list stack can be "simply" compared-and-swapped to remain lock-free and 100% valid (ie: 64-bit compare and swap over the 64-bit pointer). I did not mean to imply that you can "CAS any arbitrary node of a linked-list". A fully generic linked list is possible and I've seen it with the 128-bit CAS operator, but that wasn't what I was going for originally.
No, you cannot. The problem is what you're comparing and swapping into the head during a pop. You want to do the moral equivalent of `current = list; list.compare_exchange(current, current->next)`, but current->next might have changed if someone else popped the original head, pushed something else, and then pushed the original head again.
You need double CAS or LL/SC or a more complicated scheme to make this work.
That's obscure but it looks like you're correct in this case.
I think some Intel chips have 57-bit support. But no CPU actually reads all 64-bits for some reason.
So yeah, you can shove count-bits, either 16 of them or 7 of them or so.
https://github.com/google/re2j/blob/dc7d6e5d41225dc0825ea6fe...
Java doesn't suffer from pointer address ABA but I did have to handle reinsertion (except when the stack had only one element).
However I have a fun use for linked lists where this is NOT true.
Anyone who has played around with algorithms has encountered dynamic programming. So you can, for example, find the count of subsets that sum to a particular number without actually enumerating them all. But what if instead of counting them, you wanted to actually find some?
The answer turns out to be that instead of using dynamic programming to get a count, you use dynamic programming to build up a data structure from which you can get the answer. And the right data structure to use turns out to be...a type of linked list! There is no faster array equivalent for what you get.
In other words, with a few extra fields for clarity, here is the basic structure for subset sum of positive integers:
{
current_sum: ...,
count_of_solutions: ...,
current_value: ...,
solutions_using_current_value: (link in one dim of linked list),
solutions_using_previous_values: (link on other dim of linked list),
}
> find the count of subsets that sum to a particular number without actually enumerating them all.
Would the generating formula for partition numbers[0] work, or am I misunderstanding this problem?
(I think actually generating the subsets is necessarily a dynamic programming problem...)
[0] https://en.wikipedia.org/wiki/Partition_(number_theory)#:~:t...
Given a particular set, the question is enumerating the subsets that add to a particular thing. The fact that numbers themselves could be represented as a linked list has nothing to do with it. And there is no particularly useful generating function to use either.
For example there are 303 primes less than 2000, and 47,839,398,752,301 subsets of them add up to 2000. If you arrange them in lexicographic order, what is the 5 trillionth one?
And the first feedback is why so many unsafe blocks? What is it Option<NonNull<Node<T>>> ? '_ ?
Another reason to share, if you can understand Linkedin List, you are free to code in Rust ;)
Conceptually, the list as a vague concept owns all the nodes. The ownership just stops being expressible directly through references the way Rust wants it to be. But you don't have to re-invent hierarchical ownership to implement DLLs in other languages, because it's not really there in the problem. You just have to accept that they're always going to suck under Rust's ownership model.
The usual complaints are that "Safe Rust doesn't let you do this", when unsafe Rust is right there to let you operate on any soup of pointers datastructure that you'd want to implement.
> you don't really need either ref counting (again, pretty obviously, witness every real world implementation)
If you implement DDL in a memory managed language, you effectively have the same behavior as you would in Rust with Arc or Rc. The ownership of the nodes then belongs to the GC or the RC value. You don't have to think about it because you're abstracted from the lifetime of each node by the language and runtime.
> or hierarchical ownership outside Rust
The ownership/borrow checker requires hierarchical to operate, but it doesn't stop you from writing unsafe Rust.
> Conceptually, the list as a vague concept owns all the nodes. The ownership just stops being expressible directly through references the way Rust wants it to be. But you don't have to re-invent hierarchical ownership to implement DLLs in other languages, because it's not really there in the problem. You just have to accept that they're always going to suck under Rust's ownership model.
Yeah, and that's what unsafe is for. Most code doesn't need vague ownership, though. I'd go as far as saying that the nudge towards clear ownership helps both maintainability and performance.
My concern is with the prevalence of this idea that unsafe Rust is not "real Rust" or that the existence and use of unsafe Rust somehow precludes any benefits of Rust.
What you do instead is use integers instead of pointers. The integers are indexes into a Vec of list nodes, owned by the linked list. Since the nodes are now owned only by the Vec, which is in turn owned only by the linked list, the borrow checker will not complain.
Some people object that this is cheating somehow, but what is memory but a giant untyped global vector, shared between all parts of your application? Pointers into that giant shared array are just indexes with extra risk, since you have to trust that they point to real nodes that have been initialized. Plus, you often see users of a linked list put the nodes into an arena allocator anyway, especially in the kernel. The Vec in your Rust implementation serves the same purpose as the arena allocator.
That's pretty important actually. I'd say it's a qualitative difference. :) But yeah, arenas are great.
[1]: https://rust-unofficial.github.io/too-many-lists/sixth.html
This is a great resource that outlines several different strategies for implementing linked lists in Rust: https://rust-unofficial.github.io/too-many-lists/
As for the unsafety, I would assume the authors of collections know what they are doing and do that for performance.
The latter is easier to type but worse in almost every way. Ergonomics should guide you to the former, not the latter.
I suppose one problem with this approach for C FFI is that there's a lot of different values which could all be "null pointers". Converting them all for Option would be awkward and slow, and you wouldn't want to ever risk getting this stuff wrong.
But pointers are also useful even if you aren't doing FFI. Eg for implementing custom data structures. In that case, Option<NonNull<T>> (Or even NonNull<T>) is usually better than *mut T. But its harder to type, and it doesn't clearly tell you if the pointer should be *mut T or *const T. NonNull<T> should be preferred because security/safety is at stake for this sort of code.
> Rust guarantees to optimize the following types T such that Option<T> has the same size as T:
> - Box<U>
> - &U
> - &mut U
> - fn, extern "C" fn1
> - num::NonZero*
> - ptr::NonNull<U>
> - #[repr(transparent)] struct around one of the types in this list.
> This is called the “null pointer optimization” or NPO.
> It is further guaranteed that, for the cases above, one can mem::transmute from all valid values of T to Option<T> and from Some::<T>(_) to T (but transmuting None::<T> to T is undefined behaviour).
Although I'm not sure if the ABI is guaranteed to match (Which could differ even if the layout matches AFAIK). The ABI for Box is guaranteed to match since https://blog.rust-lang.org/2020/01/30/Rust-1.41.0.html , and I would imagine NonNull is the same. Maybe you could open an issue in the UCG asking if you're needing confirmation.
As for the Option type, it is exactly what it says. It's an optional, non-nullable node generic over type T. I suppose generics, optionals and the idea of non-nullable types might be exotic at first, but this is not a problem with Rust as much as it's a problem with C not being able to express these concepts in the first place and instead expecting you to spray null checks all over the place!
And regardless, this book is teaching from the perspective of intentional super-hard-mode. Most Rust developers will never have to write that much unsafe code.
I guess there’s plenty of space in the world for PHP programmers and their predecessors, the VB programmers. So… congrats?
Learn Rust with entirely too many linked lists (2019) - https://news.ycombinator.com/item?id=22390662 - https://rust-unofficial.github.io/too-many-lists/index.html
In this series I will teach you basic and advanced Rust programming entirely by having you implement 6 linked lists. In doing so, you should learn:
- The following pointer types: &, &mut, Box, Rc, Arc, const, mut, NonNull(?)
- Ownership, borrowing, inherited mutability, interior mutability, Copy
- All The Keywords: struct, enum, fn, pub, impl, use, ...
- Pattern matching, generics, destructors
- Testing, installing new toolchains, using miri
- Unsafe Rust: raw pointers, aliasing, stacked borrows, UnsafeCell, variance
You're acting like it's some epic burn on Rust that there's some ugly code in its stdlib. It's not. Stdlibs are like that. Furthermore, as others have pointed out, linked lists in particular are a pathological case for Rust, meaning you're pointing and snickering at a special case of a special case. Most people never have to write or look at that kind of code.
There are reasonable arguments to be had about Rust. I wish people would do those instead of all the nonsense you usually see.
Rust is not perfect. I wont go into its faults, but you know what they are. I think overall, Rust is a great language, but you have to be realistic and understand that some stuff you ignore in favor of the holistic view, others might not be able to. So sometimes maybe just take the criticism and deal with it, or if you're in the position, do something to fix the problem.
> I wish people would do those instead of all the nonsense you usually see
you seem to want to place the blame squarely on the critics, when the reality is that many people in your position are seemingly intolerant of any criticism of "their thing", even constructive criticism.
This isn't the best solution for all cases! Sometimes performance is more important than safety, and there are things you can't do as efficiently without mutable data. And sometimes (especially for systems that are reactive rather than transformational, in Harel and Pnueli's terms, or for libraries) a garbage collector is an unacceptable cost.
And Rust is actually reasonably good at singly-linked lists; it's just doubly-linked lists (which inherently feature mutation) that are troublesome. Singly-linked lists with sharing through Arc are a little more expensive in Rust than in something like GHC, Ikarus Scheme, or OCaml, but that's hardly a damning criticism of Rust.
But you seem to be claiming that linked lists are unsafe in any language, and to anyone familiar with functional programming, that claim is obvious nonsense. Did you intend it?
I would think that the implicit context for safety comparisons with Rust would be other languages designed with safety as a goal. Those languages are almost all GCed! ML, Haskell, Scheme, Oberon, Coq, Erlang — all GCed. That's because GC helps enormously with type- and memory-safety. In the example in question, it ensures that your doubly-linked list manipulation cannot cause undetected type errors, use-after-free errors, double-free errors, or memory leaks; this last guarantee goes beyond what Rust can offer in this case. In ML, Haskell, and Oberon, it even ensures that all type errors are detected at compile time instead of run time.
There are a few languages designed with safety as a goal that do not normally use GC: Pascal, Ada, COBOL, and MISRA C. But they suffer enormously in expressivity, are not pointer-heavy, and are generally only viable alternatives in restricted domains.
The usual pointer-heavy non-GC languages are C and C++, and these have no concern whatsoever for safety, so it seems like a weak-man argument to target linked-list manipulation in them as unsafe relative to Rust.
The correctness criteria for doubly-linked lists are indeed not within the capability of Rust's (or Haskell's, or ML's, or Oberon's) static checking. That doesn't imply that it's impossible to statically verify doubly-linked-list manipulation code, and in fact I think Ada SPARK is capable of doing it. Certainly it's within the scope of what you can prove with Coq or Isabelle/HOL.
We're deep into semantics territory with "what's the right context for comparing Rust", but I would strongly argue that yet another language safe via GC is not interesting for its safety. As you point out, it's been done a lot. Rust is interesting because it pushes safety into a new level of runtime performance and (to some extent) lower hardware abstraction. AIUI that's the motivation for Rust, where most of the marketing and enthusiasm is, etc. And if you don't need that speed/control, Rust isn't much of an improvement: just use a GC and have more fun (unless you just think Rust is neat, I guess, but whatever).
So it's the languages already in that "low level" domain (broadly defined) that are its real competition IMO, C/C++, upstarts like Zig/Nim/Crystal, etc, languages where linked lists are on the cards. Especially for the problems where safety has previously been seen as too costly in either runtime or development time (no one is coding to fast moving web standards in Ada/SPARK, methinks).
And I don't think I implied that those languages' list manipulation is less safe than Rust's, rather that Rust's isn't any worse, besides being uglier. I made almost the same point from the other direction in another sub-thread: there's no use denying that Rust code for DLL's is uglier for no safety benefit on that particular task.
As others have pointed out, the whole question of linked lists in Rust is a huge distraction from its actual benefits and weaknesses.
I think it's noteworthy that, not only in the doubly-linked-list case but even in cases that use Arc (which doesn't require `unsafe`), Rust is less safe than mainstream GCed languages like Java (and arguably Haskell and OCaml). Rust can leak memory; those other languages can't. Its safety guarantees in those cases are a proper subset of theirs.
Unless I'm misunderstanding the situation? I've only written very small amounts of Rust.
Re safety: Rust has, um, a very specific idea of what "safety" means. It's basically things that could cause RCE, or at least incorrect writes I guess. Memory leaks are specifically not considered "unsafe". :) And really, the worst you can do with a memory leak is DoS, until the target reboots. Handling mutable data across threads is included, though, which Java at least is somewhat famously not great at; it's really easy to write Baby's First Race Condition Demo in Java. So it feels really weird to say Rust's safety guarantees are a strict subset of Java's.
OTOH I agree it's hard to imagine Rust beating out Haskell for raw safety guarantees by any measure, and I have no idea for OCaml (despite having written a lot more Ocaml, heh).
This LinkedList obsession is a bit bizarre to me, and tends to come from older programmers who come from a time when coding interviews involved writing linked lists and balancing b-trees. To me though it also represents the stubbornness of C programmers who refuse to consider things like growable vectors a solved problem. My reaction to the LinkedList coders is not "well Rust needs to maintain ownership", its why does your benchmark for how easy a language is involve how easy it is to fuck around with raw pointers?.
LinkedLists are a tool, but to C programmers that are an invaluable fundamental building block that shows up early in any C programmers education due to how simple they are to implement and the wide range of use cases they can be used for. But they are technically an unsafe data structure and if you willing to let some of that stubbornness go and finally accept some guard rails, you have to be able to see that a data structure like linkedlists will be harder to implement.
It has nothing to do with the language; implementing with LinkedLists with any sort of guardrails adds a ton of complexity, either up front (e.g. borrowchecker) or behind the scenes (e.g. a garbage collector). When you accept this fact, it becomes ludicrous to imply that a LinkedList implementation is a good benchmark for the ergonomics of a language like Rust.
https://github.com/llvm-mirror/libcxx/blob/master/include/li...
And this is with several years cpp experience, and maybe a few months of Rust on and off.
Having said that - yes, it's not pretty. About the same length though.
https://github.com/rust-lang/rust/pull/103093/files#diff-8bd...
is the "In" in "LinkedIn" deliberate here or just a typo that was made twice?
The race is on: now you have two lists when before you had one?
Cdr coding [0] solves several problems with singly-linked (cons-style) lists including cache locality and the 2x storage overhead of these lists. But it's not typically used except in dedicated hardware e.g. Lisp machines. It could in principle be revived fairly easily on modern 64-bit Lisp systems on stock hardware -- especially if such systems provided immutable cons cells.
But it's probably not worthwhile because modern Lisp programmers (in Common Lisp at least) don't use lists all that much. CL has very nice adjustable arrays and hash tables that are easier and faster than lists for most purposes.
Before having gigantic caches that would engulf nearly any sized contiguous list, linked lists were sort of vogue, frugal, and thought of as being fairly performant.
Why bother? Because I can then easily add a few extra structs to the beginning of the (contiguously-allocated) linked-list without having to reallocate the whole thing.
Sure, pointer chasing with separately allocated structs is "slow", but I haven't yet measured to see if it's any different when (almost all) items are contiguous.
If you would... - what sort of cache behavior should one expect of this on a modern laptop CPU? - I haven't seen this approach before, have you?
It seems to me it's a super-handy way of "modifying" a compiler-allocated array of structs. I'm sticking with it!
The problem then becomes that I can't introduce NOT gates anywhere in a cycle, because then the bit will continue flipping and I'll get an infinite processing loop.
So it seems my only hope is external processes that continually walk the graph and keep track of where it visited to try and detect loops, and I don't like how that scales...
If the turtle and hare ever meet, you have a cycle. Otherwise, if the hare reaches the end of the list, you don't have a cycle.
Another notable advantage of Brent's algorithm is that it automatically finds the cycle length, rather than (in Floyd's case) any multiple of the cycle length.
https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algori...
Cycle detection in (currently) 44 languages. Most (all?) use Brent's algorithm. They're operating on an iterated function but converting most of these to detect cycles in a linked list would be straightforward.
Step through the list by one element per iteration with one of them, and with the other, step every other iteration.
If the two pointers are ever again equal you've found a cycle.
If you hit end of list, no cycle.
Or to save the comparisons make the thing the first node points to have a stop flag of some sort.
Head -> Node1 -> Node2 -> Node3
^ |
+-----------------+
To be clear, http://trout.me.uk/gc/recycler-overview.pdf
There's also a paper with the full algorithm in that directory.
It's how Nim's ORC collector works.
(note that yes, I know, this is for collection, not cycle detection in general, but it's also brilliant and works)
The paper's a really enjoyable read, Knuth's tone throughout is "look at this, this is fun"
The other time allocations are undesirable, and therefore linked lists are widely-used, is bare metal work when other allocators just aren't available. You can do tricks like representing pools of free and in-use objects with two lists where the nodes occupy the same memory block. Allocations are a fast O(1) unlink from the free list and O(1) re-link to the used list, and frees are the opposite.
Like any tool, it has its place. As long as you're not traversing large linked lists, they're probably fine.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nodepointer = None
Where linked lists really seem to come into play is with custom manual memory allocators in embedded programming, something of a niche subject.
Not unless you manually disable gc.
https://docs.python.org/3/library/gc.html
"Since the collector supplements the reference counting already used in Python, you can disable the collector if you are sure your program does not create reference cycles"
That said, conceptually, linked items are everywhere; such that you can easily find how to list things following the links. You probably just don't bother keeping that in a "List" structure in your code.
Funny, as I constantly have to tell folks to not bother using it at the office. Everyone always assumes it has to be faster than arraylist for whatever they happen to be doing this time. I think the vast majority of the time it flat doesn't matter, but I also fully expect LinkedList will lose most speed tests.
The main issue w/ the LinkedList is its memory footprint (aside being LinkedList w/ an indirection on each access), along with the increased GC costs (the GC has to iterate the nodes too, cache misses - gc pauses), even half empty ArrayList is more memory friendly than any LinkedList. ArrayDeque offers 'adds' at the both ends, if you wish to use LinkedList as a queue.
Fundamentally though the problem is that the LinkedList implementation is at odds with the abstraction provided by List -- access by index.
Certainly, straight iteration of every element is better done by a for-each loop (which uses an Iterator under the covers). But the availability of indexed access leads one to use it for a variety of additional circumstances. Consider for example processing every even-numbered element, or finding an element that meets some criterion and then operating on an adjacent element. Iterating over indexes for cases like these is quite natural given the List API. (ListIterator can be used for this sort of stuff, but it's quite cumbersome, and sometimes it doesn't actually help.)
In practice, it seems unusual for it to have any advantages over just using an ArrayList in typical JVM applications.
This ignores constant factors and cache coherency, of course. More, it also ignores that most lists that folks will make have a VERY predictable access pattern. Typically just a one way scan, if any traversal at all. With very few inserts, and mostly just appending.
(See https://rcoh.me/posts/rust-linked-list-basically-impossible/ )
To save face, the Rust astroturfers are now skipping around saying "Linked lists aren't important"
"Nobody uses this data structure stuff in real programming at work! You can forget it after college!"
https://github.com/tigerbeetledb/tigerbeetle/blob/main/src/f...
The second problem is Linked Lists are taught too early. They’re historically taught first in Data Structures 101. This results in new programmers using LinkedLists first when they should be used last.
The bad thing is that their cost nis ot obvious and not consistent (difficult to predict).
I tend prefer simple arrays.
This talk by Mike Acton is a good introduction to understand why going for the linked list as go-to data structure can lead to performance issues.
- You can certainly implement linked lists using dynamic arrays, so you call the minimal amount of `malloc()`s and also make your items stored contiguously! You need to use indices instead of pointers, since you will lose pointer stability unless you use virtual memory (though the upside is that typically a uint32_t is enough for most cases, which only takes up half as much memory as a pointer).
- A lot of data structures under the hood uses linked lists, even the ones that seem to use dynamic arrays on the surface. Have experience in writing a simple arena allocator? For the allocator to find a free space in the arena in O(1), you need to maintain a free-list data structure under the hood. And guess what: you need to write a linked list. Even your operating systems' `malloc()` itself probably uses linked lists under the hood.
- Linked lists just come up inside so many other data structures, that you can essentially call it as the 'backbone'. For example: in compute graphics there is something called a half-edge data structure [0], which stores the geometry data of a mesh that's both compact, easy to iterate, and easy to do manipulations with (for instance, you can do things like insert/delete an edge/face easily in O(1) time, and more complex mesh operations can be implemented as well). And guess what? The vertices and halfedges are essentially stored in a complex web of linked lists.
[0] https://jerryyin.info/geometry-processing-algorithms/half-ed...
Tongue-in-cheek, but this really made me smile. :-)
I don't think beginners actually make this connection for a while. Linked Lists are introduced analogously to arrays, sets, etc. Beginners think about Linked Lists in terms of what they already know.
As a beginner, I thought of Linked Lists purely as non-contiguous arrays, even though there are deeper concepts behind them.
Unless the beginners already have the perspective of "same having the power as the whole", I don't think this connection gets made for a while. Linked Lists don't expose so much possibility on their own.
You mean the people that all just got fired?
In Java particularly the both array as well as the linked implementation of blocking queues should perform equally well. FWIW most queue implementations are linked lists.
Java's queues and global threadpool queues in general are pretty old hat.
A few years later I discovered Perl that comes with dynamic size lists, dictionaries and strings. Whoa, that was a treat, so very nice to use and efficient. To this day I prefer constructs made of lists and dicts 10x more than defining classes.
One of the best engineers in Microsoft’s devdiv told me that he often gave a linked list implementation in C as a whiteboard assignment for interviewees and that no one ever managed a bug-free version. (I failed mine even after creating a full general purpose implementation on my own just a couple years before.)
I often wonder about the separation of CPU and RAM, of ways it could be done better. How about making it like neurons, where each "memory cell" is also a teeny tiny computer itself? (How DO neurons do internal computation anyway?)
A nice explanation on rationales of using linked lists in OS kernel, from a Fuchsia developer. In short, it is almost guaranteed not to fail on most typical operations given the invariant is not broken, which make it suitable for cases where there's no fallback option left like kernel codes.
Well, if one likes linked lists enough, they can replace binary search trees / hash tables with a skip list. Super powerful and easier to implement than splay trees, red black trees, avl trees, augmented trees, what-have-you.
Sadly, you can't really control the block size in C++'s std::deque so you can't communicate useful information to the library about your use case. I think MSVC allocates such a small block that it is effectively a linked list.
This is speaking in generalities though, since you could have an “alternatively implemented dequeue or a linked list entirely on the stack.
Two consecutive elements are probably in the same array, and that helps with cache locality.
In defense of what? A brigade of null pointer exceptions?
> Linked lists are conceptual. A node pointing to itself is the most self centered thing I can imagine in computing: an ideal representation of the more vulgar infinite loop. A node pointing to NULL is a metaphor of loneliness. A linked list with tail and head connected, a powerful symbol of a closed cycle.
Oh, this article is complete satire. Bravo, you had me
The one I'm getting is also for the wrong name - registered for redis.io and expired on `Fri, 07 Aug 2020 11:30:03 GMT`. Issued by Let's Encrypt. Fingerprint: `07:BF:EA:59:DB:83:33:77:50:27:A8:C5:2F:80:F6:CA:E6:EC:E2:7D:01:DB:72:7A:AF:EE:69:DD:EC:2D:DA:F3`
Seems like a MITM attack is going on.
And I answer, "I'd google it"
To give a C# example, arrays, lists and dictionaries (hash tables) implement iterators so you can always know what the next element in collection is. Elements can be accessed by key or index in O(1),elements can be added in O(1). The case in which you absolutely have to insert an element in a particular position is rare so linked lists are seldom used.
The same case is for C++, there is a vector class in STL but no linked list class. Same for Java.
Java does have a linked list in the standard library: https://docs.oracle.com/en/java/javase/17/docs/api/java.base...
No, there is std::list.
https://en.cppreference.com/w/cpp/container/list
> Same for Java.
Also no, LinkedList exists.
https://docs.oracle.com/javase/7/docs/api/java/util/LinkedLi...
However, Clojure has shown that the underlying implementation if often better done using a tree of contiguous memory blocks.
Most that Joe Random could expect to get in print would be a Letter to the Editor, or a random passerby interview. The in-crowd was even more "unusual".
Each tool has its own value it was designed for ...
Try to imagine LISP without lists ...
It's called Clojure.
Getting rid of CONS (effectively removing singly linked lists) is a huge benefit.
> get ready to read a sentimental post about a data structure
Makes a looot of sense