3 ms·

> As the table reveals, every time this function performs a multiplication, only 8 out of 82 (9+30+28+8+7=82) instructions are doing the “real” multiplication.

> As the table reveals, every time this function performs a multiplication, only 8 out of 82 (9+30+28+8+7=82) instructions are doing the “real” multiplication. That's only about 10% of the total instructions. The other 90% are considered interpretation overhead. Once we vectorized this function, its performance was improved by nearly nine times. See PR #12543. This is a misleading way to present this data. If I understand this correctly, most of the 90% "interpretation overhead" are time spent evaluating the operands to the multiplication, and this is also vectorized. So it's not just that vectorizing the 10% can give you a 9x speedup overall, although in my opinion the text tries to suggest this. In any case, there must be even more going on here. The data being processed here seem to be Float64. On an AVX-2 processor like most of us have, you can only fit up to 4 64-bit floats into a vector register. This means that, even if your entire computation vectorizes very very nicely, you should only expect a 4x maximum speedup. Even if they have an AVX-512 server (they don't say) with twice the vector width, 8x would be the expected limit. In practice it would be considerably less because the processor reduces its frequency to avoid overheating on AVX-512-heavy computations. I'm not aware of hardware that uses even wider vectors. So an end-to-end 9x improvement for the entire function here seems impossible to achieve using vectorization alone. I question both the measurement and the suggestion that vectorization is the only thing that changes here. Maybe they accidentally (? they don't seem to understand in detail what's going on) stumbled upon a much more cache friendly version of the computation they were trying to do, or maybe previously they caused the GC to interfere, or... something. But 9x due to vectorization of a Float64 computation? I'm not buying it.

justincormack 7y ago
Column access is way more cache friendly for most database computations, yes, as the values being computed are contiguous. They don't give the partial speedup for switching from row to column before they vectorised, it is probably significant.
vitus 7y ago
The article describes three optimizations: - Changing the memory layout to be column-oriented (i.e. for greater cache friendliness, as the sibling comment mentions). - Iterating over batches (analogous, possibly equivalent to loop unrolling). - Vectorizing. Iterating over batches (especially going from batches of 1 -> 1024) could very well explain a large portion of the "interpretation overhead" that was removed, since it'd basically just be checking loop conditions and jumping back to the beginning of the loop; in that case, it can be a significant portion of the overall execution, and batching in this way reduces that overhead by 1000x. And sure, vectorizing might only add up to a 4x speedup, but taken with these other changes (especially don't discount cache coherence), I could totally see where the 10x comes from. So the submission title is somewhat misleading to attribute all of it to vectorization (the article title also cites the community), but I could see it being valid, since these were steps needed to take full advantage of vectorization. I do object to the measurement of execution in instructions, since in x86 not every instruction is created equal (multiplications are the poster child of "instructions that take a long time", and certain AVX instructions can cause throttling in Intel CPUs). That said, the article does cite a nearly 9x speedup, which is solid.
mping 7y ago
I believe that in db context, vectorization means batch processing column wise. Quoting the CockroachDB blog post: Using vectorized processing in an execution engine makes more efficient use of modern CPUs by changing the data orientation (from rows to columns) to get more out of the CPU cache and deep instruction pipelines by operating on batches of data at a time. Here is the link: https://www.cockroachlabs.com/blog/how-we-built-a-vectorized-sql-engine/ https://www.cockroachlabs.com/blog/how-we-built-a-vectorized...
- senderista 7y ago
  That’s right, I believe it was MonetDB that introduced this abuse of terminology into the DB lit and it's stuck. I remember being very confused as well, looking for any mention of SIMD instructions in the MonetDB paper and finding none :) ("Pipelining" is another term that the DB community uses differently from everyone else--nobody else would refer to single-threaded execution as "pipelined".) The other typical optimization for expression evaluation is code generation, which usually targets LLVM bitcode or Java bytecode. That's pretty standard for column-oriented databases now and they're not exactly state of the art if they don't implement some equivalent of the above.
- tom_mellior 7y ago
  Ah, thanks. What a terrible abuse of terminology.

justincormack 7y ago

Column access is way more cache friendly for most database computations, yes, as the values being computed are contiguous. They don't give the partial speedup for switching from row to column before they vectorised, it is probably significant.

vitus 7y ago

The article describes three optimizations: - Changing the memory layout to be column-oriented (i.e. for greater cache friendliness, as the sibling comment mentions). - Iterating over batches (analogous, possibly equivalent to loop unrolling). - Vectorizing. Iterating over batches (especially going from batches of 1 -> 1024) could very well explain a large portion of the "interpretation overhead" that was removed, since it'd basically just be checking loop conditions and jumping back to the beginning of the loop; in that case, it can be a significant portion of the overall execution, and batching in this way reduces that overhead by 1000x. And sure, vectorizing might only add up to a 4x speedup, but taken with these other changes (especially don't discount cache coherence), I could totally see where the 10x comes from. So the submission title is somewhat misleading to attribute all of it to vectorization (the article title also cites the community), but I could see it being valid, since these were steps needed to take full advantage of vectorization. I do object to the measurement of execution in instructions, since in x86 not every instruction is created equal (multiplications are the poster child of "instructions that take a long time", and certain AVX instructions can cause throttling in Intel CPUs). That said, the article does cite a nearly 9x speedup, which is solid.

mping 7y ago

I believe that in db context, vectorization means batch processing column wise. Quoting the CockroachDB blog post: Using vectorized processing in an execution engine makes more efficient use of modern CPUs by changing the data orientation (from rows to columns) to get more out of the CPU cache and deep instruction pipelines by operating on batches of data at a time. Here is the link: https://www.cockroachlabs.com/blog/how-we-built-a-vectorized-sql-engine/ https://www.cockroachlabs.com/blog/how-we-built-a-vectorized...

senderista 7y ago
That’s right, I believe it was MonetDB that introduced this abuse of terminology into the DB lit and it's stuck. I remember being very confused as well, looking for any mention of SIMD instructions in the MonetDB paper and finding none :) ("Pipelining" is another term that the DB community uses differently from everyone else--nobody else would refer to single-threaded execution as "pipelined".) The other typical optimization for expression evaluation is code generation, which usually targets LLVM bitcode or Java bytecode. That's pretty standard for column-oriented databases now and they're not exactly state of the art if they don't implement some equivalent of the above.
tom_mellior 7y ago
Ah, thanks. What a terrible abuse of terminology.