4 ms·

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

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.
  - woodman 11y ago
    > Which is to say, the realloc problem is only a problem in memory constrained -- think embedded or kernel... Or userland, when your software is processing hundreds of millions of datapoints - each with several additional independent properties. > I think the thing you might be underestimating is how much faster it is to iterate over a vector than a linked list... No, I'm well aware of the effects of locality - the linked list of arrays is an easily tuned compromise between speed and memory consumption (leaning much more towards memory considerations).
    - albinofrenchy 11y ago
      The point I was trying to make though is that even with 100mil datapoints you are looking at probably less than 50 reallocs. In userland, the story is even nicer because that actual reserve space in the vector is mostly going to be deferred until you actually write to it. I don't get the point about additional independent properties. Size of the struct changes the memory you need to grab, but not the number of reallocs you have to do. See: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector... for actual benchmarks on this. If you disagree with these benchmarks, and find your own results to be different, I'd love to see the write up on that, and I'm sure I'm not the only one.
      - woodman 11y ago
        Yeah the disconnect seems to me to be that I'm talking about performance from the perspective of a presupposition that I haven't adequately explained. You've got hundreds of millions of data points to slurp into ram, each data point may have additional properties from a fixed set, data points are independent of one another - so not a good fit for a graph, adjacency matrix, etc. Disk access outside of the initial slurp is a no go, so we have to make this fit in ram. Throwing the data point into a struct is nice and easy, plus it eases the system call overhead for m/re/callocs. But you've got a bunch of wasted space in padding, locality is gone, compressibility is much more limited. Throwing the data into a bunch of parallel arrays is about the most memory efficient way of doing it, especially considering the ease with which you can use delta encoding and bin packing. But now every memory/sort operation is magnified by the number of arrays you've got. As far as a writeup, I'm working on a succinct atomic map for strings - I look forward to releasing the code once I finish... and rewrite it in such a way that my employer doesn't sue me (it isn't organic to the business, but better safe than sorry).

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.
- woodman 11y ago
  > Which is to say, the realloc problem is only a problem in memory constrained -- think embedded or kernel... Or userland, when your software is processing hundreds of millions of datapoints - each with several additional independent properties. > I think the thing you might be underestimating is how much faster it is to iterate over a vector than a linked list... No, I'm well aware of the effects of locality - the linked list of arrays is an easily tuned compromise between speed and memory consumption (leaning much more towards memory considerations).
  - albinofrenchy 11y ago
    The point I was trying to make though is that even with 100mil datapoints you are looking at probably less than 50 reallocs. In userland, the story is even nicer because that actual reserve space in the vector is mostly going to be deferred until you actually write to it. I don't get the point about additional independent properties. Size of the struct changes the memory you need to grab, but not the number of reallocs you have to do. See: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector... for actual benchmarks on this. If you disagree with these benchmarks, and find your own results to be different, I'd love to see the write up on that, and I'm sure I'm not the only one.
    - woodman 11y ago
      Yeah the disconnect seems to me to be that I'm talking about performance from the perspective of a presupposition that I haven't adequately explained. You've got hundreds of millions of data points to slurp into ram, each data point may have additional properties from a fixed set, data points are independent of one another - so not a good fit for a graph, adjacency matrix, etc. Disk access outside of the initial slurp is a no go, so we have to make this fit in ram. Throwing the data point into a struct is nice and easy, plus it eases the system call overhead for m/re/callocs. But you've got a bunch of wasted space in padding, locality is gone, compressibility is much more limited. Throwing the data into a bunch of parallel arrays is about the most memory efficient way of doing it, especially considering the ease with which you can use delta encoding and bin packing. But now every memory/sort operation is magnified by the number of arrays you've got. As far as a writeup, I'm working on a succinct atomic map for strings - I look forward to releasing the code once I finish... and rewrite it in such a way that my employer doesn't sue me (it isn't organic to the business, but better safe than sorry).