3 ms·

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 nice

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).
- albinofrenchy 11y ago
  I'm afraid I don't quite get the data problem. Is there a toy example of the kind of data you are talking about? Not entirely clear on how the indexing would work to your benefit with parallel arrays. If there is a 1 to 1 mapping between datapoints to items in each || array, the memory consumption is the same as a struct, so I assume thats not it. It almost sounds like you are describing a (possibly non-numeric? non-homogenous?) sparse matrix, which are usually worked with in vastly different formats for construction vs manipulation vs iterating over.
  - woodman 11y ago
    > Is there a toy example of the kind of data you are talking about? Not that I know of, sorry. > Not entirely clear on how the indexing would work to your benefit with parallel arrays. Lets say that we have data that would be represented in an array of structs like so: typedef struct { char* name; int age; } prsnT1; prsnT1* peopleAOS = calloc(100, sizeof(*peopleAOS)); You could also represent it as a struct of arrays: typedef struct { char** name; int* age; } prsnT2; prsnT2* peopleSOA = malloc(sizeof(*peopleSOA)); peopleSOA->name = calloc(100, sizeof(*peopleSOA->name)); peopleSOA->age = calloc(100, sizeof(*peopleSOA->age)); Now why would you want to use SOA over AOS (disregarding the AOS alignment padding overhead)? Locality and compression. When you want to search on age, you don't need to waste cache space stepping over name. Age can also be bin packed pretty tightly, so in reality it wouldn't be an int* - but a variably sized ADT. Ideally name wouldn't be char either, but another ADT. Transparent zlib compression isn't unheard of. > ... which are usually worked with in vastly different formats for construction vs manipulation vs iterating over. Yup, classic abstract data type - doing OO in C the hard way :)

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).

albinofrenchy 11y ago
I'm afraid I don't quite get the data problem. Is there a toy example of the kind of data you are talking about? Not entirely clear on how the indexing would work to your benefit with parallel arrays. If there is a 1 to 1 mapping between datapoints to items in each || array, the memory consumption is the same as a struct, so I assume thats not it. It almost sounds like you are describing a (possibly non-numeric? non-homogenous?) sparse matrix, which are usually worked with in vastly different formats for construction vs manipulation vs iterating over.
- woodman 11y ago
  > Is there a toy example of the kind of data you are talking about? Not that I know of, sorry. > Not entirely clear on how the indexing would work to your benefit with parallel arrays. Lets say that we have data that would be represented in an array of structs like so: typedef struct { char* name; int age; } prsnT1; prsnT1* peopleAOS = calloc(100, sizeof(*peopleAOS)); You could also represent it as a struct of arrays: typedef struct { char** name; int* age; } prsnT2; prsnT2* peopleSOA = malloc(sizeof(*peopleSOA)); peopleSOA->name = calloc(100, sizeof(*peopleSOA->name)); peopleSOA->age = calloc(100, sizeof(*peopleSOA->age)); Now why would you want to use SOA over AOS (disregarding the AOS alignment padding overhead)? Locality and compression. When you want to search on age, you don't need to waste cache space stepping over name. Age can also be bin packed pretty tightly, so in reality it wouldn't be an int* - but a variably sized ADT. Ideally name wouldn't be char either, but another ADT. Transparent zlib compression isn't unheard of. > ... which are usually worked with in vastly different formats for construction vs manipulation vs iterating over. Yup, classic abstract data type - doing OO in C the hard way :)