I re-run your benchmark, and calculated the time it takes to encode the input data. Also you should note that the whole page must be read and stored in memory to find the minimum, and while doing this, the ValuesWriter won't be able to correctly give the size of the currently encoded data. This might cause a problem.


➜  Documents  nano benchmark.cpp
➜  Documents  g++ benchmark.cpp -O3 -o a
➜  Documents  time ./a
Done 817249033.
./a  7.82s user 0.00s system 99% cpu 7.827 total <-- min encoding
➜  Documents  nano benchmark.cpp
➜  Documents  g++ benchmark.cpp -O3 -o a
➜  Documents  time ./a
Done 817249033.
./a  4.70s user 0.00s system 99% cpu 4.707 total <-- zigzag encoding
➜  Documents  cat benchmark.cpp
#include <stdio.h>
#include <algorithm>
#define ZZ
int main(int argc, char** argv) {
	const int ITERS = 50000;
	const int N = 100000;
	int values[N];
	unsigned int zigzag[N];
	int offset[N];
	int min = 1000000;
	int max_val = 100;

	for (int i = 0; i < N; ++i) {
		int r = rand();
		if (r % 2 == 0) {
			values[i] = -r;
		} else {
			values[i] = r;
		}
	}

	for (int iter = 0; iter<ITERS; iter++)
	{
		#ifndef ZZ
			for (int i = 0; i < N; i++)
				min = std::min(min,values[i]);
		#endif
		for (int i = 0; i < N; ++i) {
			#ifndef ZZ
				offset[i] = values[i] - min;
			#else
				zigzag[i] = (values[i] << 1) ^ (values[i] >> 31);
			#endif
		}
	}

	int dummy = 0;
	for (int iters = 0; iters < 1; ++iters) {
		for (int i = 0; i < N; ++i) {
			#ifndef ZZ
				dummy += (offset[i] + min);
			#else
				dummy += (zigzag[i] >> 1) ^ -(zigzag[i] & 1);
			#endif
		}
	}

	printf("Done %d.\n", dummy);
}
➜  Documents