From Fig 3 in https://arxiv.org/pdf/1709.08990.pdf, it looks like the data layout is intended to be big-endian. However, in the test data from https://bitbucket.org/marshallpierce/stream-vbyte-rust/commits/ad95ed76e271a10c0c0bb57e23800a4e23d606e9 encoding 0, 100, 200, 300, ..., we have the following hex (format from hexdump -C):

00000000  40 55 55 55 55 55 55 55  55 55 55 55 55 55 55 55  |@UUUUUUUUUUUUUUU|
00000010  55 55 55 55 55 55 55 55  55 55 55 55 55 55 55 55  |UUUUUUUUUUUUUUUU|

Since the first four numbers are 0, 100, 200, 300 taking 1, 1, 1, 2 bytes respectively, based on the figure's diagram of control bits to encoded ints I would expect the first control byte to be 0b00000001 = 0x01, not 0b01000000 = 0x40.

There are 1250 = 0x4E2 control bytes, so looking at where the encoded numbers start, we see:

000004e0  aa aa 00 64 c8 2c 01 90  01 f4 01 58 02 bc 02 20  |...d.,.....X... |

0 = 0x00, 100 = 0x64, 200 = 0xC8 are single bytes of course, but 300 = 0x012C in big endian, and the sample data has 0x2C01.

Of course, little-endian is just as valid a choice as big-endian! Am I misinterpreting the paper? Should I be letting the user choose which endianness to expect?

SSE vector-based encoder. Encodes a quad of uint's at a time.

This is for non-Delta only. The vector encoder is added to streamvbyte.c, and shuffle tables are moved to an include due to bulk.

I am trying to use streamvbyte in an in-house archiving software which we'll hopefully be able to publish as open source at some point. Your library is a great match for my use-case with it's brilliant performance and compression that's good enough.

There's a catch though.

My stream of uint32_t's looks like the following: 234, 566, 0, 0, 333, 0, 0, 0, 1578987, 0, 234, 444, <a few million uint32_t's more>. Notice that there are lots of zeroes, about 30-40% of the stream. Zero distribution is highly unpredictable, and I know that zero run length is probably gonna be about 2-3 zeroes max.

But streamvbyte can only use 1,2,3,4 bytes per integer, depending on the value. I calculated that for my use case it's much more reasonable to have something like 0,1,2,4, i.e.:

1. I don't want to include zeroes in the stream.
2. I don't really need 3 bytes values.

This would mean that I would only have to keep about 2 bits per zero value.

I am going through your related papers - which are very readable! - and the code and it seems to me that it should be possible to just patch streamvbyte to match my needs.

So here's a question:

1. Is there anything that I don't understand and that might become a problem here?
2. I'll have 3-5 full time days to solve the issue. Is there a way I can solve the issue and contribute back some code?

Thank you!

In the current version, empty space fills 75% of the xmm register, during some operations. Unrolling 4x then packing ASAP, seems to get a ~9% improvement.

https://gist.github.com/aqrit/8fb615a05586d023e07cbd997cfcb6f9

food for thought.

The cmake build is not producing libstreamvbyte.so.0.0.1, which I see is built by the mnimal Makefile. Do you see the same on your end or is there maybe something amiss in my cmake configuration?

Currently, there is no option to install other than to install the library, headers in a global scope. This doesn't play nice with other build systems.

With this file a user can simply do:

mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release \
         -DCMAKE_INSTALL_PREFIX:PATH=/path/to/install
make -j8 install

In addition, I added tests/unit to the unit test framework of cmake so that you can do ctest -V and you would get:

Test project /home/agallego/workspace/streamvbyte/build
Constructing a list of tests
Done constructing a list of tests
Updating test list for fixtures
Added 0 tests to meet fixture requirements
Checking test dependency graph...
Checking test dependency graph end
test 1
    Start 1: unit

1: Test command: /home/agallego/workspace/streamvbyte/build/unit
1: Test timeout computed to be: 9.99988e+06
1: Code looks good.
1: And you have a little endian architecture.
1: Warning: you tested non-vectorized code.
1/1 Test #1: unit .............................   Passed    0.02 sec

100% tests passed, 0 tests failed out of 1

Total Test time (real) =   0.02 sec

This works on clang-4.0, but the pextrb intrinsic throws errors on gcc:

/usr/lib/gcc/x86_64-linux-gnu/6/include/smmintrin.h:443:27: error: selector must be an integer constant in the range 0..15 return (unsigned char) __builtin_ia32_vec_ext_v16qi ((__v16qi)__X, __N); ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I believe this is simply wrong, as the arg is a const int, but not a constant.

Performance on clang is exactly the same:

kendall@skylake:~/streamvbyte$ ./perf time = 0.036000 1388888960.000000 uints/sec compsize=1281422 compsize2 = 1281422 Compressed 500000 integers down to 1281422 bytes.

We decoding, our functions may read up to 16 extra bytes from the input (beyond the actual compressed data). Thus the users of this library, for safety, should ensure that there is allocated data 16 bytes beyond the compressed data.

For #32 - please read for context. Sometimes it's better to trade off encoding runtime for reduced peak memory allocation.

Fixes https://github.com/lemire/streamvbyte/issues/32

OS: Ubuntu 20.04.5 LTS CPU: Intel Xeon X5660

Step to reproduce:

git clone [email protected]:lemire/streamvbyte.git
mkdir build && cd build
cmake ..
cmake --build .

Output cmake ..

-- The C compiler identification is GNU 9.4.0
-- The CXX compiler identification is GNU 9.4.0
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- No build type selected
-- Default to Release
-- CMAKE_SYSTEM_PROCESSOR: x86_64
-- CMAKE_BUILD_TYPE: Release
-- CMAKE_C_COMPILER: /usr/bin/cc
-- CMAKE_C_FLAGS: 
-- CMAKE_C_FLAGS_DEBUG: -g
-- CMAKE_C_FLAGS_RELEASE: -O3 -DNDEBUG
-- Configuring done
-- Generating done
-- Build files have been written to: /home/kataev/development/streamvbyte/build

Output ctest -V

UpdateCTestConfiguration  from :/home/kataev/development/streamvbyte/build/DartConfiguration.tcl
UpdateCTestConfiguration  from :/home/kataev/development/streamvbyte/build/DartConfiguration.tcl
Test project /home/kataev/development/streamvbyte/build
Constructing a list of tests
Done constructing a list of tests
Updating test list for fixtures
Added 0 tests to meet fixture requirements
Checking test dependency graph...
Checking test dependency graph end
test 1
    Start 1: unit

1: Test command: /home/kataev/development/streamvbyte/build/unit
1: Test timeout computed to be: 10000000
1/1 Test #1: unit .............................***Exception: Illegal  0.28 sec

0% tests passed, 1 tests failed out of 1

Total Test time (real) =   0.29 sec

The following tests FAILED:
	  1 - unit (ILLEGAL)
Errors while running CTest

Output ./perf

Illegal instruction (core dumped)

While integrating into another cmake project via add_subdirectory() the target check might already be defined by a parent directory.

In addition, on a parent project when you run its unit tests you don't want child project unit tests to run

For example, this won't build the unit tests:

cmake -DSTREAMVBYTE_ENABLE_TESTS=OFF .. 

Hi lemire/streamvbyte!

This is a one-off automatically generated pull request from LGTM.com :robot:. You might have heard that we’ve integrated LGTM’s underlying CodeQL analysis engine natively into GitHub. The result is GitHub code scanning!

With LGTM fully integrated into code scanning, we are focused on improving CodeQL within the native GitHub code scanning experience. In order to take advantage of current and future improvements to our analysis capabilities, we suggest you enable code scanning on your repository. Please take a look at our blog post for more information.

This pull request enables code scanning by adding an auto-generated codeql.yml workflow file for GitHub Actions to your repository — take a look! We tested it before opening this pull request, so all should be working :heavy_check_mark:. In fact, you might already have seen some alerts appear on this pull request!

Where needed and if possible, we’ve adjusted the configuration to the needs of your particular repository. But of course, you should feel free to tweak it further! Check this page for detailed documentation.

Questions? Check out the FAQ below!

FAQ

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 https://github.com/iiSeymour/pystreamvbyte/issues/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?

Following this PR https://github.com/lemire/streamvbyte/pull/26 we now have code that can use a 0,1,2,4 byte encoding. However, it is basically achieved through pure code duplication. Worse: it does not benefit from @aqrit 's latest improvements.

Obviously, we could do better.

The generic codec supports both x64 and ARM NEON, however the differential-encoded version is x64 only.

It seems like it would be easy to port them over. The Delta function in ARM is almost identical:

uint32x4_t Delta(uint32x4_t curr, uint32x4_t prev) {
   return vsubq_u32(curr, vextq_u32 (prev,curr,3));
}

And so is the prefix sum which is currently mixed with the store in _write_avx_d1 (for historical reasons I suppose)...

uint32x4_t PrefixSum(uint32x4_t curr, uint32x4_t prev) {
   uint32x4_t zero = {0, 0, 0, 0};
   uint32x4_t add = vextq_u32 (zero, curr, 3);
   uint8x16_t BroadcastLast = {12,13,14,15,12,13,14,15,12,13,14,15,12,13,14,15};
   prev = vreinterpretq_u32_u8(vqtbl1q_u8(vreinterpretq_u8_u32(prev),BroadcastLast));
   curr = vaddq_u32(curr,add);
   add = vextq_u32 (zero, curr, 2);
   curr = vaddq_u32(curr,prev);
   curr = vaddq_u32(curr,add);
   return curr;
}

It could be that my implementations are suboptimal, but I think that they are correct and given these functions it should be easy to create a differentially coded codec.

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.

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.