Hacker News Reader

Comment by zeotroph | Hacker News Reader

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/

View on HN

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

C++ supports it if you're willing to use more or less complicated templates:

http://bannalia.blogspot.de/2015/09/c-encapsulation-for-data...

https://blog.molecular-matters.com/2013/10/22/implementing-a...

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)

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?

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

I'm guessing the GCC feature and removal is this here?

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/golovanev...

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

There's also a tradition of older metaprogramming approaches in data layout optimizations, eg. ATLAS BLAS.

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.

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

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

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

Reply on news.ycombinator.com