assembly-hashmap 0.1.0

A single-threaded u64→u64 hashmap with x86-64 assembly operations and Rust-side growth.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
/* SwissTable hashmap: u64 -> u64, x86-64 System V.
 *
 * Control bytes (hashbrown / std::collections::HashMap):
 *   EMPTY   = 0xFF
 *   DELETED = 0x80
 *   FULL    = top 7 bits of the hash (0..127)
 *
 * Probe: triangular sequence over unaligned 16-byte groups (SSE2).
 */

#ifdef __APPLE__
#define C(name) _##name
#else
#define C(name) name
#endif

#define CTRL        0
#define SLOTS       8
#define MASK        16
#define ITEMS       24
#define GROWTH      32
#define CAP_ITEMS   40

#define GROUP       16
#define EMPTY       0xFF
#define DELETED     0x80
#define HASH_MUL    0x517cc1b727220a95

        .intel_syntax noprefix
        .text

#ifndef __APPLE__
        .section .note.GNU-stack,"",@progbits
        .text
#endif

        .macro HASH_AND_H2 dst_hash, dst_h2, keyreg
        mov     \dst_hash, HASH_MUL
        imul    \dst_hash, \keyreg
        mov     \dst_h2, \dst_hash
        shr     \dst_h2, 57
        .endm

        .macro BROADCAST_H2 xmm, h2reg, tmp
        mov     \tmp, 0x0101010101010101
        imul    \tmp, \h2reg
        movq    \xmm, \tmp
        punpcklqdq \xmm, \xmm
        .endm

        .p2align 4
        .globl  C(hm_get)
C(hm_get):
        mov     r8, qword ptr [rdi + CTRL]
        mov     r9, qword ptr [rdi + SLOTS]
        mov     r10, qword ptr [rdi + MASK]

        HASH_AND_H2 rax, rcx, rsi
        mov     r11, rax
        and     r11, r10                      /* pos */

        BROADCAST_H2 xmm1, rcx, rax
        pcmpeqb xmm3, xmm3                    /* EMPTY = 0xFF */

        mov     rax, r11
        shl     rax, 4
        prefetcht0 byte ptr [r9 + rax]

        xor     edi, edi                      /* stride */

        .p2align 4
.Lget_probe:
        movdqu  xmm0, xmmword ptr [r8 + r11]
        movdqa  xmm2, xmm0
        pcmpeqb xmm2, xmm1
        pmovmskb ecx, xmm2
        test    ecx, ecx
        jz      .Lget_check_empty

.Lget_scan:
        tzcnt   eax, ecx
        add     rax, r11
        and     rax, r10
        shl     rax, 4
        cmp     rsi, qword ptr [r9 + rax]
        je      .Lget_hit
        lea     edx, [rcx - 1]
        and     ecx, edx
        jnz     .Lget_scan

.Lget_check_empty:
        movdqa  xmm2, xmm0
        pcmpeqb xmm2, xmm3
        pmovmskb eax, xmm2
        test    eax, eax
        jnz     .Lget_none

        add     rdi, GROUP
        add     r11, rdi
        and     r11, r10
        jmp     .Lget_probe

        .p2align 4
.Lget_hit:
        mov     rdx, qword ptr [r9 + rax + 8]
        mov     eax, 1
        ret

        .p2align 4
.Lget_none:
        xor     eax, eax
        xor     edx, edx
        ret


        .p2align 4
        .globl  C(hm_put)
C(hm_put):
        xor     ecx, ecx                      /* overwrite */
        jmp     .Lput_entry

        .globl  C(hm_put_if_absent)
C(hm_put_if_absent):
        mov     ecx, 1                        /* preserve existing */
        jmp     .Lput_entry

        .globl  C(hm_get_or_insert)
C(hm_get_or_insert):
        mov     ecx, 1                        /* same native operation/result */
        jmp     .Lput_entry

        .globl  C(hm_replace)
C(hm_replace):
        mov     ecx, 2                        /* update only */

.Lput_entry:
        push    rbx
        push    r12
        push    r13
        push    r14
        push    r15
        push    rbp

        mov     ebp, ecx                      /* insertion mode */
        mov     r12, rdi                      /* map */
        mov     r13, rsi                      /* key */
        mov     r14, rdx                      /* value */

        mov     r8, qword ptr [rdi + CTRL]
        mov     r9, qword ptr [rdi + SLOTS]
        mov     r10, qword ptr [rdi + MASK]

        HASH_AND_H2 r15, rcx, rsi             /* r15 = hash, rcx = h2 */
        mov     r11, r15
        and     r11, r10

        BROADCAST_H2 xmm1, rcx, rax
        pcmpeqb xmm3, xmm3

        xor     edi, edi                      /* stride */
        mov     rbx, -1                       /* first empty/deleted */

        .p2align 4
.Lput_probe:
        movdqu  xmm0, xmmword ptr [r8 + r11]
        movdqa  xmm2, xmm0
        pcmpeqb xmm2, xmm1
        pmovmskb ecx, xmm2
        test    ecx, ecx
        jz      .Lput_record_slot

.Lput_scan:
        tzcnt   eax, ecx
        add     rax, r11
        and     rax, r10
        shl     rax, 4
        cmp     r13, qword ptr [r9 + rax]
        je      .Lput_update
        lea     edx, [rcx - 1]
        and     ecx, edx
        jnz     .Lput_scan

.Lput_record_slot:
        cmp     rbx, -1
        jne     .Lput_check_empty
        pmovmskb eax, xmm0                    /* EMPTY | DELETED (high bit) */
        test    eax, eax
        jz      .Lput_check_empty
        tzcnt   eax, eax
        add     rax, r11
        and     rax, r10
        mov     rbx, rax

.Lput_check_empty:
        movdqa  xmm2, xmm0
        pcmpeqb xmm2, xmm3
        pmovmskb eax, xmm2
        test    eax, eax
        jnz     .Lput_absent

        add     rdi, GROUP
        add     r11, rdi
        and     r11, r10
        jmp     .Lput_probe

        .p2align 4
.Lput_update:
        mov     rdx, qword ptr [r9 + rax + 8]
        cmp     ebp, 1
        je      .Lput_return_present
        mov     qword ptr [r9 + rax + 8], r14
.Lput_return_present:
        mov     eax, 1
        pop     rbp
        pop     r15
        pop     r14
        pop     r13
        pop     r12
        pop     rbx
        ret

        .p2align 4
.Lput_absent:
        cmp     ebp, 2
        je      .Lput_not_found               /* replace does not insert */
        cmp     rbx, -1
        jne     .Lput_have_slot
        /* Pathological: ask the Rust owner to rebuild and retry. */
        mov     eax, 2
        xor     edx, edx
        pop     rbp
        pop     r15
        pop     r14
        pop     r13
        pop     r12
        pop     rbx
        ret

.Lput_have_slot:
        mov     rax, qword ptr [r12 + GROWTH]
        mov     cl, byte ptr [r8 + rbx]
        test    rax, rax
        jnz     .Lput_do_insert
        cmp     cl, EMPTY
        jne     .Lput_do_insert               /* reuse DELETED at 0 growth */
        jmp     .Lput_full                    /* Rust rebuilds/resizes */

.Lput_do_insert:
        cmp     cl, EMPTY
        jne     .Lput_store
        dec     qword ptr [r12 + GROWTH]
.Lput_store:
        /* set_ctrl(index=rbx, h2 = hash>>57) */
        mov     rax, r15
        shr     rax, 57
        mov     byte ptr [r8 + rbx], al
        mov     rdx, rbx
        sub     rdx, GROUP
        and     rdx, r10
        add     rdx, GROUP
        mov     byte ptr [r8 + rdx], al

        mov     rax, rbx
        shl     rax, 4
        mov     qword ptr [r9 + rax], r13
        mov     qword ptr [r9 + rax + 8], r14
        inc     qword ptr [r12 + ITEMS]
        xor     eax, eax
        xor     edx, edx
        pop     rbp
        pop     r15
        pop     r14
        pop     r13
        pop     r12
        pop     rbx
        ret

.Lput_full:
        mov     eax, 2
        xor     edx, edx
        pop     rbp
        pop     r15
        pop     r14
        pop     r13
        pop     r12
        pop     rbx
        ret

.Lput_not_found:
        xor     eax, eax
        xor     edx, edx
        pop     rbp
        pop     r15
        pop     r14
        pop     r13
        pop     r12
        pop     rbx
        ret


        .p2align 4
        .globl  C(hm_remove)
C(hm_remove):
        push    rbx
        push    r12

        mov     r12, rdi
        mov     r8, qword ptr [rdi + CTRL]
        mov     r9, qword ptr [rdi + SLOTS]
        mov     r10, qword ptr [rdi + MASK]

        HASH_AND_H2 rax, rcx, rsi
        mov     r11, rax
        and     r11, r10

        BROADCAST_H2 xmm1, rcx, rax
        pcmpeqb xmm3, xmm3

        xor     edi, edi

        .p2align 4
.Lrm_probe:
        movdqu  xmm0, xmmword ptr [r8 + r11]
        movdqa  xmm2, xmm0
        pcmpeqb xmm2, xmm1
        pmovmskb ecx, xmm2
        test    ecx, ecx
        jz      .Lrm_check_empty

.Lrm_scan:
        tzcnt   eax, ecx
        add     rax, r11
        and     rax, r10
        mov     rbx, rax                      /* index */
        shl     rax, 4
        cmp     rsi, qword ptr [r9 + rax]
        je      .Lrm_found
        lea     edx, [rcx - 1]
        and     ecx, edx
        jnz     .Lrm_scan

.Lrm_check_empty:
        movdqa  xmm2, xmm0
        pcmpeqb xmm2, xmm3
        pmovmskb eax, xmm2
        test    eax, eax
        jnz     .Lrm_none

        add     rdi, GROUP
        add     r11, rdi
        and     r11, r10
        jmp     .Lrm_probe

        .p2align 4
.Lrm_none:
        xor     eax, eax
        xor     edx, edx
        pop     r12
        pop     rbx
        ret

        .p2align 4
.Lrm_found:
        mov     r11, qword ptr [r9 + rax + 8] /* old value */

        /* empty_before = match_empty(load(index - 16)) */
        mov     rdx, rbx
        sub     rdx, GROUP
        and     rdx, r10
        movdqu  xmm0, xmmword ptr [r8 + rdx]
        pcmpeqb xmm0, xmm3
        pmovmskb ecx, xmm0                    /* empty_before */
        /* leading_zeros_16(ecx) = lzcnt32(ecx & 0xffff) - 16 */
        movzx   ecx, cx
        test    ecx, ecx
        jnz     .Lrm_lz
        mov     r10d, 16
        jmp     .Lrm_have_lz
.Lrm_lz:
        bsr     r10d, ecx
        mov     eax, 15
        sub     eax, r10d
        mov     r10d, eax
.Lrm_have_lz:
        /* empty_after at index */
        mov     rax, qword ptr [r12 + MASK]
        movdqu  xmm0, xmmword ptr [r8 + rbx]
        pcmpeqb xmm0, xmm3
        pmovmskb ecx, xmm0
        movzx   ecx, cx
        test    ecx, ecx
        jnz     .Lrm_tz
        mov     ecx, 16
        jmp     .Lrm_have_tz
.Lrm_tz:
        tzcnt   ecx, ecx
.Lrm_have_tz:
        add     ecx, r10d
        cmp     ecx, GROUP
        jae     .Lrm_tomb
        inc     qword ptr [r12 + GROWTH]
        mov     edx, EMPTY
        jmp     .Lrm_set
.Lrm_tomb:
        mov     edx, DELETED
.Lrm_set:
        mov     byte ptr [r8 + rbx], dl
        mov     rcx, rbx
        sub     rcx, GROUP
        and     rcx, rax                      /* mask (saved in rax) */
        add     rcx, GROUP
        mov     byte ptr [r8 + rcx], dl
        dec     qword ptr [r12 + ITEMS]

        mov     rdx, r11
        mov     eax, 1
        pop     r12
        pop     rbx
        ret


        /* contains has exactly the get probe and returns get's presence word. */
        .p2align 4
        .globl  C(hm_contains)
C(hm_contains):
        jmp     C(hm_get)


        .p2align 4
        .globl  C(hm_len)
C(hm_len):
        mov     rax, qword ptr [rdi + ITEMS]
        ret

        .p2align 4
        .globl  C(hm_capacity)
C(hm_capacity):
        mov     rax, qword ptr [rdi + CAP_ITEMS]
        ret


        .p2align 4
        .globl  C(hm_clear)
C(hm_clear):
        mov     r8, qword ptr [rdi + CTRL]
        mov     rcx, qword ptr [rdi + MASK]
        add     rcx, 1 + GROUP                /* real + replicated controls */
        pcmpeqb xmm0, xmm0                    /* sixteen EMPTY bytes */
        xor     eax, eax
.Lclear_loop:
        movdqa  xmmword ptr [r8 + rax], xmm0  /* ctrl is 64-byte aligned */
        add     rax, GROUP
        cmp     rax, rcx
        jb      .Lclear_loop
        mov     qword ptr [rdi + ITEMS], 0
        mov     rax, qword ptr [rdi + CAP_ITEMS]
        mov     qword ptr [rdi + GROWTH], rax
        ret


        .p2align 4
        .globl  C(hm_iter_next)
C(hm_iter_next):
        mov     r8, qword ptr [rsi]            /* cursor */
        mov     r9, qword ptr [rdi + MASK]
        inc     r9                             /* bucket count */
        mov     r10, qword ptr [rdi + CTRL]
.Liter_loop:
        cmp     r8, r9
        jae     .Liter_none
        lea     rax, [r8 + 1]
        mov     qword ptr [rsi], rax
        test    byte ptr [r10 + r8], 0x80
        jz      .Liter_hit
        inc     r8
        jmp     .Liter_loop
.Liter_hit:
        mov     r10, qword ptr [rdi + SLOTS]
        shl     r8, 4
        mov     rax, qword ptr [r10 + r8]
        mov     qword ptr [rdx], rax
        mov     rax, qword ptr [r10 + r8 + 8]
        mov     qword ptr [rcx], rax
        mov     eax, 1
        ret
.Liter_none:
        xor     eax, eax
        ret