4 ms·

I started thinking this would be a rehashing of how column-oriented storage formats can be far more efficient for certain access patterns. But it really was a s

I started thinking this would be a rehashing of how column-oriented storage formats can be far more efficient for certain access patterns. But it really was a showcase of what a bloated mess C++ has become.

monkeyelite 1y ago
And you just do not need to be doing this. Just write out which columns you need and use an index. You can write generic sort and remove, and just overload the swap function for your SOA thing.
- pragma_x 1y ago
  That was my takeaway as well. Pivoting a conventional structure in a column-major storage system just smells like a look-aside of some kind (a database). Plus, you lose the benefits of bulk copy/move that the compiler will likely give you in a standard struct (e.g. memcpy()), should it be on the big side. From there, we can use lots of other tricks to further speed things up: hashes, trees, bloom filters... At the same time, I don't completely understand how such a pivot would result in a speedup for random access. I suppose it would speed up sequential access, since the multiple array storage scheme might force many more cache line updates.
  - thesz 1y ago
    These days one's program rarely does purely sequential random access. Usually, there are several threads or requests, all going into same data structure. In the extreme case where all memory accesses of a immensely massively parallel program are deferred, the result is complete absence of cache misses [1]. [1] https://disneyanimation.com/technology/hyperion/ While our programs usually not ran at Hyperion scale, they still can benefit from accesses shared between processing of several requests. For one such example, consider speech recognition with the HCLG graph. That graph is created through composition of four WFST [2] graphs, the last one is Grammar, derived from SRILM n-gram language model. This HCLG graph has scale free property [3] due to all G FST states has to backoff to the order-0 model, and some states are visited exponentially often than others. [2] https://en.wikipedia.org/wiki/Finite-state_transducer#Weighted_automata [3] https://en.wikipedia.org/wiki/Scale-free_network By sorting HCLG graph states by their fan-ins (number of states referring to a particular one), we sped recognition process up 5%. E.g., most referred state gets index 0, second most referred is 1, etc, and that's it. No code change, just preprocessing step that, I believe, lessen the pressure on the CPU's memory protection subsystem. The speech recognition process with HCLG graph uses beam search [4], there are several (9-20) hundredths of states in the beam front to be evaluated. Most of them have outgoing arc to some of the most visited (fan-in) states. By having these states close to each other we incur less page faults exception handling during processing. [4] https://en.wikipedia.org/wiki/Beam_search Basically, we shared more MMU information between requests in beam front. PS Fun fact: WFST created by OpenFST has "structure of arrays" layout. ;)
dexterous8339 1y ago
I recently went down this rabbit hole myself and came out with my own column-major array type. The explanation drifts into thinking of 2D byte arrays as 3D bit matrices, but in the end it was a 20-30x improvement in speed and binary size. I was honestly surprised that C++ doesn't have anything built in for this, but at least it's trivial to write your own array type
thechao 1y ago
I showed up to the C++ rodeo right as C++98 was taking off, and got to work with Jaakko & Gaby & Bjarne (at TAMU) on what would be C++11 (C++0x). Man — those were great times. I still can't decide which craziness — reflection or coroutines — I detest worse in "modern" C++. In either case, I really feel like I'm channeling my inner/outer old-man-shakes-fist-at-clouds. On the other hand, I see languages like Nim, Zig, Rust, Swift, Go, ... and, I mean, seriously.
- ranger_danger 1y ago
  I wished Swift got more love, I feel like it takes the "most familiar" (to C++ devs) approach to improving things, as it keeps the syntax extremely similar to C++ but fixes a lot of the issues it has, and adds some very nice things too, like memory safety and named function parameters (which Objective-C had since forever).
nickysielicki 1y ago
Boo fucking hoo, C++ isn’t C with classes. Anyone with a basic grasp of c++11 metaprogramming can more-or-less follow this easily. God forbid the language grows.
- teleforce 1y ago
  The GP is not wrong though. Perhaps someone can write similar logic in D programming and showcase how much more intuitive the programming will be since Dlang has first class arrays and its metaprogramming facility is second to none [1]. [1] D (programming language): https://en.wikipedia.org/wiki/D_(programming_language) https://en.wikipedia.org/wiki/D_(programming_language)

monkeyelite 1y ago

And you just do not need to be doing this. Just write out which columns you need and use an index. You can write generic sort and remove, and just overload the swap function for your SOA thing.

pragma_x 1y ago
That was my takeaway as well. Pivoting a conventional structure in a column-major storage system just smells like a look-aside of some kind (a database). Plus, you lose the benefits of bulk copy/move that the compiler will likely give you in a standard struct (e.g. memcpy()), should it be on the big side. From there, we can use lots of other tricks to further speed things up: hashes, trees, bloom filters... At the same time, I don't completely understand how such a pivot would result in a speedup for random access. I suppose it would speed up sequential access, since the multiple array storage scheme might force many more cache line updates.
- thesz 1y ago
  These days one's program rarely does purely sequential random access. Usually, there are several threads or requests, all going into same data structure. In the extreme case where all memory accesses of a immensely massively parallel program are deferred, the result is complete absence of cache misses [1]. [1] https://disneyanimation.com/technology/hyperion/ While our programs usually not ran at Hyperion scale, they still can benefit from accesses shared between processing of several requests. For one such example, consider speech recognition with the HCLG graph. That graph is created through composition of four WFST [2] graphs, the last one is Grammar, derived from SRILM n-gram language model. This HCLG graph has scale free property [3] due to all G FST states has to backoff to the order-0 model, and some states are visited exponentially often than others. [2] https://en.wikipedia.org/wiki/Finite-state_transducer#Weighted_automata [3] https://en.wikipedia.org/wiki/Scale-free_network By sorting HCLG graph states by their fan-ins (number of states referring to a particular one), we sped recognition process up 5%. E.g., most referred state gets index 0, second most referred is 1, etc, and that's it. No code change, just preprocessing step that, I believe, lessen the pressure on the CPU's memory protection subsystem. The speech recognition process with HCLG graph uses beam search [4], there are several (9-20) hundredths of states in the beam front to be evaluated. Most of them have outgoing arc to some of the most visited (fan-in) states. By having these states close to each other we incur less page faults exception handling during processing. [4] https://en.wikipedia.org/wiki/Beam_search Basically, we shared more MMU information between requests in beam front. PS Fun fact: WFST created by OpenFST has "structure of arrays" layout. ;)

dexterous8339 1y ago

I recently went down this rabbit hole myself and came out with my own column-major array type. The explanation drifts into thinking of 2D byte arrays as 3D bit matrices, but in the end it was a 20-30x improvement in speed and binary size. I was honestly surprised that C++ doesn't have anything built in for this, but at least it's trivial to write your own array type

thechao 1y ago

I showed up to the C++ rodeo right as C++98 was taking off, and got to work with Jaakko & Gaby & Bjarne (at TAMU) on what would be C++11 (C++0x). Man — those were great times. I still can't decide which craziness — reflection or coroutines — I detest worse in "modern" C++. In either case, I really feel like I'm channeling my inner/outer old-man-shakes-fist-at-clouds. On the other hand, I see languages like Nim, Zig, Rust, Swift, Go, ... and, I mean, seriously.

ranger_danger 1y ago
I wished Swift got more love, I feel like it takes the "most familiar" (to C++ devs) approach to improving things, as it keeps the syntax extremely similar to C++ but fixes a lot of the issues it has, and adds some very nice things too, like memory safety and named function parameters (which Objective-C had since forever).

nickysielicki 1y ago

Boo fucking hoo, C++ isn’t C with classes. Anyone with a basic grasp of c++11 metaprogramming can more-or-less follow this easily. God forbid the language grows.

teleforce 1y ago
The GP is not wrong though. Perhaps someone can write similar logic in D programming and showcase how much more intuitive the programming will be since Dlang has first class arrays and its metaprogramming facility is second to none [1]. [1] D (programming language): https://en.wikipedia.org/wiki/D_(programming_language) https://en.wikipedia.org/wiki/D_(programming_language)