25 ms·

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 meth

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.

rayiner 13y ago
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 http://lxr.free-electrons.com/ident?i=INIT_LIST_HEAD.
- alayne 13y ago
  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.
  - rayiner 13y ago
    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.
- ksk 13y ago
  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 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...
  - rayiner 13y ago
    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.h#L228 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 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 http://lxr.free-electrons.com/source/mm/slab.c), and extensively in the network stack.
    - ksk 13y ago
      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.
- yyqux 13y ago
  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.
bad_user 13y ago
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.

rayiner 13y ago

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 http://lxr.free-electrons.com/ident?i=INIT_LIST_HEAD.

alayne 13y ago
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.
- rayiner 13y ago
  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.
ksk 13y ago
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 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...
- rayiner 13y ago
  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.h#L228 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 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 http://lxr.free-electrons.com/source/mm/slab.c), and extensively in the network stack.
  - ksk 13y ago
    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.
yyqux 13y ago
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.

bad_user 13y ago

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.