[2022 day 2 - AVX]
Back when we looked at this one, about a week ago, I said that I would like to write a proper bleeding edge (unsafe{}) AVX intrinsic version, well I finally got it done and I'm quite amazed:
for b in 0..blocks {
let bl = input.as_ptr().add(b*64) as *const __m256i;
let b1 = _mm256_loadu_si256(bl);
let b2 = _mm256_loadu_si256(bl.add(1));
let b1h = _mm256_and_si256(b1, xyz_mask);
let b2h = _mm256_and_si256(b2, xyz_mask);
let b1l = _mm256_and_si256(b1, abc_mask);
let b2l = _mm256_and_si256(b2, abc_mask);
let b1h = _mm256_srli_epi32(b1h, 14);
let b2h = _mm256_srli_epi32(b2h, 14);
let b1hash = _mm256_or_si256(b1l, b1h);
let b2hash = _mm256_or_si256(b2l, b2h);
let b16 =_mm256_packus_epi32(b1hash, b2hash);
let inc1 = _mm256_shuffle_epi8(part1shuffle, b16);
let inc2 = _mm256_shuffle_epi8(part2shuffle, b16);
part1 = _mm256_add_epi16(part1, inc1);
part2 = _mm256_add_epi16(part2, inc2);
}
These 15 AVX ops are the full solver that handles a block of 16 input lines, I pad the input with 48 space chars (10048 is divisible by 64) so that I don't have to worry about the tail end.
It is probably clear, but the algorithm starts with u/ednl's packing (AND both chars with 3, shift the second one down 14 bits and merge, that's the first 10 AVX ops.
Next I pack together the two 32-bit arrays into a single 16-bit one (b16 above), before I use that variable twice to directly lookup the 8 part1 and part2 results for these lines.
So, with a single AVX op/cycle this should take a fraction less than a clock cycle per input line, right?
I do measure 3 us on my Acer, but now we get to the interesting part:
When I instead run u/maneatingape on my input file, I get 2.3 us, for much simpler and shorter integer only code!
That time is broken down into 1.2 us to convert all 2500 lines into a 0..8 index, using code like this
pub fn parse(input: &str) -> Vec<u8> {
input.as_bytes().chunks_exact(4).map(|c| 3 * (c[0] - b'A') + c[2] - b'X').collect()
}
(The original code generates an array of usize, when I switched to u8 the parsing stage dropped to 1.1 us and the total from 2.3 to 2.2 us)
In order to manage this, the CPU has to convert two lines per nanosecond, probably using code somewhat like this, which has a minimum latency of 4 cycles. The CPU must internally unroll the code over a bunch of iterations, enough to gain back the AVX advantage and then beat it!
movzx rax,[rsi]
movzx rbx,[rsi+2]
sub rax,'A'
sub rbx,'X'
lea rax,[rax+rax*2]
add rax,rbx
;; push into vector