4 ms·

Apart from Jai [1], are there any languages which support transparent conversion from one format for the programmer (who will prefer AoS) to the other for the c

Apart from Jai [1], are there any languages which support transparent conversion from one format for the programmer (who will prefer AoS) to the other for the compiler/cpu/cache? This feature - plus the inversion of the `inline` keyword (specify where the function is used, not where it is defined) - was what I remember most from the writeup. 1: https://sites.google.com/site/jailanguageprimer/ https://sites.google.com/site/jailanguageprimer/

yomritoyj 10y ago
Haskell's `vector` library does this for vectors of tuples.
asdfaoeu 10y ago
kdb will do this https://kx.com/software.php https://kx.com/software.php . A list of dictionary is converted to a table which is the same as a dictionary to lists.
boomlinde 10y ago
I remember seeing a language that compiled to 6502 do this. I can't remember the name of it, but it was fairly new. On 6502 the advantage is clear, since there is no cache, since index registers are only 8 bits and since they can only be modified by increment/decrement/load/tranfer operations.
DannyBee 10y ago
GCC, ICC, etc, will actually do it with profile guided feedback in whole program optimiation mode, when they determine it is valuable. (Actually, GCC removed it a few years back, whoops)
- zurn 10y ago
  Last I heard it was a fragile benchmark stunt, and compilers would enable the optimization in only very limited circumstances. Has there been progress since?
  - DannyBee 10y ago
    Yes, in the sense that they can do a lot more. It was implemented initially as a fragile stunt. The real problem with it in C based languages is that it requires the real, true, whole program, because it is impossible to not break the ABI of the structure :) In general, memory locality/etc optimizations are more focused on reorganizing loops to walk the data optimally, instead of reorganizing data so normal loops walk them optimally. (See, e.g., polyhedral loop optimizations, which XLC and others ship with. A good paper to read is PLUTO and PLUTO+)
    - deleted 10y ago
      [deleted]
- zurn 10y ago
  I'm guessing the GCC feature and removal is this here? https://gcc.gnu.org/gcc-4.8/changes.html https://gcc.gnu.org/gcc-4.8/changes.html "The struct reorg and matrix reorg optimizations (command-line options -fipa-struct-reorg and -fipa-matrix-reorg) have been removed. They did not always work correctly, nor did they work with link-time optimization (LTO), hence were only applicable to programs consisting of a single translation unit. " Though my web searches don't return hits about SoA in connection to GCC reorg optimizations, and a paper[1] about the struct reorg optimization doesn't mention it either... [1] https://www.research.ibm.com/haifa/dept/svt/papers/golovanevsky.pdf https://www.research.ibm.com/haifa/dept/svt/papers/golovanev...
zurn 10y ago
Depending on your language, you may not need explicit language support. For example these guys have a runtime codegen library that they use (on Scala): https://ppl.stanford.edu/papers/popl13_rompf.pdf https://ppl.stanford.edu/papers/popl13_rompf.pdf There's also a tradition of older metaprogramming approaches in data layout optimizations, eg. ATLAS BLAS.
3JPLW 10y ago
Julia's StructsOfArrays.jl package[1] does this quite simply and easily without needing to modify any downstream code. 1. https://github.com/simonster/StructsOfArrays.jl https://github.com/simonster/StructsOfArrays.jl
Kristine1975 10y ago
C++ supports it if you're willing to use more or less complicated templates: http://bannalia.blogspot.de/2015/09/c-encapsulation-for-data-oriented.html http://bannalia.blogspot.de/2015/09/c-encapsulation-for-data... https://blog.molecular-matters.com/2013/10/22/implementing-a-semi-automatic-structure-of-arrays-data-container/ https://blog.molecular-matters.com/2013/10/22/implementing-a...
chpatrick 10y ago
Haskell's standard vector package supports this: https://hackage.haskell.org/package/vector-0.11.0.0/docs/Data-Vector-Unboxed.html https://hackage.haskell.org/package/vector-0.11.0.0/docs/Dat...

yomritoyj 10y ago

Haskell's `vector` library does this for vectors of tuples.

asdfaoeu 10y ago

kdb will do this https://kx.com/software.php https://kx.com/software.php . A list of dictionary is converted to a table which is the same as a dictionary to lists.

boomlinde 10y ago

I remember seeing a language that compiled to 6502 do this. I can't remember the name of it, but it was fairly new. On 6502 the advantage is clear, since there is no cache, since index registers are only 8 bits and since they can only be modified by increment/decrement/load/tranfer operations.

DannyBee 10y ago

GCC, ICC, etc, will actually do it with profile guided feedback in whole program optimiation mode, when they determine it is valuable. (Actually, GCC removed it a few years back, whoops)

zurn 10y ago
Last I heard it was a fragile benchmark stunt, and compilers would enable the optimization in only very limited circumstances. Has there been progress since?
- DannyBee 10y ago
  Yes, in the sense that they can do a lot more. It was implemented initially as a fragile stunt. The real problem with it in C based languages is that it requires the real, true, whole program, because it is impossible to not break the ABI of the structure :) In general, memory locality/etc optimizations are more focused on reorganizing loops to walk the data optimally, instead of reorganizing data so normal loops walk them optimally. (See, e.g., polyhedral loop optimizations, which XLC and others ship with. A good paper to read is PLUTO and PLUTO+)
  - deleted 10y ago
    [deleted]
zurn 10y ago
I'm guessing the GCC feature and removal is this here? https://gcc.gnu.org/gcc-4.8/changes.html https://gcc.gnu.org/gcc-4.8/changes.html "The struct reorg and matrix reorg optimizations (command-line options -fipa-struct-reorg and -fipa-matrix-reorg) have been removed. They did not always work correctly, nor did they work with link-time optimization (LTO), hence were only applicable to programs consisting of a single translation unit. " Though my web searches don't return hits about SoA in connection to GCC reorg optimizations, and a paper[1] about the struct reorg optimization doesn't mention it either... [1] https://www.research.ibm.com/haifa/dept/svt/papers/golovanevsky.pdf https://www.research.ibm.com/haifa/dept/svt/papers/golovanev...

zurn 10y ago

Depending on your language, you may not need explicit language support. For example these guys have a runtime codegen library that they use (on Scala): https://ppl.stanford.edu/papers/popl13_rompf.pdf https://ppl.stanford.edu/papers/popl13_rompf.pdf There's also a tradition of older metaprogramming approaches in data layout optimizations, eg. ATLAS BLAS.

3JPLW 10y ago

Julia's StructsOfArrays.jl package[1] does this quite simply and easily without needing to modify any downstream code. 1. https://github.com/simonster/StructsOfArrays.jl https://github.com/simonster/StructsOfArrays.jl

Kristine1975 10y ago

C++ supports it if you're willing to use more or less complicated templates: http://bannalia.blogspot.de/2015/09/c-encapsulation-for-data-oriented.html http://bannalia.blogspot.de/2015/09/c-encapsulation-for-data... https://blog.molecular-matters.com/2013/10/22/implementing-a-semi-automatic-structure-of-arrays-data-container/ https://blog.molecular-matters.com/2013/10/22/implementing-a...

chpatrick 10y ago

Haskell's standard vector package supports this: https://hackage.haskell.org/package/vector-0.11.0.0/docs/Data-Vector-Unboxed.html https://hackage.haskell.org/package/vector-0.11.0.0/docs/Dat...