FizzBuzz – SIMD Style
morling.dev
morling.dev
You don’t need modulo instruction when the divisor is known at compile-time.
Good compilers routinely implement integer division and modulo as a sequence of faster instructions like multiplication and bit shifts. Here’s examples: https://godbolt.org/z/4noTxP
Works for SIMD just fine. Take a look at what clang auto-vectorizer did: https://godbolt.org/z/q4bcfj You see what happened to the code? It turned into a bunch of AVX2 instructions, and the loop is gone.
Turns out that you can represent a great many division problems in terms of a * (b / 4294967296).
For example, a / 2 coincides with a * 2147483648/4294967296. a / 3 coincides with a * 1431655765 / 4294967296.
------
That's the basis of the trick. The devil is in the details however. You'll find that floor(a x b / 4294967296) is not exactly equivalent to integer division: some values are "off" slightly. A few adds, or subtracts can correct for this error.
Some values are "perfect" and don't need correction. The compiler will build off of these perfect values and combine them with adds and bitshifts.
-----
Before compilers were good, embedded engineers were basically expected to know how to do this. Most embedded CPUs had no division operator (including ARMv7 and older, but also 8051 and other venerable microprocessors).
The "imperfect" division was probably most used back then. Compilers however have to implement bit-perfect results (exactly equivalent to a division operator). Embedded engineers can often make the decision that "imperfect division" was good enough.
Even JIT compilers do these optimizations: https://sharplab.io/#gist:ce7f7677cbb9f43efe74aeeadb75deb1
>
> me: Oh, just two layers deep -- one hidden layer and one output layer
Actual LOL.
Thanks for sharing!
As you noticed, the FizzBuzz pattern has a period of 15. So if you want to go fast, just go directly to a 15x vectorized unroll with unaligned stores.
Assuming 32-byte vectors like with AVX2, you initialize two vector registers v0, v1 to hold the pattern of 15 4-byte values (the 16th value doesn't matter) corresponding to 0 through 15. You also have corresponding delta vector registers d0, d1 whose entries are +15 for the "pass-through" values and 0 for the -1/-2/-3 sentinel values. The loop kernel is just this:
store_unaligned(p, v0)
store_unaligned(p + 8, v1)
v0 += d0
v1 += d1
p += 15
You could remove the unaligned stores with a monstrous lcm(15, 16) = 240x unroll (16 shifted instances of the above kernel) but you wouldn't be able to keep all the necessary loop state in registers.
I have used FizzBuzz as an introduction to wheels. Any repeating sequence will do, but everyone knows FizzBuzz. It is a great example of that because you replace a simple algorithm with one that is also simple and about twice as fast in my language of choice (using circular, singly linked lists for the wheel).
The article does a similar thing, but using masks to achieve the speedup.
Call what a wheel? What is the "it" here?
It doesn't seem to be a standard term but since you went to the trouble of posting a comment surely you were hoping it would be understood. Are you talking about modulo arithmetic? Or hierarchical timing wheels (the top hit for "wheel data structure")?
Any data structure will do. Either a circular one or one with O(1) access time. It is the concept used in the article with a vector mask repeating every 15 elements.
It is a technique. I have just always used a circular list for it :)
private static final int[] VALUES = range(0, 16).map(FizzBuzz::fizzbuzz).toArray();
private static final int[] DELTAS = stream(VALUES).map(v -> v < 0? 0: 15).toArray();
private static final VectorSpecies<Integer> SPECIES = IntVector.SPECIES_256;
private static int fizzbuzz(int i) {
return i % 15 == 0? FIZZ_BUZZ: i % 5 == 0? BUZZ: i % 3 == 0? FIZZ: i;
}
public static int[] simdFizzBuzz(int length) {
var result = new int[length];
var v1 = IntVector.fromArray(SPECIES, VALUES, 0);
var v2 = IntVector.fromArray(SPECIES, VALUES, 8);
var d1 = IntVector.fromArray(SPECIES, DELTAS, 0);
var d2 = IntVector.fromArray(SPECIES, DELTAS, 8);
var i = 0;
var upperBound = length - length % 15;
for(; i < upperBound; i += 15) {
v1.intoArray(result, i);
v2.intoArray(result, i + 8);
v1 = v1.add(d1);
v2 = v2.add(d2);
}
for(; i < length; i++) {
result[i] = fizzbuzz(i);
}
return result;
}
// We need i + 15 < length to keep the last written entry in bounds.
for (; i < length - 15; i += 15)And there is no primitive for masking on AVX2, those are only available on AVX-256.
if we want to minimize the iterations of the post loop, it should be
var upperBound = length % 15 == 0? length - 15: length - length % 15;
var upperBound = length - 15Sure there is a masking MOV in the original AVX (thus including AVX2), VMASKMOV. Works for both masked loads and stores.
https://www.felixcloutier.com/x86/vmaskmov
Notably: "Faults occur only due to mask-bit required memory accesses that caused the faults. Faults will not occur due to referencing any memory location if the corresponding mask bit for that memory location is 0. For example, no faults will be detected if the mask bits are all zero."
A nitpick: there's no such thing as AVX-256, you probably meant AVX-512.
var mask = VectorMask.fromLong(SPECIES, 0b0111_1111);
var i = 0;
var upperBound = length - length % 15;
for(; i < upperBound; i += 15) {
v1.intoArray(result, i);
v2.intoArray(result, i + 8, mask);
...That's cheating!! :D