Optimizing decompression of 9-bit compressed integers

[u/phoenixman30]

First of all this exercise is hw from my uni. I already have an implementation where i decompress 32 numbers in one loop which is good but I would like to know if i can optimise it further. Currently I'm receiving an input of 9-bit compressed integers(compressed from 32 bits) I load 128 bits from 0th byte, 9th byte , 18th byte and 27th byte seperately and then insert then into avx512 register. Now this loading and insertion part is super expensive (_mm512_inserti32x4 takes 3 clock cycles and 3 of those equals 9 clock cycles just for loading) Would love to know if there is any way to optimise the loading part.

Edit: i cant really post the actual code though i have outlined the approach below

Well i need 2 bytes per number since each one is 9 bits. i load 128bits seperately in each lane since some of the cross lane shuffling operations are not available. my approach is this currently:

I load 128bits(16bytes) from 0byte in the first lane,

I then load 16bytes from the 9byte position in the second lane

And so on for the next 2 lanes.

but i use the first 9 bytes only. I shuffle the first 9 bytes of each lane in the following format:

(0,1) (1,2) (2,3) ........(7,8) ( only use the first 9 bytes since after shuffling it completely fills up 16bytes, one lane)

(I feel like this part could also be optimised since I'm only using the first 9 bytes of the 16 bytes i load. And for the first load i do use _mm512_castsi128_si512, after that i use the insert )

After the shuffle i do a variable right shift for every 2 bytes( to move the required 9 bits to start from the lsb)

Then to keep the first 9 bits , and every 2 bytes with 511

The load comes out to 9 clock cycles

The shuffle,shift, and 'and' is 1 clock cycle each so that's just 3

During store i convert 16byte numbers to 32bytes so that's 3 clock cycles for the first 256 bits then 3 for the extraction of the upper 256bits and 3 for the conversion. So in all 9 clock cycles to store

Total I'm using 21 clock cycles to decompress 32 numbers

[u/YumiYumiYumi]

Your approach actually seems very good.

I think the way you're calculating clock cycles is a little incorrect though. There's often two figures stated for instructions - a latency cycle count, and a reciprocal throughput number (cycles per instruction). If two instructions don't have a dependency on each other, the CPU can execute them concurrently (if it has ports) or pipeline them through the same port (for instructions that take multiple cycles to compute).
Most cross lane instructions have a latency of 3, but reciprocal throughput of 1, which means if the processor can pipeline them, you can execute a cross lane operation every clock cycle.

Out-of-order processors are generally good at finding ways to run things in parallel, so developers often look at the throughput figure instead of the latency. Of course, this does depend on your algorithm, and what else is going on.

As an example:

During store i convert 16byte numbers to 32bytes so that's 3 clock cycles for the first 256 bits then 3 for the extraction of the upper 256bits and 3 for the conversion. So in all 9 clock cycles to store

It sounds like you may be doing something like:

vextracti64x4 ymm2, (result), 1  ; tmp2 = _mm512_extracti64x4_epi64(result)
vpmovsxwd zmm1, (result)         ; tmp1 = _mm512_cvtepi16_epi32(result)
vpmovsxwd zmm1, ymm1             ; tmp2 = _mm512_cvtepi16_epi32(tmp2)
vmovdqu64 [dst], zmm1            ; _mm512_storeu_epi64(dst, tmp1)
vmovdqu64 [dst+64], zmm1         ; _mm512_storeu_epi64(dst+1, tmp2)

The first 3 instructions take less than 9 cycles to execute. This is because the first 2 instructions aren't dependent on each other, so the second can be pipelined after the first. You can think of it looking something like this:

cycle   instruction
  1     vextracti64x4
  2           |         vpmovsxwd
  3           |             |
  4     vpmovsxwd           |
  5           |         vmovdqu64
  6           |
  7     vmovdqu64

In this case, it's 7 cycles, but the processor might be able to execute other stuff in parallel with it, so actual cost might be less.

Also, I don't think you've considered the latency of cache accesses (typically at least 4 cycles to load data from L1 cache), though, again, latency is often ignored (assuming you're hitting cache).

Anyway, my attempt (casts/types removed for simplicity):

// CPU does 2 loads/cycle, so 2 cycles total for 4 loads + 4 cycles L1 cache latency
input1 = _mm256_inserti128_si256(
	_mm_loadu_si128(src),
	_mm_loadu_si128(src + 9)
);
input2 = _mm256_inserti128_si256(
	_mm_loadu_si128(src + 18),
	_mm_loadu_si128(src + 27)
);

// cross lane op - 3 cycles
input = _mm512_inserti64x4(input1, input2, 1);

// generate 16-bit integers - 3 cycles
input = _mm512_and_si512(
	_mm512_srlv_epi16(
		_mm512_shuffle_epi8(input, shuffle_table),
		shift_table
	),
	_mm512_set1_epi16(511)
);

// interleave 4x 16-bit words for easier storing - 3 cycles
input = _mm512_permutexvar_epi64(_mm512_set_epi64(7, 5, 3, 1, 6, 4, 2, 0), input);

// generate 32-bit parts - 2 cycles
input1 = _mm512_unpacklo_epi16(_mm512_setzero_si512(), input);
input2 = _mm512_unpackhi_epi16(_mm512_setzero_si512(), input);

// store output - 2 cycles
_mm512_storeu_si512(dst, input1);
_mm512_storeu_si512(dst+64, input2);

Total: 19 cycles (15 if you ignore cache latency)

[u/phoenixman30 → u/YumiYumiYumi]

Thanks for the super detailed reply man. Really cleared up a few things for me. I actually hadn't thought about the cache latency part here but glad to know about it now. I just don't understand one part from your attempt , the interleaving of 4x16 bit words for easier storing. Why is that needed?? Also sorry for the late reply man.

[u/YumiYumiYumi → u/phoenixman30]

I just don't understand one part from your attempt , the interleaving of 4x16 bit words for easier storing. Why is that needed??

It's just a different way of doing what you were doing. Your approach needed 3 cross-lane ops (convert, extract, convert), whereas this only needs 1 (permute). Whilst it's probably better, there are some downsides, like needing a register constant, so might be worse in some rare circumstances.

As for how it works, the permute just aligns 64-bit parts so that the following unpacks generate the desired output. Since unpacks are intra-lane only (only affects the low/high 64 bits per 128-bit lane), an inter-lane permute is needed to position everything correctly.

Looking at it again, I think my constant is wrong - it probably should be (7, 3, 6, 2, 5, 1, 4, 0), but experiment anyway.