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]