I want more people to experience the hash-benchmark-fun, also to offer a playground/base for further improvements, so here is my newest test package(107,010,915 bytes): http://www.sanmayce.com/Downloads/_KAZE_hash_test_r2.7z
The benchmark program is written by Peter Kankowski, for more info: http://www.strchr.com
For longer(than ordinary words) strings i.e. phrases/sentences/files here comes the FNV1A_Jesteress - simply the fastest hasher so far:
There is some inconsistency(I still cannot understand what causes it) in speed tests, though.Code:D:\_KAZE_new-stuff\_KAZE_hash_test_r2>dir Volume in drive D is H320_Vol5 Volume Serial Number is 0CB3-C881 Directory of D:\_KAZE_new-stuff\_KAZE_hash_test_r2 11/14/2010 02:39 PM <DIR> . 11/14/2010 02:39 PM <DIR> .. 11/14/2010 02:39 PM 205,535 hash.cod 11/14/2010 02:39 PM 87,040 hash.exe 11/14/2010 08:06 AM <DIR> RESULTS_Intel T3400 Merom 2.16GHz 11/14/2010 02:39 PM 2,040 Runme.bat 11/14/2010 02:39 PM 4,347,243 Sentence-list_00,032,359_English_The_Holy_Bible.txt 11/14/2010 02:39 PM 388,308 Word-list_00,038,936_English_The Oxford Thesaurus, An A-Z Dictionary of Synonyms.wrd 11/14/2010 02:39 PM 1,121,365 Word-list_00,105,982_English_Spell-Check_High-Quality.wrd 11/14/2010 02:39 PM 4,024,146 Word-list_00,351,114_English_Spell-Check_Unknown-Quality.wrd 11/14/2010 02:39 PM 7,000,453 Word-list_00,584,879_Russian_Spell-Check_Unknown-Quality.slv 11/14/2010 02:39 PM 146,973,879 Word-list_12,561,874_wikipedia-en-html.tar.wrd 11/14/2010 02:39 PM 278,013,406 Word-list_22,202,980_wikipedia-de-en-es-fr-it-nl-pt-ro-html.tar.wrd 11/14/2010 07:11 AM <DIR> _Kaze_hashers 11/14/2010 05:59 AM <DIR> _Peter_source 11/13/2010 04:39 AM <DIR> _SHA1+RIPEMD-160_C_sources_EXEs 10 File(s) 442,163,415 bytes 6 Dir(s) 2,578,087,936 bytes free D:\_KAZE_new-stuff\_KAZE_hash_test_r2\RESULTS_Intel T3400 Merom 2.16GHz>dir Volume in drive D is H320_Vol5 Volume Serial Number is 0CB3-C881 Directory of D:\_KAZE_new-stuff\_KAZE_hash_test_r2\RESULTS_Intel T3400 Merom 2.16GHz 11/14/2010 08:06 AM <DIR> . 11/14/2010 08:06 AM <DIR> .. 11/14/2010 02:39 PM 3,225 Sentence-list_00,032,359.txt 11/14/2010 02:39 PM 3,225 Sentence-list_00,032,359_COLLISIONS.txt 11/14/2010 02:39 PM 3,225 Sentence-list_00,032,359_SPEED.txt 11/14/2010 02:39 PM 3,226 Word-list_00,038,936.txt 11/14/2010 02:39 PM 3,226 Word-list_00,038,936_COLLISIONS.txt 11/14/2010 02:39 PM 3,226 Word-list_00,038,936_SPEED.txt 11/14/2010 02:39 PM 3,227 Word-list_00,105,982.txt 11/14/2010 02:39 PM 3,227 Word-list_00,105,982_COLLISIONS.txt 11/14/2010 02:39 PM 3,227 Word-list_00,105,982_SPEED.txt 11/14/2010 02:39 PM 3,228 Word-list_00,351,114.txt 11/14/2010 02:39 PM 3,228 Word-list_00,351,114_COLLISIONS.txt 11/14/2010 02:39 PM 3,228 Word-list_00,351,114_SPEED.txt 11/14/2010 02:39 PM 3,228 Word-list_00,584,879.txt 11/14/2010 02:39 PM 3,228 Word-list_00,584,879_COLLISIONS.txt 11/14/2010 02:39 PM 3,228 Word-list_00,584,879_SPEED.txt 11/14/2010 02:39 PM 3,231 Word-list_12,561,874.txt 11/14/2010 02:39 PM 3,231 Word-list_12,561,874_COLLISIONS.txt 11/14/2010 02:39 PM 3,231 Word-list_12,561,874_SPEED.txt 11/14/2010 02:39 PM 3,231 Word-list_22,202,980.txt 11/14/2010 02:39 PM 3,231 Word-list_22,202,980_COLLISIONS.txt 11/14/2010 02:39 PM 3,231 Word-list_22,202,980_SPEED.txt 21 File(s) 67,788 bytes 2 Dir(s) 2,578,087,936 bytes free D:\_KAZE_new-stuff\_KAZE_hash_test_r2\RESULTS_Intel T3400 Merom 2.16GHz>type "Sentence-list_00,032,359_SPEED.txt" 65536 elements in the table (16 bits) 32359 lines read FNV1A_Jesteress: 27486 27561 27524 27740 27467| 27467 [ 6883] Fletcher: 28510 28325 28469 28188 28479| 28188 [ 7209] FNV1A_Nefertiti: 30219 32312 29868 30396 30358| 29868 [ 6878] FNV1A_Jester: 30544 30578 30522 31215 30649| 30522 [ 6874] FNV1A_Peregrine: 30986 31291 31281 30679 30843| 30679 [ 6838] Murmur2: 31362 31596 31813 31710 31811| 31362 [ 6786] FNV1A_Whiz: 31635 31615 31536 31797 31709| 31536 [ 6874] Sixtinsensitive+: 35360 35442 34830 35445 36751| 34830 [ 6839] SBox: 36080 36330 36118 36253 36079| 36079 [ 6839] Novak unrolled: 36892 36613 36636 36954 36712| 36613 [ 6826] Sixtinsensitive: 38315 38317 37942 37846 37881| 37846 [ 6876] Alfalfa_Rollick: 39244 39516 39424 39229 39412| 39229 [ 6885] Paul Hsieh: 42724 40838 41222 41249 40557| 40557 [ 6874] FNV1A_Smaragd: 41892 40755 40975 40963 40593| 40593 [ 6849] lookup3: 43049 42185 42269 41874 42486| 41874 [ 6805] Alfalfa_QWORD: 47068 46856 46821 46769 46826| 46769 [ 6943] CRC-32: 48390 48567 48308 48455 48384| 48308 [ 6891] Hanson: 49502 49056 51782 49218 49086| 49056 [ 19602] x65599: 53044 52725 52186 52662 53162| 52186 [ 6859] Alfalfa: 52692 54632 52351 52843 53162| 52351 [ 6943] Paul Larson: 53416 53142 53042 53284 53105| 53042 [ 6889] x17 unrolled: 54363 55323 54236 53174 54043| 53174 [ 6827] Alfalfa_HALF: 53612 53644 54059 54002 53651| 53612 [ 6821] Alfalfa_DWORD: 56570 57225 56451 56436 56435| 56435 [ 6943] FNV-1a: 61159 60467 60788 61494 61147| 60467 [ 6840] Sedgewick: 64141 62589 62291 62568 62991| 62291 [ 6858] K&R: 62933 63106 63761 63100 62636| 62636 [ 6785] Bernstein: 63216 63509 63090 66182 63569| 63090 [ 6858] MaPrime2c: 64022 65335 64039 64150 64417| 64022 [ 6950] Ramakrishna: 68451 67807 67843 68301 68386| 67807 [ 6943] Arash Partow: 75566 75175 74999 76481 74804| 74804 [ 6845] One At Time: 75570 75783 75724 75800 75674| 75570 [ 6937] Weinberger: 102197 101468 102603 101799 101268| 101268 [ 6871] D:\_KAZE_new-stuff\_KAZE_hash_test_r2\RESULTS_Intel T3400 Merom 2.16GHz>type "Word-list_00,351,114_SPEED.txt" 1048576 elements in the table (20 bits) 351114 lines read FNV1A_Jesteress: 239116 235346 236105 234909 234314| 234314 [ 52684] FNV1A_Jester: 235584 234335 234656 234808 234609| 234335 [ 52966] Alfalfa_Rollick: 240834 239176 240338 240299 240409| 239176 [ 52745] FNV1A_Whiz: 242844 239326 240815 241118 241192| 239326 [ 52966] FNV1A_Nefertiti: 244244 244856 243113 244750 243112| 243112 [ 52963] Novak unrolled: 244057 246934 245676 245806 244807| 244057 [ 70274] Alfalfa: 245630 246742 246417 246982 247122| 245630 [ 52594] Alfalfa_HALF: 246352 247257 246303 246377 245644| 245644 [ 52454] x17 unrolled: 246652 247410 246674 247108 247217| 246652 [ 53556] Alfalfa_DWORD: 248847 248083 247920 247774 247868| 247774 [ 52594] FNV1A_Peregrine: 250085 248014 249674 248899 248649| 248014 [ 52551] FNV1A_Smaragd: 248663 250166 249862 250336 249470| 248663 [ 52774] x65599: 251510 251392 251580 249383 250356| 249383 [ 52988] Alfalfa_QWORD: 249873 251327 250378 250879 249846| 249846 [ 52594] Sixtinsensitive+: 250431 250256 252404 249972 251453| 249972 [ 53040] K&R: 250168 250038 252611 251467 252740| 250038 [ 52642] Paul Larson: 252305 250515 252618 250781 251188| 250515 [ 52970] Bernstein: 255017 255402 255621 252200 255308| 252200 [ 52770] Murmur2: 254937 256251 254517 255447 254914| 254517 [ 52738] CRC-32: 258265 256258 255603 257567 256863| 255603 [ 52931] Sedgewick: 256001 256871 256160 257127 256278| 256001 [ 52920] SBox: 258236 256909 258268 256889 258320| 256889 [ 52688] Sixtinsensitive: 257134 259147 257767 257206 257418| 257134 [ 53081] Arash Partow: 261122 259555 258834 259786 260518| 258834 [ 52887] Ramakrishna: 260665 259010 259497 259126 261294| 259010 [ 52764] Paul Hsieh: 262324 263039 261786 262498 262633| 261786 [ 52729] Hanson: 262136 261858 262746 262155 262766| 261858 [ 57741] FNV-1a: 265027 264232 264991 263359 264623| 263359 [ 52829] lookup3: 264398 267262 265065 266661 264868| 264398 [ 52868] One At Time: 270940 271333 271857 274386 271253| 270940 [ 52836] MaPrime2c: 271199 271568 272217 272391 271783| 271199 [ 52435] Fletcher: 344244 346631 346072 344561 347241| 344244 [ 182747] Weinberger: 350983 347458 348913 346681 347302| 346681 [ 103386] D:\_KAZE_new-stuff\_KAZE_hash_test_r2\RESULTS_Intel T3400 Merom 2.16GHz>type "Word-list_22,202,980_SPEED.txt" 67108864 elements in the table (26 bits) 22202980 lines read x17 unrolled: 21249035 21206631 21225111 21208785 21220774| 21206631 [ 3830652] Alfalfa_Rollick: 21615385 21617118 21616851 21674488 21624008| 21615385 [ 3408920] Alfalfa_HALF: 21680802 21661839 21664990 21664895 21682954| 21661839 [ 3286890] K&R: 21980308 21977842 21978965 21970740 22005011| 21970740 [ 3290941] Alfalfa: 22048183 22073010 22063800 22066487 22120184| 22048183 [ 3288684] Alfalfa_DWORD: 22143918 22113485 22088269 22088822 22102205| 22088269 [ 3288684] Bernstein: 22267261 22267646 22256414 22317934 22268982| 22256414 [ 3290766] Alfalfa_QWORD: 22323732 22313971 22369480 22311173 22302576| 22302576 [ 3288684] Paul Larson: 22486254 22474359 22510759 22548480 22520904| 22474359 [ 3296692] Ramakrishna: 22704194 22721725 22767194 22714304 22726127| 22704194 [ 3321824] x65599: 23132312 23232278 23148615 23149715 23163821| 23132312 [ 3325064] FNV1A_Jester: 23186241 23234970 23212485 23175789 23187444| 23175789 [ 3369088] FNV1A_Jesteress: 24316322 23255583 23231444 23238060 23247834| 23231444 [ 3355676] FNV1A_Nefertiti: 23385856 23351235 23391253 23364136 23385342| 23351235 [ 3505371] Arash Partow: 23505829 23431813 23440854 23450457 23443500| 23431813 [ 3325683] Sedgewick: 23501821 23501463 23539971 23484549 23499059| 23484549 [ 3302263] FNV1A_Whiz: 23690695 23749482 23716266 23682663 23809154| 23682663 [ 3369088] Sixtinsensitive+: 23931012 23926230 23916959 23900365 23899991| 23899991 [ 3507772] Sixtinsensitive: 24018004 24057311 24054986 24044285 24031933| 24018004 [ 3373923] FNV1A_Smaragd: 24371846 24361565 24405802 24377296 24363265| 24361565 [ 3298433] FNV1A_Peregrine: 24445929 24444872 24411645 24489012 24415484| 24411645 [ 3333193] CRC-32: 24734870 24794646 24752787 24770516 24738277| 24734870 [ 3298998] Murmur2: 24798875 24751929 24804091 24779290 24785946| 24751929 [ 3297709] SBox: 24923474 24905714 24898059 24907650 24913870| 24898059 [ 3298021] Hanson: 25021300 25028283 25049037 25031170 25015120| 25015120 [ 3408497] FNV-1a: 25176133 25114986 25117029 25130784 25109270| 25109270 [ 3297552] lookup3: 25469807 25442736 25452416 25422856 25448586| 25422856 [ 3299369] Paul Hsieh: 25542234 25535331 25541912 25531972 25586097| 25531972 [ 3498543] MaPrime2c: 25906415 25840954 25837950 25837082 25830890| 25830890 [ 3299747] One At Time: 25980864 25969227 25954711 25976036 26034474| 25954711 [ 3304908] Weinberger: 27414912 27410857 27434902 27446566 27416657| 27410857 [ 5732660] Fletcher: 60986313 61178347 61077840 61239577 61120952| 60986313 [14915258] Novak unrolled: 76541241 76611343 76544725 76622086 76618699| 76541241 [10591108] D:\_KAZE_new-stuff\_KAZE_hash_test_r2\RESULTS_Intel T3400 Merom 2.16GHz>
At this address is the PDF booklet of my 13 C functions compiled with VS2010 and with corresponding 32bit assembly instructions: http://www.sanmayce.com/Downloads/Ha...13-HASHERS.pdf
Results 1 to 14 of 14
-
14th November 2010, 18:17 #1Member
- Join Date
- Apr 2010
- Location
- Sofia
- Posts
- 57
- Thanks
- 0
- Thanked 0 Times in 0 Posts
Fastest non-secure hash function!?
Last edited by Sanmayce; 19th November 2010 at 18:12. Reason: stings -> strings
-
14th November 2010, 18:48 #2Member
- Join Date
- Jun 2009
- Location
- Kraków, Poland
- Posts
- 1,505
- Thanks
- 26
- Thanked 136 Times in 104 Posts
If speed is the only concern, why not just use hash that's equal to first byte of data? It will be fastest hash on the planet, albeit non very useful.
Every popular hash function is designed with speed with mind, but also has to meet some other requirements.
-
14th November 2010, 18:59 #3Member
- Join Date
- Apr 2010
- Location
- Sofia
- Posts
- 57
- Thanks
- 0
- Thanked 0 Times in 0 Posts
Hi Piotr,
this test covers some useful datasets as wordlists with small/medium/big/huge sizes:
Note: Each column represents the execution time, then the number of collisions in square brackets. Execution time is expressed in thousands of clock cycles (a lower number is better).Code:262144 elements in the table (18 bits) 105982 lines read FNV1A_Jesteress: 51454 50471 50418 53355 50367| 50367 [ 18664] FNV1A_Peregrine: 53656 53210 53603 55065 54025| 53210 [ 18711] Sedgewick: 55486 56074 57137 56477 56582| 55486 [ 18720] Alfalfa_HALF: 53822 53984 54677 54690 54069| 53822 [ 18735] Bernstein: 56443 56733 58799 57237 56259| 56259 [ 18738] lookup3: 57441 58139 58464 61091 58223| 57441 [ 18739] FNV-1a: 58446 59430 58133 59491 58996| 58133 [ 18743] Arash Partow: 58142 57884 57872 57560 57437| 57437 [ 18750] FNV1A_Smaragd: 54910 53298 54432 54515 53611| 53298 [ 18755] Murmur2: 56192 56018 55883 56564 54986| 54986 [ 18762] MaPrime2c: 60231 60354 60452 59833 59975| 59833 [ 18763] FNV1A_Whiz: 51100 51437 52435 54874 51726| 51100 [ 18774] FNV1A_Jester: 50537 50838 50329 50512 50450| 50329 [ 18774] Sixtinsensitive: 55585 55811 58898 55086 55786| 55086 [ 18775] Sixtinsensitive+: 55392 54357 53470 54975 54325| 53470 [ 18799] One At Time: 61651 59952 60587 60972 61006| 59952 [ 18821] CRC-32: 56549 55682 56374 56208 55610| 55610 [ 18834] x65599: 54861 55218 54569 55047 53969| 53969 [ 18849] Alfalfa_Rollick: 52416 52991 52787 52673 52792| 52416 [ 18864] Ramakrishna: 56635 58073 57641 57131 56984| 56635 [ 18871] Paul Larson: 54817 55605 54756 55573 55528| 54756 [ 18872] Alfalfa: 53419 53416 54233 53383 53848| 53383 [ 18882] Alfalfa_QWORD: 54904 55606 55665 55285 55793| 54904 [ 18882] Alfalfa_DWORD: 54074 55020 56644 54370 54635| 54074 [ 18882] Paul Hsieh: 58044 58488 58015 57568 60210| 57568 [ 18893] K&R: 55898 56619 55887 56020 55156| 55156 [ 18921] x17 unrolled: 54344 57026 54141 53987 54133| 53987 [ 19017] FNV1A_Nefertiti: 52852 52929 52974 53223 52921| 52852 [ 19042] SBox: 55735 55658 55416 55700 56066| 55416 [ 19068] Hanson: 56465 57670 56059 56261 56408| 56059 [ 20733] Novak unrolled: 52475 52383 51580 52641 55187| 51580 [ 21190] Weinberger: 66494 66242 65898 65054 68887| 65054 [ 22917] Fletcher: 68003 73460 68448 68363 69208| 68003 [ 63426]
-
15th November 2010, 03:49 #4Member
- Join Date
- Jun 2009
- Location
- Kraków, Poland
- Posts
- 1,505
- Thanks
- 26
- Thanked 136 Times in 104 Posts
Computing hashes in those miniprograms is performed in isolated tight loop. Results aren't significantly interesting as usually hashing is done on the fly in compression algorithms. Because of that, gains from special registers allocation and other tricks vanishes and for most hashes the difference in speed is even smaller than in those tight loops you've tested.
One common use of hashes is to compute address in small array. Little differences in hash calculation speed are then insignificant as hash collisions and therefore accessing additional memory cells causes delays multiple times longer than time spent on hashing.
-
15th November 2010, 18:43 #5Member
- Join Date
- Apr 2010
- Location
- Sofia
- Posts
- 57
- Thanks
- 0
- Thanked 0 Times in 0 Posts
In my view the real boost comes(speaking of my FNV1A derivates) not from 'special registers allocation and other tricks' but from the bigger stride, namely 4bytes(FNV1A_Whiz), 4+2bytes(Sixtinsensitive) and 4+4bytes(FNV1A_Jesteress) which solely is due to the intricate strength of FNV1A.
I have some experience with collision managing and you are right, and what I can share/repeat is that the hash must be as quick as possible: regarding collisions the further processing whether it will be with linked-lists/binary-search-trees/b-trees or another hash is a different thing.
-
16th November 2010, 17:44 #6Member
- Join Date
- Apr 2010
- Location
- Sofia
- Posts
- 57
- Thanks
- 0
- Thanked 0 Times in 0 Posts
I am not interested in hashing keys longer than 1KB, so I commented the align part(borrowed from Igor Pavlov's function) which boosts even more the results below, but I do not need it because it causes a slight delay for short keys.
Note: Caution, the align fragment is intended for benchmarking only, uncommented it doesn't make sense since the hash value(stamp) varies for a given key!
The following test is attached at the bottom:Code:#define ROL(x, n) (((x) << (n)) | ((x) >> (32-(n)))) UINT FNV1A_Hash_Jesteress(const char *str, SIZE_T wrdlen) { const UINT PRIME = 709607; UINT hash32 = 2166136261; const char *p = str; // Idea comes from Igor Pavlov's 7zCRC, thanks. /* for(; wrdlen && ((unsigned)(ptrdiff_t)p&3); wrdlen -= 1, p++) { hash32 = (hash32 ^ *p) * PRIME; } */ for(; wrdlen >= 2*sizeof(DWORD); wrdlen -= 2*sizeof(DWORD), p += 2*sizeof(DWORD)) { hash32 = (hash32 ^ (ROL(*(DWORD *)p,5)^*(DWORD *)(p+4))) * PRIME; } // Cases: 0,1,2,3,4,5,6,7 if (wrdlen & sizeof(DWORD)) { hash32 = (hash32 ^ *(DWORD*)p) * PRIME; p += sizeof(DWORD); } if (wrdlen & sizeof(WORD)) { hash32 = (hash32 ^ *(WORD*)p) * PRIME; p += sizeof(WORD); } if (wrdlen & 1) hash32 = (hash32 ^ *p) * PRIME; return hash32 ^ (hash32 >> 16); }
As you can see from the results above: FNV1A_Jesteress is (778966-236095)/236095*100%=229% faster on 100MB chunk than CRC-32.Code:D:\_KAZE_new-stuff\_KAZE_hash_test_r2_100MB_at-once>dir Volume in drive D is H320_Vol5 Volume Serial Number is 0CB3-C881 Directory of D:\_KAZE_new-stuff\_KAZE_hash_test_r2_100MB_at-once 11/16/2010 03:26 PM <DIR> . 11/16/2010 03:26 PM <DIR> .. 11/16/2010 03:19 PM 104,857,601 100MBSPC.TXT 11/14/2010 02:39 PM 205,535 hash.cod 11/14/2010 02:39 PM 87,040 hash.exe 3 File(s) 105,150,176 bytes 2 Dir(s) 3,267,072,000 bytes free D:\_KAZE_new-stuff\_KAZE_hash_test_r2_100MB_at-once>hash 100MBSPC.TXT 1 lines read 4 elements in the table (2 bits) FNV1A_Jesteress: 237526 237369 236795 236095 237679| 236095 [ 0] FNV1A_Jester: 329767 330673 335947 329273 329952| 329273 [ 0] FNV1A_Smaragd: 592131 593145 600649 591819 592306| 591819 [ 0] FNV1A_Peregrine: 331617 331534 328969 334234 331522| 328969 [ 0] FNV1A_Whiz: 358981 360225 360502 361018 360666| 358981 [ 0] FNV1A_Nefertiti: 329341 330565 325612 326325 325964| 325612 [ 0] FNV-1a: 1159569 1157257 1157705 1157358 1156076| 1156076 [ 0] Sixtinsensitive+: 435560 437613 437057 434710 437152| 434710 [ 0] Sixtinsensitive: 534244 529052 534235 535813 532814| 529052 [ 0] Alfalfa_Rollick: 567182 566461 566263 567908 565027| 565027 [ 0] Alfalfa: 946159 946514 948073 948392 944457| 944457 [ 0] Alfalfa_HALF: 958551 958575 958369 958685 956776| 956776 [ 0] Alfalfa_DWORD: 1005795 1006734 1002083 1006510 1002914| 1002083 [ 0] Alfalfa_QWORD: 690093 690150 686998 690425 688936| 686998 [ 0] Bernstein: 1180226 1179028 1177361 1178756 1181853| 1177361 [ 0] K&R: 1181315 1182776 1185574 1183979 1183832| 1181315 [ 0] x17 unrolled: 967813 967329 970614 969144 969328| 967329 [ 0] x65599: 960246 966067 961713 964114 964742| 960246 [ 0] Sedgewick: 1279680 1281512 1281650 1282046 1285642| 1279680 [ 0] Weinberger: 1953078 1950771 1954538 1951673 1953309| 1950771 [ 0] Paul Larson: 964091 962247 965761 963918 961798| 961798 [ 0] Paul Hsieh: 586475 587879 589487 589068 588834| 586475 [ 0] One At Time: 1462398 1464074 1462547 1462450 1463394| 1462398 [ 0] lookup3: 570869 569553 569667 569491 570939| 569491 [ 0] Arash Partow: 1521036 1521087 1519311 1517902 1517504| 1517504 [ 0] CRC-32: 783545 778966 780100 782275 781055| 778966 [ 0] Ramakrishna: 1338637 1339530 1341250 1339241 1340524| 1338637 [ 0] Fletcher: 307873 309266 308688 309616 308991| 307873 [ 0] Murmur2: 350287 349273 351056 350930 350501| 349273 [ 0] Hanson: 521932 520819 521185 521015 522284| 520819 [ 0] Novak unrolled: 525810 524852 526112 524837 523953| 523953 [ 0] SBox: 526267 525468 525472 524999 525415| 524999 [ 0] MaPrime2c: 1220753 1220362 1220924 1220981 1221015| 1220362 [ 0] D:\_KAZE_new-stuff\_KAZE_hash_test_r2_100MB_at-once>Last edited by Sanmayce; 18th November 2010 at 19:05. Reason: Added a note
-
16th November 2010, 18:55 #7Member
- Join Date
- Feb 2010
- Location
- Nordic
- Posts
- 200
- Thanks
- 41
- Thanked 36 Times in 12 Posts
I guess speed is important, but in a compression context I would think the two extremes - low collisions for similar data, or similar hashing for similar data - would be as critical as the speed? Some hashtables and ROLZ histories used in compressors store a hash of some fixed-length (e.g. minimum match length) in 'spare' bits of padding that helps align records - perhaps only 2, 3, or 5 bits; not a lot, but maybe helps avoid dereferencing unnecessarily some of the time....
-
16th November 2010, 19:10 #8Member
- Join Date
- Apr 2010
- Location
- Sofia
- Posts
- 57
- Thanks
- 0
- Thanked 0 Times in 0 Posts
Hi Willvarfar,
the speed is everything for me, as to distribution if you take my word you don't have to worry.
-
18th November 2010, 19:29 #9Member
- Join Date
- Apr 2010
- Location
- Sofia
- Posts
- 57
- Thanks
- 0
- Thanked 0 Times in 0 Posts
Let us see the results instead:
Collisions(sorted in ascending order) Table:
No code has to be inserted here.
Obviously CRC-32 has some collision advantage, which in my opinion vanishes when a translation down to 16- bit table is done.
For visiting home of FNV-1A and to read what path I had to traverse to reach the FNV1A_Jesteress: posts #22184, #22195, #22219.
FNV1A_Hash_Jesteress C & assembly code:
Being diabolically smart and the king's most-trusted mentor jester was the KING-IN-SHADOW.Code:?FNV1A_Hash_Jesteress@@YAIPBDK@Z PROC ; FNV1A_Hash_Jesteress ; 1006 : const UINT PRIME = 709607; ; 1007 : UINT hash32 = 2166136261; ; 1008 : const char *p = str; ; 1009 : ; 1010 : // Idea comes from Igor Pavlov's 7zCRC, thanks. ; 1011 : /* ; 1012 : for(; wrdlen && ((unsigned)(ptrdiff_t)p&3); wrdlen -= 1, p++) { ; 1013 : hash32 = (hash32 ^ *p) * PRIME; ; 1014 : } ; 1015 : */ ; 1016 : for(; wrdlen >= 2*sizeof(DWORD); wrdlen -= 2*sizeof(DWORD), p += 2*sizeof(DWORD)) { 004a0 8b 54 24 08 mov edx, DWORD PTR _wrdlen$[esp-4] 004a4 8b 44 24 04 mov eax, DWORD PTR _str$[esp-4] 004a8 56 push esi 004a9 b9 c5 9d 1c 81 mov ecx, -2128831035 ; 811c9dc5H 004ae 83 fa 08 cmp edx, 8 004b1 72 2b jb SHORT $LN4@FNV1A_Hash 004b3 8b f2 mov esi, edx 004b5 c1 ee 03 shr esi, 3 004b8 57 push edi 004b9 8d a4 24 00 00 00 00 npad 7 $LL6@FNV1A_Hash: ; 1017 : hash32 = (hash32 ^ (ROL(*(DWORD *)p,5)^*(DWORD *)(p+4))) * PRIME; 004c0 8b 38 mov edi, DWORD PTR [eax] 004c2 c1 c7 05 rol edi, 5 004c5 33 78 04 xor edi, DWORD PTR [eax+4] 004c8 83 ea 08 sub edx, 8 004cb 33 f9 xor edi, ecx 004cd 69 ff e7 d3 0a 00 imul edi, 709607 ; 000ad3e7H 004d3 83 c0 08 add eax, 8 004d6 83 ee 01 sub esi, 1 004d9 8b cf mov ecx, edi 004db 75 e3 jne SHORT $LL6@FNV1A_Hash 004dd 5f pop edi $LN4@FNV1A_Hash: ; 1018 : } ; 1019 : // Cases: 0,1,2,3,4,5,6,7 ; 1020 : if (wrdlen & sizeof(DWORD)) { 004de f6 c2 04 test dl, 4 004e1 74 0f je SHORT $LN3@FNV1A_Hash ; 1021 : hash32 = (hash32 ^ *(DWORD*)p) * PRIME; 004e3 8b 30 mov esi, DWORD PTR [eax] 004e5 33 f1 xor esi, ecx 004e7 69 f6 e7 d3 0a 00 imul esi, 709607 ; 000ad3e7H 004ed 8b ce mov ecx, esi ; 1022 : p += sizeof(DWORD); 004ef 83 c0 04 add eax, 4 $LN3@FNV1A_Hash: ; 1023 : } ; 1024 : if (wrdlen & sizeof(WORD)) { 004f2 f6 c2 02 test dl, 2 004f5 74 10 je SHORT $LN2@FNV1A_Hash ; 1025 : hash32 = (hash32 ^ *(WORD*)p) * PRIME; 004f7 0f b7 30 movzx esi, WORD PTR [eax] 004fa 33 f1 xor esi, ecx 004fc 69 f6 e7 d3 0a 00 imul esi, 709607 ; 000ad3e7H 00502 8b ce mov ecx, esi ; 1026 : p += sizeof(WORD); 00504 83 c0 02 add eax, 2 $LN2@FNV1A_Hash: 00507 5e pop esi ; 1027 : } ; 1028 : if (wrdlen & 1) 00508 f6 c2 01 test dl, 1 0050b 74 0d je SHORT $LN1@FNV1A_Hash ; 1029 : hash32 = (hash32 ^ *p) * PRIME; 0050d 0f be 00 movsx eax, BYTE PTR [eax] 00510 33 c1 xor eax, ecx 00512 69 c0 e7 d3 0a 00 imul eax, 709607 ; 000ad3e7H 00518 8b c8 mov ecx, eax $LN1@FNV1A_Hash: ; 1030 : ; 1031 : return hash32 ^ (hash32 >> 16); 0051a 8b c1 mov eax, ecx 0051c c1 e8 10 shr eax, 16 ; 00000010H 0051f 33 c1 xor eax, ecx ; 1032 : } 00521 c3 ret 0 ?FNV1A_Hash_Jesteress@@YAIPBDK@Z ENDP ; FNV1A_Hash_Jesteress
I think FNV1A_Jesteress breaks a medieval rule(regarding the [she-]jester appearance): outward ugly inward hi-spi i.e. high spirited, that is: she has got a bi-beauty having both dynamism and wit.
Sometimes I wonder whether a single Jesteress existed at all.Last edited by Sanmayce; 19th November 2010 at 18:54. Reason: Tabulated source
-
19th November 2010, 10:28 #10Programmer
- Join Date
- Mar 2007
- Location
- Uzbekistan
- Posts
- 4,593
- Thanks
- 802
- Thanked 698 Times in 378 Posts
-
19th November 2010, 11:47 #11Member
- Join Date
- Feb 2010
- Location
- Nordic
- Posts
- 200
- Thanks
- 41
- Thanked 36 Times in 12 Posts
Only tangentially related, but a good read: http://cbloomrants.blogspot.com/2010...0-adler32.html
-
19th November 2010, 18:08 #12Member
- Join Date
- Apr 2010
- Location
- Sofia
- Posts
- 57
- Thanks
- 0
- Thanked 0 Times in 0 Posts
Thanks Bulat,
again I didn't make enough research.
Update November 4, 2010 - MurmurHash3 has been released in beta form here - http://code.google.com/p/smhasher/ - (I reserve the right to tweak the constants after people have had a chance to bang on it). Murmur3 has better performance than MurmurHash2, no repetition flaw, comes in 32/64/128-bit versions for both x86 and x64 platforms, and the 128-bit x64 version is blazing fast - over 5 gigabytes per second on my 3 gigahertz Core 2.
Extremely simple - compiles down to ~52 instructions on x86.
Wow, 5GB sounds like SMASH i.e. to be the dominator. I will ask Mr. Appleby to include FNV1A_Jesteress and test it on his testbed ...
-
19th November 2010, 23:14 #13Member
- Join Date
- Sep 2010
- Location
- US
- Posts
- 126
- Thanks
- 4
- Thanked 69 Times in 29 Posts
.. eh yeah ..
Back here :
http://cbloomrants.blogspot.com/2008/10/10-19-08-2.html
you'll see I found the same thing -
for hashing short strings in a hash table with probing for collisions , FNV hash results in the best total time for hash computation + lookup.
I'm trying to make a very specific statement there. That does not mean that FNV is the best hash in other usage scenarios. For example Adler and Fletcher are checksums which are designed to detect single bit flips, not for hash table lookups.
Murmur is an excellent hash but unfortunately relying on large multiplies for speed is not cross-platform compatible.Last edited by cbloom; 3rd August 2016 at 21:43.
-
20th November 2010, 20:54 #14Member
- Join Date
- Apr 2010
- Location
- Sofia
- Posts
- 57
- Thanks
- 0
- Thanked 0 Times in 0 Posts
Thanks for clearing up the subject Mr. Bloom:
http://cbloomrants.blogspot.com/2010...he-tables.html
Also I wrote/proposed to Mr. Appleby to add FNV1A_Jesteress to his testbed.
Reply With Quote
Similar Threads
-
Fastest decompressor!?
By Sanmayce in forum Data CompressionReplies: 66Last Post: 13th April 2011, 02:18 -
Hash Zip
By Black_Fox1 in forum Forum ArchiveReplies: 6Last Post: 4th March 2007, 18:12 -
Fastest Compressors
By LovePimple in forum Forum ArchiveReplies: 0Last Post: 1st November 2006, 06:36
