Support for Signed Types Integrated in the CODECs

[iiSeymour]

I have an interest in using streamvbyte with signed types (specifically int16) and have created a Python wrapper which supports this however the overhead is quite large as you would imagine iiSeymour/pystreamvbyte#1.

Native support for an efficient zigzag encoding/decoding for int16 and int32 would be great. I imagine this is something that would vectorise well?

[lemire]

Yes. I expect it would vectorize very well.

[aqrit]

Zigzag support for int32 is implemented in this branch: here

specifically:
zigzag ops
decoder
encoder

[lemire]

@aqrit Is there are clean way to bring this into the main streamvbyte repo? Want to issue a PR? Or do we do something dirtier?

[aqrit]

Is there are clean way to bring this into the main streamvbyte repo?

Not really, I touched everything. It currently lacks the ARM routines. My original plan was to implement a AVX2 table-less version then package it up... but I never got around to it.

[lemire]

@iiSeymour

What about this then... As a stopgap measure, we add zigzag_decode and zigzag_encode functions to the library with definitions such as these...

https://gist.github.com/lemire/b6437fbd193395d8e4ccac1a5b2e50cc

This is such simple code that the autovectorizer should do a fine job (with GCC using -O3, with clang use -O2).

Then you can call these functions as needed, to convert your signed integers into unsigned integers and back.

It is not going to be as fast as having zigzag encoding integrating in the main functions, but it should be a lot faster than doing the conversion in Python or whatever else.

We would leave the issue open, to be resolved with better code... but you'd have an 'ok' fix meanwhile.

Thoughts?

[iiSeymour]

Sounds like a plan 👍

[lemire]

Implemented in the latest release. Make sure to compile with aggressive optimization flags and it should be quite fast.

[0x55555555]

Testing some implementations we have internally I've found the following code to perform quite well:

https://gist.github.com/jorj1988/a2f2f14719d46074900dd563dc31a1c7

It does a delta >> zigzag >> expand to 32 bit >> streambyte encode

[lemire]

Thanks. That is a useful reference.

[iiSeymour]

With delta zigzag as per #29 I see about a 40% improvement over my Python implementation with int32 arrays and 20% with int16 (the extra cast is expensive).