4 ms·
This method of compressing integer arrays in differences and then reducing the number of bits for each difference, is very efficient for many applications. We u
by mrhill 9y ago
This method of compressing integer arrays in differences and then reducing the number of bits for each difference, is very efficient for many applications. We used it many years ago at a startup to compress and realtime render vector maps for mobile devices.
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...
- kwillets 9y agoOne of the problems with SIMD is that we can't do this kind of shuffle at bit granularity, at least not in one instruction.
- jeffffff 9y agoif you want bit level granularity you can use either SIMD-BP128 or SIMD-FastPFOR from https://arxiv.org/pdf/1209.2137.pdf https://arxiv.org/pdf/1209.2137.pdf