Reduce the size of the lookup tables

[lemire]

The current lookup tables are quite large. Finding a way to substantially reduce their memory usage without adversally affecting performance would be a worthy goal.

[aqrit]

The table for the encoding shuffle can be reduced by 75%.
This would cost 1 cycle per loop, I believe.

Same idea as the small tables in simd_prune/despacer projects.
Bit-6 and bit-7 of the key byte can be ignored if the corresponding input bytes (the last four bytes) are always written to the output. Unwanted output byte(s) will be overwritten by the next chunk, anyways.

Thus the table only needs 64x16 bytes instead of 256x16 bytes.

[aqrit]

Just mask off the top 2-bits of the key byte

https://gist.github.com/aqrit/9272c47b3f1ce23c565a7210b6935102#file-svb_alt-c-L398

[lemire]

Damn!!! You are right.

[lemire]

Update: I was thinking about the encoder in my reply.

Coming back to it, I don't see how it can work. The last two bits give us how many bytes are non-null in the last of 4 integers.

Suppose you don't have this information... then you will fill the last four bytes with data. It is not true that "unwanted output byte(s) will be overwritten by the next chunk, anyways." You need some way to set to zero the unwanted bytes.

If you have some way to make it work, please share.

Your general idea is directly applicable to other problems, however. But I don't see it here.

[aqrit]

You need some way to set to zero the unwanted bytes.

The encoder never needs to zero bytes. Ever.

Suppose you don't have this information...

The info is still saved for use by the decoder.

here is a working drop-in-replacement:
https://gist.github.com/aqrit/746d2f5e4ad1909230e2283272333dc1

please test.

[lemire]

Oh! OH ! For the encoder. I see. Yes.

[lemire]

Good point. I was thinking about the decoder.

[lemire]

@KWillets @vkazanov : It seems that @aqrit has a fast vectorized encoder that uses smaller tables (and thus less cache).

[aqrit]

The decoding shuffle table size could be reduced by 75% ... (256x16 vs 256x4)
at a cost of 1 cycle per 128-bits of output (AFAIK)

The shuffle control masks get compressed to 32-bit integers.
Masks are decompressed (32->128) by two instructions.
However, the table index now scales for "free",
saving 1 instruction.

gist

[lemire]

Looks clever. I'll investigate soon.

[lemire]

Completed with efb310d

Your name has been added as author.

[aqrit]

Neat.
Though, I've still got things to try on my todo list:

1. Transpose of elements during delta encoding to boost delta decode speed?
   Back of the envelope calculations -- for a block of 14 xmmwords - indicate that'd shave 30 instructions off from decoding (per block)... but one would have to wait until all 14 xmmwords were unpacked to begin the delta decode step, so...?

2. Using AVX2, check the speed of generating the 'compact' (32-bit) decode shuffle control on-the-fly? Obviously this requires a format change, the 2-bit keys would have to be interleaved (1 per byte) instead of packed (all 4 in one byte).

3. New tail loop on SSSE3 decoder if original count was 16 or greater.

dataPtr -= 4;
for(...){
    size_t k = keys & 3;
    keys >>= 2;
    dataPtr = dataPtr + k + 1;
    uint32_t dw = *((uint32_t*)dataPtr); 
    dw >>= ((k ^ 3) * 8); 
}

4. Add zigzag delta transform

[lemire]

+1