Vertical Bit-Packing: Optimizing Operations on Bit-Packed Vectors Leveraging SIMD Instructions

摘要

Today's in-memory column stores make heavy use of bit-packed data structures in order to reduce the required amount of main-memory and to improve the performance of memory-bound algorithms by trading more CPU cycles for less data that needs to be transferred over the memory-bus. In this paper, we propose vertical bit-packing as a slightly modified alternative compared to classic bit-packing approaches, compressing an array of integer values with a known and finite value set so that each value is stored using the minimal required amount of bits. Vertical bit-packing aims to fully exploit the data parallelism provided by the existing on-chip vector processing units of modern x86-64 CPUs as they provide speedup potentials at no additional hardware cost. In particular, we propose Vertical Bit-Packing and Aligned Vertical Bit-Packing as an alternative to the classic approach called Horizontal Bit-Packing. We show that the proposed techniques can save between one and two instructions per decompressed value block, outperforming the classic approach in some bit-cases with up to 12%.