nssalian opened a new pull request, #1750:
URL: https://github.com/apache/iceberg-go/pull/1750
## What this does
Adds a Go implementation of the Mumbling compressed bitmap (the V4 manifest
deletion-vector format,
apache/iceberg#16747) to iceberg-go.
- `mumbling.Bitmap` - `New`, `IsSet`, `Cardinality`. Lazy decode, sparse and
dense containers, spec caps enforced
(<= 8,192 containers, <= 2,097,152 set bits).
- The PFOR codec for the descriptor array (unexported).
- Standard library only.
## Checked against
- The worked examples in format/mumbling-spec.md, including the size-tie
encoding case.
- Fixtures from the Java implementation (apache/iceberg#16747): 130 PFOR
vectors and 6 full bitmaps. The Go
decoder reads them and the Go encoder reproduces the same bytes. (Stored
as TSV, one line per case.)
- 450 randomized encode/decode round-trips across the 256-value chunk
boundary.
- Malformed and truncated input: `New`/`IsSet` return a typed error, never
panic.
## PFOR on vs off - descriptor-array size
Descriptor-array size with PFOR on vs off across container-distribution
shapes, for the open question of whether
PFOR earns its complexity. The sizes match the Java encoder's; only the
input distributions are synthetic.
```
distribution nCont rawDesc pforDesc descCmp container
descFracTotal wholeSaved
all-dense 8 8 3 37.5% 256 3.0%
1.85%
all-dense 64 64 3 4.7% 2048 3.0%
2.88%
all-dense 256 256 3 1.2% 8192 3.0%
2.99%
all-dense 1024 1024 12 1.2% 32768 3.0%
2.99%
all-dense 8192 8192 96 1.2% 262144 3.0%
2.99%
uniform-sparse 8 8 3 37.5% 40 14.8%
9.26%
uniform-sparse 64 64 3 4.7% 320 16.4%
15.64%
uniform-sparse 256 256 3 1.2% 1280 16.6%
16.41%
uniform-sparse 1024 1024 12 1.2% 5120 16.7%
16.46%
uniform-sparse 8192 8192 96 1.2% 40960 16.7%
16.47%
random-sparse 8 8 8 100.0% 143 5.1%
0.00%
random-sparse 64 64 43 67.2% 893 6.6%
2.18%
random-sparse 256 256 163 63.7% 3863 6.2%
2.25%
random-sparse 1024 1024 652 63.7% 15233 6.3%
2.29%
random-sparse 8192 8192 5216 63.7% 129232 6.0%
2.17%
mixed 8 8 8 100.0% 223 3.4%
0.00%
mixed 64 64 51 79.7% 1549 4.0%
0.80%
mixed 256 256 195 76.2% 6106 4.0%
0.96%
mixed 1024 1024 780 76.2% 24203 4.1%
0.97%
mixed 8192 8192 6240 76.2% 193160 4.1%
0.97%
```
`wholeSaved` is the fraction of the whole bitmap PFOR removes: ~16% for
uniform-sparse (many containers, same
small delete count), ~1-3% for dense/random-sparse/mixed, ~0% for tiny
bitmaps where the 3-byte chunk header
dominates. Which regime real manifest DVs fall into is for the write path to
settle.
Reproduce: `go test ./mumbling/ -run TestPFORSizeAnalysis -v`.
## Benchmarks
PFOR vs raw copy for a 1,024-value descriptor array (Apple M4 Max,
`-benchtime=2s -count=5`):
```
BenchmarkPForEncode1024 13042 ns/op 9344 B/op 5 allocs/op
BenchmarkPForDecode1024 3465 ns/op 8192 B/op 1 allocs/op
BenchmarkRawEncode1024 320 ns/op 1024 B/op 1 allocs/op
BenchmarkRawDecode1024 823 ns/op 8192 B/op 1 allocs/op
```
PFOR encode is ~40x a raw byte copy and decode ~4x, but both are
microseconds for 1,024 descriptors, so codec
speed is not the deciding factor - size is.
Reproduce: `go test ./mumbling/ -run '^$' -bench . -benchmem -benchtime=2s
-count=5`.
## Scope
Read path plus the PFOR codec. No V4 manifest-DV consumer exists in
iceberg-go yet, so this is format validation
in a second language, not a wired feature.
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
