3 ms·

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

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

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