ArslanAnjum opened a new pull request, #4181:
URL: https://github.com/apache/iceberg-python/pull/4181
# perf: optimize deletion vector deserialization using zero-copy memoryview
## Summary
Optimizes deletion vector parsing by replacing repeated byte string slicing
(`pl = pl[4:]`) with zero-copy pointer tracking via Python's built-in
`memoryview`.
Repeatedly slicing `bytes` objects creates new allocations and copies
remaining payload data into memory on every iteration, leading to $O(N^2)$
memory copying behavior as payload sizes grow. Utilizing `memoryview` keeps
memory allocations at $O(1)$ during parsing, improving execution times by up to
**~39x** on large dense payloads.
---
## Benchmark Results
Benchmarks were executed across four real-world Iceberg deletion vector
scenarios using `pytest-benchmark` (`min_rounds=1000`, `warmup=True`,
`disable_gc=True`):
| Scenario | Payload Description | Original Mean | PR Mean | Speedup |
| :--- | :--- | :--- | :--- | :--- |
| `small_sparse` | 5 bitmaps (~1.5 KB) | **7.07 µs** | **7.49 µs** |
**0.94x** *(~5% overhead on tiny buffers)* |
| `gaps_sparse_keys` | 100 non-contiguous keys (~130 KB) | **429.36 µs** |
**238.16 µs** | **1.80x faster** |
| `medium_typical` | 50 bitmaps (~2.1 MB) | **488.03 µs** | **109.09 µs** |
**4.47x faster** |
| `large_dense` | 200 bitmaps (~21 MB) | **25,342.14 µs** | **645.55 µs** |
**39.26x faster** |
### Detailed Terminal Benchmark Output
```text
-----------------------------------------------------------------------
benchmark 'scenario_name=gaps_sparse_keys': 2 tests
------------------------------------------------------------------------
Name (time in us) Mean StdDev
Median OPS (Kops/s) Rounds Min
Max IQR
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_benchmark_pr[gaps_sparse_keys] 238.1630 (1.0) 44.6340
(1.0) 230.0540 (1.0) 4.1988 (1.0) 10869 180.6580 (1.0)
1,048.9360 (1.0) 20.9197 (1.0)
test_benchmark_original[gaps_sparse_keys] 429.3581 (1.80) 68.4834
(1.53) 426.8960 (1.86) 2.3291 (0.55) 5777 342.4320 (1.90)
1,397.9330 (1.33) 32.2145 (1.54)
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------
benchmark 'scenario_name=large_dense': 2 tests
------------------------------------------------------------------------------
Name (time in us) Mean StdDev
Median OPS Rounds Min
Max IQR
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_benchmark_pr[large_dense] 645.5468 (1.0) 114.8522
(1.0) 633.8070 (1.0) 1,549.0743 (1.0) 3769 521.7980
(1.0) 2,065.5120 (1.0) 39.9387 (1.0)
test_benchmark_original[large_dense] 25,342.1420 (39.26) 1,427.5573
(12.43) 25,053.5565 (39.53) 39.4600 (0.03) 1000 23,261.5680
(44.58) 34,868.0240 (16.88) 1,048.5725 (26.25)
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------
benchmark 'scenario_name=medium_typical': 2 tests
------------------------------------------------------------------------
Name (time in us) Mean StdDev
Median OPS (Kops/s) Rounds Min
Max IQR
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_benchmark_pr[medium_typical] 109.0941 (1.0) 21.4579
(1.0) 107.1850 (1.0) 9.1664 (1.0) 23456 86.7770 (1.0)
833.7140 (1.0) 5.3600 (1.0)
test_benchmark_original[medium_typical] 488.0276 (4.47) 62.2185
(2.90) 481.1955 (4.49) 2.0491 (0.22) 4674 437.6670 (5.04)
1,633.0450 (1.96) 20.8380 (3.89)
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------ benchmark
'scenario_name=small_sparse': 2 tests
-------------------------------------------------------------------
Name (time in us) Mean StdDev
Median OPS (Kops/s) Rounds Min
Max IQR
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_benchmark_original[small_sparse] 7.0736 (1.0) 2.7843 (1.16)
6.9530 (1.0) 141.3713 (1.0) 348432 5.7280 (1.0)
680.0050 (1.01) 0.4060 (1.0)
test_benchmark_pr[small_sparse] 7.4874 (1.06) 2.4043 (1.0)
7.4810 (1.08) 133.5569 (0.94) 324571 5.8790 (1.03)
672.9530 (1.0) 0.5870 (1.45)
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
```
## Reproducing Benchmarks
Run the benchmark script below using `pytest-benchmark`:
```bash
uv run --with pytest-benchmark pytest test_deletion_vector_benchmark.py \
--benchmark-columns=mean,stddev,median,ops,rounds,min,max,iqr \
--benchmark-sort=mean \
--benchmark-group-by=param:scenario_name \
-q
```
```code
import io
import pytest
from pyroaring import BitMap, FrozenBitMap
EMPTY_BITMAP = FrozenBitMap()
MAX_JAVA_SIGNED = 2147483647
def deserialize_original(pl: bytes) -> list[BitMap]:
number_of_bitmaps = int.from_bytes(pl[0:8], byteorder="little")
pl = pl[8:]
bitmaps = []
last_key = -1
for _ in range(number_of_bitmaps):
key = int.from_bytes(pl[0:4], byteorder="little")
if key < 0:
raise ValueError(f"Invalid unsigned key: {key}")
if key <= last_key:
raise ValueError("Keys must be sorted in ascending order")
if key > MAX_JAVA_SIGNED:
raise ValueError(
f"Key {key} is too large, max {MAX_JAVA_SIGNED} to maintain
compatibility with Java impl"
)
pl = pl[4:]
while last_key < key - 1:
bitmaps.append(EMPTY_BITMAP)
last_key += 1
bm = BitMap.deserialize(pl)
pl = pl[len(bm.serialize()) :]
bitmaps.append(bm)
last_key = key
return bitmaps
def deserialize_pr(pl: bytes) -> list[BitMap]:
number_of_bitmaps = int.from_bytes(pl[0:8], byteorder="little")
offset = 8
bitmaps = []
last_key = -1
buffer = memoryview(pl)
for _ in range(number_of_bitmaps):
key = int.from_bytes(buffer[offset : offset + 4], byteorder="little")
if key < 0:
raise ValueError(f"Invalid unsigned key: {key}")
if key <= last_key:
raise ValueError("Keys must be sorted in ascending order")
if key > MAX_JAVA_SIGNED:
raise ValueError(
f"Key {key} is too large, max {MAX_JAVA_SIGNED} to maintain
compatibility with Java impl"
)
offset += 4
while last_key < key - 1:
bitmaps.append(EMPTY_BITMAP)
last_key += 1
bm = BitMap.deserialize(buffer[offset:])
offset += len(bm.serialize())
bitmaps.append(bm)
last_key = key
return bitmaps
def create_sample_payload(num_bitmaps=50, values_per_bitmap=20_000) -> bytes:
buf = io.BytesIO()
buf.write(num_bitmaps.to_bytes(8, byteorder="little"))
for key in range(num_bitmaps):
buf.write(key.to_bytes(4, byteorder="little"))
bm = BitMap(range(0, values_per_bitmap * 2, 2))
buf.write(bm.serialize())
return buf.getvalue()
def create_sample_payload_with_gaps(num_bitmaps=50, step=5,
values_per_bitmap=1_000) -> bytes:
buf = io.BytesIO()
buf.write(num_bitmaps.to_bytes(8, byteorder="little"))
current_key = 0
for _ in range(num_bitmaps):
buf.write(current_key.to_bytes(4, byteorder="little"))
bm = BitMap(range(0, values_per_bitmap * 2, 2))
buf.write(bm.serialize())
current_key += step
return buf.getvalue()
BENCHMARK_SCENARIOS = {
"small_sparse": create_sample_payload(num_bitmaps=5,
values_per_bitmap=100),
"medium_typical": create_sample_payload(num_bitmaps=50,
values_per_bitmap=20_000),
"large_dense": create_sample_payload(num_bitmaps=200,
values_per_bitmap=50_000),
"gaps_sparse_keys": create_sample_payload_with_gaps(num_bitmaps=100,
step=10, values_per_bitmap=500),
}
@pytest.mark.benchmark(
min_rounds=1000,
max_time=2.0,
warmup=True,
disable_gc=True
)
@pytest.mark.parametrize(
"scenario_name, payload_bytes",
BENCHMARK_SCENARIOS.items(),
ids=BENCHMARK_SCENARIOS.keys()
)
def test_benchmark_original(benchmark, scenario_name, payload_bytes):
benchmark(deserialize_original, payload_bytes)
@pytest.mark.benchmark(
min_rounds=1000,
max_time=2.0,
warmup=True,
disable_gc=True
)
@pytest.mark.parametrize(
"scenario_name, payload_bytes",
BENCHMARK_SCENARIOS.items(),
ids=BENCHMARK_SCENARIOS.keys()
)
def test_benchmark_pr(benchmark, scenario_name, payload_bytes):
benchmark(deserialize_pr, payload_bytes)
```
--
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]
