collab/1brc
the one billion row challenge
git clone https://git.julia.blue/collab/1brc
926868e
back-to-mmap
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 13typeBitIndex = int 14typeBitString = str 15 16with open ("stations.txt" ,"rb" )as f : 17names = 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 22f" { c :08b } " [::- 1 ]for c in s 23 ) 24for 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 : 31pad_bits = ( 32f" { int ( pad_num ):08b } " if pad_num != "1st" else ( 33 (orig_bitstring [0 :]or "0" * 24 )[0 :8 ] 34 ) 35 ) 36return 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 : 54rhs = b [bit_shift_right :] 55out = '' .join ('1' if l != r else '0' for (l ,r )in zip (b ,rhs )) 56return out 57 58BITS_PER_NAME = max_bits_for_name - xor_right_shift_amount 59if xor_right_shift_amount != 0 : 60padded = [ 61xor_shift (b ,xor_right_shift_amount )for b in padded 62 ] 63else : 64xor_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 79typeBucket = list [BitString ] 80 81def split_bucket (bucket :Bucket ,bit_idx :BitIndex )-> tuple [Bucket ,Bucket ]: 82return ( 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 ]: 88out :list [Bucket ]= [] 89for bkt in buckets : 90out .extend (b for b in split_bucket (bkt ,idx )if b != []) 91 92return out 93 94def score_next_splits (buckets :list [Bucket ])-> list [tuple [BitIndex ,float ]]: 95''' 96for now, the heuristic of choice is how close to even a particular bit 97splits a bucket by 98 99we calculate the sum of abs difference of the lengths of the "left"/"right" 100buckets -- where the bit in being used to split is 0 and 1 respectively -- 101from half the length of the original bucket 102 103we then sum this value across all the buckets given to us to calculate a 104particular bit's score (lower is better) 105 106a bit that, if split on, results in every bucket having 0 or 1 item should 107have a score of 0 (perfect) 108''' 109 110""" 111TODO: for scoring splits, maybe prefer indexes that give larger buckets a 112more even split? (see below) 113 114413 115206 207 116103 103 103 104 117 118 119413 120300 113 121150 150 56 57 perfect 122 123160 140 48 65 124158 142 46 69 prefer this one because: 125larger buckets are further away from "finishing" so we want them to have 126the more even split to potentially save an iteration down the road 127""" 128 129search = BITS_PER_NAME # 80 130scores = [0. for _ in range (search )] 131not_stuck = False 132for split_idx in range (0 ,search ): 133score = 0 134for bkt in buckets : 135if len (bkt )<= 1 : 136continue # already perfect (0/1 elem); shouldn't increase score 137non_zero_for_idx = sum (n [split_idx ]!= "0" for n in bkt ) 138score += abs (non_zero_for_idx - len (bkt )/ 2 )* len (bkt ) 139not_stuck = True 140scores [split_idx ]= score 141 142if not not_stuck : 143raise Exception (f"uh-oh, stuck at: { buckets } " ) 144 145return 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 ]: 150deepest = 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 156def tree_search_resumable ( 157buckets :list [Bucket ], 158_bit_idx :BitIndex , 159_score :float , 160width :int , 161depth :int , 162l :int , 163 ): 164# if we're finished, don't bother expanding the tree (no children) 165if 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 168yield 0 # depth 0 169for _ in range (depth ): 170yield 0 171yield 0 172return [_bit_idx ] 173 174# otherwise... 175nonlocal deepest 176if l > deepest : 177deepest = l 178if l > (17 + depth ): 179f"hit depth { l } , giving up" ,file = sys .stderr ) 180sys .exit (1 ) 181# print(f"depth: {l}") 182 183# depth = 0 184yield _score 185 186# set up children, use them as an indicator: 187splits_to_try = score_next_splits (buckets )[0 :width ] 188children = [ 189tree_search_resumable ( 190split_buckets (buckets ,split_idx ), 191split_idx , 192score , 193width , 194depth , 195l + 1 , 196 ) 197for (split_idx ,score )in splits_to_try 198 ] 199 200for _ in range (depth ): 201# TODO: maybe we should sum? weighted? not sure 202child_scores = [next (c )for c in children ] 203yield 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: 207child_idx = min (enumerate (child_scores ),key = lambda t :t [1 ])[0 ] 208best_child = children [child_idx ] 209del children 210 211# return the child's best solution, with our bit tacked on 212ret = yield from best_child 213return ret + [_bit_idx ] 214 215sentinel = 999999 216gen = tree_search_resumable (buckets ,sentinel ,0.0 ,width ,depth ,0 ) 217 218ret = None 219def get_ret (g ): 220nonlocal ret 221ret = yield from g 222for score in get_ret (gen ): 223# print(score) 224pass 225 226assert ret is not None 227assert ret [- 1 ]== sentinel 228return ret [0 :- 1 ] 229 230def print_bit_indexes (indices :list [BitIndex ]): 231indices .sort () 232def do_hash (bitstring ): 233out = 0 234for i in reversed (indices ): 235out = out << 1 | (bitstring [i ]== "1" ) 236return out 237 238empty_bitstring = mk_padding ("" ) 239 240# how often is each bit in `indices` 0 or 1? 241bit_heat :list [Counter [Literal ['1' ,'0' ]]]= [Counter ()for _ in indices ] 242for bitstring in padded : 243for (i ,bit_idx )in enumerate (indices ): 244bit = bitstring [bit_idx ] 245bit_heat [i ].update ([bit ]) 246 247lines :list [str ]= [] 248seen = set [int ]() 249for name ,bitstring in zip (names + [b"<empty str>" ],padded + [empty_bitstring ]): 250hash_val = do_hash (bitstring ) 251seen .add (hash_val ) 252lines .append (f"0x { hash_val :08x } " + str (name ,encoding = "utf-8" )) 253 254if "PRINT_HASHES" in os .environ : 255for ln in sorted (lines ): 256ln ) 257if "PRINT_HEAT" in os .environ : 260"Selected Bit Frequency:" ) 261for (b ,heat )in zip (indices ,bit_heat ): 262f" - { b :2 } : { heat } " ) 263"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 269num_rows = 2 ** (len (indices )- 5 - 4 ) 270rows = [[0 for _ in range (32 )]for _ in range (num_rows )] 271for hash_val in seen : 272col_idx = (hash_val >> 4 )& (0b11111 ) 273row_idx = (hash_val >> 9 ) 274rows [row_idx ][col_idx ]+= 1 275# scale heat and display: 276hottest = max (c for row in rows for c in row ) 277bg = lambda r ,g = 0 ,b = 0 :f"\x1b[48;2; { r } ; { g } ; { b } m" 278reset = "\x1b[0m" 279bg (0 ),end = '' ) 280'–' * (len (rows [0 ])+ 2 )) 281for row in rows : 282f' { bg ( 0 ) } |' ,end = '' ) 283for cell in row : 284if cell == 0 : 285f' { reset } { bg ( 0 ) } ' ,end = '' ) 286continue 287 288scaled = (cell * 255 )// hottest 289f' { bg ( scaled ) } { bg ( 0 ) } ' ,end = '' ) 290f'| { reset } ' ) 291bg (0 ),end = '' ) 292'–' * (len (rows [0 ])+ 2 ),end = '' ) 293reset ) 294assert len (seen )== len (padded )or len (seen )== len (padded )+ 1 297empty_string_collides = len (seen )== len (padded ) 298empty_coll = f"empty string { 'collides' if empty_string_collides else '[DOES NOT COLLIDE]' } " 299 300mask = 0 301bytes = [0 for _ in range (0 ,BITS_PER_NAME // 8 )] 302for i in indices : 303mask |= 1 << i 304bytes [i // 8 ]+= 1 305num_bytes = sum (c != 0 for c in bytes ) 306f"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 )) 310f"PAD: { pad_num } ; XOR w/right shift: { xor_right_shift_amount } ; search { search_width } w { search_depth } d" ) 311# 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