22 ms·

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

• dmitrygr 4y ago
  Modern CPUs detect patterns of pointer chasing common in linked list use and prefetch to cache just fine. Your comment would have been valid a decade or more ago. And plenty of use cases are much better with linked lists than resizable vectors. Eg: queues.
  • vbezhenar 4y ago
    RAM latency is huge. No amount of prefetching can fix that. If anything, prefetching works better with arrays as RAM reads multiple bytes at once.
  • xxs 4y ago
    Queues are best implemented with a pow2 cyclic array, and you have a free deque, too.
    • attractivechaos 4y ago
      A ring-buffer based queue is mostly better than a linked list but it is not necessarily the best. The typical STL deque implementation [1], with all its complexity, is usually faster than a ring buffer. [1] https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl https://stackoverflow.com/questions/6292332/what-really-is-a...
  • Borealid 4y ago
    I think there's more to cache locality than prefetching. In an array, consecutive elements will be usually be adjacent in physical memory (excepting page boundaries ), so each cache line load where a cache line is larger than the array element will "overfetch" into the next element. This should mean fewer total cache loads and thus more efficient use of memory bandwidth for situations where it is constrained (such as walking a list).
    • AstralStorm 4y ago
      Then again, if you have control over allocations you can prefetch whole chunks of data to which the list refers making this point moot. Often lists refer to arrays or sections of memory. The performance loss if any appears in bigger structures where you do want to have explicit control anyway.
  • howinteresting 4y ago
    For most use cases a ring buffer either with or without a maximum length will do much better as a queue than a linked list will. There are some niche use cases where linked lists are good. Lock-free queues are one, and another big set of use cases is where you need hard O(1) insert even with a high constant factor, not amortized O(1).
    • anonymoushn 4y ago
      High-performance SPSC queues are always implemented with an array. If you need hard O(1) insert you can usually just allocate an array much bigger than you will need. The combination of hard performance requirements and willingness to wait for an allocator all the time is unusual.
    • gamegoblin 4y ago
      The place I see linked lists pop up the mosts are when implementing LRU caches. You need a linked hashmap of sorts where the hashmap gives O(1) lookup to the linked list node in question, and then you can extract that node and move it to the head of the queue in O(1) as well. This is a special case of where they also appear: linked hashmap implementations, where you want a hashmap that has a consistent iteration order.
      • josephg 4y ago
        I’ve seen them show up in lots of situations through intrusive lists, which I think is the general form of the example you’re giving. Intrusive lists are used in the Linux kernel, in physics engines (eg Chipmunk2d) and game engines. The way Redis uses them for TTL expiry follows the same pattern.
      • xxs 4y ago
        Having linked nodes of a hashmap, is just that - I'd not call it a linked list. You can do moving median with a binary tree and linked nodes, too.
    • xxs 4y ago
      >where you need hard O(1) insert even with a high constant factor You will need a truly concurrent memory allocator for that, too... or if you are just the kernel (one of the reasons the linux kernel can benefit from linked lists) Overall, allocating new objects/memory is not guaranteed O(1).
  • spijdar 4y ago
    There are a lot of factors involved, but given a limited number of cache lines that can be stored in low level cache, I would think there'd be at least some performance penalty for prefetching from non-linear blocks of memory vs the inherent spatial locality in an array/vector, if only because it'd cause more old cache to be evicted.
    • AstralStorm 4y ago
      Or the opposite, prefetching a whole vector when you just need one item, evicting more than needed unnecessarily. There is a reason why non-embedded CPUs have sizable L2 caches now.
  • colinmhayes 4y ago
    Queues are generally implemented with with a vector of pointers to vectors. Nicely diagrammed here https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl https://stackoverflow.com/questions/6292332/what-really-is-a... Ring buffers also work better than linked lists
    • waynesonfire 4y ago
      is Erlang and JDK general enough for you? Oh, both use linked lists, https://github.com/erlang/otp/blob/master/lib/stdlib/src/queue.erl#L55 https://github.com/erlang/otp/blob/master/lib/stdlib/src/que... https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/concurrent/LinkedBlockingQueue.java https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...
      • xxs 4y ago
        why would your refer LinkedBlockingQueue? You have ArrayBlockingQueue, too. ArrayDeque is just better than LinkedList.
  • anonymoushn 4y ago
    Even if your linked list is backed by an array and all the elements are right next to each other, computing some cheap function of the elements of a linked list is incredibly slow compared to the alternative because of the unnecessary and very long dependency chain. Vectors are basically perfect for queues.
  • optymizer 4y ago
    I'm going to call you out on this one, because it's a bold claim, and I'd love to see an explanation and some perf numbers. For example, I'm wondering how the CPU knows what the next item in the list to prefetch it. Unlike the next item in an array, list items could be pointing anywhere in process memory. Also, what counts as a modern CPU in this context? Are we talking latest generation desktop CPUs from Intel, or anything after Core 2 Duo? How about mobile devices with ARM CPUs? Would those just be ignored? Is there a benchmark?
    • dmitrygr 4y ago
      Feast your eyes on the "Intel® 64 and IA-32 Architectures Optimization Reference Manual": https://cdrdv2-public.intel.com/671488/248966_software_optimization_manual.pdf https://cdrdv2-public.intel.com/671488/248966_software_optim... (newer link, as requested by one of the child comments) It details the prefetchers, how they work, what patterns they recognize (section 3.7)
      • deleted 4y ago
        [deleted]
      • forrestthewoods 4y ago
        My benchmarks say you’re wrong. https://www.forrestthewoods.com/blog/memory-bandwidth-napkin-math/ https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...
        • dmitrygr 4y ago
          You're joking right? "I made an extra test that wraps matrix4x4 in std::unique_ptr." And that is your test? One piece of code? Not even presenting disassembly? Who the hell knows what your compiler wrought in response to your "std::unique_ptr" and "matrix4x4" ?
          • attractivechaos 4y ago
            Sorry for my ignorance – linked list matching the performance of vector is something new to me. I would like to learn more. The best way to prove your point is to show us a benchmark. However, I couldn't find one with a quick google search.
  • tylerhou 4y ago
    I have some experience using/modifying linked-list benchmarks (https://github.com/google/multichase https://github.com/google/multichase) specifically to test memory latency. It is extremely difficult, maybe impossible, to design a prefetcher that can predict the next cacheline(s) to prefetch while traversing in a linked-list. I am not aware of a single CPU that can do this consistently. For instance, if you run multichase (a linked-list chaser) on GCP servers, you generally get the expected memory latency (~70-100ns, depending on the platform).
    • AstralStorm 4y ago
      Why let the CPU guess when you can tell it what you want? (Prefetch a small arena of objects linked to by the list.)
  • deleted 4y ago
    [deleted]
  • gpderetta 4y ago
    Even with a perfect prefercher a linked list would still be slower to iterate than a vector as it is inherently serial (unless your CPU does address prediction and I don't think any CPU does).
• waynesonfire 4y ago
  • andrewmcwatters 4y ago
    Would you like to explain to the class?
    • deleted 4y ago
      [deleted]
  • klysm 4y ago
    Care to demonstrate why? I have the same experience
    • waynesonfire 4y ago
      the linked list has a wonderful capability that's frequently seen in C where you can do O(1) removal from a list. E.g. you can have an "object" detach itself. This is not possible in Java's standard linked list implementation, among other languages. in general, inserting and removing elements from a vector requires a memory copying. There are programming languages that have linked lists as their fundamental data structure, like Lisp and Erlang. For situations where I don't need random access, linked lists are hard to beat. Linked lists also make wonderful immutable data structures. linked lists have wonderful filter and flatmap performance. how much memory copying would a vector require?
      • klysm 4y ago
        Yes, but in practice the coefficients on the O() almost always end up working in the dense arrays favor because of memory locality.
      • suremarc 4y ago
        This is assuming you already have a pointer of the element you're removing, or a neighbor thereof. Otherwise, you'd have to traverse a portion of the linked list, which has a significant amount of per-element overhead.
• layer8 4y ago
  That depends on the number of elements and the size of the payload data. Both approaches can be combined by using a linked list of arrays.
  • marcosdumay 4y ago
    Yes. There is a reason why it's hard to create either a bare linked list or a bare array on modern language. It's because both are bad extremes, and the optimum algorithm is almost always some combination of them.
• pfdietz 4y ago
  Compacting garbage collectors put linked lists into nearby memory.
  • josephg 4y ago
    Even if memory was packed by a GC, linked lists still have to pay the cost of allocating and garbage collecting every cell of memory individually. I doubt a GC would solve linked lists’ woes. Do you have some benchmarks demonstrating your claim?
    • throwawaymaths 4y ago
      Erlang GC is pretty good, plus there are some nice highly local allocators
      • josephg 4y ago
        Be that as it may, it'll still take a benchmark to convince me.
    • Jach 4y ago
      There are also prefetch instructions. I listened to https://www.youtube.com/watch?v=SetLtBH43_U https://www.youtube.com/watch?v=SetLtBH43_U recently (transcript: https://signalsandthreads.com/memory-management/ https://signalsandthreads.com/memory-management/), part of it talked about some work in OCaml's GC. > ...each individual memory request that’s not in cache still has to wait the full 300 cycles. But if we can get 10 of them going at the same time, then we can be hitting a new cache line every 30 cycles. I mean, that’s not as good as getting one every 16 cycles, but it’s close. You’re actually able to get to a reasonable fraction of the raw memory bandwidth of the machine while just traversing randomly over this huge one gigabyte heap https://github.com/ocaml/ocaml/pull/10195 https://github.com/ocaml/ocaml/pull/10195 shows the change adding prefetching to the marking phase (https://github.com/ocaml/ocaml/pull/9934 https://github.com/ocaml/ocaml/pull/9934 was done earlier for sweeping). There are some benchmarks in the thread/linked from the thread.
• huhtenberg 4y ago
  > almost always As any generalization this one too is, of course, incorrect. Outside of the realm of academia, the need to keep data pieces in several containers at the same time, with no heap operations on insertion or removal and O(1) removal is very common, especially in the kernel space and embedded contexts. The only option that fits the bill - you guessed it - are the linked lists.
  • nostrademons 4y ago
    Note that this (and the article) describes an intrusive linked list. Extrusive linked lists (like you might see in a class library or CS 101 project), where the node structure is heap-allocated separately from the data that it points to, have very few practical advantages over vectors, which is why standard libraries are increasingly defaulting to vectors even when the class is named "list".
    • majjgepolja 4y ago
      Is there a difference between intrusive and extrusive list when the member type is a struct (value type)?
      • nostrademons 4y ago
        Yes. An intrusive list puts the pointers to next & prev in the struct itself. IntrusiveList<Member>::iterator is a Member*, then member->next points to another Member*. An extrusive list puts the pointers in a separate node structure, which then has a pointer to the actual member type. ExtrusiveList<Member>::iterator is a ExtrusiveListNode<Member>*, node->next points to another ExtrusiveListNode*, and you access the actual Member* with node->data. Basically it's a double indirection. The advantage of extrusive linked lists is that you don't need to modify the data layout of Member at all. All the linked list manipulation happens on ListNodes, which have a pointer to the actual member, which can be accessed with just a cast. That's why they're so well-suited to class libraries: you can easily write a generic ExtrusiveLinkedList that works with any data that can be represented with a pointer, hide all the traversal (and the existence of individual ExtrusiveListNodes) in accessor functions, and present a simple API with no codegen or modifications to Member. The advantages of intrusive linked lists are 1) performance 2) no heap allocations 3) easy traversal when given a Member*. It's only a single indirection rather than a double, and usually that indirection is necessary anyway to avoid copies. Insertion and deletion are just pointer manipulation; you don't need to allocate new space for the nodes. Oftentimes your functions will take Member* anyway, and it's nice not to take or traverse the container if you just need to peek at the next element coming up. The point of this subthread is that intrusive linked lists have very clear use cases in the kernel & embedded spaces, where these advantages are often critical. Extrusive linked lists, however, have very few advantages over vectors (which also require heap allocation but are more cache & locality friendly). In a common business app responding to user input, the difference between O(1) amortized and O(1) is negligible; you can eat the occasional pause for a vector resizing, because the user isn't going to care about a few milliseconds. They both require heap allocation. The vector will give you much faster traversal, because subsequent reads all hit cache. The vector takes less memory (1 pointer per element, with a max of 50% overhead, while an extrusive doubly-linked list is 3 pointers per element). There's just little reason to use an extrusive linked list because the use-cases where intrusive linked lists are not better are precisely the same ones where vectors are better.
• tylerhou 4y ago
  If you're iterating, sure, use a vector. If you're pulling from a queue and doing a lot of processing, maybe an RPC -- does the ~70ns memory latency hit really matter that much? Probably not.
  • kibwen 4y ago
    Why impose that latency if you don't need to? It costs me nothing to reach for a vector instead.
    • AstralStorm 4y ago
      Costs you a dynamic memory allocation, code overhead and higher memory use. There are good reasons why std::array and plain arrays exist. Vectors are for when your data is unbounded, which is actually a risk most of the time. For truly big data, you want a special structure anyway.
    • tylerhou 4y ago
      Without extra work you can’t use a vector like a queue, and a circular buffer doesn’t necessarily support all types and/or preserve iterators on insert. Could use a deque, a blocked linked list. But IMO list is fine if it’s not clearly a bottleneck.
  • pornel 4y ago
    If you're pulling from a queue use a ring buffer.
    • AstralStorm 4y ago
      Sometimes. Depends on whether you are filling in a data buffer or trying to send an already calculated data buffer. A standard ring buffer does copies/fill. A ring buffer of pointers has similar performance characteristics to a linked list.
    • Phelinofist 4y ago
      OT but does anyone know a general purpose ring buffer implementation for Java?
• jalino23 4y ago
  by vector you mean regular js arrays?
  • josephg 4y ago
    Broadly yes, C++‘s vector is the equivalent of JS arrays. But the javascript array type is much more complicated. It intelligently changes its internal structure based on how you use it - which is pretty wild.
    • andrekandre 4y ago
      nsarray (objective-c) also does something similar https://news.ycombinator.com/item?id=2413656 https://news.ycombinator.com/item?id=2413656 (sadly the article link is dead)
    • LecroJS 4y ago
      Would you mind elaborating on js arrays intelligently changing their internal structure based on use? My background is only JS/Python and have never touched C++ so I don’t have the context of how these differ.
      • josephg 4y ago
        A c++ vector internally uses an array - which is a chunk of memory where each item is just in the next spot in memory in sequential order. Eg, the array [1,2,3] might have 1 at memory address 100, 2 at memory address 101 and 3 at memory address 102. Given an array index, you can figure out where a value is stored in memory pretty trivially. When the array fills up, vector will allocate a fresh array (thats bigger - often 2x bigger) and copy everything over. This is slow - because it has to copy everything. But much faster than you think. So thats how C++'s vector (and Rust's Vec) work. Javascript implementations (like v8) can swap out the implementation behind the scenes based on how you're using your array. The API is always the same - but the way the array works in memory will be different based on whatever is fastest given the way you're using your array. (V8 doesn't know ahead of time what sort of data will be in your array or what you're using it for, so it guesses then changes things up if it guesses wrong). Here's a blog post talking about some of the internal details in V8: https://itnext.io/v8-deep-dives-understanding-array-internals-5b17d7a28ecc https://itnext.io/v8-deep-dives-understanding-array-internal... The actual implementation is much more complex than this blog post suggests. (I think they also optimize based on push/pop vs shift/unshift vs other stuff).
• bjoli 4y ago
  While I generally agree with you, I have had multiple occasions where amortized O(1) was unacceptable, whereas the overhead of linked lists was ok.
  • eru 4y ago
    You can make dynamic arrays have worst case O(1) at the cost of some extra overhead.
    • bjoli 4y ago
      Copy the array on every append? :)
      • Slasher1337 4y ago
        That would not be O(1), but O(n) per insert.
• jstimpfle 4y ago
  That works if the data that you want to put in the sequence is copyable (doesn't have "identity"), or if you can arrange so that it gets created in the right spot from the start and you can always choose the iteration order to be sequential in memory. For many more complex structures, that is not the case.
  • ay 4y ago
    Could you give an example of a data that is uncopyable ? A struct witj self-referential pointers ?
    • AstralStorm 4y ago
      If the data is relatively big buffers, you really do not want to copy them. Your memory bandwidth will thank you, and performance will vastly increase. Cache locality will be good anyway since you're referring to long blocks.
      • ay 4y ago
        This kind of data structure often has a buffer + associated metadata. If the metadata+pointer fits into 1-2 cache lines, storing it in a vector can give be win vs. storing the next/prev pointers next to data + metadata. In any case, there is always only one authoritative answer: “perf top”. :)
    • hither_shores 4y ago
      It's about the meaning, not the raw bits. I might be able to duplicate your signature, but that doesn't mean I can sign documents for you.
    • jlokier 4y ago
      Example: Any object shared among multiple lists or other data structures at the same time, or directly pointed to by other objects, such that any of those views must reach the same cheaply mutable state. This includes objects in the object-oriented programing (OOP) model, actors in the actor model, and file objects in a kernel which are in multiple lists. For those you have to store object pointers in the vector, instead of copies of the objects. That works and is often done, but it defeats or reduces the cache locality perfornance improvement which motivates using a vector in the first place. On an in-order CPU an intrusive list (pointers inside the objects) can be traversed faster than a vector or B-tree of object pointers, though a non-intrusive list (list of nodes containing object pointers) won't be faster. On an out-order CPU with heavy speculative execution it is less clear cut because the vector allows successive objects to be dereferenced speculatively in parallel to a limited extent, while this is not possible traversing an intrusive list. If the list is going to be traversed looking for objects based on some filter criterion such as flags or a number comparison, based on non-mutable state (or where it's ok for mutation to be expensive), traversal can be sped up by storing criterion data in the vector alongside the pointers, or in a second vector, to avoid dereferencing every touched object pointer during traversal.
• Smaug123 4y ago
  Nobody has mentioned immutability yet - linked lists are easily used as one of the simplest immutable persistent data structures. Your definition of "better" appears to be solely about keeping the CPU burning, but if CPU isn't the bottleneck, I prefer "immutable linked list" over "clone a vector many times" merely on aesthetic and reason-ability grounds.
  • gleenn 4y ago
    Or you could go the Clojure route and do the tree-style immutable vectors where the cost is log32(N) for most operations, small enough in all the relevant operations, and you get the amazing usability of immutable data structures that are performant enough in most cases.
    • kazinator 4y ago
      How does that scale down to small sequences of under ten items?
      • Jim_Heckler 4y ago
        an array is used for the last 1-32 elements of the vector (the "tail") so there would be no trie at all, just the tail
  • mst 4y ago
    cons cells are a local maximum. often they're sufficiently maximal.
  • yongjik 4y ago
    Well, of course if a solution is "cloning a vector many times" then arguably you're using the vectors wrong - in which case it's totally appropriate to find a different data structure (or a better way to use vectors, if possible).
  • dan-robertson 4y ago
    In C where using the simplest data structures is valuable, you’d likely do much better by upgrading your programming language to something that offers a better data structure. If you’re using a higher level language where you can abstract details about your sequence data structure, I think there’s very little benefit to using the simplest data structure and you should instead have widely used libraries that offer a good immutable sequence type, e.g. RRB trees. One exception is ML style languages where singly linked lists get a big syntax advantage (Haskell only half counts because most of its lists are really just iterators). I think this was, in hindsight, a mistake for a widely used language. It’s also a source of pointless pain for learners (eg I don’t think there’s much benefit to people having to write lots of silly tail-recursive functions or learning that you have to build your list backwards and then reverse it). Another exception would be some lisps where lists are everywhere and the cons-cell nature of them makes it hard to change.
• andirk 4y ago
  Understanding, and even sympathizing, with the machine's toil re: vectors vs manual linked list can separate a good engineer from a great one. We learn linked lists, assembly, and even machine code in Computer Science majors so that we know what's happening under the hood and can more easily surmise the runtime effects.
  • kibwen 4y ago
    All of these are indeed important, and will eventually (one hopes) result in the student realizing that linked lists are to be avoided because of their poor mechanical sympathy resulting from their awful cache locality. Valid uses for a linked list are extremely niche. Yes, you can name some, and I can name several valid uses for bloom filters. Just because a simple linked list is easy to implement does not mean it should be used, any more than bubble sort should be used for its simplicity.
    • throwawaymaths 4y ago
      Wait why do linked lists have bad cache locality? It depends on how your heap is set up. For example, you could have an allocator that gives relatively good locality by having high granularity and only bailing out if say your LL gets super long (so if your lists are usually short, they could have awesome locality)
      • AstralStorm 4y ago
        If you are in that place, you're probably using a linked list over small statically allocated memory, but you still need random ordering and fast remove or reorder.
      • duskwuff 4y ago
        That only works if you allocate lists all at once and never modify them. If there are any other allocations taking place at the same time -- say, allocations from other threads, or for other data you had to create while building the list, that locality is shot. Same goes if you insert more elements to the list later, or if you perform an operation which changes its order (like sorting it).
• dragontamer 4y ago
  > regular resizable vector At gross complexity / fragmentation / to your memory allocator. Linked Lists are definitely easier to use if you're ever in a position where you're writing your own malloc(). The infrastructure needed to cleanly resize arrays (and also: the pointers all going bad as you do so) has a lot of faults IMO. EDIT: In particular, linked lists have a fixed size, so their malloc() hand-written implementation is extremely simple.
  • ay 4y ago
    Doubling the vector size each time it needs to be enlarged takes care of fragmentation/memory overhead, in practice. Or preallocating if you know the rough size. It does take some discipline to avoid the storage of pointers, but once you get used to that it’s quite fine. Source: I work on VPP, which uses vectors quite extensively.
    • saagarjha 4y ago
      Usually you want a smaller growth factor than that to allow for more reuse. (Also: what’s VPP?)
      • ay 4y ago
        I use doubling because it’s simple to reason about and hard to screw up the math. What kind of growth factors heuristics worked for you the best ? VPP: rather fast user mode dataplane. https://fd.io/ https://fd.io/ is the “marketing” site. https://wiki.fd.io/view/VPP https://wiki.fd.io/view/VPP is the “less flashy” dev wiki.
        • Kranar 4y ago
          The optimal growth factor is the golden ratio (1.6), in practice many vectors use a growth factor of 1.5. The reason for not going above the golden ratio is that it prevents any previously allocated memory from ever being reused. If you are always doubling the size of your vector, then it is never possible to reclaim/reuse any previously allocated memory (for that vector) which means every time your vector grows you are causing more and more memory fragmentation, as opposed to using a growth factor of 1.5 which results in memory compaction.
• im3w1l 4y ago
  One data structure I recently found myself wanting is a tree-based "array", with O(log n) access by index / insertion anywhere / deletion anywhere. Kinda weird how rare it seems to be.
  • Munksgaard 4y ago
    That sounds like a pretty run-of-the-mill balanced binary tree? Rust has a BTreeMap: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...
    • vanviegen 4y ago
      Inserting into an array increments the indexes of all subsequent values. How would a regular BTree emulate that behavior?
      • AstralStorm 4y ago
        It would rebalance on insert with O(log N) performance but chunky constant factor, keeping the ordering so access by index is also O(log N) with low constant factor... Which is why usually you would use a red-black tree rather than a BTree, as it has much lower constant for insertion and access by index. However higher for traversal in order.
  • vanviegen 4y ago
    That does sound useful, although I'm having some trouble thinking of what for exactly. :-) And indeed, I don't recall seeing something like that. At a first glance O(log n) seems easy to do in the average case, but perhaps not in the worst case.
    • socksy 4y ago
      I suppose it's quite similar to the idea of Bagwell's persistent data structures[1] — those are particularly useful for lock free coding and with a high enough branching factor could be not as much overhead as a linked list or just plain copying. [1] https://hypirion.com/musings/understanding-persistent-vector-pt-1 https://hypirion.com/musings/understanding-persistent-vector...
• imbnwa 4y ago
  I've always wondered why GSAP and CreateJS both rely on linked lists for sequencing animations
• nraynaud 4y ago
  I think a lot of graph edits are a nightmare to perform with an adjacency list, and a breeze when you just edit linked pointers. Imagine the Euler Operators on a manifold (ie a 3D mesh) or on a planar graph, but on a vector instead of on a DCEL.
• sqrt_1 4y ago
  Here is a performance graph on removing items from a vector vs list - slightly old (2017) https://github.com/dtrebilco/Taren/blob/master/Articles/iter_listcmp100.png https://github.com/dtrebilco/Taren/blob/master/Articles/iter... From the article https://github.com/dtrebilco/Taren/blob/master/Articles/EraserProfile.md https://github.com/dtrebilco/Taren/blob/master/Articles/Eras...
  • devmunchies 4y ago
    That is removing an item at N index, right? (that's why it talking about iterators?) Linked lists are only fast at append/pop with the first node.
• hintymad 4y ago
  Isn't linked list the fundamental data structure for LISP? The sweet memory of cons() this and cdr() that are all backed by linked list?
  • ww520 4y ago
    Cons can build a tree, though it can certainly build a list. (a1 (b1 (c1 c2 c3) b2 (c4 c5)) a2 a3) is a tree.
  • tialaramex 4y ago
    So, two things. One: 1980s machines don't have the memory access performance you see today. If N list chase operations takes the same time as N sequential reads then the linked list has the nice properties you were probably taught in school and actual in-memory representation of a linked list is a good choice. On today's machines that list chase might incur a sizeable cache stall, making it thousands or even tens of thousands of times slower. Two: Lisp doesn't actually care whether there are literally linked lists behind everything. Today you would use a different data structure reflecting the hardware you have.
    • pjmlp 4y ago
      Not only today, since the mid-70's, yet somehow many keep thinking List only has lists.
    • _19qg 4y ago
      > 1980s machines don't have the memory access performance you see today They had similar problems. CPU with tiny caches <-> caches <-> expensive RAM in the range from 500kbytes to a few MB <-> virtual memory paging to slow disks. For example a typical Lisp Machine might have had 20 MB RAM. But the Lisp image it ran was probably already much larger. Thus paging spaces upwards from 60 megabytes were not uncommon. I had a Lisp Machine with 40 MB RAM and have used > 200 MB paging space. Disks were very slow. Were are talking about ESDI (2.5 Mbyte/sec or less) interfaces or later 5-10 Mbyte/sec SCSI 1 and 2. I had a 600MB ESDI disk inside a 1 MIPS Lisp Machine with 8 Megawords RAM of 36bit memory + 8 bit ECC. Thus locality plaid an extremely large role for usable performance. In the early days machines had to be rebooted when they ran out of memory, since a garbage collection could take a long time. Rebooting a machine was just a few minutes. Doing a full GC over 200 MB virtual memory could take half an hour. When I was making a new Lisp image (called a world), the size was upwards 50MB. 100 MB was common. A special command ran for roughly 30 minutes and reordered the objects in main memory to improve locality. The another command saved the image - which took also tens of minutes. A big breakthrough in usability came with the introduction of the Ephemeral Garbage Collector, which only touched RAM and took care of the short lived objects, with some hardware support to identify and track RAM pages with changed content. Features back then were: * cdr coded lists which were allocated like vectors * lots of other data structures like vectors, n-dimensional arrays, hashtables, records, objects, ... * an ephemeral garbage collector with hardware support tracking changes in RAM pages * incremental garbage collection * a copying/compacting generational garbage collector with type sorted memory regions * cooperation between the garbage collector and the virtual memory pager * various manual or semi-manual memory management facilities * incremental memory image saves The main reason to develop Lisp Machines in the end 70s was to get Lisp development off of time-shared computers (with limited shared RAM and virtual memory) onto single user workstations, where RAM and virtual memory is not shared between different users. The same problem appeared then on UNIX machines, where Lisp systems often were among the most memory hungry programs -> thus they needed lots of RAM, which was expensive. Thus a lot of virtual memory was used. But access to Lisp objects in virtual memory was much slower than Lisp objects in RAM. It took many years to have competitive GCs on those machines. When RAM got more affordable and larger, things improved.
• kabdib 4y ago
  The first week into my prior job, I had to fix an in-production bug involving quadratic vector growth that was tipping over servers. The vector implementation guaranteed too much, namely consecutive memory layout (which wasn't needed, and if we had needed it, it would have been a mistake). Decomposing that vector into recursive subvectors solved the problem. Going from a few tens of millions of elements in a single contiguous vector (with consequent -- and bad -- heap fragmentation!) to nested vectors with a few thousand elements each brought us back online again. Which is to say: Vectors are nice. Lists are nice. Use appropriate data structures for your scale, watch your semantic dependencies, and don't get hung up on dogma.
  • mst 4y ago
    The VList paper - which I archived at http://trout.me.uk/lisp/vlist.pdf http://trout.me.uk/lisp/vlist.pdf to avoid having to google the bloody thing every time - is an interesting hybrid.
    • GeorgeWBasic 4y ago
      Thank you for that. That's a concept I remembered reading about, but I couldn't remember the name and had no way to find it again.
      • mst 4y ago
        trout.me.uk/lisp/ and trout.me.uk/gc/ are both basically archives of "stuff I knew I'd suffer that problem with" and it's a pleasure every time the contents come in handy for people who aren't me. Also back when I was still pretending to be a mathematician I used both GWBASIC and UBASIC for assorted purposes so thank -you- for the nostalgia kick.
    • simplotek 4y ago
      Thanks for referring to the article. Great read!
      • mst 4y ago
• chrisseaton 4y ago
  > almost always, whatever problem you're trying to solve would be better done with a regular resizable vector Resizing a vector brings the whole of it into cache, potentially dragging all of it all the way from actual RAM. Prepending an entry brings nothing into cache. Cache is king.
  • KerrAvon 4y ago
    So use an array deque if you need O(1) prepending.
    • chrisseaton 4y ago
      Resizing the array in the array dequeue brings the entire thing into cache. That's a disaster.
      • kragen 4y ago
        It's a disaster but it's an amortized O(1) disaster.
      • CyberDildonics 4y ago
        It's far from a disaster because the best way to deal with a list is still to use a contiguous array. Allocation isn't free. You have to do it sometime and doing it all in bulk is going to have the same consequences as just one small allocation anyway. If you are mapping new pages into main memory, making system calls or looping through a heap structure, you're not only affecting the data cache but also the TLB while also pointer chasing. Making a list out of an allocation for every element is performance suicide on modern computers. Even the amortized resizing of an array is done at the speed of memory bandwidth because of the prefetcher. Thinking that is some sort of performance hindrance is absurd because it outweighs the alternative by orders of magnitude. If there really are hard limits on the time every insertion can take, then the solution needs to be links of large chunks of memory to still minimize allocations on every element.
        • 4y ago
• manv1 4y ago
  It's surprising people are arguing about this. That fact alone shows that lots of developers don't understand the relationship between L1/L2 cache, data access patterns, and how prefetching works. That makes sense, given how abstract things have gotten. Decades ago there was an article that showed the penalty for non-linear data access was massive. That was before speculative access, branch prediction and cache prefetching were standard features. The performance hit today would be even more (except presumably for machines that have implemented the speculative execution security mitigations).
  • couchand 4y ago
    As with any such subject, it's worth discussing the details but probably not the generalities really (except perhaps in the whimsical style of antirez). You're right to point out that given the performance characteristics of most modern CPUs, accessing memory linerally is optimum. But it doesn't necessarily follow that all collection data structures should be stored as a vector. Consider a collection traversed very slowly relative to the overall computation. There may not be any cache win if the line's always evicted by the time you come back to it.
    • fiddlerwoaroof 4y ago
      I’ve always wondered about whether you could have your cake and eat it too with linked lists where nodes are allocated in contiguous blocks of N nodes. So, the normal case of traversing the next pointer is not a discontinuous memory access.
      • tsimionescu 4y ago
        That's quite likely to happen to a linked list when using a compacting GC (such as Java's or C#'s generational garbage collectors) (assuming the elements of the list are only reachable from the preceding element, not from many other places as well).
        • fiddlerwoaroof 4y ago
• sgtnoodle 4y ago
  I often write code destined to run on a microcontroller, and linked lists are great for avoiding dynamic memory. It's nice to be able to statically or transiently allocate storage without having to bound the size of anything. Of course, the same unintuitive tradeoffs tend to apply even if there isn't much caching to worry about. A trivial linear iteration is often faster than a more elaborate algorithm when the input is small.
  • bitexploder 4y ago
    Carmack is a fan of this approach. Allocate some reasonably large number as your design constraint and if you start approaching it that is a time to ask why and is this data structure still reasonable here
  • KerrAvon 4y ago
    A memory-constrained microcontroller is actually one of the valid exceptions to the rule.
    • Sirened 4y ago
      Well, yes, and a lot of people treat kernel development as if they were developing for a constrained microcontroller. I don't think this is even a bad thing, we want the kernel to be as lean as possible because every page and cycle the kernel burns is one that users don't get to use.
      • jstimpfle 4y ago
        I suppose a more important reason is the "not have to bound anything" part. OS kernels almost definition don't know how many objects will be created. Implementing queues as vectors of pointers will require dynamic allocation and/or introduce many more failure points when going out of resources. With linked lists, once you have an object you can always append it to a linked-list queue.
      • Dylan16807 4y ago
        This is a memory vs. time tradeoff. And the time cost gets worse as the machine gets bigger. Designing for embedded is not the same thing as being lean.
• deleted 4y ago
  [deleted]
• osigurdson 4y ago
  >> This includes problems that they should be great for, like insert into the middle or the front. How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from? >> your default be a vector and not a linked list The default should be to understand the problem.
  • llbeansandrice 4y ago
    I think by “middle” they mean “at the current position” not at an arbitrary position in the middle when starting from HEAD
  • tsimionescu 4y ago
    > How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from? Both an array and a linked list are O(n) for adding in the middle. In an array, you finding the middle element is O(1), then moving the rest of the array is O(n) [you have to move n/2 elements]. In a linked list, finding the middle element is O(n) [you have to traverse n/2 elements], but adding it is O(1). So, asymptotically there is no difference. In practice though, the linked list traversal will cause O(n) cache misses to reach the middle element (since we are traversing random memory), while the array move will only incur O(1) cache misses (since we are accessing memory in order) - so, the array will actually win in practice. Edit: Note that I also don't know where the GP got the O(lg n).
    • osigurdson 4y ago
      It seems that the case where it is necessary to find the exact middle element and insert something wouldn't be very common but OK, I'll humor this use case. Let's assume that the list is huge and inserting at the middle is the only thing we do. Just maintain a pointer to the middle element and insert there: O(1) for find and insert. If it is necessary to add/remove at other places in the list, it is possible to maintain a doubly linked list and move the middle pointer back and forth accordingly (still O(1)). I suppose if the LL like structure is mostly read only with rare inserts, not that big and holds simple data types or structs and often needs to be read sequentially then an array/vector/list would be better than a regular LL but then it is obvious that an array is better anyway. It's poor guidance to tell people that the vector is the "go to" when you need a LL. Sad actually that this poor guidance has been upvoted by so many people such that it is the top comment, all in the name of some FUD about cache misses.
• halayli 4y ago
  if you can replace linked list with vector then you don't need a linked list and the two shouldn't be compared as it is almost always obvious when you need one over the other. Link lists are used in areas when there is a relationship between nodes like a list of running processes. one of the frequent operations is to remove a node from whatever position it's in and add it on either side.
  • Sirened 4y ago
    Right. Like there are so many algorithms that I shudder to think about how you'd implement them without linked lists. Like...how about a buddy allocator? Sure you could use a vector for each but you'd be copy and resizing huge swathes of memory constantly for very little gain. Use the right tool for the job!
    • tsimionescu 4y ago
      The thing is, the cost of copying memory is essentially the same as the cost of reading it, and linked lists force you to keep re-reading the same memory over and over (assuming random access). Adding an element in the middle of an array vs the middle of a linked list actually has the same asymptotic complexity (O(n)), but far better cache impact for the array (since moving a contiguous block of n/2 elements should only incur 1 cache miss, while reading n/2 randomly distributed nodes of the list will incur on average something like n/4 cache misses). Adding closer to the beginning of the linked list is faster, but adding close to the end of the vector is faster still, so overall with random access, the vector should win.
      • halayli 4y ago
        I think you missed the point here. You don't use link lists when you are going to walk the list and insert in the middle or some random place. The only time you end up walking a link list in typical scenarios is when you want to print them out or some unimportant operation. Link list is used to hold relationship between nodes and when you are operating on that node the common patterns are remove and add it to another list, or re-add it on either side. Take a look at bsd or linux source for inspiration. A process struct has more than dozen member variables of node* type because the object ends up being in several lists like sched, signal queue, child threads etc.
• WhitneyLand 4y ago
  I wish the word vector didn’t have so many different uses in science and engineering.
• eru 4y ago
  > Linked lists are great. But they have the problem that, almost always, whatever problem you're trying to solve would be better done with a regular resizable vector. One important exemption is when you want your datastructure to be persistent. See https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure But for many applications there are also better persistant data structures than linked lists around.
• xaedes 4y ago
  I learned to love linked lists as soon as I discovered that I can just store them in vectors to get the performance of guaranteed contiguous memory: // LinkedListItem[k]: item[k], prev[k], next[k] std::vector<T> item; std::vector<uint> prev; std::vector<uint> next; Similar is used in transparency rendering with per-pixel linked-lists.
  • anthomtb 4y ago
    Interesting idea but how does C++ guarantee contiguous memory for a vector? I just don’t see how a data structure with an arbitrary, dynamic size can also reside in a contiguous range of address space.
    • fnbr 4y ago
      When the array is resized, it’s moved to a new contiguous block of memory: everything is copied or moved over. See: https://stackoverflow.com/questions/8261037/what-happen-to-pointers-when-vectors-need-more-memory-and-realocate-memory https://stackoverflow.com/questions/8261037/what-happen-to-p...
    • frankchn 4y ago
      Simple, you just allocate a bigger contiguous chunk of memory and copy the entire vector over when the current chunk maxes out.
    • zabzonk 4y ago
      the size of a c++ object is fixed at compile-time
  • nynx 4y ago
    The performance of vectors comes from iterating through them and letting the cpu prefetch items before you need them. Random access in a vector doesn’t really get you that if the vector is larger than your L1/L2 caches, which linked lists would be in anyway if you used them recently enough.
• deleted 4y ago
  [deleted]
• theCodeStig 4y ago
  Assuming rust or other systems language. Linked lists are optimal for head access; not random access. For random access, yes a vector would be better.
• DeathArrow 4y ago
  Also, when in doubt, do a quick benchmark with different implementation.
• _19qg 4y ago
  what makes you think that list operations make the CPU jump randomly in memory and that implementors of, say, Lisp systems haven't optimized memory management for linked lists? A modern GC provides features generations, areas, copying and compacting. One a Lisp Machine from the 80s/90s the system saves a type sorted and locality optimized memory image, from which it later boots the Lisp system. Additionally to the typical GC optimizations (incl. integration with the paging system) it also provided CDR coding, which allocates lists as continuous memory. The GC also creates those CRD coded lists. CDR coding fell out of fashion in modern Lisp implementations, because the space and time savings aren't that great to justify the more complex implementation.
• djha-skin 4y ago
  This is only a problem with implementation of linked lists. The article talks about how linked lists are conceptual. They make a nice data structure to work with in code. But several ways could easily be conceived of that optimize them so that elements are adjacent to each other.
• ShredKazoo 4y ago
  Has there been any work on nudging the allocator towards putting all the nodes on the linked list on the same page? Or close together in memory more generally (to leverage the L1 & L2 caches)
  • tsimionescu 4y ago
    If you're allocating the entire linked list at once, that may well happen in practice. Otherwise, there is no good way it can happen automatically; but, compacting GCs will usually do this for you (assuming that the list elements are only reachable from the previous element).
    • ShredKazoo 4y ago
      Interesting thanks!
• acje 4y ago
  An underlying problem here is that we have come to favor computers that scales out the Von Neumann architecture with more cache coherent cores and more memory. If we take the path of hardware that implements smaller Von Neumann scales, and rather partitions smaller sets of cores and memory into actors that communicate with memssages we would get lower memory latency and less penalty from random access patterns.