collab/1brc

the one billion row challenge

git clone https://git.julia.blue/collab/1brc

Rahul Butaniexp/hash: rework search, notesdddb811

main
2.3 KiB64 linesraw
1#!/usr/bin/env python
2
3from collections import Counter, defaultdict
4import sys
5
6inp = (sys.argv[1:] or ["/tmp/_1br/1br/measurements.txt"])[0]
7
8def entry_len_dist(path: str) -> Counter[int]:
9    with open(path, 'rb') as f:
10        out = Counter(len(line) for line in f)
11    return out
12
13# num entries in window => (num times seen, Counter of byte len of window)
14type EntryWindowInfo = dict[int, tuple[int, Counter[int]]]
15def num_entries_in_window(path: str, window_byte_len: int) -> EntryWindowInfo:
16    # naive; doesn't consider chunking...
17    out: EntryWindowInfo = defaultdict(lambda: (0, Counter()))
18    with open(path, 'rb') as f:
19        curr_len, count = 0, 0
20        for line in f:
21            # add to current window, if fits
22            if curr_len + len(line) <= window_byte_len:
23                curr_len += len(line)
24                count += 1
25                continue
26            # otherwise, flush current window and start a new window:
27            count_for_window, byte_counter = out[count]
28            byte_counter.update([curr_len])
29            out[count] = (count_for_window + 1, byte_counter)
30
31            curr_len, count = len(line), 1
32            # NOTE: if `len(line)` exceeds `window_byte_len` it'll be flushed
33            # individually on the next iteration... but we want to record this
34            # separately so denote as zero?
35            if curr_len > window_byte_len:
36                count = 0
37                count_for_window, byte_counter = out[count]
38                byte_counter.update([curr_len])
39                out[count] = (count_for_window + 1, byte_counter)
40
41                curr_len = 0
42
43        count_for_window, byte_counter = out[count]
44        byte_counter.update([curr_len])
45        out[count] = (count_for_window + 1, byte_counter)
46    return out
47
48def print_entry_window_info(info: EntryWindowInfo):
49    for num_ents, (seen, counts) in sorted(info.items()):
50        print(f"  {num_ents:2}: {seen}")
51        # print(f"    - {counts}")
52        avg_byte_len = sum(v * c for v, c in counts.items()) / sum(c for _, c in counts.items())
53        print(f"    - {avg_byte_len}")
54
55print(sorted(entry_len_dist(inp).items()))
56print()
57print(16)
58print_entry_window_info(num_entries_in_window(inp, 16))
59print()
60print(32)
61print_entry_window_info(num_entries_in_window(inp, 32))
62print()
63print(64)
64print_entry_window_info(num_entries_in_window(inp, 64))