5 ms·

In some cases you can benefit by "struct of arrays" instead of "array of structs". This benefits packing, enables SIMD, and usually improves persistence speed t

by herf 12y ago

In some cases you can benefit by "struct of arrays" instead of "array of structs". This benefits packing, enables SIMD, and usually improves persistence speed too. Database people call this a "column store". So if you abstract it a little you can do per-column compression that is really hard to do with vanilla structs. One thing I learned with Picasa (which is basically an in-memory database): if you're storing a lot of data in RAM, sometimes you should think of the data structures more as a database (with copy in/out, rather than reference). In multithreaded cases, this kind of approach unexpectedly gets you more parallelism and speed.

TrainedMonkey 12y ago
Column store is really just making sure values for a column are continuous in memory, instead of rows as it is done usually. Basic premise is that modern CPU's can chew through continuous memory locations at light speed, with single core being capable of scanning a gigabyte of RAM in few milliseconds[0]. This is extremely beneficial when your tables have large number of columns, but you only want to do computations on a few of them. Columnar stores usually implemented using dictionaries which allow for efficient duplicate handling and blazing fast lookups. Often those dictionaries also contain run length optimizations, so values 1 through 100 are only stored using two values start-range 1 and end-range 100. All in all, column stores are efficient at analytic workload, but struggle when a lot of inserts and updates need to happen. [0] Using prefetch, properly aligned data, and likely other optimizations I am not thinking of.
- seiji 12y ago
  but struggle when a lot of inserts and updates need to happen. I ran across this with Redis recently. Redis has an internal data structure called ziplist that's a doubly linked list with no pointers. It just uses byte offsets to the next element, so all elements are in one contiguous block of memory. It's great because you can store a lot of values compactly without needing 1 to 5 pointers (8 to 40 bytes) overhead per element in your data structure. But, a problem shows up when you want to insert or delete items. Every insert or delete requires expanding or shrinking the entire solid-chunk-of-memory allocation, which isn't the fastest thing in the world when your allocation is large. Also, inserting into the HEAD requires copying the _entire_ ziplist up exactly one element position because the block of your memory layout just changed. So, obviously these things are useful, but their usefulness degrades as your solid blocks of memory hit cache limits. Everything is super fast when your entire ziplist fits in L1, still about the same in L2, worse in L3, and horrible if your ziplist grows any larger. But, what can we do? We can fix the entire problem by creating a traditional linked lists of solid memory block ziplists. Now, each ziplist can remain small (8 KB to 16 KB), and when we grow bigger, we just cut a new ziplist, pointer-attach it to the previous ziplist, and now we have a minimal-pointer, high-locality data structure with unlimited growth potential without performance defects. It doesn't buckle under inserting or updating arbitrary elements since each memory block is isolated to a maximum ~8 KB size (reminder: your L1 cache is 32 KB to 64 KB depending on architecture) and now your memory usage due to pointer overhead is now also _greatly_ reduced (assuming your data was small and dominated or matched by pointer overhead size in the first place). As a double bonus, now when your data structure is a solid block of memory, you can compress individual contiguous memory blocks (usually with great compression ratios) because your contents will tend to be homogeneous in shape inside the same container. Result: huge reduction in pointer overhead + sequential access + compression = best of all possible worlds. Other details/comparisons at https://matt.sh/redis-quicklist-visions https://matt.sh/redis-quicklist-visions
  - hyc_symas 12y ago
    This isn't news. Arrays are fast until you need to insert/delete in them, then they get horrible. This is why we have B-trees. Every page in a B-tree is essentially a sorted array - you can find items in it quickly using binary search, and you can insert/delete in it relatively quickly because it has a small bounded size. When you need to grow beyond a single page you do a page-split and add a parent above it, etc. B-trees are the optimal implementation of dynamic arrays, end of story.
    - seiji 12y ago
      This reply is golden. It starts off completely dismissive with "this isn't news" and it ends completely dismissive with "end of story." I am quite sorry my free internet post failed to meet your quality guidelines. A wise man once said: Things have now gotten to the stage where I flinch slightly as I click on the "comments" link, bracing myself for the dismissive comment I know will be waiting for me at the top of the page.
      - tough-crowd 12y ago
        For what it is worth I enjoyed your parent post.
      - hyc_symas 12y ago
        If you honestly believe your linked list of blocks is actually superior in efficiency to a B-tree, you're delusional.
    - crucini 12y ago
      >B-trees are the optimal implementation of dynamic arrays Then why don't the popular scripting languages use B-trees for their sequence containers? Both Perl and Python use arrays for this. Both pay the price of O(n) inserts mid-container.
      - TJSomething 12y ago
        I would be unsurprised if it was for legacy reasons. Both of those programming languages were written over twenty years ago. Furthermore, arrays play nicely with C extensions.
ddorian43 12y ago
1.by Picasa you mean google-picasa? 2.you are saying it's good to use in-memory column-store for oltp?
- Crito 12y ago
  > "1.by Picasa you mean google-picasa?" Yes, that Picasa.
  - jonstewart 12y ago
    Yes, that herf.
sukilot 12y ago
The Perl folks call this "inside-out objects" I guess the MATLAB folks call this "Array Programming"
frozenport 12y ago
Indeed, this argument is speaks to a fundamental incompatibility between OOP and efficient code. I wonder how to write a compiler to perform this transformation.
- crucini 12y ago
  Same tension occurs in Java games for phones, at least pre-android. Instead of an array of Sprite objects, turns out its more efficient to have parallel arrays of ints, which leads to less readable code.
  - blt 12y ago
    with Java it's even worse because SoA is the only way to get your data packed in contiguous memory, as opposed to spraying it all over there GC heap.
CyberDildonics 12y ago
Interestingly Intel's ISPC compiler actually uses a hybrid of the two layouts to store its memory of arrays. I think it stores an array of vectors as xxxx, yyyy, zzzz, wwww, xxxx, ...
kragen 12y ago
Adam Rosenberg wrote a really interesting book advocating not just this but the entire Fortran programming style. He hasn’t persuaded me that this is a good idea in general, but it’s a really interesting way of looking at things: http://www.the-adam.com/adam/rantrave/st02.pdf http://www.the-adam.com/adam/rantrave/st02.pdf. If you struggle to imagine how you would structure software without structs or objects, you should definitely read this book! Among other things, it incidentally solves the problem Yossi Kreinin identified in "I want a struct linker": http://yosefk.com/blog/i-want-a-struct-linker.html http://yosefk.com/blog/i-want-a-struct-linker.html
epsylon 12y ago
Game developers call that principle "Data Oriented Design".
gumby 12y ago
This is my favorite example of where object oriented programming (and in particular C++) is an advantage. OO as it is usually practiced (gross generalization I know) is often hell on memory layout and memory access which causes problems that never show up in unit testing but show up in deployment. Pattern fetishism exacerbates the problem. But a data structure abstraction that hides the storage implementation is an ideal application of OO. Moderation in all things....

by herf 12y ago

TrainedMonkey 12y ago

Column store is really just making sure values for a column are continuous in memory, instead of rows as it is done usually. Basic premise is that modern CPU's can chew through continuous memory locations at light speed, with single core being capable of scanning a gigabyte of RAM in few milliseconds[0]. This is extremely beneficial when your tables have large number of columns, but you only want to do computations on a few of them. Columnar stores usually implemented using dictionaries which allow for efficient duplicate handling and blazing fast lookups. Often those dictionaries also contain run length optimizations, so values 1 through 100 are only stored using two values start-range 1 and end-range 100. All in all, column stores are efficient at analytic workload, but struggle when a lot of inserts and updates need to happen. [0] Using prefetch, properly aligned data, and likely other optimizations I am not thinking of.

seiji 12y ago
but struggle when a lot of inserts and updates need to happen. I ran across this with Redis recently. Redis has an internal data structure called ziplist that's a doubly linked list with no pointers. It just uses byte offsets to the next element, so all elements are in one contiguous block of memory. It's great because you can store a lot of values compactly without needing 1 to 5 pointers (8 to 40 bytes) overhead per element in your data structure. But, a problem shows up when you want to insert or delete items. Every insert or delete requires expanding or shrinking the entire solid-chunk-of-memory allocation, which isn't the fastest thing in the world when your allocation is large. Also, inserting into the HEAD requires copying the _entire_ ziplist up exactly one element position because the block of your memory layout just changed. So, obviously these things are useful, but their usefulness degrades as your solid blocks of memory hit cache limits. Everything is super fast when your entire ziplist fits in L1, still about the same in L2, worse in L3, and horrible if your ziplist grows any larger. But, what can we do? We can fix the entire problem by creating a traditional linked lists of solid memory block ziplists. Now, each ziplist can remain small (8 KB to 16 KB), and when we grow bigger, we just cut a new ziplist, pointer-attach it to the previous ziplist, and now we have a minimal-pointer, high-locality data structure with unlimited growth potential without performance defects. It doesn't buckle under inserting or updating arbitrary elements since each memory block is isolated to a maximum ~8 KB size (reminder: your L1 cache is 32 KB to 64 KB depending on architecture) and now your memory usage due to pointer overhead is now also _greatly_ reduced (assuming your data was small and dominated or matched by pointer overhead size in the first place). As a double bonus, now when your data structure is a solid block of memory, you can compress individual contiguous memory blocks (usually with great compression ratios) because your contents will tend to be homogeneous in shape inside the same container. Result: huge reduction in pointer overhead + sequential access + compression = best of all possible worlds. Other details/comparisons at https://matt.sh/redis-quicklist-visions https://matt.sh/redis-quicklist-visions
- hyc_symas 12y ago
  This isn't news. Arrays are fast until you need to insert/delete in them, then they get horrible. This is why we have B-trees. Every page in a B-tree is essentially a sorted array - you can find items in it quickly using binary search, and you can insert/delete in it relatively quickly because it has a small bounded size. When you need to grow beyond a single page you do a page-split and add a parent above it, etc. B-trees are the optimal implementation of dynamic arrays, end of story.
  - seiji 12y ago
    This reply is golden. It starts off completely dismissive with "this isn't news" and it ends completely dismissive with "end of story." I am quite sorry my free internet post failed to meet your quality guidelines. A wise man once said: Things have now gotten to the stage where I flinch slightly as I click on the "comments" link, bracing myself for the dismissive comment I know will be waiting for me at the top of the page.
    - tough-crowd 12y ago
      For what it is worth I enjoyed your parent post.
    - hyc_symas 12y ago
      If you honestly believe your linked list of blocks is actually superior in efficiency to a B-tree, you're delusional.
  - crucini 12y ago
    >B-trees are the optimal implementation of dynamic arrays Then why don't the popular scripting languages use B-trees for their sequence containers? Both Perl and Python use arrays for this. Both pay the price of O(n) inserts mid-container.
    - TJSomething 12y ago
      I would be unsurprised if it was for legacy reasons. Both of those programming languages were written over twenty years ago. Furthermore, arrays play nicely with C extensions.

ddorian43 12y ago

1.by Picasa you mean google-picasa? 2.you are saying it's good to use in-memory column-store for oltp?

Crito 12y ago
> "1.by Picasa you mean google-picasa?" Yes, that Picasa.
- jonstewart 12y ago
  Yes, that herf.

sukilot 12y ago

The Perl folks call this "inside-out objects" I guess the MATLAB folks call this "Array Programming"

frozenport 12y ago

Indeed, this argument is speaks to a fundamental incompatibility between OOP and efficient code. I wonder how to write a compiler to perform this transformation.

crucini 12y ago
Same tension occurs in Java games for phones, at least pre-android. Instead of an array of Sprite objects, turns out its more efficient to have parallel arrays of ints, which leads to less readable code.
- blt 12y ago
  with Java it's even worse because SoA is the only way to get your data packed in contiguous memory, as opposed to spraying it all over there GC heap.

CyberDildonics 12y ago

Interestingly Intel's ISPC compiler actually uses a hybrid of the two layouts to store its memory of arrays. I think it stores an array of vectors as xxxx, yyyy, zzzz, wwww, xxxx, ...

kragen 12y ago

Adam Rosenberg wrote a really interesting book advocating not just this but the entire Fortran programming style. He hasn’t persuaded me that this is a good idea in general, but it’s a really interesting way of looking at things: http://www.the-adam.com/adam/rantrave/st02.pdf http://www.the-adam.com/adam/rantrave/st02.pdf. If you struggle to imagine how you would structure software without structs or objects, you should definitely read this book! Among other things, it incidentally solves the problem Yossi Kreinin identified in "I want a struct linker": http://yosefk.com/blog/i-want-a-struct-linker.html http://yosefk.com/blog/i-want-a-struct-linker.html

epsylon 12y ago

Game developers call that principle "Data Oriented Design".

gumby 12y ago

This is my favorite example of where object oriented programming (and in particular C++) is an advantage. OO as it is usually practiced (gross generalization I know) is often hell on memory layout and memory access which causes problems that never show up in unit testing but show up in deployment. Pattern fetishism exacerbates the problem. But a data structure abstraction that hides the storage implementation is an ideal application of OO. Moderation in all things....