jonasdedden commented on PR #51611:
URL: https://github.com/apache/arrow/pull/51611#issuecomment-5906505525
972bc4c speeds up the per-list scan: short lists are now 2.4–4.1× faster,
long lists are unchanged. The scan used to build an
`OptionalBinaryBitBlockCounter` per list. Now it folds validity into the match
bitmap once, reads a single unaligned word for lists spanning ≤ 64 bits, and
looks up the offsets/sizes/width once per batch.
| List length | Match rate | `equal` alone | `list_contains` before
(95d6b87) | `list_contains` after (972bc4c) | Speedup |
|---:|---:|---:|---:|---:|---:|
| 1 | 1e-5 | 18 ms | 346 ms | 108 ms | 3.2× |
| 3 | 1e-5 | 19 ms | 140 ms | 48 ms | 2.9× |
| 3 | 30% | 19 ms | 196 ms | 48 ms | 4.1× |
| 10 | 30% | 19 ms | 68 ms | 28 ms | 2.4× |
| 100 | 30% | 18 ms | 26 ms | 26 ms | 1.0× |
| 1,000 | 1e-5 | 19 ms | 21 ms | 20 ms | 1.0× |
| 1,000 | 30% | 18 ms | 19 ms | 19 ms | 1.0× |
<details>
<summary>Setup and script</summary>
50M `int64` values in one `list<int64>` array, `int64` item, best of 7, best
of two runs per build (runs differed by ≤ 6 ms). Release build, 8 cores, system
allocator; same PyArrow, only `libarrow_compute` swapped between the two
commits. `equal alone` is the comparison over the same values, a lower bound
for the kernel.
```python
"""Time pc.list_contains against the `equal` pass it is built on. Run once
per build."""
import json
import sys
import time
import numpy as np
import pyarrow as pa
import pyarrow.compute as pc
N_VALUES = 50_000_000
CASES = [(1, 1e-5), (3, 1e-5), (3, 0.3), (10, 0.3), (100, 0.3), (1000,
1e-5), (1000, 0.3)]
def best_ms(func, repeats=7):
times = []
for _ in range(repeats):
start = time.perf_counter()
func()
times.append(time.perf_counter() - start)
return min(times) * 1e3
results = {}
for list_length, match_rate in CASES:
rng = np.random.default_rng(42)
values = rng.integers(2, 1 << 40, N_VALUES)
values[rng.random(N_VALUES) < match_rate] = 1
offsets = np.arange(0, N_VALUES + 1, list_length, dtype=np.int32)
lists = pa.ListArray.from_arrays(offsets, pa.array(values))
flat = lists.values
item = pa.scalar(1, pa.int64())
results[f"{list_length},{match_rate}"] = {
"list_contains": best_ms(lambda: pc.list_contains(lists, item)),
"equal": best_ms(lambda: pc.equal(flat, item)),
}
json.dump(results, sys.stdout)
```
</details>
--
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]
