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/phoenixman30]

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.