Compute quickly the byte lengths without look-ups

[lemire]

Some look-ups could be efficiently replaced by fast instructions such as a pdep followed by a multiplication and a shift. It is unlikely to be generally faster than a look-up, but it might be worth exploring.

[KWillets]

The length is 1 + the rightmost index in the decoding shuffle, which is within the last four entries.

[lemire]

As per this commit dac1b23 , @KWillets's approach can be enabled by defining a macro. I am concerned about making this a default without enough hard numbers.

Note that I have ported the approach to neon (it was trivial).

[aqrit]

// is mod15 faster than pdep?
len = ((key * 0x0401 & 0x00033033) % 0x0F) + 4; 

// simd
v = ((v >> 2) & 0x33333333) + (v & 0x33333333);
v = ((v >> 4) & 0x0F0F0F0F) + (v & 0x0F0F0F0F);
len4 = v + 0x04040404;
// todo: now extract each byte...

[KWillets]

It is definitely susceptible to various bithacks. I used the permutation table since it's available, but the 2-bit fields could also be summed in a few instructions.

mod15 compiles to a multiply and some shifts and subtracts, so it may be decomposable into fewer instructions in this context.

Generally I would spread the bitfields out and use a multiply to sum them into something like the most significant byte; that's what I do in the compressor when I have the 2-bit fields already spread out. Your method of multiplying by 0x401 and masking looks promising -- they're far enough apart to sum into a nybble at that point. Multiplying by (1<<28)|(1<<24)|(1<<16)|(1<<12) should drop them on top of each other in the high nybble, if I've got those shifts right.

[lemire]

@KWillets @aqrit

I ran some numbers on my blog: Bit hacking versus memoization: a Stream VByte example.

[KWillets]

@lemire @aqrit I started a branch to see if precomputing byte lengths 8-at-a-time and prefix summing would speed up the decode loop. The pointer arithmetic in each decode_avx seemed like a barrier to ILP, and this modification makes it possible to dispatch the 8 decode_avx calls independently.

However it has proved slower for the two methods I've tried (scalar shift/mask/add and a pshufb LUT, both similar to the blog article).

I suspect the pshufb's are already single-threaded (there is only one port for them, I believe), and the length processing is not the critical path.

[aqrit]

@KWillets suggestion:
len = pshuf[12 + (key >> 6)] + 1;

could eventually become:
len = 16 - pshuf[0];

If the literal data bytes get loaded at the high-end of the xmmword...
(rather than the low-end as is currently done)

then the lowest byte of the shuffle mask will also be the number of unused bytes in the data xmmword
(which can be converted to length at little to no additional cost)

gist here

[aqrit]

The length value could broken into bits and deposited into the sign bits of the byte shuffle table.
The length value would be retrieved using pmovmskb. The sign bits get fixed-up for pshufb by adding 0x40 to each byte.

I used this for "0124" decoding in svb0_dec.c over here.