0

A C coder here.

My wish is to find the best way to search words and phrases within the ever-growing English Wikipedia XML dump. As a first layer/step, hashing is the answer, yes? The problem is that the latest dump is around 72GB in size. Would appreciate more experienced coders sharing their vision on the matter.

As an amateur, an old dream of mine is to have the ability to auto-complete (to have a predictor) any Latin (1..31 bytes long) chunk within a given text. This would help tremendously when one has to instantly check whether the English text which is typed appears within a given corpus. Still, far from the goal.

Since, speed is the most sought after property (second only to dispersion, speaking of up to 32bit hashtables fittable in RAM), I raised the granularity/order of FNV-1A from 1 octet up to 8 octets i.e. QWORD - the result - FNV1A_Pippip, the Y-axis is the hashes/s:

enter image description here

For example, I did a quick test with enwik9 (the first 1,000,000,000 bytes of Wikipedia XML dump) using the first power of 2 bigger than ALL POSITIONS, i.e. 30bit hashtable:

iSCSI CRC32 : All Keys 1 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 0 = (206 - 206)
FNV1A_Pippip: All Keys 1 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 0 = (206 - 206)
WYHASH_v3   : All Keys 1 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 0 = (206 - 206)
XXH3        : All Keys 1 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 0 = (206 - 206)

iSCSI CRC32 : All Keys 2 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 0 = (22,664 - 22,664)
FNV1A_Pippip: All Keys 2 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 0 = (22,664 - 22,664)
WYHASH_v3   : All Keys 2 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 0 = (22,664 - 22,664)
XXH3        : All Keys 2 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 0 = (22,664 - 22,664)

iSCSI CRC32 : All Keys 3 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 0 = (491,817 - 491,817)
FNV1A_Pippip: All Keys 3 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 79 = (491,817 - 491,738)
WYHASH_v3   : All Keys 3 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 108 = (491,817 - 491,709)
XXH3        : All Keys 3 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 100 = (491,817 - 491,717)

iSCSI CRC32 : All Keys 4 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 9,499 = (3,222,263 - 3,212,764)
FNV1A_Pippip: All Keys 4 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 4,722 = (3,222,263 - 3,217,541)
WYHASH_v3   : All Keys 4 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 4,807 = (3,222,263 - 3,217,456)
XXH3        : All Keys 4 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 4,752 = (3,222,263 - 3,217,511)

iSCSI CRC32 : All Keys 5 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 47,509 = (11,375,257 - 11,327,748)
FNV1A_Pippip: All Keys 5 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 60,568 = (11,375,257 - 11,314,689)
WYHASH_v3   : All Keys 5 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 60,200 = (11,375,257 - 11,315,057)
XXH3        : All Keys 5 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 59,971 = (11,375,257 - 11,315,286)

iSCSI CRC32 : All Keys 6 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 365,489 = (28,245,411 - 27,879,922)
FNV1A_Pippip: All Keys 6 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 369,173 = (28,245,411 - 27,876,238)
WYHASH_v3   : All Keys 6 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 367,134 = (28,245,411 - 27,878,277)
XXH3        : All Keys 6 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 367,425 = (28,245,411 - 27,877,986)

iSCSI CRC32 : All Keys 7 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 1,320,238 = (53,725,626 - 52,405,388)
FNV1A_Pippip: All Keys 7 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 1,320,750 = (53,725,626 - 52,404,876)
WYHASH_v3   : All Keys 7 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 1,322,350 = (53,725,626 - 52,403,276)
XXH3        : All Keys 7 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 1,322,572 = (53,725,626 - 52,403,054)

iSCSI CRC32 : All Keys 8 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 3,502,617 = (87,951,564 - 84,448,947)
FNV1A_Pippip: All Keys 8 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 3,506,053 = (87,951,564 - 84,445,511)
WYHASH_v3   : All Keys 8 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 3,505,492 = (87,951,564 - 84,446,072)
XXH3        : All Keys 8 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 3,507,241 = (87,951,564 - 84,444,323)

iSCSI CRC32 : All Keys 9 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 7,640,445 = (130,682,041 - 123,041,596)
FNV1A_Pippip: All Keys 9 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 7,632,636 = (130,682,041 - 123,049,405)
WYHASH_v3   : All Keys 9 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 7,640,436 = (130,682,041 - 123,041,605)
XXH3        : All Keys 9 bytes; Hash_Collisions = (Distinct_Keys - Used_Slots): 7,640,264 = (130,682,041 - 123,041,777)

My benchmark, called Look-up-er-o-rama, allows to give such dumps for keys up to 31 bytes, EZ. Yet, the most common use case is (3..9) when I have to type e.g. Stallone but instead typing Staloune - the goal is to have a superfast and superdispersy function able to search for millions of such queries, per second. Is there a better way to do such searches?

I checked all the 64+GB of English Wikipedia with a fuzzy searcher, and found that the correct spelling of 'Sylvester Stallone' was misspelled 4 times - which prompts for writing a heavy-duty verifier, based on...

Add-on, 2019-Nov-18:

Wanted to see the most wanted scenario - pure English texts in ASCII encoding - in contrast to XML UTF-8 English Wikipedia, the hash dispersion is a bit worse (in short, on par with the three main rivals, while being much faster):

Star_Trek_-_737_TXT-Ebooks.tar (325,071,872 bytes), 29bit hashtable:

enter image description here

--------------------------------------------------------------------------------------------------------------------------------
| Hasher, Building-Blocks order    | Collisions                                                                                |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 01 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (171 - 171) =                       [0] |
| FNV1A_Pippip: All Keys 01 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (171 - 171) =                       [0] |
| WYHASH_v3   : All Keys 01 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (171 - 171) =                       [0] |
| XXH3        : All Keys 01 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (171 - 171) =                       [0] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 02 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (7,540 - 7,540) =                   [0] |
| FNV1A_Pippip: All Keys 02 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (7,540 - 7,540) =                   [0] |
| WYHASH_v3   : All Keys 02 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (7,540 - 7,540) =                   [0] |
| XXH3        : All Keys 02 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (7,540 - 7,540) =                   [0] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 03 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (81,269 - 81,269) =                 [0] |
| FNV1A_Pippip: All Keys 03 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (81,269 - 81,265) =                 [4] |
| WYHASH_v3   : All Keys 03 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (81,269 - 81,263) =                 [6] |
| XXH3        : All Keys 03 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (81,269 - 81,262) =                 [7] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 04 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (427,531 - 427,471) =              [60] |
| FNV1A_Pippip: All Keys 04 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (427,531 - 427,358) =             [173] |
| WYHASH_v3   : All Keys 04 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (427,531 - 427,380) =             [151] |
| XXH3        : All Keys 04 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (427,531 - 427,362) =             [169] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 05 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (1,469,991 - 1,468,831) =       [1,160] |
| FNV1A_Pippip: All Keys 05 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (1,469,991 - 1,467,836) =       [2,155] |
| WYHASH_v3   : All Keys 05 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (1,469,991 - 1,467,984) =       [2,007] |
| XXH3        : All Keys 05 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (1,469,991 - 1,467,969) =       [2,022] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 06 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (3,990,514 - 3,976,606) =      [13,908] |
| FNV1A_Pippip: All Keys 06 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (3,990,514 - 3,975,612) =      [14,902] |
| WYHASH_v3   : All Keys 06 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (3,990,514 - 3,975,699) =      [14,815] |
| XXH3        : All Keys 06 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (3,990,514 - 3,975,820) =      [14,694] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 07 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (9,150,775 - 9,073,465) =      [77,310] |
| FNV1A_Pippip: All Keys 07 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (9,150,775 - 9,072,819) =      [77,956] |
| WYHASH_v3   : All Keys 07 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (9,150,775 - 9,073,588) =      [77,187] |
| XXH3        : All Keys 07 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (9,150,775 - 9,072,886) =      [77,889] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 08 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (17,941,023 - 17,644,835) =   [296,188] |
| FNV1A_Pippip: All Keys 08 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (17,941,023 - 17,644,064) =   [296,959] |
| WYHASH_v3   : All Keys 08 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (17,941,023 - 17,644,106) =   [296,917] |
| XXH3        : All Keys 08 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (17,941,023 - 17,645,122) =   [295,901] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 09 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (30,981,351 - 30,106,215) =   [875,136] |
| FNV1A_Pippip: All Keys 09 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (30,981,351 - 30,104,837) =   [876,514] |
| WYHASH_v3   : All Keys 09 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (30,981,351 - 30,105,085) =   [876,266] |
| XXH3        : All Keys 09 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (30,981,351 - 30,104,309) =   [877,042] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 10 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (48,387,322 - 46,272,512) = [2,114,810] |
| FNV1A_Pippip: All Keys 10 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (48,387,322 - 46,273,345) = [2,113,977] |
| WYHASH_v3   : All Keys 10 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (48,387,322 - 46,272,960) = [2,114,362] |
| XXH3        : All Keys 10 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (48,387,322 - 46,271,345) = [2,115,977] |
--------------------------------------------------------------------------------------------------------------------------------
| iSCSI CRC32 : All Keys 11 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (69,456,330 - 65,156,973) = [4,299,357] |
| FNV1A_Pippip: All Keys 11 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (69,456,330 - 65,146,568) = [4,309,762] |
| WYHASH_v3   : All Keys 11 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (69,456,330 - 65,150,706) = [4,305,624] |
| XXH3        : All Keys 11 bytes; | (Distinct_Keys - Used_Slots) = [Hash_Collisions]: (69,456,330 - 65,152,752) = [4,303,578] |
--------------------------------------------------------------------------------------------------------------------------------

Also, a sight for the naysayers:

https://godbolt.org/z/D9MyQQ

The Whole Function: 00085 - 00000 + 1 = 134 bytes
The Main Loop: 00048 - 00026 + 2 = 36 bytes

; mark_description "Intel(R) C++ Compiler XE for applications running on Intel(R) 64, Version 15.0.0.108 Build 20140726";
; mark_description "-TP -O3 -arch:SSE4.1 -D_N_XMM -D_N_prefetch_4096 -D_N_alone -D_N_HIGH_PRIORITY -D_icl_mumbo_jumbo_ -FAcs -DH";
; mark_description "ashInBITS=24 -DHashChunkSizeInBITS=24 -DRAMpoolInKB=5120 -DBtreeHEURISTIC -D_WIN32_ENVIRONMENT_ -DLongestLin";
; mark_description "eInclusive=64 -D_N_CRC32C";

?FNV1A_Pippip_Yurii@@YAIPEBD_K@Z    PROC 
; parameter 1: rcx
; parameter 2: rdx
.B20.1::                        

;;; uint32_t FNV1A_Pippip_Yurii(const char *str, size_t wrdlen) {

  00000 49 89 c8         mov r8, rcx                            

;;;     const uint32_t PRIME = 591798841; uint32_t hash32; uint64_t hash64 = 14695981039346656037;

  00003 48 b8 25 23 22 
        84 e4 9c f2 cb   mov rax, 0cbf29ce484222325H            

;;;     size_t Cycles, NDhead;
;;; if (wrdlen > 8) {

  0000d 48 83 fa 08      cmp rdx, 8                             
  00011 76 39            jbe .B20.8 

.B20.2::                        

;;;     Cycles = ((wrdlen - 1)>>4) + 1; NDhead = wrdlen - (Cycles<<3);

  00013 48 8d 4a ff      lea rcx, QWORD PTR [-1+rdx]            
  00017 48 c1 e9 04      shr rcx, 4                             
  0001b 4c 8d 49 01      lea r9, QWORD PTR [1+rcx]              
  0001f 49 c1 e1 03      shl r9, 3                              
  00023 49 2b d1         sub rdx, r9                            

.B20.6::                        

;;; #pragma nounroll
;;;         for(; Cycles--; str += 8) {
;;;         hash64 = ( hash64 ^ (*(uint64_t *)(str)) ) * PRIME;        

  00026 49 33 00         xor rax, QWORD PTR [r8]                

;;;         hash64 = ( hash64 ^ (*(uint64_t *)(str+NDhead)) ) * PRIME;        

  00029 49 89 c9         mov r9, rcx                            
  0002c 48 69 c0 39 22 
        46 23            imul rax, rax, 591798841               
  00033 49 33 04 10      xor rax, QWORD PTR [r8+rdx]            
  00037 49 83 c0 08      add r8, 8                              
  0003b 48 69 c0 39 22 
        46 23            imul rax, rax, 591798841               
  00042 48 ff c9         dec rcx                                
  00045 4d 85 c9         test r9, r9                            
  00048 75 dc            jne .B20.6 
  0004a eb 28            jmp .B20.9 

.B20.8::                        

;;;     }
;;; } else
;;;     hash64 = ( hash64 ^ _PADr_KAZE(*(uint64_t *)(str+0), (8-wrdlen)<<3) ) * PRIME;        

  0004c 48 f7 da         neg rdx                                
  0004f 48 c1 e2 03      shl rdx, 3                             
  00053 89 d1            mov ecx, edx                           
  00055 49 8b 00         mov rax, QWORD PTR [r8]                
  00058 49 b8 25 23 22 
        84 e4 9c f2 cb   mov r8, 0cbf29ce484222325H             
  00062 48 d3 e0         shl rax, cl                            
  00065 89 d1            mov ecx, edx                           
  00067 48 d3 e8         shr rax, cl                            
  0006a 4c 33 c0         xor r8, rax                            
  0006d 49 69 c0 39 22 
        46 23            imul rax, r8, 591798841                

.B20.9::                        

;;; hash32 = (uint32_t)(hash64 ^ (hash64>>32)); return hash32 ^ (hash32 >> 16);

  00074 48 89 c2         mov rdx, rax                           
  00077 48 c1 ea 20      shr rdx, 32                            
  0007b 48 33 c2         xor rax, rdx                           
  0007e 89 c1            mov ecx, eax                           
  00080 c1 e9 10         shr ecx, 16                            
  00083 33 c1            xor eax, ecx                           
  00085 c3               ret                                    
  00086 0f 1f 00 0f 1f 
        80 00 00 00 00   ALIGN     16

.B20.10::
; mark_end;
?FNV1A_Pippip_Yurii@@YAIPEBD_K@Z ENDP
;?FNV1A_Pippip_Yurii@@YAIPEBD_K@Z   ENDS
_TEXT   ENDS
_DATA   SEGMENT      'DATA'
_DATA   ENDS
; -- End  ?FNV1A_Pippip_Yurii@@YAIPEBD_K@Z
| improve this question | | | | |
  • Is there a better way to search Wikipedia? Yes, by using Wikipedia's search form. It will also suggest results while entering your query. Why are you trying to reinvent the wheel? – Dan Wilson Nov 18 '19 at 1:35
  • >Why are you trying to reinvent the wheel? Having C superfast etudes is the primary goal, all textual processing comes as a result, or rather, by-product. – Georgi Nov 18 '19 at 18:25
  • Is there a question here? – JimmyJames Nov 18 '19 at 22:19
  • @JimmyJames See, since the logo is kinda invitational, my wish is software engineers to share their view how to speed up not only hashing of English texts but also other related stuff. – Georgi Nov 18 '19 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.