Why You Should AVOID Linked Lists
HTML-код
- Опубликовано: 28 июн 2023
- 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 
Наука
Haskell programmers: Linked lists all the way and back.
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.
Lisp too, the entire language is linked lists lol
@@demolazerdepends on the dialect. Common lisp hews imperative over functional and supports arrays just fine.
Like how your pfp is just "C"
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.
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.
^-- yaya
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
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.
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
Fu fact: Brute force attacks on encrypted text is O(1). But the constant is quite large, by design.
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.
Also depends on what you use them for, they are quite handy when writing certain allocators
Also fun to write
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.
My hardware is weather independent and doesn't have cache .....
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
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.
The dumb quicksort
Is your name Tom, by chance? That sounds like a Tom-level of genius-ness
Bogus-IO?
@@Gelo2000origami Bogosort, right?
Critsort
_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.
"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.
@@ErazerPT depends on the demo scene. 8 bit scene could always expect constant time access to RAM.
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.
@@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.
@@donkeyy8331That is incorrect.
C++ not censured, it thought it was family friendly channel
much sorry
@@ThePrimeTimeagen hey, some people are into uncensored hardcore C++
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).
I don't like "Avoid " videos, every DS has its use, for something like unordered data or streams LL are the only option.
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.
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.
"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.
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.
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.
I love listening to Stroustrup talk. His pacing and tone are just fantastic when he's explaining _anything_ :)
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.
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.
when you don't need to search?
I think searching or accessing is one of the common things one does.
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.
access =\= search. You can access the head of a linked list like a queue, no search required
But how would you know that you won't need to search in the future?
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
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.
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.
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.
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.
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
@@shiinondogewalker2809 an array deque is a specific implementation of a deque that is the same idea as a ring buffer. The head and tail 'pointers' are actually indexes into the array. If you were to remove several elements from the head, it would increment the head index by however many, leaving empty slots at the start of the array. Then if you keep adding elements to the end, the tail will eventually increment past the end of the array, so what you do is wrap back around to index 0 where that empty space is. If you remove elements from the tail, it will decrement below index 0 so then you wrap around the other way back to the end of the array (i.e. N-1). Adding and removing elements from the array deque's head can wrap the same way.
Sometimes it's easier to visualize what's happening by bending the array into a circle so that elements 0 and N-1 touch.
It's a wonderfully clever way to keep the lower overhead and contiguous layout of an array without having to shuffle the existing contents about if all you're doing is working with the head and tail.
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.
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.
I think that's how std::deque is implemented
en.wikipedia.org/wiki/Unrolled_linked_list
You're a genius you idiot!
@@kebien6020 I think it's also close to std::colony. Which use skip list in contrast.
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.
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 :)
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).
This is useful specifically for unordered data structures, which in my experience... yeah haven't used unordered lists like ever lol
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.
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
@@christopherpepin6059
No? He did not. He's assuming you already know the position of the item, the index, and if you know the time complexity is constant. With linked lists even indexes need to be traversed in order to get to the correct element, and this is not what make them slower than normal lists. What makes them slower is memory spreading and being prone to cache misses, in this sense a normal vector would perform better even if you need to iterate it entirely first.
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.
Most devs have dead brains. Skip lists are too difficult for them.
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.
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.
Exactly.
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).
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.
Is it possible to explicit case an array to a linked list and then link the two? Given 1..69420 as an contiguous array, then remove one element, instead of creating a new array thats array1.length -1, then copy 0 to n-1 to array2 and then n+1..array.length-1 to array2 at element n, could you just recast the array1 as a linkedlist, replace elements n's value with the memory address to element n+1?
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.
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
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.
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.
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
vector
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.
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.
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...
You can maybe use relative pointers of some kind to reduce the overhead even further.
@@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".
+
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.
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 !
In C#, Java, and Kotlin I literately never had the a problem that would be solved with a linked list while in C I've seen people using it all the time. Is it a lack of generics/templates or are they actually good for something?
Just saying that I'm watching his course on frontend masters and its fenomenal! Such an awesome work Prime! I'm loving it!
What program are you using to do the diagrams at the beginning? And what text editor are you using at the end?
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
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.
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.
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).
@@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.
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.
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.
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
@@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.
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.
cache locality is worse when iterating through it still
New to data structures what's an arena allocator? Do you mean having two arrays, one for the data and one for the pointers?
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
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.
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.
@@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.
@@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#.
@@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)
@@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.
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
I call a linked list, a leaked list.
One mistake and you leaked memory
to be fair, if you use linked lists in the real world you probably didn't code them yourself
This is why it's good to implement singly linked lists with unique pointers and doubly linked lists with shared pointers and weak pointers
@@embedded_software And then you blow the stack on the destructor
well, do you HAVE to do a linear search every time ?
i always thought that linked lists only are viable with some sort of indexing, of a tree, to get to the point faster
i learned this, like, second semester of computer science
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.
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.
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.
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.
Linked list is taught as an practical alternative to arrays to fledgling programmers, but raw linked list is actually only useful as specialized data structure.
I like these types of videos. Like pair learning.
Didn't realize linked list was so slow compared to arrays, but it makes sense.
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.
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.
Link List vs Vector is good example of why you can't just look at Big-Oh.
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.
If you'd have shown me a picture of him and asked why I thought he was famous, I would have said he was that German cannibal.
What's the drawing tool you use to make those diagrams so swiftly?
excallidraw
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
Lispchads I don't feel so good!
is this the guy responsible for making cpp
shhh... don't say that outloud
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.
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.
making you memory more cache friendly is the whole point of Data Oriented Programming, I feel like more people should know this exists.
Is there a book or other learning resource you would recommend on Data Oriented Programming?
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.
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 😮
video quality is so good that it looks like I have myopia
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)
Having to search the list is really the problem here though, if you had a pointer to where to insert/delete then you wouldn't spend O(n) time searching (and cause a bunch of cache misses in the process).
does anyone know what software he uses to sketch the linked list stuff at 1:51?
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.
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
yep
the difference of an array of structs or a struct of arrays
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.
What tool are you using for sketching when you start explaining at 1:00 ?
trying to figure this out
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...
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
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.
Cache coherency is important! How do the insertion and deletion operations on a vector affect it?
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.
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
I suppose if you have a strange situation where you already always have the relevant pointers to the elements of the list stored somewhere, then using them to do the insertions or deletions would be efficient. But what would be a problem that would be structured that way?
LRU cache would be such a case
I'm curious about the diagram at 1:02 was he explaining something with it on stream?
These criticisms of linked lists are usually based on certain assumptions of bad surrounding programming practices which make linked lists perform badly. Insert IQ bell curve meme.
The first assumption is that nodes will be individually dynamically allocated with e.g. malloc/free. In fact, allocating linked lists as a static array or on something like an arena allocator - potentially all at once, instead of individually per element - can eliminate not only tons of allocation overhead, but cache misses as well. If list elements are linearly allocated, cache coherence is very high, and you only have to worry about fragmentation as elements are shuffled around, contingent on your usage.
The next big assumption is that pointer traversal is inherently slow. Not so. As above, cache misses are the main cause of slow pointer traversal on modern hardware. Following a pointer to a location in cache is very fast.
There are a couple other related assumptions I'll point out - namely, the assumption linked lists are being used as generic containers, as non-intrusive linked lists, and that the element size is small. Generic containers are indeed not always an ideal use case for linked lists. Intrusive linked lists are also often more desirable. And the overhead is amortized somewhat when you are using larger elements, such as game entities, versus having a generic linked list of small elements like integers.
If you keep all of this in mind and use linked lists tailored to your specific use case, with allocation patterns that aren't stupid, you will get dramatically better performance out of them. Even fragmentation, which slows them down significantly due to cache decoherence, usually indicates usage patterns that vectors/arrays are very poor at (lots of insertion and removal from the middle).
Here is a good writeup by Ryan Fleury of the case for linked lists:
open.substack.com/pub/ryanfleury/p/in-defense-of-linked-lists
I've read this article and it's a whole lot of nothing… Basically, the author says all standard implementations of linked lists are bad, lists a lot of troubles with linked lists, and says you can solve them (at least some of them like cache misses) by making them less of a linked list by clumping multiple data in a single node. Another warning flag for lined lists not being all that cool is that he advises to handcraft an implementation of each linked list based on the circumstances, use a bunch of tricky optimizations, and all that without any confirmation in a form of benchmarks that it's actually faster in a real world scenario. Apparently rather than citing sources or producing working examples, it's easier to criticize other people for not being scientifically rigorous, even though all they do is express very reasonable skepticism, e.g. to the "there is also no guarantee that nodes have any locality in memory" the author responds with "this is not a well-formed nor meaningful criticism of linked lists, because it is assuming concrete information (namely, how linked list nodes are allocated)" - NO, IT IS NOT ASSUMING! It doesn't say there is no locality, it questions it's reliability. That example is probably the biggest offense to logical reasoning I found in this article, and I wonder how much more absurd is hidden there in the convoluted reasoning, that I didn't care to completely unwrap - nor did the author care to thoroughly explain, even though he aims this to be a defense towards the beginners, who are allegedly mislead by linked-lists-critics.
All in all, a whole lot of mental masturbation all just to unconsciously DISPROVE one's own thesis. Sorry for the hateful attitude, but with the little actual merit of the article and unjustifiably confident tone, it could as well be some GPT generated text.
There are two more aspects that didn't get mentioned:
(1) In order to end up with a neat compact array/vector you either need to know the total amount of elements, or you'll end up having to increase your capacity if you run out of free slots. And at the very end you either have to compact your array or live with having unused slots.
(2) Arrays are easy if the only thing you have to worry about are elements of the exact same type - a.k.a elements that have the exact same size. That however is usually not the case with random objects. That's the same issue relational databases have with text-based columns. You either restrict the application to strings of fixed size and by that waste unused space, or you use pointers to text content of arbitrary size.
["If list elements are linearly allocated, cache coherence is very high"]
Do you perceive the stupidity of this, right? If the point is to keep the memory contiguous then linked lists , they render to be useless. You use a linked list because of the constant time insertions/removals so you will still end up in the same problems as you have with normal heap-based linked lists.
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)
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?
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.
"Head removal probably wins in a linked list"
Use a std::deque.
There are very few reasons to use std::list.
on team don't use list
What diagramming/drawing app is this?
These are the videos I like, where he gets out the chalk board
Inserting integers into a sorted sequence is literally the purpose of a family of datastructures called heaps...
Didn't notice this turning into a education channel...
EDJACASHUN!
When I first heard about big O and linked list I couldn't understand why everybody ignored the fact that you have to get there before removing or inserting something. Why is that process ignored?
It's ignored because they assume you have access to the node you care about in the linked list without having to traverse the list. Maybe not the most realistic assumption, but not entirely unreasonable IMO.
Because you usually insert via reference, not by index. If you know the item left or right to it, you just reset 2 pointers.
@@jeffu92 sounds like a weirdly selective way of looking at the "worst case scenario", but hey, my background is mathematics so maybe i'm reading too much into it
Because insertion in a linked list is defined as taking as arguments the previous node and the node you want to insert. With those 2 parameters, insertion is O(1). If you don't have the previous node and you need to perform a search for it, that's a different operation.
There are really three different operations: insert at position, insert before id, and insert after id. For linked lists, a pointer to the element, is its id. Whereas for arrays, you need to store a separate id as data in the element (unless you can guarantee that the element will never move - that is, no item will be deleted or added before it - , in which case you can use the position as the id).
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.
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
I’ve seen a node server handle 7000 concurrent connections. Need better engineers :)
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.
Don't use either a vector or a list if your average linear search is dominating. Use a tree.
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.
Doesn't it vary from processor to processor?
Though I do enjoy hearing "always use a vector unless you can prove a map is faster"
At 5:36 i have started screaming "B+ Trees, goddamit!". It is an unrolled linked list with a tree as a search index assistant.
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
My dude, your course is pure gold. I very nearly spit out my coffee when you randomly chose 69420
What software are you using?
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.
Why is there an assumption that it is a contiguous memory space? What if... its 16mb on a z80 based system 16kb banked into the main 64kb at a time where 48kb other main memory also exists?
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...
...I'm only halfway through, but whyfor not having compared with skiplists?
I don't use vectors because I'm not a filthy C++ programmer. I use arrays. All arrays all day.