Re:Stream VByte: breaking new speed records for integer comp...
by kwillets on Wednesday September 27, 2017 @05:03PM
(#15352332)
One of the problems with SIMD is that we can't do this kind of shuffle at bit granularity, at least not in one instruction.
Re:Stream VByte: breaking new speed records for integer comp...
by jeffffff on Thursday September 28, 2017 @05:05PM
(#15360695)
if you want bit level granularity you can use either SIMD-BP128 or SIMD-FastPFOR from https://arxiv.org/pdf/1209.2137.pdf
Not only made it the data really small (we could fit all the roads of a country like Germany in 5 MB), it was also blazing fast to decode. Our vector map renderer used to do the vector map decompression on the fly, while doing coordinate transformation, and rendering to the screen. That was really the trick to get realtime zooming and panning vector maps on ~100 MHz ARM CPUs with tiny data caches of the time.
We even took that compression scheme a step further from byte-bound to bit-granularity. Above article made me wonder, how our old scheme performs on today's CPU...