The "core" of the trick is nice : amortizing interpreter dispatch over many items.
(ignoring the column layout/SIMD stuff which basically helps in any case)<p>Essentially it's turning :<p><pre><code> LOAD
DISPATCH
OP1
DISPATCH
OP2
... (once per operation in the expression)
STORE
... (once per row)
</code></pre>
into<p><pre><code> DISPATCH
LOAD
OP1
STORE
LOAD
OP1
STORE
... (once per row)
DISPATCH
... (once per operation in the expression)
</code></pre>
The nice trade-off here is that you don't require code generation to do that, but it's still not optimal.<p>If you can generate code it's even better to fuse the operations, to get something like :<p><pre><code> LOAD
OP1
OP2
...
STORE
LOAD
...
</code></pre>
It helps because even though you can tune your batch size to get mostly cached loads and stores, it's still not free.<p>For example on Haswell you can only issue 1 store per cycle, so if OP is a single add you're leaving up to 3/4 of your theoretical ALU throughput on the table.
Pretty impactful work for an intern! One thing I would have liked to see, both from a process and communication standpoint, is leading with some stats on how much faster the vectorized loops are in isolation from the surrounding engine.<p>It's always good practice to dig into a deep project like this with some napkin estimates of how much you stand to gain, and how much overhead you can afford to spend setting yourself up for the faster computation. (Not to mention how much of your own time is merited!)
Awesome work. Really cool!<p>I have a hobby project to write an analytics DB that uses ISPC for vectorized execution. Currently not much (sums are real easy) but I really wonder if it could reduce the effort to vectorize these sorts of things.
Great write-up. Is the long-term vision to go completely to the vectorised query execution model, or are there cases where a row-oriented plan might be better, such as cases when there are complex computations involving multiple columns of a single row?
Column oriented dbs have been doing parallel (column per thread) joins for a while now, no? And I know they have been leaning heavily on vectorization for over a decade.
Genetic specialization (List<int>) is coming. See <a href="https://openjdk.java.net/projects/valhalla/" rel="nofollow">https://openjdk.java.net/projects/valhalla/</a>. Not this year (value types will be first). But they're working in it really hard.