10 ms·

Exotic? Obsolete? Really? Linked lists are used in pretty much all functional programming languages (because head/tail splitting is extremely useful)

CyberDildonics 11y ago
Exotic at least for performance. Not only do you have to chase pointers to loop through them, you have to deal with the heap on every append or delete. They can be great for software that doesn't have speed as a high priority.
- woodman 11y ago
  I'd be interested to know how you arrived at this conclusion, like what domain do you spend all your time in where this is true? I frequently see linked lists used for all manner of things, in some widely deployed performant code: https://github.com/mackyle/sqlite/search?q=linked+list https://github.com/mackyle/sqlite/search?q=linked+list https://github.com/freebsd/freebsd/search?l=c&q=linked+list https://github.com/freebsd/freebsd/search?l=c&q=linked+list
  - malisper 11y ago
    Stroustrup gave a talk where he demonstrated that the performance of a linked list is terrible compared to a vector. Here[0] is a summary. [0] http://bulldozer00.com/2012/02/09/vectors-and-lists/ http://bulldozer00.com/2012/02/09/vectors-and-lists/
    - woodman 11y ago
      I'm not debating that iterating over a vector is faster than iterating over a linked list, I'm asking where this guy has seen linked lists become "exotic". I'd love to dive into that code, because I've actually spent a lot of time implementing parallel arrays vs linked lists or arrays of structs, it would be nice to see how folks have addressed the pain points like sorting in constant space...
      - CyberDildonics 11y ago
        What do you mean by sorting in constant space?
        woodman 11y ago
        I mean sorting parallel arrays with a compile time constant amount of memory for sorting scratch space, this of course also means no unbound recursion into the stack. The most obvious solution is an additional index array, but that seems pretty wasteful. This is one area, in my experience, where linked lists beat out vectors, multidimensional sorting. Consider all that data that needs to get moved around in a parallel arrays implementation, vs simply changing the * prev and * next pointers in a linked list.
        overgard 11y ago
        Sure, but I think you need to consider how fast moving blocks of memory can be on modern computers. memcpy feels intuitively slow, but because it's such a ubiquitous operation, it's really really fast. On the other hand, changing pointers sounds fast, until you consider that a pointer read might flush everything out of cache and result in the cpu stalling for hundreds of cycles while the RAM retrieves something. I'm not suggesting like, never used linked lists or anything. I just think that most computer science is predicated on an abstract machine with predictable memory latency, and naturally people tend to design things with that in mind, while in reality, unless you're processing data sets so large that memory latency is insignificant, an O(1) operation might be way slower than an O(N) operation.
        woodman 11y ago
        Well for a bunch of parallel arrays you aren't really moving big blocks. Consider this: struct City { char *name; int popstrat[5]; float bounds[2]; }; A a memcpy on struct City would take care of eight distinct values, whereas a copy operation on a parallel arrays version would take at least three separate memcpy calls (maybe eight if naively implemented). I certainly agree with you on the weight given to O notation though.
  - CyberDildonics 11y ago
    Those are just search results for linked lists. It isn't as if sqlite using a linked list somewhere slows the entire thing down. I can promise you that if there is a linked list in a performance crucial place that it could be sped up a non trivial amount. Linked lists can be convenient and they can be consistent, but they aren't fast. The pointer chasing hurts performance. The extra heap allocations may or may not be able to be avoided. The alternative is something like a vector of pointers (although I would in practicality not being using a raw pointer, it would be some sort of larger data structure). That will be faster with the exception of resizes, which should be fast in general, since what they hold should be small, but they won't be consistent. Beyond that there is the idea that concurrency could mean that needing to lock a data structure makes a linked list less of an outlier because the time that it would need to remain locked would be smaller. In that case I think a vector would likely still be much better in general, since you could keep the current index to write to in an atomic, which wouldn't require a lock.
    - woodman 11y ago
      The point of the search results is that I'm not seeing the use of linked lists, in code bases that I could consider fairly performant, at a level that I would describe as "exotic". I'm not trying to be argumentative, I'd really love for you to point me to a code base that has replaced linked lists with arrays. I've spent the last week writing a library to do just that, but I'd happily abandon it in a heartbeat if I could (the novelty of binary packing parallel arrays wore off after day two). You're preaching to the choir on deference overhead, that I why I prefer c over c++ :)
    - altarius 11y ago
      Linked lists aren't fast in general but there are workloads on which they outperform vectors -- which is why it is important to understand the advantages and disadvantages of each data structure. Most lower-level memory allocators e.g. tend to use linked-lists afaik because you end up removing and inserting slabs a lot, the Linux kernel also makes wide use of linked lists as well. If there were substantial performance gains to be made without other large tradeoffs it would have been done. EDIT: Some additional info: http://www.jikos.cz/jikos/Kmalloc_Internals.html http://www.jikos.cz/jikos/Kmalloc_Internals.html
  - albinofrenchy 11y ago
    Context matters a lot. Linked lists are great for small lists, where you want very little memory overhead and you care more about each operation taking a pretty small, consistent amount of time. Vectors/Arrays are great when you don't care as much about the total memory consumption, but you want to reduce the amount of heap fragmentation. A downside to using arrays like this, and likely a leading reason you don't see them used that much in the linux kernel is that every once and a while an insert is going to force a realloc which takes a relatively long time. std::vector and the like mitigate this by reserving more space than they'll need and so they minimize the # of reallocs required. There is also performance implications to doing std::vector<myStruct> vs std::vector<myStruct*>. The later can very easily mimic the same cache coherence issues that happen with a linked list of myStructs. So when we are talking about speed in terms of millions of items in some data crunching program, vector is almost always going to win out. But if we are talking about minimal memory footprint where we want consistent timings , linked lists are a contender.
    - woodman 11y ago
      The only thing that I really agree with in that is that context matters :) My view on the matter is pretty simple, if you know how much data you are going to handle, before your first malloc, and the dimensionality is low, arrays win from the perspective of both processing speed and low memory usage. Otherwise (a lot of cases fall into otherwise) use linked lists - for your listing needs. BTW, a linked list of arrays is a pretty nice way of getting around the realloc problem. Sorting arrays across the linked list is not very nice though... If it weren't for pointer overhead I'd just throw everything into a graph, but 64-bit addressing makes that expensive.
      - albinofrenchy 11y ago
        Well, I think you'd agree to that if random access is a requirement, arrays are nearly always going to work better. Even then, that might be a good strategy if inserting into a vector type data structure required a realloc everytime. However, most implementations use an exponential strategy, so for a million item vector grown one at a time, you'd see only 10-20 reallocs. Which is to say, the realloc problem is only a problem in memory constrained -- think embedded or kernel -- systems where a memory overhead of 1.5-2x isn't viable. You can do the same thing -- and some linked list implementations do -- with linked lists, where you grab a block of nodes at a time. If you don't though, just in inserts, the vector will be faster. Mallocs are non-trivial in most applications and can easily become the bottleneck. I think the thing you might be underestimating is how much faster it is to iterate over a vector than a linked list, nevermind random access. Cache issues really, really do matter. If you want to see this in action and happen to have a SoC dev board around, disable the data cache and run some benchmarks with vectors. If you re-enable it, you will easily see a 10x-20x improvement. If you watch https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo, he goes into some of the use cases and some benchmarks that might be compelling to you.
overgard 11y ago
I should preface this by saying I love functional programming, I think it's a great way to write stable and testable code, it's likely the future, but... Functional programming is much more popular in academic circles than in industry. I think academics tend to hand wave away practical concerns like cache coherency as "an implementation detail" or as an "exercise for the reader." Big O times are often considered, but rarely do researchers make a career off of "how well does this fit into an X86 L3 cache" So yes, functional programming tends to depend on linked lists, and that's probably why you don't see it in things like the game industry. This might change in the future, for instance, I could see it being the case where having provably immutable memory could allow processors to manage more memory efficiently, but I don't think you can have a fast language that considers the CPU as an abstract entity; you have to design these things in.
- jacquesm 11y ago
  Erlang is used quite a bit in the gaming industry (backend stuff for online games) and depends quite strongly on the linked list concept.
  - CyberDildonics 11y ago
    He is obviously talking about engine programming. For tools and back ends game studios will use whatever.

CyberDildonics 11y ago

Exotic at least for performance. Not only do you have to chase pointers to loop through them, you have to deal with the heap on every append or delete. They can be great for software that doesn't have speed as a high priority.

woodman 11y ago
I'd be interested to know how you arrived at this conclusion, like what domain do you spend all your time in where this is true? I frequently see linked lists used for all manner of things, in some widely deployed performant code: https://github.com/mackyle/sqlite/search?q=linked+list https://github.com/mackyle/sqlite/search?q=linked+list https://github.com/freebsd/freebsd/search?l=c&q=linked+list https://github.com/freebsd/freebsd/search?l=c&q=linked+list
- malisper 11y ago
  Stroustrup gave a talk where he demonstrated that the performance of a linked list is terrible compared to a vector. Here[0] is a summary. [0] http://bulldozer00.com/2012/02/09/vectors-and-lists/ http://bulldozer00.com/2012/02/09/vectors-and-lists/
  - woodman 11y ago
    I'm not debating that iterating over a vector is faster than iterating over a linked list, I'm asking where this guy has seen linked lists become "exotic". I'd love to dive into that code, because I've actually spent a lot of time implementing parallel arrays vs linked lists or arrays of structs, it would be nice to see how folks have addressed the pain points like sorting in constant space...
    - CyberDildonics 11y ago
      What do you mean by sorting in constant space?
      - woodman 11y ago
        I mean sorting parallel arrays with a compile time constant amount of memory for sorting scratch space, this of course also means no unbound recursion into the stack. The most obvious solution is an additional index array, but that seems pretty wasteful. This is one area, in my experience, where linked lists beat out vectors, multidimensional sorting. Consider all that data that needs to get moved around in a parallel arrays implementation, vs simply changing the * prev and * next pointers in a linked list.
        overgard 11y ago
        Sure, but I think you need to consider how fast moving blocks of memory can be on modern computers. memcpy feels intuitively slow, but because it's such a ubiquitous operation, it's really really fast. On the other hand, changing pointers sounds fast, until you consider that a pointer read might flush everything out of cache and result in the cpu stalling for hundreds of cycles while the RAM retrieves something. I'm not suggesting like, never used linked lists or anything. I just think that most computer science is predicated on an abstract machine with predictable memory latency, and naturally people tend to design things with that in mind, while in reality, unless you're processing data sets so large that memory latency is insignificant, an O(1) operation might be way slower than an O(N) operation.
        woodman 11y ago
        Well for a bunch of parallel arrays you aren't really moving big blocks. Consider this: struct City { char *name; int popstrat[5]; float bounds[2]; }; A a memcpy on struct City would take care of eight distinct values, whereas a copy operation on a parallel arrays version would take at least three separate memcpy calls (maybe eight if naively implemented). I certainly agree with you on the weight given to O notation though.
- CyberDildonics 11y ago
  Those are just search results for linked lists. It isn't as if sqlite using a linked list somewhere slows the entire thing down. I can promise you that if there is a linked list in a performance crucial place that it could be sped up a non trivial amount. Linked lists can be convenient and they can be consistent, but they aren't fast. The pointer chasing hurts performance. The extra heap allocations may or may not be able to be avoided. The alternative is something like a vector of pointers (although I would in practicality not being using a raw pointer, it would be some sort of larger data structure). That will be faster with the exception of resizes, which should be fast in general, since what they hold should be small, but they won't be consistent. Beyond that there is the idea that concurrency could mean that needing to lock a data structure makes a linked list less of an outlier because the time that it would need to remain locked would be smaller. In that case I think a vector would likely still be much better in general, since you could keep the current index to write to in an atomic, which wouldn't require a lock.
  - woodman 11y ago
    The point of the search results is that I'm not seeing the use of linked lists, in code bases that I could consider fairly performant, at a level that I would describe as "exotic". I'm not trying to be argumentative, I'd really love for you to point me to a code base that has replaced linked lists with arrays. I've spent the last week writing a library to do just that, but I'd happily abandon it in a heartbeat if I could (the novelty of binary packing parallel arrays wore off after day two). You're preaching to the choir on deference overhead, that I why I prefer c over c++ :)
  - altarius 11y ago
    Linked lists aren't fast in general but there are workloads on which they outperform vectors -- which is why it is important to understand the advantages and disadvantages of each data structure. Most lower-level memory allocators e.g. tend to use linked-lists afaik because you end up removing and inserting slabs a lot, the Linux kernel also makes wide use of linked lists as well. If there were substantial performance gains to be made without other large tradeoffs it would have been done. EDIT: Some additional info: http://www.jikos.cz/jikos/Kmalloc_Internals.html http://www.jikos.cz/jikos/Kmalloc_Internals.html
- albinofrenchy 11y ago
  Context matters a lot. Linked lists are great for small lists, where you want very little memory overhead and you care more about each operation taking a pretty small, consistent amount of time. Vectors/Arrays are great when you don't care as much about the total memory consumption, but you want to reduce the amount of heap fragmentation. A downside to using arrays like this, and likely a leading reason you don't see them used that much in the linux kernel is that every once and a while an insert is going to force a realloc which takes a relatively long time. std::vector and the like mitigate this by reserving more space than they'll need and so they minimize the # of reallocs required. There is also performance implications to doing std::vector<myStruct> vs std::vector<myStruct*>. The later can very easily mimic the same cache coherence issues that happen with a linked list of myStructs. So when we are talking about speed in terms of millions of items in some data crunching program, vector is almost always going to win out. But if we are talking about minimal memory footprint where we want consistent timings , linked lists are a contender.
  - woodman 11y ago
    The only thing that I really agree with in that is that context matters :) My view on the matter is pretty simple, if you know how much data you are going to handle, before your first malloc, and the dimensionality is low, arrays win from the perspective of both processing speed and low memory usage. Otherwise (a lot of cases fall into otherwise) use linked lists - for your listing needs. BTW, a linked list of arrays is a pretty nice way of getting around the realloc problem. Sorting arrays across the linked list is not very nice though... If it weren't for pointer overhead I'd just throw everything into a graph, but 64-bit addressing makes that expensive.
    - albinofrenchy 11y ago
      Well, I think you'd agree to that if random access is a requirement, arrays are nearly always going to work better. Even then, that might be a good strategy if inserting into a vector type data structure required a realloc everytime. However, most implementations use an exponential strategy, so for a million item vector grown one at a time, you'd see only 10-20 reallocs. Which is to say, the realloc problem is only a problem in memory constrained -- think embedded or kernel -- systems where a memory overhead of 1.5-2x isn't viable. You can do the same thing -- and some linked list implementations do -- with linked lists, where you grab a block of nodes at a time. If you don't though, just in inserts, the vector will be faster. Mallocs are non-trivial in most applications and can easily become the bottleneck. I think the thing you might be underestimating is how much faster it is to iterate over a vector than a linked list, nevermind random access. Cache issues really, really do matter. If you want to see this in action and happen to have a SoC dev board around, disable the data cache and run some benchmarks with vectors. If you re-enable it, you will easily see a 10x-20x improvement. If you watch https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo, he goes into some of the use cases and some benchmarks that might be compelling to you.

overgard 11y ago

I should preface this by saying I love functional programming, I think it's a great way to write stable and testable code, it's likely the future, but... Functional programming is much more popular in academic circles than in industry. I think academics tend to hand wave away practical concerns like cache coherency as "an implementation detail" or as an "exercise for the reader." Big O times are often considered, but rarely do researchers make a career off of "how well does this fit into an X86 L3 cache" So yes, functional programming tends to depend on linked lists, and that's probably why you don't see it in things like the game industry. This might change in the future, for instance, I could see it being the case where having provably immutable memory could allow processors to manage more memory efficiently, but I don't think you can have a fast language that considers the CPU as an abstract entity; you have to design these things in.

jacquesm 11y ago
Erlang is used quite a bit in the gaming industry (backend stuff for online games) and depends quite strongly on the linked list concept.
- CyberDildonics 11y ago
  He is obviously talking about engine programming. For tools and back ends game studios will use whatever.