12 ms·

Stop Using Linked Lists

128 points by aespinoza 13y ago

gamegoblin 13y ago
I feel like this could have perhaps mentioned the cases where one should use linked lists. Is a simple queue still implemented as a linked list? That is all I ever seem to use them for.
- theboss 13y ago
  A queue would be an excellent time to use a linked list. I don't understand the point of making a claim like this about a data-structure. The most fundamental thing in data-structures is that there is a time and a place for using each one. No data-structure is inherently 'better' than the others.
  - jhawk28 13y ago
    Based on the disruptor paper (http://disruptor.googlecode.com/files/Disruptor-1.0.pdf http://disruptor.googlecode.com/files/Disruptor-1.0.pdf) linked lists make poor queues also. Ring buffers backed by arrays are much better.
    - theboss 13y ago
      Very interesting, but I feel there is a difference of need here. You're right...there a Ring buffer with an array is better, but for average programmers a linked-list makes a damn good (maintainable, easy, understandable, and pretty quick) queue.
rayiner 13y ago
What stupid advice. Linked lists (and trees formed from lists) are a fundamental functional data structure. They have tremendous expressive advantages in functional code where operating on the head and the rest of the list leads to clear expression of an algorithm, and easy sharing of sub-parts makes certain other algorithms much more elegant. An example is maintaining the lexical environment as you're compiling a programming language. The first response might be to use something like a hash table. But then how do you handle shadowing (where an inner block shadows a variable of the same name in an other block)? A much cleaner way is to use an association list that's implicitly maintained as you recurse over the AST. E.g. in psuedo-Python: def parse_let(form, environment): (name, value) = parse_declaration(declaration_part(form)) return parse_body(body_part(form), acons(name, value, environment)) For those unfamiliar with Lisp, "let" introduces a new name bound to the value of an initializing expression, which is only in scope for the body of the "let" construct. Assume here that we're generating code from an AST and that the return value of a parse function is the register number where you can find the result of the expression, and the lexical environment maintains a mapping from a variable name to the register where that variable can be found. Or we could be creating an intermediate representation and the lexical environment maintains a mapping from a name to an IR node. Or whatever. Here, "environment" is the association list. Assume that "acons" is a Python function that adds a pair of (key, value) to the front of a linked list. Note how the list is never explicitly mutated, it is maintained implicitly by passing a new value for "environment" as you recurse down. The beauty of this is that entries are removed from the lexical environment implicitly as parsing functions return, and also that "environment" is a purely functional data structure. You can stash away "environment" in say an IR node and it will always refer to a snapshot of the lexical environment for a given AST node, even after other nodes are parsed or the current function returns. This is non-trivial with say a hash table. Storing a copy at each IR node would eat memory. With a linked list, sharing of sub parts falls out for free. Also, look at the Linux kernel sometime. It uses linked lists all over the place. Your malloc() implementation likely keeps a set of segregated free lists maintained as linked lists. They do this because they avoid ever traversing the list completely. They just operate on the head/tail.
- thirsteh 13y ago
  I agree about lists being much more expressive in a lot of functional code, and sometimes compilers can optimize away some of the overhead. On the other hand, take a language like Haskell: It has Data.ByteString and Data.Text, which are array-backed string types that exist (almost) solely because String (i.e. [Char]) is inefficient unless you're doing a lot of manipulation such as insertions and deletions in the middle of the string (in which case you might want to use some form of Builder instead, anyway.) The advice should probably be "use the right tool for the job." I wouldn't dream of writing functional programs without lists, but I also don't use e.g. the String type if I don't actually need it to be a list. Lists and arrays have very different algorithmic complexities for different operations. Figure out which operations you need, and pick the data structure that best suits what you intend to do.
  - evincarofautumn 13y ago
    Yeah. There’s a finer point too: in Haskell, linked lists are useful less as data structures but more as iterators, because of their relatively large size overhead per element. A large proportion of list-based algorithms can be made streaming thanks to laziness and the immense cleverness of GHC, in which case only a constant number of allocations actually occur—often zero.
  - millstone 13y ago
    > String (i.e. [Char]) is inefficient unless you're doing a lot of manipulation such as insertions and deletions in the middle of the string Is String actually efficient for this use case? If you insert in the middle of a String, wouldn't it have to copy all of the preceding characters? Only the tail could be shared, I would think.
    - thirsteh 13y ago
      Yeah, it's not very efficient. I mainly use lists as stacks, or when I'm filtering some collection and I just need to traverse it.
- jeffreyg 13y ago
jvanenk 13y ago
Stop Using Linked-Lists (in areas where linked-lists are the wrong structure to use) Edit: I should note this article's advice is really good advice if your focus is performance.
- deleted 13y ago
  [deleted]
- skw 13y ago
  This! Linked lists / trees are great in applicable use cases, I think the author or the article just being an attention whore... to be fair I haven't actually needed to use binary trees or linked lists in ages...
- ajross 13y ago
  More: "Linked lists are much, much slower than you think they are and should not be used in performance-sensitive code." That fact isn't remotely obvious to most hackers, and simply brushing it aside as an area where linked lists are "wrong" is missing important details.
  - gizmo686 13y ago
    Even in performance sensitive code, linked lists might be the right way to go. If you need to store an unknown amount of data, a resizable array probably does amoratize to a better performance than linked lists. But, all of the 'slowness' happens at the same time, so it might be worth slowing down the average case to avoid the worst case. The most notable examples I can think of are video games where FPS is king, and kernels, where you always want to exit quickly. Linked lists can also work better in limited memory environments because, with the overhead of 1 pointer per element, you can make use of fragmented memory.
    - olivier1664 13y ago
      Or something between the two: "Unrolled linked list": In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list
justin_hancock 13y ago
They're useful where you need to grow a collection in constant time. Re-sizing arrays is potentially very expensive.
- alayne 13y ago
  That's why you use a growth factor, say doubling the backing array when you need to grow. That makes the amortized cost of adding an item constant. The only case where a LL may be preferable are when you care about performance of inserting/deleting in the middle of a list.
- Bill_Dimm 13y ago
  You might want to take a look at the graph (scroll down a little) in this article that is linked in the blog post: http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/#TOC_LOCALITY_OF_REF_1 http://kjellkod.wordpress.com/2012/02/25/why-you-should-neve... It's not just growing the collection (it does read and insert), but it may be a bit surprising.
- voidlogic 13y ago
  If really needed you can have it both ways, you could roll a data structure that is a linked list of arrays. Then you have constant time growth and good caching/prefetching. Toy example: struct ListSegment { T[64] items int nextItem = 0 ListSegment* nextSeg, prevSeg }
  - Bill_Dimm 13y ago
    If you're using C++ you don't need to roll your own because the standard library provides it. It is called deque.
mosqutip 13y ago
I'M ARGUING AGAINST CONVENTIONAL WISDOM! PLEASE GIVE ME ATTENTION! Use linked-lists in situations where you need fast insertion and lookup time isn't as important. Don't use linked-lists when lookup time is important. Don't make fallacious claims supported with misguided and incomplete examples.
- bnegreve 13y ago
  > I'M ARGUING AGAINST CONVENTIONAL WISDOM! PLEASE GIVE ME ATTENTION! I don't think it's like this, it's true that the article is a bit harsh, but it contains a lot of references that support the claim. Additionally I also came to the conclusion that plain linked list are virtually always slower in practice because insertions in vector is amortized constant time, or because you can use better more local structures like deques, or because hash tables are always an option, and so on. Also check Soustrup's vector vs list slide in the presentation by linked by chmike's in this thread it's pretty demonstrative.
ska 13y ago
It seems that often articles like this overstate their case to the point that it really detracts from the message. There is a valid point, that a naive analysis of linked list vs. static array based on intro CS course descriptions of their properties isn't a good model for what is going on in a modern system. The real lesson is: if you want to achieve high performance you simply must understand the impact of things like cache localization, vectorization, hardware prefetch, pipelining etc., and how your data structure operation will interact with them. "Never use a linked list" is a silly lesson to take from this though. "In these situations, linked lists might not perform as well as you expect" is more like it. "Use the right data structure for the job" is still as good advice as it ever was.
- zwieback 13y ago
  Exactly. Also, pointers are just an implementation detail of linked lists. You can implement an array based linked list and avoid "scribbling all over memory", which really is a valid concern raised in the article.
  - stormbrew 13y ago
    What exactly would an array based linked list be but either an array or an array deque? These things have names for a reason.
    - betterunix 13y ago
      Instead of pointers, you would store an index in the array of nodes: struct node { void * data; uint32_t idx_next; }; You are still dereferencing pointers, of course, but you have better locality, even after doing a lot of insertions and deletions.
      - marshray 13y ago
        It's even better with intrusive containers. As an extreme case, let's say we need a collection of 24 bit RGB triplets: struct node { uint8_t r, g, b; uint8_t idx_next; }; Of course, a contiguous array uint8_t[256][3] might still be faster.
dudus 13y ago
Just a bogus claim by a troll. Nothing to see here move on.
ebbv 13y ago
This is akin to saying "Don't use text! Binary data is always more efficient!" Or "Never use uncompressed data storage!" The reality is linked lists are a tool. They can be used well or they can be used poorly. Just because there are disadvantages doesn't mean they should never be used. Very link-baity article.
- thirsteh 13y ago
  They're bad in the same way arrays are bad and "should never be used": appends often require reallocating the entire array, and are thus O(n) (although the reallocs are usually better on average.)
  - jimmaswell 13y ago
    I thought generally dynamic arrays were allocated more memory than the last allocation every time an appending happens, so that future appends are faster. Might've been the vector class from C++ I heard that about.
    - kbolino 13y ago
      Indeed, and most implementations use exponential scaling when allocating a new array. So although your worst-case insertion time is O(n) from copying the entire array, over a sequence of n operations, this only happens log n times, so you have O(log n) amortized time. Edit: All the references to "constant amortized time" lead me to reevaluate this claim, and it's not correct. Let's say you start with an initial capacity of 2, and double the capacity when necessary. Then the cost of adding n elements to the list will be n + the sum of 2^i from i=1 to i=log(n), which is n + 2(n - 1) or O(n). Over n operations, that's O(1) amortized.
      - deleted 13y ago
        [deleted]
  - koenigdavidmj 13y ago
    Right, but if you overallocate a bit you can ensure amortized constant time. (A comment in Python's list resize code claims that it does this, at least. You can look at http://hg.python.org/cpython/file/d047928ae3f6/Objects/listobject.c http://hg.python.org/cpython/file/d047928ae3f6/Objects/listo... , function 'list_resize' for their sizing algorithm.)
mamcx 13y ago
So, exist a list of wich structures are better for the main use cases? ie, a simple "cheat list" or something like that? Because the norm, I think, for the naive developer is use the main one offered by the language (ie: in python, list, dicts).
francispelland 13y ago
I'm almost certain my tests I did a few years ago were valid, when attempting to push, pop and sort array vs linked list. Would be nice if there were so numbers, examples, etc.
- Bill_Dimm 13y ago
  The article links to another article that gives a ton of numbers and examples: http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/ http://kjellkod.wordpress.com/2012/02/25/why-you-should-neve...
jamesaguilar 13y ago
Mmmmmeehhh. Profile it first.
btilly 13y ago
I was recently working some data structures in C++ where I needed to have tree-based structures and sustained performance. The compromise that I hit on was to allocate all of the nodes of a tree out of an std::vector. This allowed me the flexibility of tree-based structures together with all of the locality of reference that I needed. As the tree grew, the vector would resize and move, but the amortized average cost of that is directly proportional to the size of my data structure. I offer this in case a similar compromise might be useful for someone else. (My guess is that it is probably standard for people who need to know this sort of stuff. I'm just not usually someone who needs to know this sort of stuff.)
- minimax 13y ago
  How big of a tree was it and how big were the nodes? I don't see how you get any locality of reference for a large enough tree, and you certainly don't get any of the hardware prefetch. To get any benefit out of this I think you need multiple nodes to fit on a cache line and for tree traversal to hit adjacent nodes in the vector (but how could you guarantee that?)
  - btilly 13y ago
    I had several related data structures, and the details varied. But for the most part 5-1000 nodes per tree, with a node size of 12-32 bytes. And in my use case I'd be walking through a vector with thousands to hundreds of thousands of things, having to do operations involving lookups into 2-3 of these trees at a time. The trick would not make sense for large trees. But it worked out very well for me.
- berkut 13y ago
  This is used a lot for things like acceleration structures in 3D graphics - you also get the benefit of being able to store an uint32_t offset instead of a 64-bit pointer, fitting a bigger tree in memory/cache.
  - btilly 13y ago
    I used that trick as well. :-)
b0b_d0e 13y ago
I've been working on an application for a card game and I have been considering the implications of using a linked list for the deck structure. I just don't see how using an array would make sense for a deck of cards. I need the ability to constantly grow and shrink the deck (this is for Yugioh so cards would get put back into the deck often). I did consider using an array but it seemed to be more trouble than its worth considering the need to remove cards from random locations in the deck. My question is then what kind of data structure is optimal for this then? Are arrays still the better choice or is there another data structure I don't know about that is optimal for card decks?
- mkilling 13y ago
  Just use linked lists. If it turns out to be a performance problem (my guess: it won't) you can change the data structure later.
- betterunix 13y ago
  First implement this using a linked list; then an array; and then, if you have some time, see if a random access list improves on performance: http://www.cl.cam.ac.uk/teaching/2004/IntroFuncProg/lecture08.html http://www.cl.cam.ac.uk/teaching/2004/IntroFuncProg/lecture0...
- VLM 13y ago
  "optimal for card decks" When n is human-typical card deck size, the optimal solution is whatever minimizes some balance of development time and debugging time. CPU and coding efficiency will never enter as a limitation. The absolute dirt simplest way to test your numerous card manipulation algorithms might be two arrays (or plain text files?) and your algos copy from one array into the other. In Yugioh isn't there some inherent (however ridiculously large) limit to the possible number of cards in a deck?
m0wfo 13y ago
Has someone mentioned premature optimization yet? Yeah, using some kind of 'immortal', randomly accessible structure will surely perform better than a linked list; I've had jobs where this was the case (c.f. disruptor). But as performance tweaks go, this one falls into the category of last-resort. What you gain in speed you lose in sheer simplicity, elegance and power (no linked-lists, no LISP :)
aphyr 13y ago
On a related note, cache alignment is one of the reasons Clojure's vectors (log32 insertion, access, and deletion) and linked lists (o(index) insertion, access, and deletion) have unintuitive performance characteristics. For instance, constructing lists of either type takes roughly the same amount of time for big lists: user=> (with-progress-reporting (bench (into '() (range 100000)))) Execution time mean : 9.293932 ms Execution time std-deviation : 269.771284 µs user=> (with-progress-reporting (bench (into [] (range 100000)))) Execution time mean : 9.882163 ms Execution time std-deviation : 359.744662 µs And with smaller lists, building vectors is ~30-50% slower. user=> (with-progress-reporting (bench (into '() (range 24)))) Execution time mean : 2.483705 µs Execution time std-deviation : 71.302962 ns user=> (with-progress-reporting (bench (into [] (range 24)))) Execution time mean : 3.349080 µs Execution time std-deviation : 114.007930 ns However, traversal is significantly faster for vectors, because you can pack 32 references into a cache line at a time. Here's a decent-sized list: user=> (let [x (apply list (range 100000))] (bench (reduce + x))) Execution time mean : 8.586510 ms Execution time std-deviation : 80.923357 µs Vs a comparable vector: user=> (let [x (vec (range 100000))] (bench (reduce + x))) Execution time mean : 4.564553 ms Execution time std-deviation : 135.795328 µs Traversing small lists: user=> (let [x (apply list (range 24))] (bench (reduce + x))) Execution time mean : 2.041794 µs Execution time std-deviation : 18.752533 ns Vs small vectors: user=> (let [x (vec (range 24))] (bench (reduce + x))) Execution time mean : 1.051182 µs Execution time std-deviation : 10.413211 ns http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ http://blog.higher-order.net/2009/02/01/understanding-clojur...
- gtani 13y ago
  Benchmarking on the JVM is tricky, beyond pure algorithmic efficiency (assuming all memory accesses are equal), there's cache effects, JVM heap and GC effects and the usual warmup/inlining concerns of benchmarking. On page 551 of the excellent scala staircase book (2nd edition[1]) there's a collection efficiency table w.r.t. head/tail/indexing/insert, but that's a jumping off point (sorry, I can't find an online version of the table). [1] http://www.artima.com/shop/programming_in_scala_2ed http://www.artima.com/shop/programming_in_scala_2ed
seivan 13y ago
Funny this should pop up on a day where I'm writing some flocking.... switching away from a home built linked list. Mostly to use foundation classes - just saw the talk form the developer of Braid about not wheel-inventing or optimizing data structures.
iTrollFreely 13y ago
hey look, yet another web developer/blogger who thinks he is a programmer!
themstheones 13y ago
If you use a List in .NET, you get a wrapper for an array that will expand as needed (doubling in size every so often). The reasoning is quite similar to the reasons given in this article.
- thomasz 13y ago
  System.Collections.Generic.List<T> is similar to std::vector, but oddly named. System.Collections.Generic.LinkedList<T> is the implementation of the canonical double linked list ADT.
strictfp 13y ago
Who used linked lists in practice anyway?
- betterunix 13y ago
  The Linux kernel, among other things.
- cnvogel 13y ago
  It's heavily used in the Linux kernel, for example: http://kernelnewbies.org/FAQ/LinkedLists http://kernelnewbies.org/FAQ/LinkedLists [fbsd /home/chris/linux-tegra (master)] $ git grep LIST_HEAD|wc 5939 12872 372136
- GnarfGnarf 13y ago
  LIBXML uses them for in-memory representation of DOM parsed XML. They are also very effective in Trie node structures (http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Trie). They provide super-fast searching of large texts. I prefer arrays. I experimented with linked lists in my early C days, and this code turned about to be the most bug-prone and hard to maintain. They have their place, but given a choice, arrays are simpler, and faster to code for.
  - gizmo686 13y ago
    >I experimented with linked lists in my early C days, and this code turned about to be the most bug-prone and hard to maintain. I had almost the exact opposite experience. Arrays always felt like I was shuffling indexes around, and needed to do extra bookkeeping to keep track of where I was. Linked-lists seemed more explicit. Granted, I have had times where arrays produced easier code. These tended to be when I need random access (or to backtrack n-elements or such). Furtuantly, these cases also (normally) coincide with the cases where arrays are the more (asymptotically) performant data-structure.
- gizmo686 13y ago
  Kernels, embeded, games come to mind. For all of them, a major advantage of linked-lists is that they really are constant time. For example, if you are programming a game, you gennerally do not want to use a vector. Even though vectors amoratize to O(1), and may be, on average, faster, they occasionally take a long time. Switching to a linked list could be the difference from going from 100FPS with an occasional 1FPS, to going at a constant 80FPS. Also, linked lists can (counterintuitivly) often make better use of a low memory environment. This is because they do not require a continuous block of ram, so they can fill in free memory that has become fragmented. Also, in many cases linked-lists produce very clear and understandable code. And functional programming.
justinhj 13y ago
The link to the article about "Starcraft crashes because it uses linked lists" seems underhanded. That article talks about intrusive lists and why they are useful, and what the down sides are. The actual crash seems to be related not to the use of a linked list at all, but just lack of shared data synchonisation which can happen with many other data structures.
stiff 13y ago
I don't understand all the hate about the post, one of the referenced articles is actually very good and gives a quite compelling case (maybe it should have been submitted instead): http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/ http://kjellkod.wordpress.com/2012/02/25/why-you-should-neve... It shows that linked lists are slower than vectors for real-world-like scenarios even for those cases where the asymptotic complexity for linked lists is lower. Seems that that modern CPU architectures have changed so much that our theoretical models diverge further and further from reality, I think this is pretty interesting.
- betterunix 13y ago
  I do not think our theoretical models diverge from reality; the theoretical models are based on how the performance relates to the size of the input, and remain valid even if you have a very fast computer. What modern architectures have done is to change the constant factors a bit; that just raises the threshold for problem sizes, but it does not eliminate it. Sure, there are cases where asymptotic analysis can be dismissed. Matrix multiplication comes to mind: the fastest algorithms have impractically large constant factors. Usually, though, asymptotic analysis does matter, because it is often the case that input sizes will grow unexpectedly.
  - stiff 13y ago
    This has nothing to do with simply having a "fast computer", it would be all fine if we just used 486s clocked at 10Ghz, but we don't, the changes in the architecture of CPUs do indeed make the theoretical model more diverged from reality, because it presupposes a lot of things, like that every instruction takes the same time to execute, also implying that instruction execution times are independent, that one instruction gets executed at a time, etc. If those assumptions do not hold you cannot assume the factor is really constant, and even if it were so, you cannot dismiss this difference indefinitely on this ground, if on datasets of the size commonly encountered in practice the algorithms with a larger asymptotic complexity start outperforming the ones with a smaller one. For matrix multiplication this was known for years, for linked lists it is a relatively new development that came with larger and faster CPU caches etc.
berkut 13y ago
In performance-critical code, this is well known. Also, since the 64-bit days, storing linked lists also has a significant overhead over arrays due to the additional storage requirements of the pointers, which means you fit less in cache which compounds the problem even more.
gosu 13y ago
The correct way to do linked lists is to store the list traversal fields next to the data. In C, this would mean storing next/prev pointers inside of the structs which will be placed on lists. In light of this, the things in the OP are often non-issues because you'll need the data in cache immediately after the list operation anyway (or during the traversal, for O(n) operations like list_find). In fact, vectors of pointers are worse for the hardware because you'll need to load in more cache lines than with lists, in order to traverse the array. Lists aren't clearly the better option when the data will need to live exactly as long as the data exists in the container. In this case, you can store the data itself in a vector's backing array (and so the data will be invalid as soon as it's removed from the vector).
- cygx 13y ago
  Anecdotal evidence to back up your claim: Mergesorting an intrusive linked list can outperform quick or heap sorting an array of pointers.
- yason 13y ago
  Who the heck puts the payload into a separate allocation? I'm pretty sure I've never seen such an implementation. Not once. I could imagine seeing something like that in textbooks where they use graphical diagrams to illustrate how a linked list works but who would actually implement it like that -- I don't know. The canonical way is to do: struct listnode { struct listnode *next; struct listnode *prev; }; struct your_own_data_node { struct listnode node; int x, y, z; }; which ensures that you can have a set of functions that operate on struct listnode * and you can use them for all of your lists.
  - gosu 13y ago
    I wouldn't call that canonical. You can take a further step, as in the Linux version that someone posted below: http://kernelnewbies.org/FAQ/LinkedLists http://kernelnewbies.org/FAQ/LinkedLists
- ternaryoperator 13y ago
  That's a very interesting refinement. Dangit, now I've got to go and code it up and profile it. Unless you've done this legwork?
Qantourisc 13y ago
Maybe we should use Linked Arrays :)
- angersock 13y ago
  Back in highschool we'd come up with the idea of using arrays of pointers, those getting the speed of iteration of arrays with the smaller memory footprint of linked-lists. At the time, we thought we'd discovered something magical.
chmike 13y ago
At page 45 of this presentation of Soustrup, [http://ecn.channel9.msdn.com/events/GoingNative12/GN12Cpp11Style.pdf http://ecn.channel9.msdn.com/events/GoingNative12/GN12Cpp11S...], he shows benhmark comparison between linked list, preallocated list and array for insertion and deletion of small element values in list up to 500 000 elemnts. Arrays are beating linked list.
- gizmo686 13y ago
  That example involves inserting (and deleting) elements at a specific index, which means you would have to traverse (on average) half of the linked-list each time. Generally, when I work with linked-lists (excluding functional programming) I only delete elements after I already have a pointer to them for something else. Similarly, I generally do not care about the order of elements, so I can either insert a new element at whatever index my cursor happens to be at, or append them to the end.
  - chmike 13y ago
    These are specific use case. Indeed in some cases lists are more efficient than arrays. The advice to use arrays instead of linked list is a rule thumb. Not all programmers are still sucking their thumb. ;)
haberman 13y ago
There's been some discussion on HN in the last few days about negativity. If there's one thing that inspires negativity, it's hearing categorical statements like "ALWAYS do X," or "Y is NEVER true" when the listener has specific experiences that contradict this. We all come at computing from different perspectives. The perspective of a JS developer is very different from the perspective of an OS developer. "Rules of thumb" that make sense in one scenario may be completely wrong in another. Different programmers are faced with different constraints, different performance profiles, and different relative costs (which can lead to different tradeoffs). If you're tempted to make a categorical statement, maybe it's better to first consider whether your statement is as universal as you think it is.
gsg 13y ago
This is awful advice which is based on a complete misunderstanding of the use cases of linked lists. Linked lists apply in situations when you can't place things in arrays (because they are too large to copy, or because there will be pointers maintained to them). The author makes much ado about locality of reference and cpu friendly layout without understanding that those things are irrelevant because this is a data structure to use when indirection is required. It always amazes me that such simple data structures can be so poorly understood.
stormbrew 13y ago
I think a lot of people are missing the point, and that's probably at least in part because of the bold claim of the title. The point is that some of the (very most common) conventional wisdom about the appropriateness of linked list has become outdated and wrong in the age of very fast local cache. It really does mean that in a lot of cases that, say, Knuth's books would have suggested you use a linked list, you really probably shouldn't any more, even if it doesn't really mean you never should.
stcredzero 13y ago
True story. I was working for a property/casualty insurance company in South Carolina. There was a local community college that had programming, and most of the "programmer analysts" at this place went there and took the intro to C course, which included writing a doubly linked list. It also had the notion that not writing your own code was "cheating." The application I was working on had something like 500 separate implementations of a doubly linked list, each of which was used to support exactly one collection, and each of which involved hours of coding and debugging. The company didn't care, as client companies were billed by the hour. One of the client companies had programmers who were horrified at this and their programmers introduced an adaptable linked-list library called "SuperLink." It was accepted as a "modification," incorporated into just the one implementation, then forgotten.
pcwalton 13y ago
This is not good advice if you need your list to have unbounded size and want it to be lock-free. Growing an array and copying all the elements over is very expensive in a thread-safe scenario. If you use a linked list, however, you can implement all the operations without using any locks at all. (Linked lists are what we use for our channels in Rust, and as a result they're extremely fast: in the new scheduler they're totally lock-free except if the task is sleeping, which we can optimize to be lock-free later. They have unlimited size, which helps prevent deadlocks.)
- gosu 13y ago
  Very cool. What kind of lockfree linked lists? Did you work from one of the papers on the subject? (Searching "rust lockfree" reveals a feature request for a lockfree malloc. I happen to have one of those, but the reality is that synchronization will probably not be your bottleneck.)
jwise0 13y ago
From the perspective of computer architecture, the author provides what look like -- on their face -- good arguments. They quote from Aeter Suleman, who says things like: "they throw off hardware prefetching", or "they reduce the benefit of out-of-order execution". These may have been true on machines of the past, but these are no longer true on modern systems. With the advent of trace caches and runahead execution [1], linked lists are really no longer as painful as they once were. (Indeed, even back in the day, Alpha had low-cost "explicit" runahead-like semantics, where the programmer could specify other work to do while waiting for DRAM; this was usable to accelerate linked-list traversal.) [1] http://users.ece.cmu.edu/~omutlu/pub/mutlu_hpca03.pdf http://users.ece.cmu.edu/~omutlu/pub/mutlu_hpca03.pdf (disclosure: I worked closely with Onur at one point; his Ph.D thesis introduced runahead. I may be excessively biased in favor of that technique :-))
raymondh 13y ago
The article( and its referenced article) recommends against using linked lists because they are inefficient on modern processors (due to cache misses). However, there is a better solution than throwing away a powerful and expressive data structure. Rather than linking individual data elements, instead link blocks of consecutive elements. This hybrid approach takes full advantage of cache locality and it minimizes the memory overhead of storing both the links and the data. This is the approach used in Python's implementation of deques: http://hg.python.org/cpython/file/85c04fdaa404/Modules/_collectionsmodule.c#l4 http://hg.python.org/cpython/file/85c04fdaa404/Modules/_coll...
ucee054 13y ago
I don't think any advice you can get from highscalability.com can be any good, because their whole mission statement is crap. They talk about getting 10 million concurrent clients only; they don't talk about scaling in any other dimension. And you'll never have 10 million clients of one server in practice, because how much network bandwidth does your super server have? 10 gbps? So that means you'll be strangling each client down to only a few kbps - way to go for performance. The 1980s called, they want their network apps back. In real life, you'd offload the task from the server onto middle-tier machines that talk to the clients. There'll be at most thousands of these, and each one would have at most thousands of clients. And this will let you provide several mbps to each client if you get the networking right. In fact, it means that even highscalability.com's original mission statement of 10 thousand clients was moot in the first place.
yyqux 13y ago
This is pretty reasonable advice. There was a time when linked-lists didn't have such a massive performance disadvantage compared with more contiguous data structures, but that time has passed and I'm not sure that the programming community is fully aware of it (certainly you wouldn't be explicitly told it in most CS programs). Memory efficiency is also often terrible on 64-bit machines, especially for doubly-linked lists. Sometimes they're the right data structure, but I've definitely come across programmers who want to use a linked list for everything, even in code where performance is important. Edit: the general advice that you should avoid linked lists for performance reason is good. The idea that you should never use them I just took as additional trolling for page views.
pfortuny 13y ago
What is that about "premature optimization" and "the root of all evil"? O(n) arguments are all very well as long as you keep in mind that, ehem, there are constants all around and they usually tend to be pretty big. So a more honest title would be "linked lists may harm your efficiency in high-speed environments". Notice the 'may' and the context. The title implies straightaway "stop using LISP", which to my taste is a rather bold statement.

128 points by aespinoza 13y ago

I feel like this could have perhaps mentioned the cases where one should use linked lists. Is a simple queue still implemented as a linked list? That is all I ever seem to use them for.

theboss 13y ago
A queue would be an excellent time to use a linked list. I don't understand the point of making a claim like this about a data-structure. The most fundamental thing in data-structures is that there is a time and a place for using each one. No data-structure is inherently 'better' than the others.
- jhawk28 13y ago
  Based on the disruptor paper (http://disruptor.googlecode.com/files/Disruptor-1.0.pdf http://disruptor.googlecode.com/files/Disruptor-1.0.pdf) linked lists make poor queues also. Ring buffers backed by arrays are much better.
  - theboss 13y ago
    Very interesting, but I feel there is a difference of need here. You're right...there a Ring buffer with an array is better, but for average programmers a linked-list makes a damn good (maintainable, easy, understandable, and pretty quick) queue.

rayiner 13y ago

What stupid advice. Linked lists (and trees formed from lists) are a fundamental functional data structure. They have tremendous expressive advantages in functional code where operating on the head and the rest of the list leads to clear expression of an algorithm, and easy sharing of sub-parts makes certain other algorithms much more elegant. An example is maintaining the lexical environment as you're compiling a programming language. The first response might be to use something like a hash table. But then how do you handle shadowing (where an inner block shadows a variable of the same name in an other block)? A much cleaner way is to use an association list that's implicitly maintained as you recurse over the AST. E.g. in psuedo-Python: def parse_let(form, environment): (name, value) = parse_declaration(declaration_part(form)) return parse_body(body_part(form), acons(name, value, environment)) For those unfamiliar with Lisp, "let" introduces a new name bound to the value of an initializing expression, which is only in scope for the body of the "let" construct. Assume here that we're generating code from an AST and that the return value of a parse function is the register number where you can find the result of the expression, and the lexical environment maintains a mapping from a variable name to the register where that variable can be found. Or we could be creating an intermediate representation and the lexical environment maintains a mapping from a name to an IR node. Or whatever. Here, "environment" is the association list. Assume that "acons" is a Python function that adds a pair of (key, value) to the front of a linked list. Note how the list is never explicitly mutated, it is maintained implicitly by passing a new value for "environment" as you recurse down. The beauty of this is that entries are removed from the lexical environment implicitly as parsing functions return, and also that "environment" is a purely functional data structure. You can stash away "environment" in say an IR node and it will always refer to a snapshot of the lexical environment for a given AST node, even after other nodes are parsed or the current function returns. This is non-trivial with say a hash table. Storing a copy at each IR node would eat memory. With a linked list, sharing of sub parts falls out for free. Also, look at the Linux kernel sometime. It uses linked lists all over the place. Your malloc() implementation likely keeps a set of segregated free lists maintained as linked lists. They do this because they avoid ever traversing the list completely. They just operate on the head/tail.

thirsteh 13y ago
I agree about lists being much more expressive in a lot of functional code, and sometimes compilers can optimize away some of the overhead. On the other hand, take a language like Haskell: It has Data.ByteString and Data.Text, which are array-backed string types that exist (almost) solely because String (i.e. [Char]) is inefficient unless you're doing a lot of manipulation such as insertions and deletions in the middle of the string (in which case you might want to use some form of Builder instead, anyway.) The advice should probably be "use the right tool for the job." I wouldn't dream of writing functional programs without lists, but I also don't use e.g. the String type if I don't actually need it to be a list. Lists and arrays have very different algorithmic complexities for different operations. Figure out which operations you need, and pick the data structure that best suits what you intend to do.
- evincarofautumn 13y ago
  Yeah. There’s a finer point too: in Haskell, linked lists are useful less as data structures but more as iterators, because of their relatively large size overhead per element. A large proportion of list-based algorithms can be made streaming thanks to laziness and the immense cleverness of GHC, in which case only a constant number of allocations actually occur—often zero.
- millstone 13y ago
  > String (i.e. [Char]) is inefficient unless you're doing a lot of manipulation such as insertions and deletions in the middle of the string Is String actually efficient for this use case? If you insert in the middle of a String, wouldn't it have to copy all of the preceding characters? Only the tail could be shared, I would think.
  - thirsteh 13y ago
    Yeah, it's not very efficient. I mainly use lists as stacks, or when I'm filtering some collection and I just need to traverse it.
jeffreyg 13y ago

jvanenk 13y ago

Stop Using Linked-Lists (in areas where linked-lists are the wrong structure to use) Edit: I should note this article's advice is really good advice if your focus is performance.

deleted 13y ago
[deleted]
skw 13y ago
This! Linked lists / trees are great in applicable use cases, I think the author or the article just being an attention whore... to be fair I haven't actually needed to use binary trees or linked lists in ages...
ajross 13y ago
More: "Linked lists are much, much slower than you think they are and should not be used in performance-sensitive code." That fact isn't remotely obvious to most hackers, and simply brushing it aside as an area where linked lists are "wrong" is missing important details.
- gizmo686 13y ago
  Even in performance sensitive code, linked lists might be the right way to go. If you need to store an unknown amount of data, a resizable array probably does amoratize to a better performance than linked lists. But, all of the 'slowness' happens at the same time, so it might be worth slowing down the average case to avoid the worst case. The most notable examples I can think of are video games where FPS is king, and kernels, where you always want to exit quickly. Linked lists can also work better in limited memory environments because, with the overhead of 1 pointer per element, you can make use of fragmented memory.
  - olivier1664 13y ago
    Or something between the two: "Unrolled linked list": In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list

justin_hancock 13y ago

They're useful where you need to grow a collection in constant time. Re-sizing arrays is potentially very expensive.

alayne 13y ago
That's why you use a growth factor, say doubling the backing array when you need to grow. That makes the amortized cost of adding an item constant. The only case where a LL may be preferable are when you care about performance of inserting/deleting in the middle of a list.
Bill_Dimm 13y ago
You might want to take a look at the graph (scroll down a little) in this article that is linked in the blog post: http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/#TOC_LOCALITY_OF_REF_1 http://kjellkod.wordpress.com/2012/02/25/why-you-should-neve... It's not just growing the collection (it does read and insert), but it may be a bit surprising.
voidlogic 13y ago
If really needed you can have it both ways, you could roll a data structure that is a linked list of arrays. Then you have constant time growth and good caching/prefetching. Toy example: struct ListSegment { T[64] items int nextItem = 0 ListSegment* nextSeg, prevSeg }
- Bill_Dimm 13y ago
  If you're using C++ you don't need to roll your own because the standard library provides it. It is called deque.

mosqutip 13y ago

I'M ARGUING AGAINST CONVENTIONAL WISDOM! PLEASE GIVE ME ATTENTION! Use linked-lists in situations where you need fast insertion and lookup time isn't as important. Don't use linked-lists when lookup time is important. Don't make fallacious claims supported with misguided and incomplete examples.

bnegreve 13y ago
> I'M ARGUING AGAINST CONVENTIONAL WISDOM! PLEASE GIVE ME ATTENTION! I don't think it's like this, it's true that the article is a bit harsh, but it contains a lot of references that support the claim. Additionally I also came to the conclusion that plain linked list are virtually always slower in practice because insertions in vector is amortized constant time, or because you can use better more local structures like deques, or because hash tables are always an option, and so on. Also check Soustrup's vector vs list slide in the presentation by linked by chmike's in this thread it's pretty demonstrative.

ska 13y ago

It seems that often articles like this overstate their case to the point that it really detracts from the message. There is a valid point, that a naive analysis of linked list vs. static array based on intro CS course descriptions of their properties isn't a good model for what is going on in a modern system. The real lesson is: if you want to achieve high performance you simply must understand the impact of things like cache localization, vectorization, hardware prefetch, pipelining etc., and how your data structure operation will interact with them. "Never use a linked list" is a silly lesson to take from this though. "In these situations, linked lists might not perform as well as you expect" is more like it. "Use the right data structure for the job" is still as good advice as it ever was.

zwieback 13y ago
Exactly. Also, pointers are just an implementation detail of linked lists. You can implement an array based linked list and avoid "scribbling all over memory", which really is a valid concern raised in the article.
- stormbrew 13y ago
  What exactly would an array based linked list be but either an array or an array deque? These things have names for a reason.
  - betterunix 13y ago
    Instead of pointers, you would store an index in the array of nodes: struct node { void * data; uint32_t idx_next; }; You are still dereferencing pointers, of course, but you have better locality, even after doing a lot of insertions and deletions.
    - marshray 13y ago
      It's even better with intrusive containers. As an extreme case, let's say we need a collection of 24 bit RGB triplets: struct node { uint8_t r, g, b; uint8_t idx_next; }; Of course, a contiguous array uint8_t[256][3] might still be faster.

dudus 13y ago

Just a bogus claim by a troll. Nothing to see here move on.

ebbv 13y ago

This is akin to saying "Don't use text! Binary data is always more efficient!" Or "Never use uncompressed data storage!" The reality is linked lists are a tool. They can be used well or they can be used poorly. Just because there are disadvantages doesn't mean they should never be used. Very link-baity article.

thirsteh 13y ago
They're bad in the same way arrays are bad and "should never be used": appends often require reallocating the entire array, and are thus O(n) (although the reallocs are usually better on average.)
- jimmaswell 13y ago
  I thought generally dynamic arrays were allocated more memory than the last allocation every time an appending happens, so that future appends are faster. Might've been the vector class from C++ I heard that about.
  - kbolino 13y ago
    Indeed, and most implementations use exponential scaling when allocating a new array. So although your worst-case insertion time is O(n) from copying the entire array, over a sequence of n operations, this only happens log n times, so you have O(log n) amortized time. Edit: All the references to "constant amortized time" lead me to reevaluate this claim, and it's not correct. Let's say you start with an initial capacity of 2, and double the capacity when necessary. Then the cost of adding n elements to the list will be n + the sum of 2^i from i=1 to i=log(n), which is n + 2(n - 1) or O(n). Over n operations, that's O(1) amortized.
    - deleted 13y ago
      [deleted]
- koenigdavidmj 13y ago
  Right, but if you overallocate a bit you can ensure amortized constant time. (A comment in Python's list resize code claims that it does this, at least. You can look at http://hg.python.org/cpython/file/d047928ae3f6/Objects/listobject.c http://hg.python.org/cpython/file/d047928ae3f6/Objects/listo... , function 'list_resize' for their sizing algorithm.)

mamcx 13y ago

So, exist a list of wich structures are better for the main use cases? ie, a simple "cheat list" or something like that? Because the norm, I think, for the naive developer is use the main one offered by the language (ie: in python, list, dicts).

francispelland 13y ago

I'm almost certain my tests I did a few years ago were valid, when attempting to push, pop and sort array vs linked list. Would be nice if there were so numbers, examples, etc.

Bill_Dimm 13y ago
The article links to another article that gives a ton of numbers and examples: http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/ http://kjellkod.wordpress.com/2012/02/25/why-you-should-neve...

jamesaguilar 13y ago

Mmmmmeehhh. Profile it first.

btilly 13y ago

I was recently working some data structures in C++ where I needed to have tree-based structures and sustained performance. The compromise that I hit on was to allocate all of the nodes of a tree out of an std::vector. This allowed me the flexibility of tree-based structures together with all of the locality of reference that I needed. As the tree grew, the vector would resize and move, but the amortized average cost of that is directly proportional to the size of my data structure. I offer this in case a similar compromise might be useful for someone else. (My guess is that it is probably standard for people who need to know this sort of stuff. I'm just not usually someone who needs to know this sort of stuff.)

minimax 13y ago
How big of a tree was it and how big were the nodes? I don't see how you get any locality of reference for a large enough tree, and you certainly don't get any of the hardware prefetch. To get any benefit out of this I think you need multiple nodes to fit on a cache line and for tree traversal to hit adjacent nodes in the vector (but how could you guarantee that?)
- btilly 13y ago
  I had several related data structures, and the details varied. But for the most part 5-1000 nodes per tree, with a node size of 12-32 bytes. And in my use case I'd be walking through a vector with thousands to hundreds of thousands of things, having to do operations involving lookups into 2-3 of these trees at a time. The trick would not make sense for large trees. But it worked out very well for me.
berkut 13y ago
This is used a lot for things like acceleration structures in 3D graphics - you also get the benefit of being able to store an uint32_t offset instead of a 64-bit pointer, fitting a bigger tree in memory/cache.
- btilly 13y ago
  I used that trick as well. :-)

b0b_d0e 13y ago

I've been working on an application for a card game and I have been considering the implications of using a linked list for the deck structure. I just don't see how using an array would make sense for a deck of cards. I need the ability to constantly grow and shrink the deck (this is for Yugioh so cards would get put back into the deck often). I did consider using an array but it seemed to be more trouble than its worth considering the need to remove cards from random locations in the deck. My question is then what kind of data structure is optimal for this then? Are arrays still the better choice or is there another data structure I don't know about that is optimal for card decks?

mkilling 13y ago
Just use linked lists. If it turns out to be a performance problem (my guess: it won't) you can change the data structure later.
betterunix 13y ago
First implement this using a linked list; then an array; and then, if you have some time, see if a random access list improves on performance: http://www.cl.cam.ac.uk/teaching/2004/IntroFuncProg/lecture08.html http://www.cl.cam.ac.uk/teaching/2004/IntroFuncProg/lecture0...
VLM 13y ago
"optimal for card decks" When n is human-typical card deck size, the optimal solution is whatever minimizes some balance of development time and debugging time. CPU and coding efficiency will never enter as a limitation. The absolute dirt simplest way to test your numerous card manipulation algorithms might be two arrays (or plain text files?) and your algos copy from one array into the other. In Yugioh isn't there some inherent (however ridiculously large) limit to the possible number of cards in a deck?

m0wfo 13y ago

Has someone mentioned premature optimization yet? Yeah, using some kind of 'immortal', randomly accessible structure will surely perform better than a linked list; I've had jobs where this was the case (c.f. disruptor). But as performance tweaks go, this one falls into the category of last-resort. What you gain in speed you lose in sheer simplicity, elegance and power (no linked-lists, no LISP :)

aphyr 13y ago

On a related note, cache alignment is one of the reasons Clojure's vectors (log32 insertion, access, and deletion) and linked lists (o(index) insertion, access, and deletion) have unintuitive performance characteristics. For instance, constructing lists of either type takes roughly the same amount of time for big lists: user=> (with-progress-reporting (bench (into '() (range 100000)))) Execution time mean : 9.293932 ms Execution time std-deviation : 269.771284 µs user=> (with-progress-reporting (bench (into [] (range 100000)))) Execution time mean : 9.882163 ms Execution time std-deviation : 359.744662 µs And with smaller lists, building vectors is ~30-50% slower. user=> (with-progress-reporting (bench (into '() (range 24)))) Execution time mean : 2.483705 µs Execution time std-deviation : 71.302962 ns user=> (with-progress-reporting (bench (into [] (range 24)))) Execution time mean : 3.349080 µs Execution time std-deviation : 114.007930 ns However, traversal is significantly faster for vectors, because you can pack 32 references into a cache line at a time. Here's a decent-sized list: user=> (let [x (apply list (range 100000))] (bench (reduce + x))) Execution time mean : 8.586510 ms Execution time std-deviation : 80.923357 µs Vs a comparable vector: user=> (let [x (vec (range 100000))] (bench (reduce + x))) Execution time mean : 4.564553 ms Execution time std-deviation : 135.795328 µs Traversing small lists: user=> (let [x (apply list (range 24))] (bench (reduce + x))) Execution time mean : 2.041794 µs Execution time std-deviation : 18.752533 ns Vs small vectors: user=> (let [x (vec (range 24))] (bench (reduce + x))) Execution time mean : 1.051182 µs Execution time std-deviation : 10.413211 ns http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ http://blog.higher-order.net/2009/02/01/understanding-clojur...

gtani 13y ago
Benchmarking on the JVM is tricky, beyond pure algorithmic efficiency (assuming all memory accesses are equal), there's cache effects, JVM heap and GC effects and the usual warmup/inlining concerns of benchmarking. On page 551 of the excellent scala staircase book (2nd edition[1]) there's a collection efficiency table w.r.t. head/tail/indexing/insert, but that's a jumping off point (sorry, I can't find an online version of the table). [1] http://www.artima.com/shop/programming_in_scala_2ed http://www.artima.com/shop/programming_in_scala_2ed

seivan 13y ago

Funny this should pop up on a day where I'm writing some flocking.... switching away from a home built linked list. Mostly to use foundation classes - just saw the talk form the developer of Braid about not wheel-inventing or optimizing data structures.

iTrollFreely 13y ago

hey look, yet another web developer/blogger who thinks he is a programmer!

themstheones 13y ago

If you use a List in .NET, you get a wrapper for an array that will expand as needed (doubling in size every so often). The reasoning is quite similar to the reasons given in this article.

thomasz 13y ago
System.Collections.Generic.List<T> is similar to std::vector, but oddly named. System.Collections.Generic.LinkedList<T> is the implementation of the canonical double linked list ADT.

strictfp 13y ago

Who used linked lists in practice anyway?

betterunix 13y ago
The Linux kernel, among other things.
cnvogel 13y ago
It's heavily used in the Linux kernel, for example: http://kernelnewbies.org/FAQ/LinkedLists http://kernelnewbies.org/FAQ/LinkedLists [fbsd /home/chris/linux-tegra (master)] $ git grep LIST_HEAD|wc 5939 12872 372136
GnarfGnarf 13y ago
LIBXML uses them for in-memory representation of DOM parsed XML. They are also very effective in Trie node structures (http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Trie). They provide super-fast searching of large texts. I prefer arrays. I experimented with linked lists in my early C days, and this code turned about to be the most bug-prone and hard to maintain. They have their place, but given a choice, arrays are simpler, and faster to code for.
- gizmo686 13y ago
  >I experimented with linked lists in my early C days, and this code turned about to be the most bug-prone and hard to maintain. I had almost the exact opposite experience. Arrays always felt like I was shuffling indexes around, and needed to do extra bookkeeping to keep track of where I was. Linked-lists seemed more explicit. Granted, I have had times where arrays produced easier code. These tended to be when I need random access (or to backtrack n-elements or such). Furtuantly, these cases also (normally) coincide with the cases where arrays are the more (asymptotically) performant data-structure.
gizmo686 13y ago
Kernels, embeded, games come to mind. For all of them, a major advantage of linked-lists is that they really are constant time. For example, if you are programming a game, you gennerally do not want to use a vector. Even though vectors amoratize to O(1), and may be, on average, faster, they occasionally take a long time. Switching to a linked list could be the difference from going from 100FPS with an occasional 1FPS, to going at a constant 80FPS. Also, linked lists can (counterintuitivly) often make better use of a low memory environment. This is because they do not require a continuous block of ram, so they can fill in free memory that has become fragmented. Also, in many cases linked-lists produce very clear and understandable code. And functional programming.

justinhj 13y ago

The link to the article about "Starcraft crashes because it uses linked lists" seems underhanded. That article talks about intrusive lists and why they are useful, and what the down sides are. The actual crash seems to be related not to the use of a linked list at all, but just lack of shared data synchonisation which can happen with many other data structures.

stiff 13y ago

I don't understand all the hate about the post, one of the referenced articles is actually very good and gives a quite compelling case (maybe it should have been submitted instead): http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/ http://kjellkod.wordpress.com/2012/02/25/why-you-should-neve... It shows that linked lists are slower than vectors for real-world-like scenarios even for those cases where the asymptotic complexity for linked lists is lower. Seems that that modern CPU architectures have changed so much that our theoretical models diverge further and further from reality, I think this is pretty interesting.

betterunix 13y ago
I do not think our theoretical models diverge from reality; the theoretical models are based on how the performance relates to the size of the input, and remain valid even if you have a very fast computer. What modern architectures have done is to change the constant factors a bit; that just raises the threshold for problem sizes, but it does not eliminate it. Sure, there are cases where asymptotic analysis can be dismissed. Matrix multiplication comes to mind: the fastest algorithms have impractically large constant factors. Usually, though, asymptotic analysis does matter, because it is often the case that input sizes will grow unexpectedly.
- stiff 13y ago
  This has nothing to do with simply having a "fast computer", it would be all fine if we just used 486s clocked at 10Ghz, but we don't, the changes in the architecture of CPUs do indeed make the theoretical model more diverged from reality, because it presupposes a lot of things, like that every instruction takes the same time to execute, also implying that instruction execution times are independent, that one instruction gets executed at a time, etc. If those assumptions do not hold you cannot assume the factor is really constant, and even if it were so, you cannot dismiss this difference indefinitely on this ground, if on datasets of the size commonly encountered in practice the algorithms with a larger asymptotic complexity start outperforming the ones with a smaller one. For matrix multiplication this was known for years, for linked lists it is a relatively new development that came with larger and faster CPU caches etc.

berkut 13y ago

In performance-critical code, this is well known. Also, since the 64-bit days, storing linked lists also has a significant overhead over arrays due to the additional storage requirements of the pointers, which means you fit less in cache which compounds the problem even more.

gosu 13y ago

The correct way to do linked lists is to store the list traversal fields next to the data. In C, this would mean storing next/prev pointers inside of the structs which will be placed on lists. In light of this, the things in the OP are often non-issues because you'll need the data in cache immediately after the list operation anyway (or during the traversal, for O(n) operations like list_find). In fact, vectors of pointers are worse for the hardware because you'll need to load in more cache lines than with lists, in order to traverse the array. Lists aren't clearly the better option when the data will need to live exactly as long as the data exists in the container. In this case, you can store the data itself in a vector's backing array (and so the data will be invalid as soon as it's removed from the vector).

cygx 13y ago
Anecdotal evidence to back up your claim: Mergesorting an intrusive linked list can outperform quick or heap sorting an array of pointers.
yason 13y ago
Who the heck puts the payload into a separate allocation? I'm pretty sure I've never seen such an implementation. Not once. I could imagine seeing something like that in textbooks where they use graphical diagrams to illustrate how a linked list works but who would actually implement it like that -- I don't know. The canonical way is to do: struct listnode { struct listnode *next; struct listnode *prev; }; struct your_own_data_node { struct listnode node; int x, y, z; }; which ensures that you can have a set of functions that operate on struct listnode * and you can use them for all of your lists.
- gosu 13y ago
  I wouldn't call that canonical. You can take a further step, as in the Linux version that someone posted below: http://kernelnewbies.org/FAQ/LinkedLists http://kernelnewbies.org/FAQ/LinkedLists
ternaryoperator 13y ago
That's a very interesting refinement. Dangit, now I've got to go and code it up and profile it. Unless you've done this legwork?

Qantourisc 13y ago

Maybe we should use Linked Arrays :)

angersock 13y ago
Back in highschool we'd come up with the idea of using arrays of pointers, those getting the speed of iteration of arrays with the smaller memory footprint of linked-lists. At the time, we thought we'd discovered something magical.

chmike 13y ago

At page 45 of this presentation of Soustrup, [http://ecn.channel9.msdn.com/events/GoingNative12/GN12Cpp11Style.pdf http://ecn.channel9.msdn.com/events/GoingNative12/GN12Cpp11S...], he shows benhmark comparison between linked list, preallocated list and array for insertion and deletion of small element values in list up to 500 000 elemnts. Arrays are beating linked list.

gizmo686 13y ago
That example involves inserting (and deleting) elements at a specific index, which means you would have to traverse (on average) half of the linked-list each time. Generally, when I work with linked-lists (excluding functional programming) I only delete elements after I already have a pointer to them for something else. Similarly, I generally do not care about the order of elements, so I can either insert a new element at whatever index my cursor happens to be at, or append them to the end.
- chmike 13y ago
  These are specific use case. Indeed in some cases lists are more efficient than arrays. The advice to use arrays instead of linked list is a rule thumb. Not all programmers are still sucking their thumb. ;)

haberman 13y ago

There's been some discussion on HN in the last few days about negativity. If there's one thing that inspires negativity, it's hearing categorical statements like "ALWAYS do X," or "Y is NEVER true" when the listener has specific experiences that contradict this. We all come at computing from different perspectives. The perspective of a JS developer is very different from the perspective of an OS developer. "Rules of thumb" that make sense in one scenario may be completely wrong in another. Different programmers are faced with different constraints, different performance profiles, and different relative costs (which can lead to different tradeoffs). If you're tempted to make a categorical statement, maybe it's better to first consider whether your statement is as universal as you think it is.

gsg 13y ago

This is awful advice which is based on a complete misunderstanding of the use cases of linked lists. Linked lists apply in situations when you can't place things in arrays (because they are too large to copy, or because there will be pointers maintained to them). The author makes much ado about locality of reference and cpu friendly layout without understanding that those things are irrelevant because this is a data structure to use when indirection is required. It always amazes me that such simple data structures can be so poorly understood.

stormbrew 13y ago

I think a lot of people are missing the point, and that's probably at least in part because of the bold claim of the title. The point is that some of the (very most common) conventional wisdom about the appropriateness of linked list has become outdated and wrong in the age of very fast local cache. It really does mean that in a lot of cases that, say, Knuth's books would have suggested you use a linked list, you really probably shouldn't any more, even if it doesn't really mean you never should.

stcredzero 13y ago

True story. I was working for a property/casualty insurance company in South Carolina. There was a local community college that had programming, and most of the "programmer analysts" at this place went there and took the intro to C course, which included writing a doubly linked list. It also had the notion that not writing your own code was "cheating." The application I was working on had something like 500 separate implementations of a doubly linked list, each of which was used to support exactly one collection, and each of which involved hours of coding and debugging. The company didn't care, as client companies were billed by the hour. One of the client companies had programmers who were horrified at this and their programmers introduced an adaptable linked-list library called "SuperLink." It was accepted as a "modification," incorporated into just the one implementation, then forgotten.

pcwalton 13y ago

This is not good advice if you need your list to have unbounded size and want it to be lock-free. Growing an array and copying all the elements over is very expensive in a thread-safe scenario. If you use a linked list, however, you can implement all the operations without using any locks at all. (Linked lists are what we use for our channels in Rust, and as a result they're extremely fast: in the new scheduler they're totally lock-free except if the task is sleeping, which we can optimize to be lock-free later. They have unlimited size, which helps prevent deadlocks.)

gosu 13y ago
Very cool. What kind of lockfree linked lists? Did you work from one of the papers on the subject? (Searching "rust lockfree" reveals a feature request for a lockfree malloc. I happen to have one of those, but the reality is that synchronization will probably not be your bottleneck.)

jwise0 13y ago

From the perspective of computer architecture, the author provides what look like -- on their face -- good arguments. They quote from Aeter Suleman, who says things like: "they throw off hardware prefetching", or "they reduce the benefit of out-of-order execution". These may have been true on machines of the past, but these are no longer true on modern systems. With the advent of trace caches and runahead execution [1], linked lists are really no longer as painful as they once were. (Indeed, even back in the day, Alpha had low-cost "explicit" runahead-like semantics, where the programmer could specify other work to do while waiting for DRAM; this was usable to accelerate linked-list traversal.) [1] http://users.ece.cmu.edu/~omutlu/pub/mutlu_hpca03.pdf http://users.ece.cmu.edu/~omutlu/pub/mutlu_hpca03.pdf (disclosure: I worked closely with Onur at one point; his Ph.D thesis introduced runahead. I may be excessively biased in favor of that technique :-))

raymondh 13y ago

The article( and its referenced article) recommends against using linked lists because they are inefficient on modern processors (due to cache misses). However, there is a better solution than throwing away a powerful and expressive data structure. Rather than linking individual data elements, instead link blocks of consecutive elements. This hybrid approach takes full advantage of cache locality and it minimizes the memory overhead of storing both the links and the data. This is the approach used in Python's implementation of deques: http://hg.python.org/cpython/file/85c04fdaa404/Modules/_collectionsmodule.c#l4 http://hg.python.org/cpython/file/85c04fdaa404/Modules/_coll...

ucee054 13y ago

I don't think any advice you can get from highscalability.com can be any good, because their whole mission statement is crap. They talk about getting 10 million concurrent clients only; they don't talk about scaling in any other dimension. And you'll never have 10 million clients of one server in practice, because how much network bandwidth does your super server have? 10 gbps? So that means you'll be strangling each client down to only a few kbps - way to go for performance. The 1980s called, they want their network apps back. In real life, you'd offload the task from the server onto middle-tier machines that talk to the clients. There'll be at most thousands of these, and each one would have at most thousands of clients. And this will let you provide several mbps to each client if you get the networking right. In fact, it means that even highscalability.com's original mission statement of 10 thousand clients was moot in the first place.

yyqux 13y ago

This is pretty reasonable advice. There was a time when linked-lists didn't have such a massive performance disadvantage compared with more contiguous data structures, but that time has passed and I'm not sure that the programming community is fully aware of it (certainly you wouldn't be explicitly told it in most CS programs). Memory efficiency is also often terrible on 64-bit machines, especially for doubly-linked lists. Sometimes they're the right data structure, but I've definitely come across programmers who want to use a linked list for everything, even in code where performance is important. Edit: the general advice that you should avoid linked lists for performance reason is good. The idea that you should never use them I just took as additional trolling for page views.

pfortuny 13y ago

What is that about "premature optimization" and "the root of all evil"? O(n) arguments are all very well as long as you keep in mind that, ehem, there are constants all around and they usually tend to be pretty big. So a more honest title would be "linked lists may harm your efficiency in high-speed environments". Notice the 'may' and the context. The title implies straightaway "stop using LISP", which to my taste is a rather bold statement.