Re:The Simple Beauty of XOR Floating Point Compression
by hugh-avherald on Friday April 12, 2024 @07:34AM
(#40011385)
What is stride order?
Re:The Simple Beauty of XOR Floating Point Compression
by pxeger1 on Friday April 12, 2024 @10:23AM
(#40013255)
It means the order in which you serialise a multi-dimensional array. So for this 2D table:
1262
3418
9076
Because it’s 2D it has two stride orders, xy and yx, i.e. row-major and column-major, which would be 126234189076 and 139240617286 respectively.
Re:The Simple Beauty of XOR Floating Point Compression
by enizor2 on Friday April 12, 2024 @12:23PM
(#40014665)
The BYTE_STREAM_SPLIT is a Z-order (also known as Morton encoding).
As it is better a preserving locality, it usually performs really well compared to classical "orthogonal" orders.
It also is really simple to implement as it boils down to interleaving bits or bytes.
I noticed this a decade ago when I stumbled on a voxel engine that used some complex height map compression scheme for game map data. It seemed gratuitous to me, so I tried the simplest thing I could come up with: gzipping a 3D array of voxel colors. It didn't really work until I chose the right stride order (xyz, zyx, yzx, etc) and then suddenly it was 5x better.
The parquet format has the BYTE_STREAM_SPLIT encoding strategy which basically splits an array of floats/doubles into 4/8 arrays of bytes so they can be compressed independently. https://parquet.apache.org/docs/file-format/data-pages/encod...
Just choosing the correct stride order before compression is still underutilized. It's also undersupported in our tools too; e.g. that voxel engine used numpy, but it was a pita to get numpy to transparently change the stride order in the memory representation without also affecting the indexing order.