News for hackers. Stuff that matters.
Re:Stop Using Linked Lists by rayiner on Wednesday May 22, 2013 @12:52PM (#5752096)
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.

Re:Stop Using Linked Lists by christopheraden on Wednesday May 22, 2013 @02:03PM (#5752639)
Consider that the source is High Scalability, a blog that focuses on how orthodox methods are inadequate for 1-10M concurrent connections and how different methods are being employed to reach these lofty goals, I think the advice is pretty spot-on.

It's important to consider that if your objective is scalability and performance, then the article's advice is appropriate. The article's title ought to read "Stop Using Linked Lists if you care about High Scalability", but I attach the dependent clause on many titles I read from that site.

Re:Stop Using Linked Lists by rayiner on Wednesday May 22, 2013 @02:18PM (#5752751)
I'm sure the Linux kernel developers care about scalability and performance. Count how many linked lists you see in the kernel code. See: http://lxr.free-electrons.com/ident?i=INIT_LIST_HEAD.
Re:Stop Using Linked Lists by alayne on Wednesday May 22, 2013 @03:28PM (#5753165)
I'm sure you will find strlen and linear searches too. It's more likely that absolute performance wasn't necessary for those cases, or memory usage with linked lists is better than a more complex data structure, or maybe even that linked lists were easiest for C developers.
Re:Stop Using Linked Lists by rayiner on Wednesday May 22, 2013 @03:40PM (#5753239)
Linked lists are used pervasively in performance critical parts of the code (e.g. the scheduler, the VM, etc). Linked lists just happen to have very suitable performance characteristics for the kind of tasks that happen often in a kernel. E.g. say you keep queue of IO buffers that have pending operations on them. You get an interrupt and the driver gives you back a pointer to the IO buffer it just filled. You want to copy that data out, and them remove the IO buffer from the pending queue and add it to a free queue. In this case, you'd almost certainly rather use an (intrusive) linked list rather than maintaining these queues as arrays.
Re:Stop Using Linked Lists by yyqux on Wednesday May 22, 2013 @05:43PM (#5753953)
They're pretty good at using the right tool for the right job. There are plenty of places where they use arrays or other data structures too.

In a lot of cases they really want to be able to do O(1) inserts/deletes at the beginning/end of the list, which is where linked lists do have a major advantage.

Short linked lists aren't too bad, using them for storing bulk data is mostly a bad idea unless you can't avoid it.

Re:Stop Using Linked Lists by ksk on Wednesday May 22, 2013 @04:53PM (#5753628)
Citing kernel code is not a good argument without actually understanding why they're using linked lists, when they are used and how many of them are used at a time, etc, etc. Most of those linked lists are not really relevant. Because (1) they are far too few of them (2) they do not occur in areas where performance is significantly impacted. Besides which.. the kernel is a single instance program. Its not like there are 1,000 different kernels running simultaneously.

So.. if you want to write a web server/service that can serve tens of thousands of requests - Write it both ways and see for yourself. Its obvious that linked lists are a performance drag. Although they have much in common with other forced indirection penalties (virtual functions, etc)

Edit: ah, found a nice post that has analyzed just this.

http://rusty.ozlabs.org/?p=168

Look at the performance profile here. Using linked lists is the right choice because of the way they are used...

Re:Stop Using Linked Lists by rayiner on Wednesday May 22, 2013 @05:37PM (#5753921)
As I've said elsewhere, there are linked lists buried in key operations of the kernel. E.g. the O(1) scheduler's core data structure was an array of linked lists (www.cis.ksu.edu/~gud/docs/ppt/scheduler.pdf‎). There was one list per priority level, and tasks were queued/removed from the lists at each scheduler tick. The current scheduler (CFS) uses an RB-tree. Virtual memory areas are tracked using vm_area_struct structures organized in a sorted linked list (http://lxr.free-electrons.com/source/include/linux/mm_types....). They're used in the futex implementation (http://lxr.free-electrons.com/source/kernel/futex.c#L467, the kernel's internal memory allocators (http://lxr.free-electrons.com/source/mm/slab.c), and extensively in the network stack.
Re:Stop Using Linked Lists by ksk on Thursday May 23, 2013 @03:37AM (#5755723)
Those links are of little value to the current discussion. If you took the performance profile, you'd find that the primary reason linked lists are used in those scenarios is because the performance worst case for linked lists occurs rarely. Which means the choice of datastructure is irrelavant w.r.t performance in those cases.
Re:Stop Using Linked Lists by bad_user on Wednesday May 22, 2013 @03:30PM (#5753178)
First of all, there's the issue of asymptotic complexity.

Usage of various data structures determines the asymptotic complexity of whatever you're doing. However, the thing that some uneducated people don't understand about asymptotic complexity is that this metric doesn't measure performance, but rather growth.

Usage of a linked list may mean that searches in it will always be O(n). However, depending on the case, this may be worse than logarithmic or O(1) complexity only for large-enough values of N, because for small values the constant factor plays a role too. Say for instance that you're searching for some value in a linked list. If you're talking about 100 items tops that's being traversed, that's probably going to be faster than a recursive function without TCO searching in a tree.

Priceless is the moment you realise that thinking in terms of asymptotic complexity is the most important thing you could ever do for performance.

Because it's a rather stupid thing to worry about things like cache locality if you don't first optimize the algorithms used. Because, for example, a quick-sort is going to be more efficient for most cases than a bubble sort and a bubble sort is going to be more efficient than a quick-sort for nearly sorted lists, with all the branch predictions or cache locality you could ever pull.

For a real world example, think of databases like MySQL. Performance on inserts in most databases, such as MySQL, deteriorates at an exponential rate, even though most of them are written in hard-core C with all CPU optimizations thrown at it that you can think of. This means that at scale, in one moment your database server is running fine, but in the next moment your server is gone. By comparisson, with a database where inserts degrade linearly, you can notice problems with months in advance.

All one can accomplish with CPU or GPU optimizations is improving the constant factor. This constant factor can be significant indeed, but at large scale it pales in comparison with the speed benefits you get from proper algorithms.

Going further, after you get your algorithms right, which is much easier to do with clean code that uses the right data-structures, you can then easily optimize the underlying implementation of those data-structures. For lists, for the interface of "push()" and "pop()" or of "queue()" and "dequeue()", you can use arrays instead, or linked lists where the items are arrays, or balanced binary search trees, or freaking Patricia tries, or whatever floats your boat, as long as you can maintain the FIFO or LIFO contract.

So that's why the advice is stupid. Because it's not putting things into context.

In fact, I would tell people - try not to use linked lists, because the notion of head and tail is an imperative concept that leaked into the functional world. Which really means it's not a future-proof concept and you'll have problems optimizing it, because you're still thinking in terms of how, versus what.

Re:Stop Using Linked Lists by gizmo686 on Wednesday May 22, 2013 @04:16PM (#5753410)
>In fact, I would tell people - try not to use linked lists, because the notion of head and tail is an imperative concept that leaked into the functional world.

Citation needed. Haskell's most basic data structure is a singly-linked list. The concept of a linked list seems to fit quite well with functional programming, as adding an additional element is simply a matter of making an element that points back to the unchanged previous element. And, linked lists work very well with recursion, as you can process the head, then move on to the rest of the list.

Are you aware of a functional datatype that can store an arbitrary amount of information and is simpler than a linked-list?

Re:Stop Using Linked Lists by bad_user on Wednesday May 22, 2013 @04:30PM (#5753496)
I got this idea from Guy Steele's keynote at Scala Days, named "What Fortress and Scala can learn from each other". For reference, Guy Steele worked on multiple programming languages, including Scheme and he can explain it better than me:

http://skillsmatter.com/podcast/scala/scala-days-keynote-301...

The gist of the matter is this - lists preserve insertion order (instead of the elements themselves having a natural order) and can only be accessed sequentially. You cannot easily split lists in two, or multiple chunks, which means we'll have a hard time doing automatic parallelizing of computations performed on linked lists.

Think of this simple expression:

    someList.filter(_ % 2 == 0).map(_ + 10)
If the underlying data-structure would be a balanced binary tree, you could easily split the work required in multiple threads. Because you're specifying the "what" instead of "how" and you can let the platform choose the best solution, like splitting it in threads or offloading that to a GPU, right? Well, linked list have the "how" encoded in them.

Maybe it helps to think of data-structures for what they really are: frozen algorithms.

Guy Steele is working on some pretty cool stuff in Fortress. Check that video out.

Re:Stop Using Linked Lists by gizmo686 on Wednesday May 22, 2013 @05:03PM (#5753692)
That makes sense. Still, I don't think its fair to say that linked lists are an imperative concept. While they lack one of the most mentioned advantages of functional programming, they still feel 'natural' in functional programming, not like they are borrowed from imperative.

Furthermore, I am not aware of another functional data structure which has O(1) append time, which allows us to construct lists element by element easily.

Re:Stop Using Linked Lists by bad_user on Wednesday May 22, 2013 @05:14PM (#5753765)
You can have amortized O(1) with trees for example. Appending elements to the end of Vectors in Scala or Clojure is done in amortized O(1), being a tree with a high branching factor. And I'm not sure how the immutable Queue is implemented in Scala, but it's also O(1) for queue() and dequeue() and it can't be a list.

It's true though, Lists are easy to implement, easy to reason about and speaking of frozen algorithms, you can view a linked list as being a frozen tail-recursion :-)

Re:Stop Using Linked Lists by yyqux on Wednesday May 22, 2013 @05:34PM (#5753904)
Linked lists are a good fit for functional languages, and arrays aren't a great fit: this can be a major obstacle to writing Haskell code that is both idiomatic and efficient.
Re:Stop Using Linked Lists by thirsteh on Wednesday May 22, 2013 @12:55PM (#5752135)
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.

Re:Stop Using Linked Lists by evincarofautumn on Wednesday May 22, 2013 @03:10PM (#5753067)
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.
Re:Stop Using Linked Lists by millstone on Wednesday May 22, 2013 @03:37PM (#5753223)
> 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.

Re:Stop Using Linked Lists by thirsteh on Wednesday May 22, 2013 @04:06PM (#5753359)
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.
Re:Stop Using Linked Lists by ScottBurson on Wednesday May 22, 2013 @02:26PM (#5752798)
In general I've found that people who have spent their whole careers writing just one kind of code tend to overgeneralize the lessons from that experience. If you spend all your time doing numerical physics simulations, indeed you probably don't see many occasions when a linked list would be a good choice. A compiler, though, is, by its nature, going to be crawling with them (as rayiner points out). It wouldn't make any sense to run a compiler on a SIMD GPU anyway -- it's far too full of conditional branches.
Re:Stop Using Linked Lists by jeffreyg on Wednesday May 22, 2013 @01:31PM (#5752396)
I appreciate your post, but I wish you would've addressed his examples of when linked lists are less efficient instead of responding to the link bait title and calling it stupid advice. Your post was informative in its own right, though, so thanks for that.
Re:Stop Using Linked Lists by rayiner on Wednesday May 22, 2013 @01:39PM (#5752452)
The title wasn't link bait. The article said: never used linked lists ever. That's stupid advice.

His examples aren't bad. But they're focused on traversal. Of course use an array when you're mostly traversing linearly. But linked lists are very versatile. Deep down in your OS, the kernel is probably not representing IO buffers as linked lists. But, it's almost certainly storing free IO buffers in a linked list, or using lists to track threads waiting on a lock, etc.

Also, the implication you should ignore algorithmic complexity is questionable. I'd rather be slower by a constant factor than sometimes suffer catastrophic performance when a workload causes the asymptotic complexity to dominate the constant factors. I remember debugging an algorithm that worked fine on some developer's test machine with a few nodes, but exploded on a load with many nodes. It had factorial complexity...

Re:Stop Using Linked Lists by jeffasinger on Wednesday May 22, 2013 @02:11PM (#5752699)
The article should be viewed in the context of High Scalability. I think the author is more saying that you should test which works faster, rather than solely relying on algorithmic complexity.
Re:Stop Using Linked Lists by w0utert on Wednesday May 22, 2013 @02:45PM (#5752927)
Maybe I have a different idea about what's important for highly scalable architectures, because in my mind ignoring algorithmic complexity theory and adhering to mantra's like 'stop using linked lists' is one of the best ways to end up with a solution that doesn't scale at all.
Re:Stop Using Linked Lists by bad_user on Wednesday May 22, 2013 @03:09PM (#5753065)
Err, no, he's not saying that.
Re:Stop Using Linked Lists by papsosouid on Wednesday May 22, 2013 @02:02PM (#5752632)
There's nothing to address. Your introductory data structures and algorithms class taught you when lists are good and when they are bad. That isn't controversial. The problem is the claim that you should never use lists, which is absurd.
Re:Stop Using Linked Lists by opinali on Wednesday May 22, 2013 @04:13PM (#5753390)
The advice is not against lists, it's against linked lists which are a particular implementation. You can have dynamic-sized lists that are backed by arrays, yet have O(1) amortized time for operations that require the list to grow or allow it to return freed space (add/remove at either end). Linked lists will only win when you need to add or remove elements in random positions (AND don't need random access, so this is usually very niche scenarios where you iterate the list end-to-end but make some updates, e.g. to insert new elements in order). Trees made up of list nodes are another obvious exception, but then we're not arguing about trees, just pure lists. (And even then... denser kinds of trees such as heaps or b-trees can often wipe the floor with traditional trees made of tiny, linked nodes.)
Re:Stop Using Linked Lists by rayiner on Wednesday May 22, 2013 @04:35PM (#5753518)
> You can have dynamic-sized lists that are backed by arrays

Lists backed by arrays have the same problem as arrays: pointers to elements are not stable. To take the example in my post, say you want to save the environment of every AST node so you can generate debug info mapping from variable names to register numbers at each line. When the list nodes are stable, it's trivial to just save a pointer to the head of the list. When addition/removal operations on the list can cause reallocation, that becomes much harder.

> Linked lists will only win when you need to add or remove elements in random positions (AND don't need random access, so this is usually very niche scenarios where you iterate the list end-to-end but make some updates, e.g. to insert new elements in order).

This is not a niche use. There are a huge number of operations where you don't traverse the list but need to add/remove from the middle. Consider something like the task scheduler in a kernel. When a process makes a call that blocks, the scheduler gets a pointer to the task structure and needs to remove the process from the run queue until the data it is waiting for arrives. If you store the runque as an array, you need to search it and remove the relevant task. If you store it as a doubly linked list, you can remove it with just a couple of pointer modifications. Indeed, inside a kernel or memory allocator, if you're iterating over any potentially large sequences, you've already lost the battle.

Re:Stop Using Linked Lists by opinali on Monday May 27, 2013 @03:33PM (#5776182)
> pointers to elements are not stable

This is only a problem if the list is constituted exclusively by its backing store; which is a common implementation for linked lists in some langs/libraries, but rarely for lists backed by arrays. In the latter case, the "list object" typically has a pointer to the backing array, and also other fields like indexes of first/last element in use. This means one extra level of indirection for any use of the list, but in practice compiler optimizations easily hoist or constant-propagate this overhead away in any code where it matters.

> There are a huge number of operations where you don't traverse the list but need to add/remove from the middle

Admittedly, my use of "niche" is context-dependent. In languages like Java where List is a kind of catch-all data structure -- it's the collection that people use when they don't have a very good reason for any other option -- the huge majority of uses do not involve updates in non-tail position (or even any updates after the initial population; most of the time a fixed-size array would work just right... except that it's against modern Java religi, er, style, to ever use its primitive arrays).

Re:Stop Using Linked Lists by bad_user on Wednesday May 22, 2013 @04:43PM (#5753559)
Actually lists of arrays are still linked-lists, with the definition being: a data-structure where nodes are grouped together, with each node being made of a datum and a reference to the next item, where you can push() and pop() from one or both ends in O(1) and that can only be accessed sequentially in O(n).

It really doesn't matter what the reference actually is, all that matters is that the information for accessing the next node is contained within the current node.

Having optimizations like XOR-ing the back/forth pointers for encoding a doubly-linked list with a single word per node, instead of two, or linking together arrays of fixed size, that's just an implementation detail.

Re:Stop Using Linked Lists by opinali on Monday May 27, 2013 @03:42PM (#5776232)
What I meant is a list where all elements are stored in a single, dense array, which grows automatically if necessary for adding new elements. See C++'s std::vector, and Java's java.util.ArrayList.
Re:Stop Using Linked Lists by bad_user on Wednesday May 22, 2013 @03:05PM (#5753040)
Your first sentence was enough for me to up-vote you, without reading the rest of the comment.

Also, your whole explanation is unnecessary, when this advice is analogous to ... stop using stacks!

I would add queues here too, though people might mistake that for priority queues, which can be modelled as trees.

Re:Stop Using Linked Lists by marshray on Wednesday May 22, 2013 @03:12PM (#5753080)
I remember being asked once in a job interview what I thought about heaps. I confessed that I didn't recall the specifics of all the different variants of that data structure as I hadn't had the occasion to use one before. https://en.wikipedia.org/wiki/Heap_(data_structure)#Variants

It turned out he was asking about dynamic memory allocation, i.e., malloc/free and new/delete.

(I didn't get the job)

Re:Stop Using Linked Lists by bad_user on Wednesday May 22, 2013 @03:52PM (#5753294)
Hehe, it happens.

Speaking of memory allocation, the stack is named that way because it's an actual stack and most function calls receive parameters through it and return their results through it. This is why it's cheaper to store things on the stack, because if you want to use a value from memory, it's going to end up on that stack anyway (e.g. boxing / unboxing), not to mention that items get allocated and deallocated in LIFO order, so you've got no issues with searching for available space or fragmentation.