PERF, TODO: Ensure 128-bit alignment all rows/columns for SIMD friendliness

[stephenwlin]

Split off from #3114 ...

It doesn't seem (from my testing) that numpy guarantees 128-bit alignment the start of an array (which is odd, since malloc usually does that no matter what, from my testing), and it certainly doesn't 128-bit align each row/column since they're always contiguous.

Apparently it can be done manually via a method like described below:
http://mail.scipy.org/pipermail/scipy-user/2009-March/020283.html
(This just aligns the start of the array, but if you overallocate more and play with strides you can do the same thing to every c-contig row or f-contig column)

The downside is that this has to be done everywhere where allocation currently happens...even with a helper function to do it it's going to be somewhat messy.

Also, to avoid too much overhead, I think this should only be done when each row/column is at least 256 bits (32 bytes) naturally, so the absolute worst case space penalty is 33% + 96 bits constant (on a 32-bit machine) or 20% + 64 bits constant (on a 64-bit machine)...

We can bump that up a bit higher to 512 bits if that still seems like too much, but it means that DataFrames with 5-7 float64/int64 columns could be pathologically misaligned. (So basically, this won't help at all until at least 9 columns are present...)

[stephenwlin]

@y-p

alignment can yield big wins. most def.

need to validate that this is what's actually happening though.

Already almost 99% sure that arrays are not always 128-bit aligned at the start (I tried testing for it manually at runtime from Cython, requiring both input and output arrays to be 128-bit aligned basically eliminates the effect of my refinement, meaning they're almost never both aligned unless randomly so), I don't know if that's causing the entire performance/variability issue but it can't be helping.

This sounds like it might involve some pain to apply throughout?

Just getting some perf numbers on a toy example, measuring the
benefit if any, would be real interesting...

This really is turning into an ATLAS/BLAS style line of research.. :)

[stephenwlin]

@y-p can probably just target a few key cases (block consolidation, DataFrame construction, etc.) to handle 90%...and with a helper function

Making performant code often involves making the codebase more fragmented,
less readable, and raises the entry barrier for new developers to come in.
Just a good idea to do a spot check to make sure the perf gains are significant
enough before monkey patching the libc with inline asm....

Would this be somehthing users can employ in their own code, so if they
invest the effort, pandas perf will benefit? or does it strictly require changes
to pandas itself?

[stephenwlin]

@y-p I think just handling allocations that Python does internally is good enough...if someone passes us a non-aligned array then we just won't trigger the optimized case (detecting alignment at runtime is easy, just convert the pointer to an integer and mod 16)...to be honest, just handling the block consolidation case might do 75% of what we need in practice (but not for the test suite, since it almost never consolidates), and that's just one line of code.

[stephenwlin]

Also, notice that on the low-end, I've gotten results with my SIMD-triggering small-array optimization like:

frame_reindex_axis0                         0.4789     1.0887     0.4399
frame_reindex_axis0                         0.4191     0.9355     0.4480

This happened more than once and on an overnight run with no competing processes, so it's probably not a fluke.

The high end results:

frame_reindex_axis0                         1.4141     0.4546     3.1107
frame_reindex_axis0                         1.4211     0.4163     3.4140

make sense too because it's repeatedly calling the vectorized code in a loop, but the vectorized code needs to check for alignment at the beginning and end of both input and output source arrays. If the stride is not a multiple of 128-bits, then the alignments will be random (since the indexing is random as well) and branch prediction will not only defeated, you'll actually pay a significant penalty having to revert the mispredicted pipeline. (See Why is processing a sorted array faster than an unsorted array?)

That looks really promising.

[stephenwlin]

@wesm any thoughts on the space overhead? (again, worst case would be at 288 bits per row, bumped up to 384 bits per row, all downhill from there. (guess we have to see how much performance improves at that size, first, of course, just curious if you think its enough overhead to be relevant)

[jreback]

I suspect there might be a nice trade off here

say u increase memory by 1.5x but get 1.5 speed improvement
I would take that say <10000 rows for sure

[stephenwlin]

@jreback looks more like absolute-worst-case 33% (i.e. 1.33x) space for up to 125% (i.e. 2.25x) improvement (or possibly more, with further refinement), we'll see after more testing :)...we can always bump up the minimum size for alignment but that means that anyone with fewer columns per block than the minimum gets the short shrift even if they'd prefer the speed

[jreback]

then that's even better

wonder how that scales to lots of rows ...

[stephenwlin]

@y-p non-cached builds have the same variability, apparently, so your build cacher is vindicated :) (sorry for the bad guess!)

link

[stephenwlin]

if 288 -> 384 is ok, then 192 -> 256 should be ok too (same ratio)...so this allows speedup anytime >= 3 int64/float64 are stored together

[stephenwlin]

wonder how that scales to lots of rows ...

The percent improvement should stay constant (or even get better, due to better branch prediction) as the number of rows increases; the real variable is the size of the copied row (not sure if that's what you meant...)...presumably it should improve the most with smaller rows and then gradually even out until you get to 256 bytes (which is where we start calling memmove() anyway)