5 ms·

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://bulldozer

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
      I've actually dug into this a tremendous amount, and sorting using an array of indices is the way to go. I tried a lot of different things and a lot of different memory layouts and I couldn't beat std::partition swapping a vector of ints. There is no way a linked list will be the fastest way to do this on modern hardware. A big part of the reason it is so fast I think is because intel cpus are so good at prefetching, caching, and instruction reordering. If you are talking about kd-trees specifically you might want to ask questions if you have any. I've done 4 full implementations, each one with more refinement. I see more what you are saying below but I can't reply to it. First, you could have that a vector of that struct and memmove the elements on swap, which wouldn't be too bad performance-wise. In a struct of arrays set up it wouldn't perform as well since the swaps would be multiple cache-incoherent reads and writes (sort of as you said). Sorting an array of ints will be very fast and likely the fastest way to do it. Then you can structure your data however you want and re-write it once you've sorted it.
      - woodman 11y ago
        Yeah I'm not very happy about needing to allocate an n sized array for sort operations, but it doesn't look like there is any way around it. To be clear, the struct is really just a opaque data type for what is essentially a dynamically defined struct of arrays. Most of the work has gone into compressing the array contents, as memory is the primary point of concern. I look forward to finishing it so that I can rewrite it a few more times :)
        CyberDildonics 11y ago
        You can always sort portions of it and then merge those portions. In that case it might actually make sense to use packets on dense memory in a linked list. You could put the packet with the highest high value ahead of the other and merge middle out.
        woodman 11y ago
        Yeah, I'd considered something like that to avoid large reallocs - I hadn't considered independent sort state for each chunk. That would allow for a single compile time constant sort index. Sounds like a good idea, thanks for that.
  - uxcn 11y ago
    He's referring to spatial complexity of sorting algorithms. For example, mergesort can be implemented in parallel and in place (O(1) spatial) easily using linked lists. Introsort and quicksort can be done in place using an array, but constant spatial complexity isn't always priority one. Some of the more recent algorithms aren't constant (timsort, spreadsort). Linked lists (doubly linked lists) still have valid uses, but it's generally better to use an array (or vector) until you can justify otherwise.

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
    I've actually dug into this a tremendous amount, and sorting using an array of indices is the way to go. I tried a lot of different things and a lot of different memory layouts and I couldn't beat std::partition swapping a vector of ints. There is no way a linked list will be the fastest way to do this on modern hardware. A big part of the reason it is so fast I think is because intel cpus are so good at prefetching, caching, and instruction reordering. If you are talking about kd-trees specifically you might want to ask questions if you have any. I've done 4 full implementations, each one with more refinement. I see more what you are saying below but I can't reply to it. First, you could have that a vector of that struct and memmove the elements on swap, which wouldn't be too bad performance-wise. In a struct of arrays set up it wouldn't perform as well since the swaps would be multiple cache-incoherent reads and writes (sort of as you said). Sorting an array of ints will be very fast and likely the fastest way to do it. Then you can structure your data however you want and re-write it once you've sorted it.
    - woodman 11y ago
      Yeah I'm not very happy about needing to allocate an n sized array for sort operations, but it doesn't look like there is any way around it. To be clear, the struct is really just a opaque data type for what is essentially a dynamically defined struct of arrays. Most of the work has gone into compressing the array contents, as memory is the primary point of concern. I look forward to finishing it so that I can rewrite it a few more times :)
      - CyberDildonics 11y ago
        You can always sort portions of it and then merge those portions. In that case it might actually make sense to use packets on dense memory in a linked list. You could put the packet with the highest high value ahead of the other and merge middle out.
        woodman 11y ago
        Yeah, I'd considered something like that to avoid large reallocs - I hadn't considered independent sort state for each chunk. That would allow for a single compile time constant sort index. Sounds like a good idea, thanks for that.
- uxcn 11y ago
  He's referring to spatial complexity of sorting algorithms. For example, mergesort can be implemented in parallel and in place (O(1) spatial) easily using linked lists. Introsort and quicksort can be done in place using an array, but constant spatial complexity isn't always priority one. Some of the more recent algorithms aren't constant (timsort, spreadsort). Linked lists (doubly linked lists) still have valid uses, but it's generally better to use an array (or vector) until you can justify otherwise.