zeroshade opened a new pull request, #1553:
URL: https://github.com/apache/arrow-go/pull/1553

   ### Rationale for this change
   
   Most of the time ALP encoding takes goes to four things:
   
   - Every value is scaled by `alpScaling.tryEncode`, a method generic over the 
float type that is not inlined into the loop and that branches on whether the 
value is an exception. Where exceptions and encodable values mix, that branch 
is mispredicted.
   - The integers are packed through `BitWriter.WriteValue`, one call per 
value, with a `BitWriter` and its buffer wrapper allocated for every vector.
   - The search over every exponent and factor scales the whole sample for each 
of the 190 pairs (66 for `FLOAT`), although nearly all of them are out of the 
running after a few values. A column chunk pays for that search on its first 
eight vectors, and again whenever the data changes scale.
   - Once the shortlist is built, each vector's sample is scaled to choose 
among the shortlisted scalings, even when there is only one to choose from.
   
   ### What changes are included in this PR?
   
   - `alpScale64` and `alpScale32` scale a vector in a loop written for one 
type that does not branch on the data. They give the integers and exceptions 
`tryEncode` gives. The range of the integers is found in a separate integer 
pass.
   - `alpPack` packs the integers' distances from the frame of reference a word 
at a time, in four runs side by side, with no allocation.
   - A size estimate stops as soon as its scaling can no longer beat the best 
one. Neither the exceptions nor the packing width can shrink as more values are 
scaled, so the size so far is a lower bound.
   - With one scaling on the shortlist, the vector is scaled straight away, and 
what the sample would have estimated is read off the result.
   - `Put` encodes a whole vector from the caller's slice instead of copying it 
into the encoder's buffer first.
   
   The pages are byte for byte what `main` writes. I compared the two encoders 
on decimals, whole numbers, incompressible values, data that changes scale 
partway, and values at the edges of the integer range, mixed with NaN, 
infinities and -0.0, for both types, at vector sizes from 8 to 32768.
   
   Timings on an Apple M4 (darwin/arm64). The machine was busy with other work, 
so `main` and this branch were run in alternating short turns, 50 samples each. 
The spread is wide, and the absolute times are slower than on an idle machine, 
but both sides ran under the same conditions:
   
   ```
                                                  │     main      │             
     PR                  │
                                                  │    sec/op     │    sec/op   
  vs base                │
   ALPEncodingFloat32/no_exceptions/len_1024-10      7.084µ ± 19%   2.964µ ± 
20%  -58.16% (n=50)
   ALPEncodingFloat32/no_exceptions/len_65536-10     471.0µ ± 11%   200.5µ ± 
13%  -57.43% (p=0.000 n=50)
   ALPEncodingFloat32/10%_exceptions/len_1024-10     8.116µ ± 13%   3.720µ ± 
13%  -54.17% (p=0.000 n=50)
   ALPEncodingFloat32/10%_exceptions/len_65536-10    525.7µ ± 22%   240.9µ ± 
15%  -54.19% (p=0.000 n=50)
   ALPEncodingFloat32/all_exceptions/len_1024-10    13.150µ ±  4%   4.557µ ± 
27%  -65.34% (p=0.000 n=50)
   ALPEncodingFloat32/all_exceptions/len_65536-10    863.4µ ±  4%   324.4µ ± 
21%  -62.42% (p=0.000 n=50)
   ALPEncodingFloat64/no_exceptions/len_1024-10      6.906µ ± 23%   2.765µ ± 
15%  -59.96% (n=50)
   ALPEncodingFloat64/no_exceptions/len_65536-10     515.9µ ± 17%   206.9µ ± 
13%  -59.90% (p=0.000 n=50)
   ALPEncodingFloat64/10%_exceptions/len_1024-10     7.670µ ± 18%   2.993µ ±  
9%  -60.98% (n=50)
   ALPEncodingFloat64/10%_exceptions/len_65536-10    562.4µ ±  9%   252.2µ ± 
17%  -55.16% (p=0.000 n=50)
   ALPEncodingFloat64/all_exceptions/len_1024-10    13.631µ ±  9%   4.467µ ± 
18%  -67.23% (n=50)
   ALPEncodingFloat64/all_exceptions/len_65536-10    921.9µ ± 10%   328.1µ ± 
18%  -64.41% (p=0.000 n=50)
   geomean                                           74.91µ         29.84µ      
  -60.17%
   
                                                  │     main     │              
     PR                    │
                                                  │  allocs/op   │ allocs/op   
vs base                     │
   ALPEncodingFloat32/no_exceptions/len_1024-10     2.000 ± 0%     0.000 ± 0%  
-100.00% (n=50)
   ALPEncodingFloat32/no_exceptions/len_65536-10    128.0 ± 0%       0.0 ± 0%  
-100.00% (n=50)
   ALPEncodingFloat32/10%_exceptions/len_1024-10    2.000 ± 0%     0.000 ± 0%  
-100.00% (n=50)
   ALPEncodingFloat32/10%_exceptions/len_65536-10   128.0 ± 0%       0.0 ± 0%  
-100.00% (n=50)
   ALPEncodingFloat32/all_exceptions/len_1024-10    0.000 ± 0%     0.000 ± 0%   
      ~ (p=1.000 n=50) ¹
   ALPEncodingFloat32/all_exceptions/len_65536-10   0.000 ± 0%     0.000 ± 0%   
  0.00% (p=0.000 n=50)
   ALPEncodingFloat64/no_exceptions/len_1024-10     2.000 ± 0%     0.000 ± 0%  
-100.00% (n=50)
   ALPEncodingFloat64/no_exceptions/len_65536-10    128.0 ± 0%       0.0 ± 0%  
-100.00% (n=50)
   ALPEncodingFloat64/10%_exceptions/len_1024-10    2.000 ± 0%     0.000 ± 0%  
-100.00% (n=50)
   ALPEncodingFloat64/10%_exceptions/len_65536-10   128.0 ± 0%       0.0 ± 0%  
-100.00% (n=50)
   ALPEncodingFloat64/all_exceptions/len_1024-10    0.000 ± 0%     0.000 ± 0%   
      ~ (p=1.000 n=50) ¹
   ALPEncodingFloat64/all_exceptions/len_65536-10   1.000 ± 0%     0.000 ± 0%  
-100.00% (p=0.000 n=50)
   geomean                                                     ²               
?                       ² ³
   ² summaries must be >0 to compute geomean
   ³ ratios must be >0 to compute geomean
   ```
   
   I have no amd64 timings.
   
   ### Are these changes tested?
   
   Yes, by new tests that hold the new loops to `alpScaling.tryEncode` and to a 
bit-at-a-time packer, and by the existing ALP tests.
   
   ### Are there any user-facing changes?
   
   No.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to