Results 1 to 14 of 14

Thread: Fastest non-secure hash function!?

  1. #1
    Member Sanmayce's Avatar
    Join Date
    Apr 2010
    Location
    Sofia
    Posts
    57
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Fastest non-secure hash function!?

    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:

    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>
    There is some inconsistency(I still cannot understand what causes it) in speed tests, though.
    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
    Last edited by Sanmayce; 19th November 2010 at 18:12. Reason: stings -> strings

  2. #2
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 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.

  3. #3
    Member Sanmayce's Avatar
    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:

    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]
    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).

  4. #4
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 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.

  5. #5
    Member Sanmayce's Avatar
    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.

  6. #6
    Member Sanmayce's Avatar
    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!

    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);
    }
    The following test is attached at the bottom:

    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>
    As you can see from the results above: FNV1A_Jesteress is (778966-236095)/236095*100%=229% faster on 100MB chunk than CRC-32.
    Attached Files Attached Files
    Last edited by Sanmayce; 18th November 2010 at 19:05. Reason: Added a note

  7. #7
    Member
    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....

  8. #8
    Member Sanmayce's Avatar
    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.

  9. #9
    Member Sanmayce's Avatar
    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:
    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
    Being diabolically smart and the king's most-trusted mentor jester was the KING-IN-SHADOW.
    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

  10. #10
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts

  11. #11
    Member
    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

  12. #12
    Member Sanmayce's Avatar
    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 ...

  13. #13
    Member
    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.

  14. #14
    Member Sanmayce's Avatar
    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.

Similar Threads

  1. Fastest decompressor!?
    By Sanmayce in forum Data Compression
    Replies: 66
    Last Post: 13th April 2011, 02:18
  2. Hash Zip
    By Black_Fox1 in forum Forum Archive
    Replies: 6
    Last Post: 4th March 2007, 18:12
  3. Fastest Compressors
    By LovePimple in forum Forum Archive
    Replies: 0
    Last Post: 1st November 2006, 06:36

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •