timholy
commented
4 years ago Dang! A real tour de force. I had only just started thinking along similar lines, but had gotten nowhere close to where you've arrived. I think ImageFiltering could easily have blocks that look like
if all(s->s <= 9, size(kern))
wrappedkernel = SizedOffsetArray{params...}(kern)
_imfilter!(out, img, wrappedkernel)
else
_imfilter!(out, img, kernel)
endThere's going to be dynamic dispatch for the Sized case but that's probably not a problem in practice unless people are filtering really tiny arrays. We could even pull out very common cases (e.g., axes are (-1:1, -1:1)) and do what is essentially manual union-splitting.
Is it worth asking whether it makes sense to just provide static size information about the first dimension of the kernel? That would make it easy to have a block like
if axes(kern, 1) === Base.IdentityUnitRange(-1:1)
_imfilter!(out, img, StaticSize1{-1,1}(kern))
if axes(kern, 1) === Base.IdentityUnitRange(0:2)
_imfilter!(out, img, StaticSize1{0,2}(kern))
if axes(kern, 1) === Base.IdentityUnitRange(-2:0)
_imfilter!(out, img, StaticSize1{-2,0}(kern))
elseif axes(kern, 1) === Base.IdentityUnitRange(-2:2)
_imfilter!(out, img, StaticSize1{-2,2}(kern))
elseif ...
else ...
endand it would never need dynamic dispatch.
My suspicion is that, given your demo above, this particular use of dynamic dispatch is not worth worrying about and we should provide static information for any reasonably-small kernel. We're talking microseconds vs nanoseconds.
chriselrod
LaurentPlagne
I've simplified the lowering code as a first step, but it still expects input in terms of unrolled and tiled. This should be replaced with a vector of integers indicating by how much each loop is unrolled (1 means not unrolled).
The more complicated step will be generalizing the constrained optimization problem within solve_tilesize to an arbitrary number of dimensions.
I think I'll have it handle unrolling a single loop as a special case. The
solve_tilesizefunction tries to occupy all the registers, which wouldn't really be appropriate for a single loop.It also needs the ability to recognize more kinds of loads that can be eliminated. In particular, it should be able to realize that if an array is accessed with both
A[i]andA[i+1], unrollingiwill only require a single extra load, not 2 extra loads, becauseA[i+1]==A[(i+1)].The motivating example was inspired by @timholy , although before LoopVectorization is going to see major benefits over the current performance, it will have to be able to realize t
Most of the code here is also in the offset array tests.
@avxyields a substantial improvement:This yields a substantial improvement, but we'd naturally always wonder if we can do better. Let's find out what it's doing.
This means that it orders the loops
[:j, :i, :jk, :ik](which happens to be the same order in which they were written, but this is not true in general). The next two symbols indicate thatikandjare unrolled (4x and 4x, respectively), whileiis "vectorized". These numbers are machine-dependent, so you're likely to at least see different unroll factors if you don't have avx512 (i.e., something other than 4 and 4).The most obvious problem we may notice here is that the
ikloop is only 3 iterations long, so unrolling by 4 is excessive. We can improve that with static size information:Getting show to work off the
AbstractArrayinterface would take some more methods.To see that this works, we'll have to inspect a
LoopSetobject created with type information (not from an expression). The@avx_debugmacro lets us do this, but requires all the symbols in the loop to be defined (otherwise, which object's types will it be reading?)It
gensyms names, but we can figure out thatSymbol("##n#1304")is theikloop as before, but it is now unrolled by a factor of 3, matching the length of this loop.LoopVectorization's optimizer uses this static size information, but much of the lowering does not: it'll still generate code to handle other sizes. Addressing that's been a low priority, because I've found LLVM to be very good at eliminating all the code handling other sizes.
This yields a sizeable performance improvement:
Yet, I think ideally, it ought to be much more aggressive.
It's important to emphasize that most modern CPU's throughput for unaligned loads is half that of
fmainstructions. This means that naively following how the function is written, where you load from bothAandkernfor eachfma, it will spend up to 4 times longer loading memory than it will computing arithmetic. Loading and arithmetic don't really interfere, so the time is going to be governed largely by memory loading; anything we can do will help.Given static size information, it should completely unroll the small
-1:1loops, and then additionally unroll the other loops to save on redundant loads. Then we know for sure it is not reloadingkern, and the additional unrolling on theiandjloops will yield savings because of all the reuse we get since many of them will be the same across iterations.This yields
Another big improvement. But, LoopVectorization doesn't realize how aggressive it can get yet, due to not itself realizing that many of the loads alias. LLVM does, so it should eliminate redundant loads and give us the performance benefits, even if we cheat to make LoopVectorization be more aggressive.
I'm specifying 4,4 here, and performance looks quite good. Without AVX512, it is likely that smaller numbers will give you better performance. The generated assembly shows lots of chunks that look like this:
Mountains of vectorized arithmetic. (Note however that many of the
vfmadd___psinstructions accessmem)Finally, we can align the loads and stores by spacing the columns of
Aandoutat multiples of 64-byte intervals (64 bytes is 16 xFloat32):That's more than 40x the original version without LoopVectorization! But it'd be great if we could get this performance automatically (or, at least automatically given size information), without the need for both
Base.Cartesianunrolling and manually specifying additional unrolling behavior on top of it.