Why You Should AVOID Linked Lists

Recorded live on twitch, GET IN
/ theprimeagen
Original: • Bjarne Stroustrup: Why...
Author: / @alessandrostamatto
MY MAIN YT CHANNEL: Has well edited engineering videos
/ theprimeagen
Discord
/ discord
Have something for me to read or react to?: / theprimeagenreact

[@adambickford8720]

People don't seem to understand that O(1) is not FASTER than O(n), it just SCALES better; there's a breakpoint. Imagine a "hashcode as a service" rest call vs doing it in memory: it'd still scale better, but it'd take an awfully large 'n' to get there. I see people missing this in PRs, streaming/looping an array is often faster with small arrays than something like a `HashSet`. And in practice, its really unlikely either makes a tangible difference in most use cases.

[@ThePrimeTimeagen]

^-- yaya

[@KayOScode]

Yeah, I’ve started picking and choosing what I optimize a bit more. I don’t need to optimize a dictionary that maps an enum to a value when that enum has 30 elements, and the iteration happens once a cycle outside of the heavy loops. I need to optimize the heavy loops

[@batatanna]

That's true for any O() btw. O()s are the simplification of a function to represent the shape of its curve. Depending on the full function you can get a O(n²) that's faster in low levels than a O(n), all we can say is that eventually O(n) will be quicker but knowing this breakpoint requires testing and depending on application is pointless.

[@IStMl]

yes thats why you say O is for worst-case, when n gets big. But for small n the bigger O could very well perform better. That's when you need Omega() of your runtime

[@orychowaw]

Fu fact: Brute force attacks on encrypted text is O(1). But the constant is quite large, by design.

[@ea_naseer]

Haskell programmers: Linked lists all the way and back.

[@StopBuggingMeGoogleIHateYou]

In functional programming, singly linked lists play a special role of being immutable, and being able to be prepended to without modifying the existing list. Arrays are virtually impossible to implement as anything other than an array of lists, which throws away most of the performance benefits that one would get from using an array in an ordinary imperative language.

[@demolazer]

Lisp too, the entire language is linked lists lol

[@colemanroberts1102]

​@@demolazerdepends on the dialect. Common lisp hews imperative over functional and supports arrays just fine.

[@swanandmodak6666]

Like how your pfp is just "C"

[@alurma]

1) Yes. 2) Arrays are not impossible, Haskell has efficient arrays, they are just clumsy to work with. Linear Haskell can improve this a bit I think. 3) Immutable data structures exist and they play with cache pretty well. 4) Linked lists are cool because you can have multiple heads share portions of the list.

[@core36]

Store data in a dynamic array, add a unique ID to each entry and shuffle it every time you add an entry. Every time you need to access an entry, search for the index by randomizing the current index and check if the ID matches the ID of the entry you are looking for.

[@Gelo2000origami]

The dumb quicksort

[@tannerted]

Is your name Tom, by chance? That sounds like a Tom-level of genius-ness

[@LiveErrors]

Bogus-IO?

[@liegon]

@@Gelo2000origami Bogosort, right?

[@KucheKlizma]

Critsort

[@orychowaw]

This is an absolutely classic talk that every software developer must see. I remember writing a lot of linked list code back in the days of DOS and it worked wonderfully... but computers changed a lot since 1990.

[@defeqel6537]

Also depends on what you use them for, they are quite handy when writing certain allocators

[@tetraquark2402]

Also fun to write

[@c0ldfury]

Everyone knows that if you want to store a list you store them as bucket on S3 and then if you want to count the size of it you use Spark.This is all nonsense that assumes users know how to download RAM when we all know now that it's in the cloud.

[@MrHaggyy]

My hardware is weather independent and doesn't have cache .....

[@TheSulross]

memory caching architectures screwed up all that wonderful 1970s/1980s intuitive simplicity but all of our Comp-Sci data structures 101 courses still get tought as though that were the reality the one place I find I can return to that simplicity, though, is FPGA programming where digital circuits do their thing on a clock cycle - but even there, there is signal propagation latency to contend with, but the design and simulation tools help coping with that

[@dekutree64]

There are some cases where linked lists are highly efficient. One real-world example is dynamically allocating sound channels. When you need a new channel, grab the head of the free list. When freeing a channel, link it onto the head of the free list. Both constant-time operations. And you have to traverse the active list every update, so you have your prev/next pointers to unlink if a channel has ended. And because it's all management of elements within a single array, you don't need pointers, or even to store the prev link. Just a single next index. Another is overhead RPG sprites. They need to be rendered in order of Y position, and you can do an insertion sort every frame to relink them in proper order. Normally an insertion sort is O(n2) because you have to traverse the list to find the insertion point, but because the list is still mostly sorted from last frame, you end up linking most entries to the head of the new list so it's O(n).

[@SimGunther]

_Back in my day_ cache friendly code wasn't a thing; now these newfangled caches make the case for arrays stronger than ever. Having that said, solving the problem correctly before measuring performance and making the case for struct of arrays is super important or else you're just gonna have a lot of arrays that aren't doing you any good.

[@ErazerPT]

"Cache friendly" was always or never a thing depending on the circles you moved in. Go ask the OG's in the demo scene, image processing and others the lengths they'd go to make sure the performance critical sections of code COULD fit in the cache. The only difference between then and now is that before you had to do some work with limited resources and now you have to A LOT MORE work with (a bit more) resources. Think VGA vs 4K, it's 29x more work just for the basic pixel count, now add "new shiny stuff", and it quickly becomes "any optimization counts". The key take is obviously "performance critical", and most people don't tread those nasty paths, unless they have to.

[@blarghblargh]

@@ErazerPT depends on the demo scene. 8 bit scene could always expect constant time access to RAM.

[@donkeyy8331]

what do you mean? spatial locality and temporal locality have always been a thing, that's kinda the whole point of caches and why engineers calculated cache hits and misses to find the sweet spot of how much do you actually need for them to start making a difference in performance.

[@marcossidoruk8033]

​​@@ErazerPTn the very old days, CPUs were in general much slower than memory access latency, so cache efficiency didn't matter, in fact, most of these CPUs didn't have caches because memory was fast enough. Of course there were other tricky optimizations specific to each CPU that often had to do with memory layout, for example some CPUs may be extremely picky with regards to alignment, but cache efficiency in particular is a relatively new idea in the history of computing.

[@marcossidoruk8033]

​@@donkeyy8331That is incorrect.

[@KonradGM]

C++ not censured, it thought it was family friendly channel

[@ThePrimeTimeagen]

much sorry

[@switchblade6226]

​@@ThePrimeTimeagen hey, some people are into uncensored hardcore C++

[@arcanernz]

I saw this a while ago and it blew my mind. It just shows that when you move theory to practice things may not work how you expect since there's a lot of complexity such as caching, predictable usage patterns, compactness, number of pointer redirections, etc. that significantly impacts performance. It's very difficult to correctly optimize a piece of code without first measuring and understanding where the bottle necks unless you already have experience in tuning.

[@ChrisCox-wv7oo]

"Premature optimization is the root of all evil" -Donald Knuth That's not to say, optimized code is bad, but that many programmers will attempt to optimize what doesn't matter to the detriment of maintainability, while ignoring the very small section of code that matters most. Don't optimize 90% of your code before you optimize where your code spends 90% of its time.

[@dire_prism]

The linked lists gain a lot for some special purposes when the elements themselves have prev and next pointers and you never have to search. But even then not always - contiguous memory really makes a difference.

[@Bunny99s]

Exactly. And that's the only case I would use it :) I'm mainly a C# programmer and I never used the "LinkedList" class but I have implemented my own linked list structures here and there where it made sense.

[@MrGencyExit64]

I love listening to Stroustrup talk. His pacing and tone are just fantastic when he's explaining _anything_ :)

[@HamishArb]

This is a good take. I think it's good to educate people that if they need to search for a node to do something with it, then it will be expensive. I personally rarely use linked lists when I have to search for the node I want to do things to, but you don't always need to actually search for the node - when you don't need to search is when linked lists are (more likely to be) useful.

[@_TeaMaster]

I would presume, it really depends on what kind of linked lists, with what kind of data inside we are talking about. The mentioned example may hold true for the primitives, especially if they can be stored and processed on the stack, but I'm not sure it would be the same when applied to, for example, a list of pointers to the attributes of objects stored on the heap, where addition/deletion is performed based on the logic that requires accessing their values.

[@mvargasmoran]

when you don't need to search? I think searching or accessing is one of the common things one does.

[@adamhenriksson6007]

A trivial example of where a linked list shines is when implementing algorithms that require queues which can grow and shrink with ease like BFS. Again, very trivial example.

[@trevorroddy3773]

access =\= search. You can access the head of a linked list like a queue, no search required

[@parlor3115]

But how would you know that you won't need to search in the future?

[@leeachristie]

If you're doing only head or only tail removal/addition I'd go to a vector or a vector in reversed order. If you're doing both, I'd go to an array deque which is essentially just a vector treated as if wrapped in a circle. I try to avoid linked lists whenever possible.

[@christoferstenberg3920]

If you're not order dependent you can always do a swap remove on the vector, get O(1) there too. i.e. Swap with the last element of the vector and shrink the vector by 1.

[@shiinondogewalker2809]

I'd say deque is an optimized linked list. I'm not entirely sure what a vector wrapped in a circle would mean from a memory point of view. From a usage point of view it makes more sense, but usage of deque can be thought of as just being a linked list also

[@woolfel]

one additional thing is the impact of linked list and structures with lots of pointers is heap fragmentation and compaction. At some point, your system may need to compact the memory to get better performance. A lot of programmers don't think about heap fragmentation and how much if affects performance.

[@rohitaug]

I like to use a combination of both. Make chunks of max 4K elements (or whatever size is suitable for your cache), store these chunks in a linked list. Insertion and deletion with a chunk is fast since you're shifting stuff already in the cache. Split a chunk if it gets near 4K elements into 2 chunks of 2K elements, or merge 2 chunks if they fall below 2K elements. Should be as fast as arrays, with the flexibility of linked lists.

[@kebien6020]

I think that's how std::deque is implemented

[@ribethings]

en.wikipedia.org/wiki/Unrolled_linked_list

[@jumpergamer1913]

You're a genius you idiot!

[@mapron1]

@@kebien6020 I think it's also close to std::colony. Which use skip list in contrast.

[@romannasuti25]

And if you build a level of the same structure, with each element pointing to one of those chunks, and another up, until you have a single chunk parenting all chunks, that’s a b-tree. Literally THE fundamental index structure in RDBMS.

[@flamewave000]

This was great. I remember watching Bjarne's presentation a few years ago and was blown away by how simple the problem was after he explained it but yet so damning for Linked-Lists. My favourite language is C++ and I miss it dearly (been stuck doing Kotlin for several years now).

[@JoshuaWise1994]

Linked lists aren't good for containers, because of the linear search problem mentioned here. Linked lists are good when they're built into the data type itself. That way, if you have a reference to an object, you can just call something like appendAfter() efficiently, without searching for the insertion point

[@stephenspackman5573]

Exactly. The cursors are a critical part of the linked list data structure. Linked lists without cursors are like vectors with encrypted indices. There's just no reason to do that to yourself.

[@throwaway3227]

A skip list is a clever and interesting method of speeding up lookups in sorted linked lists. It's possible, though, that cache misses still give it a disadvantage to vectors.

[@jacquesolivierlapeyre]

Most devs have dead brains. Skip lists are too difficult for them.

[@davidandrewthomas]

It’s not even just cache misses and prefetching like he mentions, but it’s also a linear chain of data dependencies. When traversing a linked list, the out of order CPU can’t do anything for you because it doesn’t know where the next node is until it gets the result of the memory load of the next pointer for the current node. So the CPU is just stuck waiting around for stuff to do while memory loads. Basically, linked lists are the worst case data structure for allowing your CPU to do what it’s good at. Hybrid data structures (lists with fat nodes that contain compact arrays) can give many benefits of both, though.

[@martijn3151]

If the items aren’t sorted, you can just swap the to-be-deleted item with the last item in the vector and then pop that. Super fast. No linked list will beat that :)

[@redonion3184]

yeah! in rust there's a method for in Vecs called swap_remove()

[@Ehal256]

Thinking about this.. Useful if you don't have external references to items in the list, but probably difficult if you do. I use linked lists in my game engine in some cases for this reason, deletions only occur via external pointers, no searching required, and because they're only iterated once a frame at most, (and because it runs on an uncached cpu).

[@jacknguyen5220]

This is useful specifically for unordered data structures, which in my experience... yeah haven't used unordered lists like ever lol

[@christopherpepin6059]

But you have just created the exact problem that made linked lists slow. Every single time you want to find something in your vector you need to traverse through the entire vector first.

[@doctoralfman8393]

It is all about use case. There is no best data structure to store multiple elements. If you only need to store multiple elements and dont care about order or finding specific elements, say a game where you have a list of objects to update each frame (note, not render order) then an array where you delete by replacing with the last element makes an amazing data structure.@@christopherpepin6059

[@emyrulz]

I think there is a small implied assumption when stating that insertion/removal is faster in a list, namely that you already have a pointer to the desired location and linear search is not an issue. Just like with an array, you don't usually search the element to be removed, you just index into the array by keeping track of the "interesting" indices, with a smart use of a linked list you usually keep track of pointers to the "interesting" nodes. In this circumstance, the list is better.

[@quincy2142]

A good example of when a linked list beats an array is if you get the data served randomly and you want to sort it, and you also have a HEAD that keeps track of the current Node's position. Then if you want to sort the random data in ascending order all you do is: Move head forwards if current node is smaller, move head backwards if current node is bigger. Insert when value before is smaller and value after is bigger. (Which is O(1) Now at worst you're doing a linear scan, but usually you're only moving a few nodes at a time depending on distribution of numbers. If you did an array however, even if you did this HEAD approach, you would need to to first find the number, which is a linear scan in the worst case and on average only a few array cells. But even if that type of perf is similar, once you get to actually inserting you are now having to shuffle n cells to accomodate the new element.

[@simonmaracine4721]

Exactly.

[@Matthew-eu4ps]

I've done some work of trying to optimize algorithms, and this is my opinion at the moment: - The tighter you can pack your problem in memory the faster your algorithm will run. - The CPU is fast, memory is slow - It may be best to think of memory as linear-access rather than random-access. The number of passes through memory your algorithm needs determines a lot about performance. - there isn't much that can substitute for just testing different implementations of your problem. (Though the specifics of your system may influence the results a lot)

[@mazthespaz1]

Maybe I missed it, but when doing the insertion on the linked list you have the pointer to the last thing you inserted. if the next random number to insert is bigger than the last you don't start at beginning of linked list, you start at last item you inserted. I haven't thought this out, but it seems quicker

[@user-lk2vo8fo2q]

yeah head insertion/deletion, or things that can be effectively reduced to head insertion/deletion. if the problem you're solving is amenable to having a "cursor" (or multiple "cursors") linked list would still be better because it avoids the search you'd need for true random access. has the side benefit of letting you do thread safe access with fewer locks too, although i think in most practical cases you don't actually need every thread to be able to randomly access any element in the list at any time. if your access pattern is random you'd probably want to divide your list up among the worker threads instead, or have some kind of batch update scheme.

[@nicolassilvagni7909]

If you do head or tail removal, you would leverage a dequeue or other FIFO like structure made for that, to still maximize cache hits, not a linked list. Pick the structure that minimize the services you need of it :) I would also say, off the record that it is bold to go and comment on a Bjarne Stroustrup presentation !

[@porky1118]

You could also put a linked list into an array, where you store the next and the previous index in each element. And the removed elements, which are still inside the array also form a linked list in the same array. No custom allocation, pretty cache friendly, and almost all operations are O(1) until you resize. And sorting doesn't need to copy the elements itself, but only the indices.

[@nonamehere9658]

Doesn't support insertion between elements (or it does, but then you need to waste "tombstone" elements between each real element and also you can only do a fixed number of inserations in a position).

[@porky1118]

@@nonamehere9658 It does support insertions between elements in O(1). It only has empty elements where elements have been removed. And I only can do one insertion per index, or multiple insertions before and after indices. Indices are not related to the position in the list, though.

[@SaHaRaSquad]

I suspect this is still slower than vectors. You still have to store two pointers per element which makes the dataset larger. Binary search is impossible and linear search will randomly jump through the array if it's unordered. And if the values (without pointers/indices) are only integers then sorting is guaranteed to be much slower compared to a vector. And this isn't just about cache efficiency, if you do a linear search through memory without indirection the compiler and CPU can do further optimizations.

[@BosonCollider]

If the size of the thing you are putting in each linked list node is comparable to or larger than 8 kB, linked lists start performing better again (though trees will do even better since for large nodes extra pointers per node are cheap). But the default page size in virtual memory is 8 kB, so fetching the next element during a linear scan will be a cache miss anyway even if you use a vector That 50-100x ratio is basically the ratio of the node size to the memory page size. Also, Rusts btreemap is _incredibly_ underrated if you plan on iterating through your keys or look up closely related objects often

[@vonnikon]

If your elements are large, then you use a vector of structs, each struct containing the key value and a pointer to the bulk data.

[@steveg1961]

In specific use cases, you can make using a vector even more efficient. For example, let's say you are first populating your vector with values that occur in some set of data, and then after that you are deleting from that vector any of those same values that occur in a second set of data. So after you populate the vector, then you sort it, and then when you go into the deletion procedure you do NOT move any items in the vector at all, but merely NULL those entries. No moving necessary. And then, if you want, you can create a second vector, traverse the first vector and populate the second vector with non-null values, and then deallocate the first vector, and just use the second vector.

[@malusmundus-9605]

BRAVO 👏 EXCELLENT use of raw C pointers. You DID mean to say you are populating the vector with the addresses of the values contained in the first data set correct? You said "values" but I didn't want to be a d*** and assume you were trying to assign NULL to stack values. The sort is probably better saved until after the pointers/values are copied into vector 2 though- as vector 2 should be smaller.

[@steveg1961]

@@malusmundus-9605 You're correct that the vector contains addresses to the values. When you sort is a use case. Typically I'm using a binary search on the vector, then checking for matching values, which if found means it's a duplicate - and since I'm looking for unique values, I null the dupes. A different usage may not require the sort up front. (My context here is string values.) I save processing time because nothing is moved until the end when I copy the "values" (addresses) into the second vector, skipping the nulls.

[@steveg1961]

@@malusmundus-9605 You're know, thinking back over the years, I think I did actually arrive at that kind of method when coding in C. But then I've used it in C++, Perl, Java, and C#.

[@malusmundus-9605]

@@steveg1961 yes I do this sort of thing when I code in C and C++. I don't why but ever since I started coding in C and using pointers I think of copy/move operations as being "fat" and I tend to avoid them whenever possible... even though in reality the difference is negligible on most modern machines. Hey how do you like Perl though? I know it's kind of an old language but I was thinking of picking it up for fun. Seems like it would be nice to have in my repertoire for parsing strings. (I like Python for this but it's really slow)

[@steveg1961]

@@malusmundus-9605 Perl is great for string parsing/matching. (The regular expression system is a dream.) But the one thing about Perl that irritates me to this day is how you pass parameters to functions - klunkiest method I've ever experienced. Other than that, Perl feels concise and elegant to me. Note that I haven't used any version beyond Perl 5.

[@joshuamanton]

Just gonna say my thoughts as I watch: -Okay the thing about the linear search dominating makes sense at first blush but that's just bad usage of a linked list. Generally you will couple it with a hashtable from some key to the node. Any simple LRU cache would work like this. -The nodes don't have to be malloc'd randomly. You could malloc sizeof(Node)*1024 and then dole them out. -Linear search is especially bad for linked lists because with an array it can prefetch elements that it knows you are going to touch. Not so with a linked list because it's all through pointers so who knows what you're going to need next. Again, use a hashtable if you need lookups into your linked list. Linked lists are good at insertion and removal, not at random access. Nothing new there. -"Vectors are more compact than [linked] lists." No, see above about mallocing a pool of nodes. -"Always use a vector unless you can prove a map is faster." For a trivial case of searching for a given integer in a vector of integers, a map becomes faster after about 100 elements (from my testing a while ago. Also depends on the implementation of those data structures. I did my test in C# (List vs Dictionary so take that with a grain of salt). Linked lists are very powerful when you start using them how they are meant to be used. They are not merely "a worse vector." They afford different things.

[@u9vata]

Very good to pick up this topic. Honestly data being randomly all over the place makes these JS/TS languages even more slow than the slowdown that GC uses... Btw I have a data structure that uses a locally linked liist with all kinds of trickery to make it still continous in memory. However you skimmed over whatt he talks about having multiple bytes wasted for the forward and back pointers... In my case the data locality is not so shit - I totally try to make linked data close, yet I had to fight with the pointer overhead too! That is for example instead of using pointers I started using 32 bit indices when there is a jump - just because its smaller. Imagine this data structure templatized with x,y,z float triplet (like Vector3), which is small enough that 32 vs 64 bit size wasted for the pointer counts HUGE - not just in memory use, but in cache use. also people seem to think "not used memory is wasted memory" however memory in use also means cache collisions more often... winblows people never understand why its better to have minimalism, than the OS trying to keep everything in memory for "what if the next moment it is needed". Page table handling becomes harder, addresses for cache lines that mix with each grow, all kinds of subtle issues. TL;DR: pOOP style really hurts performance...

[@marcossidoruk8033]

You can maybe use relative pointers of some kind to reduce the overhead even further.

[@u9vata]

@@marcossidoruk8033 Thta is good advice, was toying with the idea after seeing that in JohnBlows language supposedly supporting it on language level. However actually yesterday night I did a more nasty thing: I literally found a way to overwrite parts of the "data" as "key" and mark a topmost bit on that position: this makes me need a preprocessing step in my data structure that now I separate based on that key first into two of these local lists. This only works because I provide accessors that "undo" this operation on the fly. It also has a lot of pros and cons - will see how it fares and real use cases not just in local tests, but microbenchmark-way it looks plausible "hack".

[@jt....]

+

[@Cygx]

A deque in python is also implemented using doubly linked list, hence searching for a node in the middle of the list will be O(n) where using a vector would be better unless you only work with popping the first and last elements.

[@cfehunter]

Almost always vector is the rule. Unless it's C#, because C# List is equivalent to C++'s vector. The only reasons to ever use a list for storage are if it's intrusive (like intrusively linking slabs inside an allocator) or if you have a collection that's constantly changing and your objects have a highly complex move.

[@mu11668B]

I'm glad that our professor emphasized the linear search bottleneck in the DS course. I still use linked list a lot, but the cases are almost always about some other abstract data structures like a stack or a hashtable (for each slot, not the whole mapping, of course). If something by design only uses head/tail removal or requires linear search anyway, linked list is the way to go. When sorting comes into the play, the first things that go through my mind would be an array, a heap or a RB tree. You'd better retake the whole data structure and algorithm curriculum if you come up with a linked list first.

[@avatar098]

This also gets much faster when you’re talking about caching. Data locality is king and keeping your data compact like this enables stupid fast lookup because the memory will always be in CPU cache. This is literally the idea behind ECS (entity component system). Essentially create a compact list for each component of an entity rather than Malloc a bunch of objects with the components attached. Because the components are compacted and destructed in this way, you get more cache hits and improved performance for your simulation

[@autistadolinux5336]

You generally use (double) linked lists when you want fast deletion and fast "top" insertion and you have to iterate all elements anyway. In fact, i'm doing an entity system for a game and i had to do BOTH dynamic buffer (std::vector) and linked lists, and with relative pointers instead absolute pointers to avoid dangling pointers. Use the std::vector for memory buffer, a stack for reserving all the free entity and a linked list to iterate just the entities that is not freed.

[@QberryShortcake]

The one place I see linked lists pretty commonly in the Real World is in allocators, for example if you're managing your own free list. Since you can't control what malloc actually *gives* you as far as a memory address, it can be helpful (and way faster) to keep track of the pointers that you *are* given and their size, and serve those up first when a new allocation is requested, before asking for more memory. This is mostly a video game code thing, and this saves cycles, so while it may seem like we're splitting hairs over fractions of a second....we are. We try to avoid *actual* allocation and deallocation at all costs.

[@scottyoung100]

There appears to be two types of linked lists taught: one where a node is a separate object, and one where the node is a composite member. The latter I have only seen done with kernel programming in C, because constructs like CONTAINING_RECORD cannot be done in high-level languages such as Javascript. For example, if you have a process object (struct task_struct on linux or KPROCESS on windows), removing that process from the list does not require iterating all processes because you can directly access the list_entry member. Whereas for generic containers, the node is external and must be searched.

[@dire_prism]

Funny thing is, the first linked lists I saw was when studying source code for MUDs, and they use a lot of those "intrinsic" linked lists. I thought that was how all linked lists were done. I have never used the linked lists with separate nodes in my career, and have a few use cases for the intrinsic linked lists, but mostly for gamedev.

[@dawre3124]

this is so cool. i'm self teaching rn and learned about the different cpu components yesterday. abusing the cache with a simple array over a more complex structure like a tree or list with nodes sounds super interesting. i'll start to code up a hybrid in c with different node sizes where each node is an array that fits in cache. gotta do some more research tho how the diffrent cache levels interact when loading a node like that on my intel cpu. on an amd something like this could also have insane multi core performance when the infinity fabric is abused with each core dealing with a different array(node) with, tho i did not study amd cpus yet and don't have one

[@InconspicuousChap]

The main reason for avoiding linked lists and preferring array-based structures is that the machine memory since dr. von Neumann and dr. Turing is an array, not a linked list.

[@redcrafterlppa303]

I think what he is missing is vertical scaling. Make the stored type 10 or 50 bytes and the overhead of the pointers will go away and the copy issue of the array will get a lot worse. Would like to see the performance graphs with larger types.

[@yjlom]

wouldn't you just store a pointer for larger types? would kill the array's cache locality but apart from that it's probably best

[@kebien6020]

vector

[@isodoubIet]

The list would probably still be worse because each node would get copied into cache with every cache miss, which is every access. The vector would get the benefits of prefetching whereas the list would stall on every indirection.

[@PalladinPoker]

50 bytes is nowhere near big enough, it has to be at least a kilobyte. Linked lists suck because of cache misses and data localisation. Because of this the stored data in each element needs to be comparable to the page size. At that point you are probably storing objects when a vector of pointers to an object array/vector is faster.

[@sorcdk2880]

As a general rule of thumb, if you have to look for the element in your list, linked list are usually beat by some kind of array construct, because the search is still the same assymtotic speed as the more expensive operations on array constructs, so it comes down to the exact cost inside that, and linked list can easily end up with a lot of overhead. Now, one can then try and come up with some specific cases where linked lists should be better, but in practise I do not recall an instance where a well set up array construct could not handle it more efficiently. In the end, the main use of linked lists are as a basic concept of nodes and graphs, which can then be used to construct more advanced datastructures, like trees, that do contain some more advantages. Also, it can often be useful to fist think of a problem in terms of a node datastructure, and then figure out a way to effectively turn it into an array construct of some kind, for instance you can handle a lot of cache-misses by simply implementing your linked list with indexes in a larger array instead of in general memory. In reality, most of structures like this are not used with the purpose of performance, but because they can be more readable, maintainable, and easier to work with, especially once you build several layers of such things together. In most cases I use a hashmap of some kind, it is not because I really need the special hashmap performance (hint: hashing can be expensive, and hashing cheats a bit to appear to have constant operations, by just starting with large enough constants that you would not reasonably escape to the part where it stops being constant), but because I want something to be stored based on just some hashable value, usually either because it is convinient for the problem or because it makes it more readable or quicker to write. In practise, you often get a fairly performant result by structuring the inner part of the logic in array constructs of some kind, and then you can build the other structure through nodes, maps and other convinient data-structures. This works, because a lot of the advantages of array constructs fall off once the content of said array are pointers, and directly and fully building larger problems with multiple levels combined into efficient array structures is a nightmare in maintainablity.

[@pierreabbat6157]

In Haskell, linked lists are used more than anything else, and it's common for a list to be produced by one function while it's being consumed by another, so the whole list is never in memory. For updating/inserting/deleting elements at random positions in a container, I'd use a sequence, since if you use an array, you have to copy the entire array every time you update one element.

[@n4bb12]

I've seen the weirdest linked list interview challenges... putting numbers in a linked list digit by digit in reverse order and then "adding" the linked lists and turning the result back to a number. Never in my career did I encounter a use case for linked lists. Now I realize I've been doing math wrong the hole time...

[@brad6742]

post your comment in Chatgpt and then ask: give me a solution to one of these questions It's longer than I was hoping lol

[@mrpocock]

This is why you really want some kind of tree of arrays, with the nodes annotated with data that lets you look up by index rapidly. Ideally each of the nodes sits in a page, including the node annotations.

[@sthiag0]

there's a good video by computerphile on this topic, called "arrays vs linked lists", in which they compare this on computers with and without cache

[@brianviktor8212]

Before the video starts: Because they are less efficient than having an array, even if it is a ListArray that doubles its array size when necessary. LinkedList means the items are all over the memory and therefore it's slower. Edit: And yes, the 'n' complexity for get, set, delete. Getting a value is basically always needed at least once... unless you traverse it step by step and do something as you go... well then it might be _not as bad_. Still worse than array even in that case.

[@pesterenan]

Just saying that I'm watching his course on frontend masters and its fenomenal! Such an awesome work Prime! I'm loving it!

[@davidhand9721]

I've always implemented linked lists and the like using a pre-allocated buffer for all of my nodes to improve locality of reference. Honestly, with as many elements as the big guys like Amazon have, there's no chance I would use linked lists _or_ arrays unless the array was all IDs.

[@lesfreresdelaquote1176]

That's interesting. I read a blog post a couple of weeks ago by a guy at Naver (a Korean company), who implemented a Lisp based on vectors instead of lists. The title was: LispE isn't exactly your granny's Lisp. And basically the guy was stating the same facts as well.

[@cabeloDoPardal2]

I would try making a parallel index of pointers, in an array, ordered. The objects would be stored in a linked list because of faster allocations. But for search, an ordered array of pointers without rearrange would be good, depending on the size of elements.

[@thewelder3538]

To my understanding of the question, if you have 100k elements and need to remove the one at 702, you can index directly to that element with a vector and it just requires a memory copy to move the elements down and that memory copy is amazingly quick because the data is contiguous in the cache. With a list, it's never going to be contiguous and possibly in a different numa and you have to traverse the list from the start to the desired node to remove the element.

[@OnFireByte]

Linked list is better when we need to insert or remove elements in the middle of lists and we also already have a reference to element next to it, which is kinda very specific. Removing head element, like chat said, is not really strong reason (but still good one) to use linked list, since vector with ring buffer (or something like deque that usually implemented using vector) is still better. Real use case is modified linked list that usually used by functional language to do "immutable" list with less memory footprint (less copied), which is understandable.

[@ThePrimeTimeagen]

what you are describing is effectively LRU implementations (map -> node, node cut out and put on front / back depending on the impl)

[@Taverius]

​@@ThePrimeTimeagenyeah, that sort of thing is basically the main/only way to efficiently use memory in a Pure FP/immutable paradigm - you're copying everything, but because everything is immutable that's just passing a pointer in practice, and you structure your data so that when you do change things you only have to allocate the bits that have changed. I've seen this video before and to me it seemed like a long and unfocused way of saying "use the right tool for the job and be aware of how your structures exist in memory" idk. 🤷‍♂️

[@khatdubell]

There are only three reasons i'd use a std::list. Stability Extremely large elements Expensive to copy/move elements

[@leddoo]

good take! some more examples where linked lists shine are retained mode guis (like the dom), intermediate representations in compilers (like ssa), and language runtime stuff (memory allocators, sometimes work queues). (incidentally, those are the things i work on primarily. so i could definitely see linked lists being useful in other areas too!)

[@martinpata2899]

I thought that list were made because it was hard to have long arrays, and if you had to move it to expand the array it was costly

[@scvnthorpe__]

Basically, linked lists involve more jumping around memory + they railroad you into a linear search

[@ddddddddd345]

Where LLs are used, like in Linux kernel one does not do list traversal. Things have pointer right to the node they care about and add, remove/add it/other nodes right there.

[@viktorcaleis]

TLDR and for grug: Make linked list inside array. Advantage of both linked list and array, less disadvantage. The magic of data structures is that you can combine them. If you allocate your linked lists with an arena allocator(pool allocator, bump allocator), then the point Stroustrup makes doesn't make sense. Linked lists aren't defined as having to use malloc (even if the do most of the time). Arrays(vectors) vs Linked lists doesn't make sense in all algorithms, as some necessitate one or the other. If you do what I suggest (arena allocator) there is cache locality, no memory fragmentation, the only draw back that remains is the memory overhead of the linked list structure.

[@ea_naseer]

so an array cell that stores a list where at the end of the list it points to the next index of the array? Is that correct

[@viktorcaleis]

@@ea_naseer more like store the list inside a growable array (vector in c++) so when you need to allocate a new list you grow the array and store it in the next cell.

[@airman122469]

I’ve done exactly this. It works super well. You can get access to any point in the list, and then traverse directly. It’s awesome.

[@climatechangedoesntbargain9140]

cache locality is worse when iterating through it still

[@kkounal974]

New to data structures what's an arena allocator? Do you mean having two arrays, one for the data and one for the pointers?

[@LusidDreaming]

To be fair, linear search insertion is not the only method. There are many contexts where you would just pass the node directly before or after where you want to insert. But these are probably not as common as needing to do the linear search, so definitely a valid point.

[@zxuiji]

4:07, 6:48, that's bull, just keep existing allocations even if they're removed from the main list, like this: buff = all head = ... kept = NULL when a link is removed just move it to the "kept" linked list instead, whenever you need a new link you check to see if "kept" is NULL, if not take from there, otherwise you make an allocation. The links are instead offsets from the current link determined from a simple link->next = a - b which in turn is used for link = link + link->next, the "head" and "kept" will always be an offset from buff, this method gives the speed of buffer allocations + the speed of linked list management

[@ricardog2165]

Wow I saw Mr Stroustrup during lunch at a conference years ago, he looked to be in his 40s. He was talking about his Tetris scores. Time sure flies 😮

[@SilaDrenja]

if you have a pointer, or an iterator/IENumerable depending on your language, it's fast to insert around it. It's only slower if you use it the same way as you use vectors, WHICH THEY ARE NOT MEANT TO. There's a reason there are both vectors and linked lists. I sped up a lot of my programs by using linked lists. I remember having a competitive task where I had to insert N numbers before Mth character. I took the iterator to the Mth character, and just inserted to the list from that iterator. IRL applications are queues, dequeues and stacks. If I know how much I need to insert into memory, it's the array/vector that's the best. But if I have teoretically unlimited insertions, vectors quickly start to have bottlenecks, and also the memory taken by it, since there is a massive memory padding in huge vectors. (it is worth noting the built in stack, queue and dequeue are all using vectors and not linked lists tho)

[@kruppelfield]

We were taught the same thing about using lists, but the condition on these algorithms was always that there was no space limit aswell as allocation and other things that are done in the background were not considered/ irgnored, to fully focus on the efficency of the actual algorithm you'd write

[@mattmmilli8287]

I’ve seen a node server handle 7000 concurrent connections. Need better engineers :)

[@JanuszKrysztofiak]

And in C++ std::vector you can preallocate space upon creation, so adding new elements will be very quick (up to certain point).

[@GiacomoSorbi]

If you need to keep the order of insertion, a LL with a hashmap matching values to their node (or ancestor node, in a singly LL), works just fine. I know, not the most common use case ever, but, still...

[@orisphera]

There's a version of linked lists that can be copied in O(1). For a vector, the complexity depends on what you count as an elementary operation

[@kr12a2y]

I had a similar argument about 20 years ago. My "you need to find the thing before you do the thing, so it'll be trash" ran right into "it's computer science!" I quickly gave up.

[@IBMboy]

That was kinda the same argument for Unity engine to introduce ECS, they explained how OO code was slower, and using arrays was faster because objects were contiguous in memory, benefiting from CPU caches

[@ThePrimeTimeagen]

yep the difference of an array of structs or a struct of arrays

[@Zutraxi]

I like these types of videos. Like pair learning. Didn't realize linked list was so slow compared to arrays, but it makes sense.

[@lepidoptera9337]

Cool topic and I admit that I didn't think about it like that, either... but I always arrange my data in arrays if I can. That includes the way I define objects. If "some thing" has to do the same function a lot of times, I allocate arrays for the data. The main reason why I do this is memory layout. By pre-allocating a fixed memory block and checking range all kinds of nasty dynamic bugs can be avoided because the system always knows how much memory it has left.

[@ferahl]

But what about the case where you combine a LinkedList with a HashTable, so an item can be looked up by ID without traversal and removed. If the majority of your operations are removing (e.g. a trade orderbook 80%+ are order cancels). Is this then faster? I suspect even then a vector could be faster (especially as orders in a price level can be binary searched), but I've often wondered. I should benchmark some day.. RE Javascript, there is no definition of how arrays are stored. I suspect that the JIT would try to use a vector, but then fallback to a hashmap depending on if e.g. it is a sparse array or the items are not of the same type/size

[@talis1063]

I don't get where the idea to use a linked list comes from for this example. Sometimes you already have a pointer to the insertion/deletion point, I feel like that's the only interesting use case to compare. Like "userptr" in some library, a dictionary matching UI element to a linked list node or something like that, no linear search involved.

[@oblivion_2852]

Only time a linked list made sense to me was when I was storing really large state objects in a ring buffer (2000 simulation steps "forward") for visualising orbits. It was basically a huge FIFO queue and using a linked list meant I didn't have to reorder anything

[@ThePrimeTimeagen]

even then... a properly allocated ring buffer (an array) with a head / tail pointer can work for this thing too! (maybe, i don't know the exact details)

[@oblivion_2852]

​@@ThePrimeTimeagenthis is true but you'd still have a ring array of pointers to heap allocated objects since they're so large. In the end it would probably be the same speed since you're still looking at a pointer dereference per 20kb block. Within each state block the rendering is iterating over super compact data oriented position states. So uh. Overall. Performance is the same lol

[@volimsir]

I remember seeing this video around 10 years ago when I was in university, and having my mind blown. Very satisfying seeing the same look on Prime's face.

[@ScottyDMcom]

When I was learning about linked lists using Java, I made them manually. Each element (data + pointers) was its own object. While debugging I dumped the pointers of the objects to the screen, and was horrified to discover that objects were scattered around the heap. The compiler knows how big each object is, why not pack them together--which would at least give you some cache hits. But that's not the way Java works. I've never tested C++ to see of the compiler randomizes the location of things in the heap. Perhaps I should. Anyway, I believe Stroustrup. Doing a linear search of a linked list is far slower than doing a linear search of a vector (or an array). With the list you not only get to fool around with pointers + data, rather than just data with the vector, but if the compiler randomizes the location of the elements you are guaranteed a cache miss for every access. Of course that'd be the compiler's fault.

[@dekutree64]

Obviously a vector is faster when the elements are comparable size to a linked list pointer, but what if each element is a complex class, hundreds of bytes? You could make a vector of pointers to the real elements, but then the real traversal order is still chaotic. The pointers would have cache coherency, but if you're doing a complex update or render operation on each element, then the next pointer will have probably already left the cache by the time you need it.

[@Fulminin]

I kinda thought the optimal would be somewhere in the middle. where you would map to vectors which are the size of a cache block. So you load vectors of like 10000 elements in to the cache then go to the heap periodically to fetch the next block.

[@colinmaharaj50]

For me its memory fragmentation. (Haven't look at the video yet), I will use it in a text editor if I create one.

[@Omnifarious0]

I was hired as a 'systems administrator' and I was looking over the shoulder of the guy who was working on a custom MySQL table engine that was key to what the company did. I pointed out an indirection in a data structure the guy was using and told him that it would be a lot faster if he removed it. He did it, and I was right, and he was a little surprised and rather pleased. 🙂 I also dissected the file structure of a proprietary b-tree and wrote code in Python to traverse it and highlighted a way in which they were doing the comparisons wrong in their own code to manipulate this structure that would result in an inconsistent b-tree.. They fired me after I worked there for three months, and after they had begged me to switch from being a contractor to being an employee... it was all pretty obnoxious.

[@cparks1000000]

a doubly linked list will be much faster if you're doing lots of head-insertions or concatenation. Honestly speaking, I can't remember the last time I've removed random elements from my data structure.

[@animanaut]

games that use entity component system architectures make heavy use of this principle. line up similar components in continuous blocks to reduce cache misses and increase throughput

[@charactername263]

Quickly removing elements not at the head/tail is very valuable - but List should be used with an allocator to avoid fragmentation and poor memory locality.

[@morgwai667]

i guess the frequency of cache misses in case of linked lists (as well as of other dynamic structures) heavily depends on efficiency of the memory management algorithm being used and AFAIR the default implementation of 'new' operator coming with most C++ RTs was known for some controversial design decisions.

[@bitskit3476]

Insertion and deletion is faster in a linked list than in an array/vector. What's not faster is lookup by index. Lookup for an array is O(1) and basically a single instruction. For a linked list, it's O(n), and is going to be some multiple of n-deep number of instructions. So if you're trying to implement insertions and deletions in such a way that they use indices instead of pointers to nodes, it's *obviously* going to be the case that linked lists are going to be slower than arrays for insertion/deletion. The source of this problem is people designing and implementing APIs for linked lists without understanding exactly why you'd want to use one in the first place or what it is that makes them efficient. Memory locality also matters for caching purposes, but there's nothing saying that you can't use a custom allocator where you have say, a pool of 100,000 usable nodes which has a pointer to a chain of removed nodes for reclaiming memory. I actually do this in my generic linked list implementation for C, with links between notes being integers and a variant of new_list_item() that allow the pool to automatically resize in powers of 2.

[@melonenlord2723]

But isnt it as said that a liked list is better if you remove or add items in between? In this case you dont have to shift a lot around. So you more should ask what you want to do with the list. Is it pre defined list with a constant number of items in it or you want it to change dynamically?

[@phazechange3345]

On modern hardware, you basically have two things that contribute to your speed: 1) cache hits 2) good branch prediction (note that "branch-less" code doesn't solve this and is usually slower) If you use code that makes both of these difficult (as linked lists do), then you blow your speed away. That is to say: no inserting is not faster in a linked list except in special cases.

[@sabriath]

You have to do a linear search on an array if you are looking for a specific thing within the array....the only difference is the reference look-in and the cache misses that cause a slowdown, but it's still considered O(n). The bigger point is when you have data that stores a pointer to within the linked list for fast referencing, and when that object is destroyed, it can quickly delete itself from the list without having to move all other elements at a O(1) speed to search. These are also more thread safe and can be handled in multitasking efforts unlike arrays where elements can change mid-search (a linked list that changes other elements within it won't affect the read because the list doesn't shift). Linked lists can also be sorted in-place without ever moving memory position. A bridge can be formed in order to move any active throughput points into a new set without effort, which makes sorting also thread-able. Objects can move between linked lists in-place and thereby anything that has a reference to it will not have to change its reference, retaining all other data across the move. So...basically....arrays are great for....quicksort stuff? I honestly don't know the point of an array unless it is literally a math vector or a place to store sync or roundrobin data....linked lists are better, at just about everything. I'm sure you can inch out a few ms of speed, but I prefer flexibility and expandability over perceived speed (which can be improved using several links in an octree fashion anyway)

[@okuno54]

Just for reference, default Haskell strings are linked lists of 32-bit char values. The first thing you do to improve performance is replace the default string type with one from the text library. These are byte arrays containing (as of v2) utf8. That one change can give a 20x speedup in string manipulating code. If even the weird hair-shirt pure functional language can benefit from arrays over lists... how are you confused about the utility of arrays?

[@sabriath]

@@okuno54 you are comparing static to a dynamic and then saying it is the reason for its use case.....yes, as I stated in my comment 5 months ago, "unless it is vectors or sync/roundrobin" (static) then there is no need for an array. Majority of programmers will be quick to use an array because that's what they are taught, and then they start performing moves, insertions, deletions and sorts....then it becomes a dynamic type, at which point the array becomes useless in comparison. Also, bad implementation is still bad implementation....giving one as an example does not set the rule either.

[@HansLemurson]

Cache coherency is important! How do the insertion and deletion operations on a vector affect it?

[@Mempler]

I call a linked list, a leaked list. One mistake and you leaked memory

[@JakobKenda]

to be fair, if you use linked lists in the real world you probably didn't code them yourself

[@embedded_software]

This is why it's good to implement singly linked lists with unique pointers and doubly linked lists with shared pointers and weak pointers

[@isodoubIet]

@@embedded_software And then you blow the stack on the destructor

[@godowskygodowsky1155]

Sometimes, it's okay to increase indirection if it makes the overall structure of your code more manageable, testable, and maintainable. If you're making a game or working in high-frequency trading, go ahead and be particular with how you allocate memory and pass data around, but if you're working with enterprise microservices handling thousands of API calls per second, a few cache misses is negligible compared to network latency, load balancing, and visibility of issues. Software is full of tradeoffs, and part of being an engineer is knowing what things to value in each situation.

[@valseedian]

unless you're using block move semantics on a large set* like radix buckets

[@shmuelisrl]

If you fir some reason know the general area of where the things you want in the list is then it could be faster. You can make a workflow out of that. (I think)

[@D.a.n_D]

The problem the guy had with the presenter in the first minutes, its a classic monitor / presenter / projecter contrast issue. He would have to go to settings and change contrast to something like 70-90 to see the graph he drew. He used a grayish color, that on low contrast setting doesn't appear. Happened in one of our courses too

[@orisphera]

I have a program where I use 2D linked lists. It's not for performance reasons; the reason is that it's the easiest (I think) way to represent levels with certain features in computer memory. The features are called compactification and conic singularities (I also call the latter portals). The program is a game called Ortal, although I don't have any interesting levels for it (although there's a task that one can try to do in one that's not very easy, although you don't get anything for it). I'm in the process of making a different program that uses 2DLL for the same reason, although in a slightly different way; currently, I have a version with no portals that doesn't work for an unknown reason, but I'm planning on adding them after fixing the issue. I'm also thinking of making a game similar to Ortal, but better, and modifications of two existing programs that add compactification and conic singularities with something I call cut surfaces (which are hard to optimise automatically, but may be faster than 2DLL when not too messed with; for one of the programs, they also allow for some spaces impossible with 2DLL)

[@egor.okhterov]

A lot depends on the language, compiler version, operating system, architecture and usage patterns. Always benchmark and look at your metrics before jumping to conclusions. At first prefer the simplest, most readable and most idiomatic version of the code. Optimize when absolutely necessary.

[@danser_theplayer01]

To me linked lists are pretty cool as a concept. Since they are just nodes floating about, with easily rearrangeable connections, you can avoid linear thinking that comes with arrays. One cool example is a structure with O(√(n)/2) random access time, and since it's a linked list the deletion/insertion has the same scaling time complexity.

[@i007c]

is this the guy responsible for making cpp

[@ThePrimeTimeagen]

shhh... don't say that outloud

[@1over137]

There is no guarantee an array is consecutive in memory. Not in virtual memory, not in physical memory and not on disk. If you look into the malloc functionality you will discover this. You will also encounter how they store long lists of things to manage the always moving, allocating, deallocating and even resizing of the allocated page list.

[@Entropy67]

Yeahhh, i dont linear search my linked lists. I keep pointers to either ends of my linked lists internally, thus working from the ends is O(1). Basically a fancy deque with nodes not arrays. Its absolutely not worth working from the middle lmao. And I cant think of a reason why someone wouldn't add that extra pointer to the tail, considering lists are kind of useless otherwise...

[@silak33]

Linked lists only make sense in theory if you are constantly traversing it so you already are at the correct location when deleting. The problem with using it like a collection with an index is that every operation has to come after a linear traversal (or lookup).

[@flynnfittz]

8:01 I once failed an interview for stating this exact argument, definitely I wasn't good enough in conveying it at the time, definitely I won't try using it ever again in an interview...

[@donkeyy8331]

making you memory more cache friendly is the whole point of Data Oriented Programming, I feel like more people should know this exists.

[@Next80sProject]

Is there a book or other learning resource you would recommend on Data Oriented Programming?

[@amorphousblob2721]

Just as I expected, it all boils down to the bizzare effects of modern cached processors. I wonder if Stroustrup is still right when it comes to a list of numbers that far outstrips the CPU's cache. It could be that the CPU's loading of cache-sized chunks improves the shift-by-one process so much, that this is even true for arbitrarily-long arrays/lists. But it's also likely to be affected by concurrency since we use shared-cache multicore processors instead of true multiprocessors where each CPU has its own cache. So a completely external event such as a user clicking over to a KZbin video while your program is running could possibly change whether vectors or linked lists are faster. In today's environment, the only way to know for sure what's faster than what is direct experimentation in realistic conditions.

[@boruch4986]

I just took a class at NYU (DSA) and they went into all of this and wayyy deeper, but this was a nice refresher lol

[@WeirdDuck781]

This is why list implementations such as in JS and C# simply use arrays, by allocating more arrays as the list grows and vice versa. Indexing on multiple arrays is easily done with some basic math even tho it's still random access. However some implementations simply copy over the array to a new one, which is really expensive but makes it a cache efficient for accessing...