GGraziadei commented on PR #17774:
URL: https://github.com/apache/iceberg/pull/17774#issuecomment-5382755566
# Numerical example with 3 columns
A worked example of the table-based interleaving, with every intermediate
value.
## 1. Input data
Three 1-byte columns, one bit set each, so it is easy to follow where each
bit lands:
| Column | Name | Hex | Binary (MSB→LSB) |
|--------|------|-----|------------------|
| 0 | A | `0x80` | `1000 0000` |
| 1 | B | `0x40` | `0100 0000` |
| 2 | C | `0x20` | `0010 0000` |
`N = 3` columns, each contributes 1 byte → output = `N × 1 = 3 bytes` = 24
bits.
## 2. What Z-order must produce (conceptual definition)
Interleaving takes one bit at a time, rotating across the columns, from the
MSB down to the LSB:
```
A7 B7 C7 A6 B6 C6 A5 B5 C5 A4 B4 C4 ...
```
Substituting the values (A has only bit7, B only bit6, C only bit5):
```
A7 B7 C7 A6 B6 C6 A5 B5 C5 ... rest 0
1 0 0 0 1 0 0 0 1 0 0 0 ...
```
Grouping into 8-bit bytes:
```
bits 1..8 : 1000 1000 = 0x88
bits 9..16: 1000 0000 = 0x80
bits 17..24: 0000 0000 = 0x00
```
**Expected result: `[0x88, 0x80, 0x00]`.** This is what the old bit-by-bit
loop produced.
## 3. The SPREAD table
Every group of `N=3` output bits holds one bit from A, one from B, one from
C, so a bit sits `N` positions away from the next one. `SPREAD[N][b]` spreads
the 8 bits of byte `b` that far apart. From `buildSpreadTables`:
```
if bit 'bit' of b is set (bit=0 is the MSB):
spread |= 1 << (8*N - 1 - bit*N)
```
With `N=3` the target position is `24 - 1 - 3*bit = 23 - 3*bit`:
- **A = `0x80`** → only `bit=0`. Position `23` → `SPREAD[3][0x80] = 1 << 23
= 0x800000`
- **B = `0x40`** → only `bit=1`. Position `20` → `SPREAD[3][0x40] = 1 << 20
= 0x100000`
- **C = `0x20`** → only `bit=2`. Position `17` → `SPREAD[3][0x20] = 1 << 17
= 0x020000`
SPREAD positions the bits as if every column were column 0 (highest slot of
each triple).
## 4. Combining the columns: `interleaveGroup`
Each column is placed into its slot with a right shift equal to its index:
```
group |= SPREAD[column] >>> column_index
```
| Column | SPREAD | shift | Contribution |
|--------|--------|-------|--------------|
| 0 (A) | `0x800000` | `>>> 0` | `0x800000` |
| 1 (B) | `0x100000` | `>>> 1` | `0x080000` |
| 2 (C) | `0x020000` | `>>> 2` | `0x008000` |
```
0x800000 = 1000 0000 0000 0000 0000 0000
| 0x080000 = 0000 1000 0000 0000 0000 0000
| 0x008000 = 0000 0000 1000 0000 0000 0000
-----------------------------------------------
0x888000 = 1000 1000 1000 0000 0000 0000
```
`group = 0x888000`. A (col 0) stays at bit 23, B (col 1) drops to bit 19, C
(col 2) drops to bit 15 — exactly `A B C` within their triples, non-overlapping.
## 5. Extracting the output bytes
`group` sits in the low 3 bytes of a `long`. The loop writes MSB-byte first
(`groupByte` from `N-1=2` down to `0`):
| groupByte | `group >>> (8*groupByte)` | byte |
|-----------|---------------------------|------|
| 2 | `0x888000 >>> 16 = 0x88` | `0x88` |
| 1 | `0x888000 >>> 8 → (byte) 0x80` | `0x80` |
| 0 | `0x888000 >>> 0 → (byte) 0x00` | `0x00` |
**Output: `[0x88, 0x80, 0x00]`** ✓ — identical to the bit-by-bit result in
step 2.
## 6. Why it is faster
- The old method did `8 × interleavedSize` iterations (192 for 3 output
bytes), moving one bit at a time, with a next-column search at every step that
the CPU cannot pipeline.
- The table version processes one source byte at a time: `N` lookups + `N`
ORs per byte offset, then writes `N` bytes. No per-row allocation; only the
`SPREAD[N]` row in use (~2 KB) is touched.
--
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]
