collab/1brc

the one billion row challenge

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

Rahul Butaniexp/hash: add heatmap output, notes926868e

back-to-mmap
11.2 KiB341 linesraw
1
2from collections import Counter
3import os
4import sys
5from typing import Literal
6pad_num = (sys.argv[1:] or ["0"])[0] # 0-255 or "1st"
7xor_right_shift_amount = int((sys.argv[2:] or [0])[0]) # 0-...
8search_width = int((sys.argv[3:] or [3])[0]) # >0
9search_depth = int((sys.argv[4:] or [3])[0]) # >0
10
11################################################################################
12
13type BitIndex = int
14type BitString = str
15
16with open("stations.txt", "rb") as f:
17    names = f.readlines()
18names = [n[:-1] for n in names]
19bits: list[BitString] = [ # low index -> LSB
20    "".join(
21        # reverse bit repr for string so lsb is index 0
22        f"{c:08b}"[::-1] for c in s
23    )
24    for s in names
25]
26
27max_bits_for_name = max(len(b) for b in bits)
28
29# returns bitstring to concatenate (as padding)
30def mk_padding(orig_bitstring: BitString) -> BitString:
31    pad_bits = (
32        f"{int(pad_num):08b}" if pad_num != "1st" else (
33            (orig_bitstring[0:] or "0" * 24)[0:8]
34        )
35    )
36    return pad_bits[::-1] * (max_bits_for_name // 8)
37
38padded: list[BitString] = [
39    # .ljust(max_bits_for_name, "0")
40    # (b + ("0" * 300))[0:max_bits_for_name] for b in bits
41    # (b + ("101" * 300))[0:max_bits_for_name] for b in bits # !!!, 16b hash across 8 bytes (highest 68)
42    # (b + ("10001011" * 300))[0:max_bits_for_name] for b in bits
43    # (b + (b[0:8] * 300))[0:max_bits_for_name] for b in bits  # !!!, results in a 15b hash across 8 bytes (+ start byte)
44    # (b + (b[9:16] * 300))[0:max_bits_for_name] for b in bits  # !!!, results in a 15b hash across 10 bytes
45    # (b + (f"{len(b) // 8:0b}" * 300))[0:max_bits_for_name] for b in bits # 16b across 8 bytes
46    # (b + ((f"{int(pad_num):08b}" if pad_num != "1st" else b[0:8]) * 300))[0:max_bits_for_name] for b in bits
47
48    # pad each name to len..
49    (b + mk_padding(b))[0:max_bits_for_name] for b in bits
50]
51
52# shift and xor each name, if requested:
53def xor_shift(b: BitString, bit_shift_right: int) -> BitString:
54    rhs = b[bit_shift_right:]
55    out = ''.join('1' if l != r else '0' for (l, r) in zip(b, rhs))
56    return out
57
58BITS_PER_NAME = max_bits_for_name - xor_right_shift_amount
59if xor_right_shift_amount != 0:
60    padded = [
61        xor_shift(b, xor_right_shift_amount) for b in padded
62    ]
63else:
64    xor_right_shift_amount = "N/A"
65
66# print(len(padded))
67# print(len(set(padded)))
68# from collections import defaultdict
69# x = defaultdict(list)
70# for i, n in enumerate(names):
71#     x[padded[i][0:64]].append(str(n, encoding="utf-8"))
72# for l in x.values():
73#     if len(l) > 1:
74#         print(l)
75# raise "f"
76# Alexandra
77# Alexandria
78
79type Bucket = list[BitString]
80
81def split_bucket(bucket: Bucket, bit_idx: BitIndex) -> tuple[Bucket, Bucket]:
82    return (
83        [n for n in bucket if n[bit_idx] == "0"],
84        [n for n in bucket if n[bit_idx] == "1"]
85    )
86
87def split_buckets(buckets: list[Bucket], idx: BitIndex) -> list[Bucket]:
88    out: list[Bucket] = []
89    for bkt in buckets:
90        out.extend(b for b in split_bucket(bkt, idx) if b != [])
91
92    return out
93
94def score_next_splits(buckets: list[Bucket]) -> list[tuple[BitIndex, float]]:
95    '''
96    for now, the heuristic of choice is how close to even a particular bit
97    splits a bucket by
98
99    we calculate the sum of abs difference of the lengths of the "left"/"right"
100    buckets -- where the bit in being used to split is 0 and 1 respectively --
101    from half the length of the original bucket
102
103    we then sum this value across all the buckets given to us to calculate a
104    particular bit's score (lower is better)
105
106    a bit that, if split on, results in every bucket having 0 or 1 item should
107    have a score of 0 (perfect)
108    '''
109
110    """
111    TODO: for scoring splits, maybe prefer indexes that give larger buckets a
112    more even split? (see below)
113
114        413
115        206 207
116        103 103 103 104
117
118
119        413
120        300 113
121        150 150 56 57 perfect
122
123        160 140 48 65
124        158 142 46 69 prefer this one because:
125        larger buckets are further away from "finishing" so we want them to have
126        the more even split to potentially save an iteration down the road
127    """
128
129    search = BITS_PER_NAME # 80
130    scores = [0. for _ in range(search)]
131    not_stuck = False
132    for split_idx in range(0, search):
133        score = 0
134        for bkt in buckets:
135            if len(bkt) <= 1:
136                continue # already perfect (0/1 elem); shouldn't increase score
137            non_zero_for_idx = sum(n[split_idx] != "0" for n in bkt)
138            score += abs(non_zero_for_idx - len(bkt) / 2) * len(bkt)
139            not_stuck = True
140        scores[split_idx] = score
141
142    if not not_stuck:
143        raise Exception(f"uh-oh, stuck at: {buckets}")
144
145    return sorted(enumerate(scores), key=lambda t: t[1]) # idx, score
146
147# objective: find the fewest number of `BitIndex`es to retain from each name
148# such that each name is in its own bucket
149def tree_search(buckets: list[Bucket], width: int = 1, depth: int = 1) -> list[BitIndex]:
150    deepest = 0
151
152    # each resumable search generator yields `depth` score results; past that
153    # it just picks the best child and drives it to completion
154    #
155    # depth must be >= 1
156    def tree_search_resumable(
157        buckets: list[Bucket],
158        _bit_idx: BitIndex,
159        _score: float,
160        width: int,
161        depth: int,
162        l: int,
163    ):
164        # if we're finished, don't bother expanding the tree (no children)
165        if all(len(bkt) <= 1 for bkt in buckets):
166            # instead just yield 0 scores (best) for all of `depth` and then
167            # return our bit index
168            yield 0 # depth 0
169            for _ in range(depth):
170                yield 0
171            yield 0
172            return [_bit_idx]
173
174        # otherwise...
175        nonlocal deepest
176        if l > deepest:
177            deepest = l
178            if l > (17 + depth):
179                print(f"hit depth {l}, giving up", file=sys.stderr)
180                sys.exit(1)
181            # print(f"depth: {l}")
182
183        # depth = 0
184        yield _score
185
186        # set up children, use them as an indicator:
187        splits_to_try = score_next_splits(buckets)[0:width]
188        children = [
189            tree_search_resumable(
190                split_buckets(buckets, split_idx),
191                split_idx,
192                score,
193                width,
194                depth,
195                l + 1,
196            )
197            for (split_idx, score) in splits_to_try
198        ]
199
200        for _ in range(depth):
201            # TODO: maybe we should sum? weighted? not sure
202            child_scores = [next(c) for c in children]
203            yield min(child_scores)
204
205        # pick the best child (and drop other children to save memory); then
206        # use the best child to find a solution:
207        child_idx = min(enumerate(child_scores), key=lambda t: t[1])[0]
208        best_child = children[child_idx]
209        del children
210
211        # return the child's best solution, with our bit tacked on
212        ret = yield from best_child
213        return ret + [_bit_idx]
214
215    sentinel = 999999
216    gen = tree_search_resumable(buckets, sentinel, 0.0, width, depth, 0)
217
218    ret = None
219    def get_ret(g):
220        nonlocal ret
221        ret = yield from g
222    for score in get_ret(gen):
223        # print(score)
224        pass
225
226    assert ret is not None
227    assert ret[-1] == sentinel
228    return ret[0:-1]
229
230def print_bit_indexes(indices: list[BitIndex]):
231    indices.sort()
232    def do_hash(bitstring):
233        out = 0
234        for i in reversed(indices):
235            out = out << 1 | (bitstring[i] == "1")
236        return out
237
238    empty_bitstring = mk_padding("")
239
240    # how often is each bit in `indices` 0 or 1?
241    bit_heat: list[Counter[Literal['1', '0']]] = [Counter() for _ in indices]
242    for bitstring in padded:
243        for (i, bit_idx) in enumerate(indices):
244            bit = bitstring[bit_idx]
245            bit_heat[i].update([bit])
246
247    lines: list[str] = []
248    seen = set[int]()
249    for name, bitstring in zip(names + [b"<empty str>"], padded + [empty_bitstring]):
250        hash_val = do_hash(bitstring)
251        seen.add(hash_val)
252        lines.append(f"0x{hash_val:08x} " + str(name, encoding="utf-8"))
253
254    if "PRINT_HASHES" in os.environ:
255        for ln in sorted(lines):
256            print(ln)
257        print()
258
259    if "PRINT_HEAT" in os.environ:
260        print("Selected Bit Frequency:")
261        for (b, heat) in zip(indices, bit_heat):
262            print(f"  - {b:2}: {heat}")
263        print()
264
265        print("Heatmap:")
266        # each cell covers a range of 16 addrs (4 bits)
267        # 32 cols (another 5 bits)
268        # rows determined by num remaining bits
269        num_rows = 2 ** (len(indices) - 5 - 4)
270        rows = [[0 for _ in range(32)] for _ in range(num_rows)]
271        for hash_val in seen:
272            col_idx = (hash_val >> 4) & (0b11111)
273            row_idx = (hash_val >> 9)
274            rows[row_idx][col_idx] += 1
275        # scale heat and display:
276        hottest = max(c for row in rows for c in row)
277        bg = lambda r, g=0, b=0: f"\x1b[48;2;{r};{g};{b}m"
278        reset = "\x1b[0m"
279        print(bg(0), end='')
280        print('–'*(len(rows[0]) + 2))
281        for row in rows:
282            print(f'{bg(0)}|', end='')
283            for cell in row:
284                if cell == 0:
285                    print(f'{reset} {bg(0)}', end='')
286                    continue
287
288                scaled = (cell * 255) // hottest
289                print(f'{bg(scaled)} {bg(0)}', end='')
290            print(f'|{reset}')
291        print(bg(0), end='')
292        print('–'*(len(rows[0]) + 2), end='')
293        print(reset)
294        print()
295
296    assert len(seen) == len(padded) or len(seen) == len(padded) + 1
297    empty_string_collides = len(seen) == len(padded)
298    empty_coll = f"empty string {'collides' if empty_string_collides else '[DOES NOT COLLIDE]'}"
299
300    mask = 0
301    bytes = [0 for _ in range(0, BITS_PER_NAME // 8)]
302    for i in indices:
303        mask |= 1 << i
304        bytes[i // 8] += 1
305    num_bytes = sum(c != 0 for c in bytes)
306    print(f"mask {mask:#X}; bits ({len(indices)}) across {num_bytes} bytes; {empty_coll};", indices)
307
308
309print_bit_indexes(tree_search([padded], search_width, search_depth))
310print(f"PAD: {pad_num}; XOR w/right shift: {xor_right_shift_amount}; search {search_width}w {search_depth}d")
311print()
312
313# TODO: consider incorporating len to the hash? (more than just bit extraction)
314# TODO: try to use only bits in first 8 bytes; can use `PEXT` (x86)
315
316# TODO: try weirder stuff like xors?
317#   - or variable rotates like https://www.officedaytime.com/simd512e/simdimg/binopv5.php?f=vprolvd
318#   - or indexing from the _end_ of the strings rather than the start
319#   - or using carryless multiplication on the inputs? (PCLMULQDQ)
320
321# want to minimize range of bit indices (pext)
322#
323# but also want to minimize number of bits (size of table)
324#
325# NOTE: constant pads are nice (easy to implement); bonus if the hash derived
326# entirely from constant pads doesn't conflict with any of the entries
327
328
329# 0X10100020000800204040586800C0; (15 bits)
330#   A99  88   77  6655443322  11
331
332# 0X880001404060383000E8; (16 bits)
333#
334
335# mask 0X14C010A0A060602800; bits (15) across 8 bytes [11, 13, 21, 22, 29, 30, 37, 39, 45, 47, 52, 62, 63, 66, 68]
336# WITH: pad w/b[0:8]
337
338# mask 0X100008283090D028E0; bits (16) across 8 bytes [5, 6, 7, 11, 13, 20, 22, 23, 28, 31, 36, 37, 43, 45, 51, 68]
339# WITH: pad w/010 repeating? (hard...)
340
341# want to prefer answers where fewer bytes are relevant