Hacker News Reader

Comment by pillmillipedes | Hacker News Reader

[1] seems to have the actual details on compressed vectors. looks like for each page you're storing min&max, and the values come as offsets from the min (smaller->less bits per value), did I get that right?

  primitive speedup  
  sum price 7.7x  
  avg price 33x

how does this even happen though?

[1]https://lv1.sh/blog/compression-memory-wall/

View on HN

simple example at https://lv1.sh/blog/compute-on-compressed/ But in general compression is reducing the bit width of the input through an encoder (FOR or Frame of Reference is an old and good example). So we store the base in an offset location then the large payload is a much smaller size. E.g. i64 can goto i16. Then simd gets more #'s per cycle on the smaller, and the base is added to the scratch in stack (for sum). avg is similar (since it is just sum / count)

there's even a secret -17!`name that will show the details. e.g.

  //100k random 32b ints ... 
  l>v:100000?255
  l>v
  196 124 18 216 63 169 151 173 126 99 90 133 92 158 217 169 201 191 138 105 13..
  // but actually they are 1/4 the size e.g. int8
  l>-17!`v
  1b        // is compressed?
  100032j   // compressed bytes
  400000j   // original bytes

Reply on news.ycombinator.com