GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5361125612
## JMH: Hilbert curve math vs Z-order interleaving
Answering the question about whether the JMH run compares against Z-order
interleaving on the same inputs, and the request for a relative number. It
does, and the figures are below.
> **Scope note.** Sections 1, 2 and 4 describe the branch as pushed. Section
3 measures an allocation fix that is **not yet pushed**; it is reported here
because the benchmark is what surfaced the defect, but the current diff does
not yet contain it.
### Method
`HilbertByteUtilsBenchmark` and `ZOrderByteUtilsBenchmark` are structurally
matched: identical `NUM_ENTRIES = 10_000_000`, identical `new Random(42)` seed,
identical setup loop. Both arms therefore see byte-for-byte identical input,
and both were executed in a single JMH invocation so they share one JIT and GC
context.
```
JMH 1.37 · JDK 17.0.19 · 1 fork · 1 thread · SingleShotTime
5 warmup + 15 measurement iterations · -Xmx8g · gc profiler
1 op = one pass over 10M rows, 64 bits per column
```
One methodological caveat worth stating up front: the committed benchmark
classes declare no `@Warmup` and only 5 iterations. Measured that way,
confidence intervals reach ±43% and — more seriously — the reported allocation
rates are dominated by JIT compilation artifacts rather than by the code under
test. Running the unmodified Z-order benchmark under the two configurations
yields 396 MB/op without warmup versus 3.71 MB/op with it, a
two-order-of-magnitude discrepancy attributable entirely to measurement rather
than to any code change. All figures below use warmup and 15 iterations and are
consequently **not** comparable to a default run of the committed classes.
### 1. Time
```
s/op, lower is better
2 cols Hilbert ████████████████████████▏ 14.64
Z-order ██████▏ 3.71
3 cols Hilbert ███████████████████████████████▌ 19.09
Z-order █████████ 5.43
4 cols Hilbert ██████████████████████████████████████ 22.88
Z-order ████████████▏ 7.45
```
| Columns | Hilbert (s/op) | Z-order (s/op) | Ratio | Added cost |
|--------:|---------------:|---------------:|------:|-----------:|
| 2 | 14.644 ± 0.447 | 3.707 ± 0.119 | 3.95x | +1.09 µs/row |
| 3 | 19.094 ± 0.512 | 5.433 ± 0.100 | 3.51x | +1.37 µs/row |
| 4 | 22.881 ± 0.537 | 7.452 ± 0.278 | 3.07x | +1.54 µs/row |
**`hilbertIndex` costs 3.1–4.0x a pure Z-order interleave on identical
inputs.** This is a structural rather than incidental result: `hilbertIndex`
issues the same `ZOrderByteUtils.interleaveBits` call and adds
`axesToTranspose` on top, so the ratio is precisely the price of the curve
transform. The ratio decreases with dimensionality because the interleave grows
linearly in the number of columns while the transpose does not.
### 2. Attribution
Stack profiler, 4 columns, percentages of RUNNABLE thread state.
```
Hilbert Z-order
axesToTranspose ██████ 30.8% interleaveBits ██████████ 49.8%
interleaveBits ███ 15.1% unattributed ██████████ 50.0%
hilbertIndex ▌ 3.1%
read/writeBigEndian ▏ 0.8%
unattributed ██████████ 50.0%
```
Within Hilbert the curve transform costs approximately twice the interleave
it wraps (30.8% versus 15.1%), which corroborates the ~3x aggregate through an
independent measurement path. Half the samples are unattributed, which is
expected for a sampling profiler against inlined frames; these proportions
should be read as indicative rather than exact.
### 3. Allocation
The benchmark surfaced a defect worth fixing independently of the timing
question. `hilbertIndex` allocated a `long[numColumns]` and a `new
byte[numColumns][bytesPerColumn]` **per invocation**, i.e. per row, while the
output `ByteBuffer` was already correctly reused. At four columns that is six
objects per row and 60M objects per pass.
```
bytes per op, log10 scale
before Hilbert ███████████████████████████████████ 1.77 GB
Z-order ████████████████████████▌ 3.71 MB
after Hilbert ██████████████▌ 6.7 KB
Z-order ██████████████▌ 6.6 KB
```
| | Hilbert | Z-order |
|---|---:|---:|
| before | 1.774 GB/op, 8 GC pauses | 3.711 MB/op, 0 GC pauses |
| after | 6 743 B/op, 0 GC pauses | 6 570 B/op, 0 GC pauses |
The remedy is an overload accepting caller-owned scratch — the same `reuse`
convention `ZOrderByteUtils` applies throughout — with `SparkHilbertUDF`
holding it in the `ThreadLocal`s it already maintains. The three-argument
overload is unchanged and still allocates, so no existing caller is affected.
The residual ~6.6 KB/op is JMH's own per-op baseline and is identical across
both arms.
**Hilbert now allocates no more than Z-order, and neither triggers a single
garbage collection across 10M rows.**
### 4. Interpretation and limits
- **The allocation fix produced no measurable time improvement** (−0.2%,
+2.6%, −9.5% across the three widths). The inconsistent signs identify this as
noise. The −9.5% at four columns is regression to the mean of a prior outlier,
whose interval was ±2.463 before and ±0.537 after. This is the expected
outcome: the objects were short-lived and young-generation-cheap, and GC
accounted for 0.5% of wall time even before the fix. The benefit is reduced
allocator pressure across concurrent Spark tasks, which a single-threaded
micro-benchmark cannot exhibit.
- **The 3x applies to the combine step in isolation.** In an end-to-end
rewrite that step is a minor term next to I/O, shuffle, and the per-column
ordered-byte conversion. The measured end-to-end penalty is **+15.4%** (169.8s
→ 196.0s), and the gap between 3x and 15.4% is itself evidence that the combine
does not dominate.
- **Absolute values are machine-specific.** These were collected on a
developer workstation with other applications resident. Since both arms
executed in the same fork against the same inputs, the Hilbert-to-Z-order ratio
is the robust quantity; the absolute s/op figures are not.
--
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]
