Efficacité d'un algorithme de hachage de chaînes de caractères - Page 5

Test fait

Sur le fichier megamix.txt, la fonction modulo 257 telle qu'elle est au post ./120 est moins bonne que la fonction modulo 256 :

Variance pour hach_wkp_pollux : 60
Variane pour hash_toutcon : 62
Variance pour hach_wkp_pollux_257 : 63

Oui mais c'est presque normal, tu le fait que des mots cours donc le nombre de collision est moindre

Oui mais c'est presque normal, tu le fait que sur des mots courts

... sur des mots réels qu'on manipulera en pratique avec l'algo quoi

oui mais, ce genre d'algo n'est pas fait que pout manipuler des mots, on peut tout a fait utiliser des phrases ou des groupes de mots. Mais bon comme dit plus haut, il faut choisir la methode la plus efficace pour le besoin qu'on a ^^

Thibaut (./121) :
Test fait

Sur le fichier megamix.txt, la fonction modulo 257 telle qu'elle est au post ./120 est moins bonne que la fonction modulo 256 :

Variance pour hach_wkp_pollux : 60
Variane pour hash_toutcon : 62
Variance pour hach_wkp_pollux_257 : 63

j'ai regardé ton code et tu stockes la moyenne dans un entier, donc c'est normal d'avoir des résultats anormalement élevés : en modifiant le code pour passer par un double on obtient une variance sensiblement équivalente à la moyenne (26), donc tous les hash dont on parle sont équivalents à des hash idéaux sur ton fichier de test donc autant pas se prendre la tête et prendre hash_toutcon si ton but est de l'utiliser sur ce genre de fichier-là ^^
(et tu peux aussi simuler une fonction de hash idéale en renvoyant rand()%256 pour vérifier )

Quelle erreur idiote !

Comme quoi, à plusieurs on finit toujours par venir à bout des choses les plus étranges

Thibaut (./120) :
(je pose la question car j'avoue que je n'ai pas compris ton optimisation, pour moi la raison qui fait que l'algo de départ et ta version optimisée sont équivalentes reste obscure)

c'est parce que 33 = 1 + 2^5, donc d'après la formule du binôme de newton 33^n = 1 + n*2^5 + n*(n-1)/2*2^10 + ... = 1 + n*2^5 mod 2^10, et puis le reste découle du fait qu'on calcule hash = sum(string[i]*33^(n-i)) ^^

En effet, ça change tout !

_pollux_257 28,1

Voici les variances :hach_wkp_pollux          25,2
hash_toutcon             27,4
hach_wkp

Moyenne : 26,7.

La fonction toute conne est plus proche de la moyenne que la fonction DJB

Source : topics/103443-efficacite-dun-algorithme-de-hachage-de-chaines-de-caracteres#0

Thibaut (./128) :
La fonction toute conne est plus proche de la moyenne que la fonction DJB

l'écart-type des variances () est censé être de 26.7/16 = 1.7, donc on ne peut absolument rien conclure ^^

Toujours là pour chipoter !

Sinon encore merci pour avoir trouvé l'origine des variances énormes. C'était pas forcément évident, d'ailleurs aucun de nous n'y avait fait gaffe depuis le début Ca ne change pas le classement mais ça rassure : les fonctions sont très bonnes.

La conclusion te semble correcte ? topics/103443-efficacite-dun-algorithme-de-hachage-de-chaines-de-caracteres#0

On pourra compléter cette conclusion si on fait d'autres tests.

Je viens de rajouter un bench vitesse :

mtrapier@prod500 ~/Desktop/test $ make && ./GPHFATest 
cc -std=c99 -pedantic -Wall -o GPHFATest GPHFATest.c GeneralHashFunctions.o
--------------------------------------------------------------------------------
Speed test with 10000000 loop
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          252473028       255787564       3.31    3017013.54
 1      PJWHash         255787625       260715030       4.93    2029465.81
 2      ELFHash         260715124       266130561       5.42    1846573.05
 3      BKDRHash        266130660       269310539       3.18    3144773.75
 4      SDBMHash        269310626       272172184       2.86    3494599.79
 5      DJBHash         272172223       274582796       2.41    4148391.27
 6      DEKHash         274582868       276952781       2.37    4219564.18
 7      BPHash          276952820       279312673       2.36    4237552.08
 8      FNVHash         279312761       282890292       3.58    2795223.86
 9      APHash          282890370       286404914       3.51    2845319.34
10      StpdHash        286405011       288797336       2.39    4180034.07
11      ThibHash        288797426       290852921       2.06    4865008.19
mtrapier@prod500 ~/Desktop/test $ make && ./GPHFATest 
make: Rien à faire pour « all ».
--------------------------------------------------------------------------------
Speed test with 10000000 loop
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          294256136       297539010       3.28    3046111.43
 1      PJWHash         297539106       302442713       4.90    2039315.14
 2      ELFHash         302442749       307792876       5.35    1869114.51
 3      BKDRHash        307792914       310943942       3.15    3173567.48
 4      SDBMHash        310943979       313771009       2.83    3537281.17
 5      DJBHash         313771046       316175117       2.40    4159610.93
 6      DEKHash         316175155       318531509       2.36    4243844.52
 7      BPHash          318531546       320884391       2.35    4250173.73
 8      FNVHash         320884426       324475608       3.59    2784598.50
 9      APHash          324475645       327948631       3.47    2879366.63
10      StpdHash        327948667       330323512       2.37    4210801.13
11      ThibHash        330323548       332360510       2.04    4909271.75

Ta fonction a au moins un avantage, c'est la plus rapide (STM = StartTime en µSec, ETM = EndTime en µSec, EXT = Execution Time en S et HPS = Hash Par Seconde)

C'est curieux parceque hash_toucon fait moins d'opérations à priori que hash_thib, qui d'ailleurs nécessite le passage d'un paramètre supplémentaire

C'est peut-être parceque la boucle de hash_toucon n'est pas déroulée, contrairement à la boucle de hash_thib. On aurait la preuve qu'une boucle déroulée peut largement compenser la lenteur d'une suite d'opérations plus grande ?

Pour DJBHash, tu as utilisé la fonction optimisée par Pollux qu'on trouve dans le nouveau hashtest.zip ?
Tiens, je veux bien que tu testes la rapidité de cette version :

int hach_wkp_pollux_deroul(const char *str, int length)
{
    unsigned int hash = 5381; // DJB Hash
    unsigned int hash5 = 0;
    const char  *s;
    int          i4;
    int          ir;


    s = str;
    i4= length / 4;
    ir= length % 4;

    while (i4-- > 0) {
        hash5+= hash;  hash+= *s++;
        hash5+= hash;  hash+= *s++;
        hash5+= hash;  hash+= *s++;
        hash5+= hash;  hash+= *s++;
    }

    while (ir-- > 0) {
        hash5+= hash;
        hash+= *s++;
    }

    return (hash + (hash5<<5)) % HASH_TABLE_SIZE;
}

J'ai l'impression qu'on peut accélérer encore plus. Si on peut se passer de hash5, on double la vitesse d'exécution.

---- grosse connerie dans ce message

non DJBHash c'est l'originale du soft

unsigned int DJBHash(char* str, unsigned int len)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = ((hash << 5) + hash) + (*str);
   }

   return hash;
}

(et tes fonctions, enfin le "con" je l'ai modifié car l'API passe en parametre la longueur)

Si tu as le temps je serais curieux de voir la vitesse de la version accélérée par Pollux. Elle doit être aussi, voir plus rapide, que le stupid hash (qui n'est pas si stupide que ça sur un modulo 256 d'ailleurs).

Alors PolD = Pollux Déroulé
Pol7 = PolluxHash
Sqly = Java Hash (ou K&R hash)


J'en ai oublié un je refait...

edit: voila j'avais oublié le hash de java (celui de K&R en réalitée)

mtrapier@prod500 ~/Desktop/test $ ./GPHFATest 
General Purpose Hash Function Algorithms Test
By Arash Partow - 2002
Moded by Manoel Trapier - 2007
Key:                          abcdefghijklmnopqrstuvwxyz1234567890
 1. RS-Hash Function Value:   4097835502
 2. JS-Hash Function Value:   1651003062
 3. PJW-Hash Function Value:  126631744
 4. ELF-Hash Function Value:  126631744
 5. BKDR-Hash Function Value: 3153586616
 6. SDBM-Hash Function Value: 3449571336
 7. DJB-Hash Function Value:  729241521
 8. DEK-Hash Function Value:  2923964919
 9. BP-Hash Function Value:   1726880944
10. FNV-Hash Function Value:  3243095106
11. AP-Hash Function Value:   3929913477
12. StpdHash Function Value:  3372
13. ThibHash Function Value:  178
14. PolDHash Function Value:  8285105
15. PolDHash Function Value:  8285105
16. SqlyHash Function Value:  2134697992
---------------------------------------------------------------------------------------------------
                                   HASH QUALITY TEST
---------------------------------------------------------------------------------------------------
***************************************************************************************************
***************************************************************************************************
   Definitions:

   LCL:     Longest chain length                          LCL_CNT: Count of buckets with longest chain length
   NZL:     Number of zero chaining buckets (aka empty bucket)             NC:      Number of chained buckets
   ACL:     Average chaining length                                  UP:      Usage percentange of hash-table
   AVG:     Ideal Average                                                                   VAR:     Variance
***************************************************************************************************
***************************************************************************************************
---------------------------------------------------------------------------------------------------
Table size : 42
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          196     1       0       42      42      095.24  100.00   95.24  6167.37
 1      PJWHash         133     1       0       42      42      095.24  100.00   95.24  145.04
 2      ELFHash         133     1       0       42      42      095.24  100.00   95.24  145.04
 3      BKDRHash        208     1       0       42      42      095.24  100.00   95.24  6336.32
 4      SDBMHash        181     1       0       42      42      095.24  100.00   95.24  6084.28
 5      DJBHash         206     1       0       42      42      095.24  100.00   95.24  6413.99
 6      DEKHash         108     1       0       42      42      095.24  100.00   95.24   40.37
 7      BPHash          104     2       0       42      42      095.24  100.00   95.24   34.85
 8      FNVHash         195     2       0       42      42      095.24  100.00   95.24  6176.51
 9      APHash          119     1       0       42      42      095.24  100.00   95.24  106.80
10      StpdHash        1800    1       32      10      9       400.00   23.81   95.24  132625.94
11      ThibHash        250     1       7       35      35      114.29   83.33   95.24  5400.94
12      Pol7Hash        253     1       0       42      42      095.24  100.00   95.24  6905.51
13      PolDHash        253     1       0       42      42      095.24  100.00   95.24  6905.51
14      SqlyHash        191     1       0       42      42      095.24  100.00   95.24  6114.94
---------------------------------------------------------------------------------------------------
Table size : 50
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          168     1       0       50      50      080.00  100.00   80.00  4370.04
 1      PJWHash         108     2       0       50      50      080.00  100.00   80.00  157.08
 2      ELFHash         108     2       0       50      50      080.00  100.00   80.00  157.08
 3      BKDRHash        164     2       0       50      50      080.00  100.00   80.00  4373.68
 4      SDBMHash        153     1       0       50      50      080.00  100.00   80.00  4298.16
 5      DJBHash         155     1       0       50      50      080.00  100.00   80.00  4298.64
 6      DEKHash         97      1       0       50      50      080.00  100.00   80.00   52.84
 7      BPHash          83      2       0       50      50      080.00  100.00   80.00    2.08
 8      FNVHash         175     1       0       50      50      080.00  100.00   80.00  4391.80
 9      APHash          104     1       0       50      50      080.00  100.00   80.00   72.16
10      StpdHash        1800    1       39      11      10      363.64   22.00   80.00  112611.88
11      ThibHash        375     2       18      32      32      125.00   64.00   80.00  9963.28
12      Pol7Hash        443     1       2       48      44      083.33   96.00   80.00  15631.60
13      PolDHash        443     1       2       48      44      083.33   96.00   80.00  15631.60
14      SqlyHash        159     1       0       50      50      080.00  100.00   80.00  4305.16
---------------------------------------------------------------------------------------------------
Table size : 100
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          147     2       0       100     100     040.00  100.00   40.00  2562.12
 1      PJWHash         81      1       0       100     100     040.00  100.00   40.00  165.08
 2      ELFHash         81      1       0       100     100     040.00  100.00   40.00  165.08
 3      BKDRHash        147     1       10      90      88      044.44   90.00   40.00  2711.82
 4      SDBMHash        137     2       1       99      87      040.40   99.00   40.00  2675.62
 5      DJBHash         153     1       27      73      61      054.79   73.00   40.00  3644.44
 6      DEKHash         61      1       0       100     100     040.00  100.00   40.00   93.20
 7      BPHash          50      2       0       100     100     040.00  100.00   40.00   64.80
 8      FNVHash         104     1       0       100     100     040.00  100.00   40.00  1149.90
 9      APHash          58      1       0       100     100     040.00  100.00   40.00   35.36
10      StpdHash        1800    1       89      11      10      363.64   11.00   40.00  57905.94
11      ThibHash        250     2       57      43      43      093.02   43.00   40.00  3944.78
12      Pol7Hash        441     1       33      67      54      059.70   67.00   40.00  9302.04
13      PolDHash        441     1       33      67      54      059.70   67.00   40.00  9302.04
14      SqlyHash        139     1       7       93      88      043.01   93.00   40.00  2674.98
---------------------------------------------------------------------------------------------------
Table size : 256
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          130     1       30      226     168     017.70   88.28   15.62  976.59
 1      PJWHash         41      1       120     136     130     029.41   53.12   15.62  305.64
 2      ELFHash         41      1       120     136     130     029.41   53.12   15.62  305.64
 3      BKDRHash        182     4       86      170     151     023.53   66.41   15.62  1780.05
 4      SDBMHash        1921    1       157     99      77      040.40   38.67   15.62  17090.00
 5      DJBHash         900     2       215     41      33      097.56   16.02   15.62  8468.13
 6      DEKHash         80      1       85      171     140     023.39   66.80   15.62  369.36
 7      BPHash          201     10      236     20      20      200.00    7.81   15.62  2880.94
 8      FNVHash         49      1       5       251     228     015.94   98.05   15.62  188.38
 9      APHash          27      1       0       256     256     015.62  100.00   15.62   15.41
10      StpdHash        1800    1       245     11      10      363.64    4.30   15.62  23000.37
11      ThibHash        180     1       198     58      57      068.97   22.66   15.62  1453.35
12      Pol7Hash        900     2       215     41      33      097.56   16.02   15.62  8468.13
13      PolDHash        900     2       215     41      33      097.56   16.02   15.62  8468.13
14      SqlyHash        961     2       88      168     120     023.81   65.62   15.62  8433.47
---------------------------------------------------------------------------------------------------
Table size : 257
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          32      1       0       257     257     015.56  100.00   15.56   22.28
 1      PJWHash         337     1       38      219     208     018.26   85.21   15.56  932.92
 2      ELFHash         337     1       38      219     208     018.26   85.21   15.56  932.92
 3      BKDRHash        26      4       0       257     257     015.56  100.00   15.56   22.49
 4      SDBMHash        29      2       0       257     257     015.56  100.00   15.56   30.99
 5      DJBHash         21      2       0       257     257     015.56  100.00   15.56    4.79
 6      DEKHash         36      1       0       257     257     015.56  100.00   15.56   44.89
 7      BPHash          55      4       58      199     182     020.10   77.43   15.56  251.81
 8      FNVHash         25      2       0       257     257     015.56  100.00   15.56   14.44
 9      APHash          27      2       0       257     257     015.56  100.00   15.56   17.00
10      StpdHash        1800    1       246     11      10      363.64    4.28   15.56  22911.82
11      ThibHash        180     1       199     58      57      068.97   22.57   15.56  1448.64
12      Pol7Hash        152     1       91      166     125     024.10   64.59   15.56  955.27
13      PolDHash        152     1       91      166     125     024.10   64.59   15.56  955.27
14      SqlyHash        23      3       0       257     257     015.56  100.00   15.56    8.81
---------------------------------------------------------------------------------------------------
Table size : 1000
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          29      3       265     735     447     005.44   73.50    4.00   56.03
 1      PJWHash         16      2       40      960     860     004.17   96.00    4.00    7.26
 2      ELFHash         16      2       40      960     860     004.17   96.00    4.00    7.26
 3      BKDRHash        65      2       392     608     374     006.58   60.80    4.00  119.47
 4      SDBMHash        31      1       343     657     426     006.09   65.70    4.00   59.98
 5      DJBHash         34      2       727     273     216     014.65   27.30    4.00   90.08
 6      DEKHash         13      3       25      975     877     004.10   97.50    4.00    5.32
 7      BPHash          16      2       266     734     686     005.45   73.40    4.00   13.09
 8      FNVHash         17      2       252     748     583     005.35   74.80    4.00   15.06
 9      APHash          11      3       22      978     897     004.09   97.80    4.00    3.80
10      StpdHash        1800    1       989     11      10      363.64    1.10    4.00  5934.59
11      ThibHash        180     1       942     58      57      068.97    5.80    4.00  418.56
12      Pol7Hash        148     1       827     173     126     023.12   17.30    4.00  304.43
13      PolDHash        148     1       827     173     126     023.12   17.30    4.00  304.43
14      SqlyHash        33      2       416     584     421     006.85   58.40    4.00   60.22
---------------------------------------------------------------------------------------------------
Table size : 1024
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          34      2       332     692     466     005.78   67.58    3.91   61.52
 1      PJWHash         13      1       516     508     502     007.87   49.61    3.91   20.63
 2      ELFHash         13      1       516     508     502     007.87   49.61    3.91   20.63
 3      BKDRHash        54      1       471     553     393     007.23   54.00    3.91  112.75
 4      SDBMHash        482     1       730     294     176     013.61   28.71    3.91  1068.23
 5      DJBHash         227     2       903     121     96      033.06   11.82    3.91  547.63
 6      DEKHash         40      1       721     303     236     013.20   29.59    3.91   81.78
 7      BPHash          81      10      944     80      80      050.00    7.81    3.91  203.51
 8      FNVHash         17      3       256     768     596     005.21   75.00    3.91   14.78
 9      APHash          11      1       7       1017    962     003.93   99.32    3.91    2.95
10      StpdHash        1800    1       1013    11      10      363.64    1.07    3.91  5795.87
11      ThibHash        180     1       966     58      57      068.97    5.66    3.91  409.11
12      Pol7Hash        227     2       903     121     96      033.06   11.82    3.91  547.63
13      PolDHash        227     2       903     121     96      033.06   11.82    3.91  547.63
14      SqlyHash        245     1       604     420     268     009.52   41.02    3.91  527.63
---------------------------------------------------------------------------------------------------
Table size : 5178
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          5       8       2700    2478    1131    001.61   47.86    0.77    0.94
 1      PJWHash         14      1       2469    2709    956     001.48   52.32    0.77    0.92
 2      ELFHash         14      1       2469    2709    956     001.48   52.32    0.77    0.92
 3      BKDRHash        6       1       2694    2484    1088    001.61   47.97    0.77    0.96
 4      SDBMHash        6       1       2855    2323    1079    001.72   44.86    0.77    1.12
 5      DJBHash         6       4       2851    2327    1121    001.72   44.94    0.77    1.10
 6      DEKHash         6       1       2350    2828    941     001.41   54.62    0.77    0.73
 7      BPHash          4       18      2154    3024    802     001.32   58.40    0.77    0.63
 8      FNVHash         7       1       2876    2302    1080    001.74   44.46    0.77    1.17
 9      APHash          5       3       2387    2791    936     001.43   53.90    0.77    0.77
10      StpdHash        1800    1       5167    11      10      363.64    0.21    0.77  1148.61
11      ThibHash        180     1       5120    58      57      068.97    1.12    0.77   83.33
12      Pol7Hash        183     1       4982    196     139     020.41    3.79    0.77   57.57
13      PolDHash        183     1       4982    196     139     020.41    3.79    0.77   57.57
14      SqlyHash        6       4       2938    2240    1143    001.79   43.26    0.77    1.17
---------------------------------------------------------------------------------------------------
Table size : 9728
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          8       1       7632    2096    883     001.91   21.55    0.41    1.01
 1      PJWHash         9       9       7030    2698    993     001.48   27.73    0.41    0.62
 2      ELFHash         9       9       7030    2698    993     001.48   27.73    0.41    0.62
 3      BKDRHash        10      2       8195    1533    807     002.61   15.76    0.41    1.54
 4      SDBMHash        64      2       8693    1035    237     003.86   10.64    0.41   12.32
 5      DJBHash         30      2       9138    590     423     006.78    6.06    0.41    6.32
 6      DEKHash         7       20      7644    2084    1098    001.92   21.42    0.41    0.89
 7      BPHash          9       60      8968    760     760     005.26    7.81    0.41    2.31
 8      FNVHash         5       10      6847    2881    876     001.39   29.62    0.41    0.53
 9      APHash          5       2       6400    3328    591     001.20   34.21    0.41    0.40
10      StpdHash        1800    1       9717    11      10      363.64    0.11    0.41  611.53
11      ThibHash        180     1       9670    58      57      068.97    0.60    0.41   44.50
12      Pol7Hash        139     2       9511    217     149     018.43    2.23    0.41   28.33
13      PolDHash        139     2       9511    217     149     018.43    2.23    0.41   28.33
14      SqlyHash        28      4       8733    995     501     004.02   10.23    0.41    6.00
---------------------------------------------------------------------------------------------------
Table size : 54862
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          4       1       51164   3698    275     001.08    6.74    0.07    0.08
 1      PJWHash         9       9       51088   3774    157     001.06    6.88    0.07    0.09
 2      ELFHash         9       9       51088   3774    157     001.06    6.88    0.07    0.09
 3      BKDRHash        2       118     50980   3882    118     001.03    7.08    0.07    0.07
 4      SDBMHash        3       8       51091   3771    221     001.06    6.87    0.07    0.08
 5      DJBHash         2       178     51040   3822    178     001.05    6.97    0.07    0.07
 6      DEKHash         3       3       50964   3898    99      001.03    7.11    0.07    0.07
 7      BPHash          1       4000    50862   4000    0       001.00    7.29    0.07    0.07
 8      FNVHash         3       17      51096   3766    217     001.06    6.86    0.07    0.08
 9      APHash          4       1       51041   3821    175     001.05    6.96    0.07    0.07
10      StpdHash        1800    1       54851   11      10      363.64    0.02    0.07  108.46
11      ThibHash        180     1       54804   58      57      068.97    0.11    0.07    7.92
12      Pol7Hash        139     2       54632   230     156     017.39    0.42    0.07    4.97
13      PolDHash        139     2       54632   230     156     017.39    0.42    0.07    4.97
14      SqlyHash        3       1       51050   3812    187     001.05    6.95    0.07    0.07
---------------------------------------------------------------------------------------------------
Table size : 98751
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          2       45      94796   3955    45      001.01    4.01    0.04    0.04
 1      PJWHash         9       9       94867   3884    51      001.03    3.93    0.04    0.05
 2      ELFHash         9       9       94867   3884    51      001.03    3.93    0.04    0.05
 3      BKDRHash        2       43      94794   3957    43      001.01    4.01    0.04    0.04
 4      SDBMHash        2       25      94776   3975    25      001.01    4.03    0.04    0.04
 5      DJBHash         2       38      94789   3962    38      001.01    4.01    0.04    0.04
 6      DEKHash         2       52      94803   3948    52      001.01    4.00    0.04    0.04
 7      BPHash          1       4000    94751   4000    0       001.00    4.05    0.04    0.04
 8      FNVHash         2       82      94833   3918    82      001.02    3.97    0.04    0.04
 9      APHash          3       1       94836   3915    84      001.02    3.96    0.04    0.04
10      StpdHash        1800    1       98740   11      10      363.64    0.01    0.04   60.26
11      ThibHash        180     1       98693   58      57      068.97    0.06    0.04    4.40
12      Pol7Hash        139     2       98522   229     156     017.47    0.23    0.04    2.76
13      PolDHash        139     2       98522   229     156     017.47    0.23    0.04    2.76
14      SqlyHash        3       1       94814   3937    62      001.02    3.99    0.04    0.04
---------------------------------------------------------------------------------------------------
Table size : 104729
Index   Hash Name       LCL     LCL_CNT NZL     NC      COL       ACL    UP%       AVG     VAR
 0      RSHash          3       1       100797  3932    67      001.02    3.75    0.04    0.04
 1      PJWHash         9       9       100905  3824    110     001.05    3.65    0.04    0.04
 2      ELFHash         9       9       100905  3824    110     001.05    3.65    0.04    0.04
 3      BKDRHash        2       40      100769  3960    40      001.01    3.78    0.04    0.04
 4      SDBMHash        3       1       100854  3875    124     001.03    3.70    0.04    0.04
 5      DJBHash         2       31      100760  3969    31      001.01    3.79    0.04    0.04
 6      DEKHash         3       2       100877  3852    146     001.04    3.68    0.04    0.04
 7      BPHash          1       4000    100729  4000    0       001.00    3.82    0.04    0.04
 8      FNVHash         2       69      100798  3931    69      001.02    3.75    0.04    0.04
 9      APHash          3       2       100802  3927    71      001.02    3.75    0.04    0.04
10      StpdHash        1800    1       104718  11      10      363.64    0.01    0.04   56.82
11      ThibHash        180     1       104671  58      57      068.97    0.06    0.04    4.15
12      Pol7Hash        139     2       104499  230     156     017.39    0.22    0.04    2.61
13      PolDHash        139     2       104499  230     156     017.39    0.22    0.04    2.61
14      SqlyHash        2       42      100771  3958    42      001.01    3.78    0.04    0.04
---------------------------------------------------------------------------------------------------
                                   HASH SPEED TEST
---------------------------------------------------------------------------------------------------
***************************************************************************************************
***************************************************************************************************
   Definitions:

   STM:     Start time in microsecond
   ETM:     End time in microsecond
   EXT:     Execution Time in second (lower is better)
   HPS:     Hash per second (higher is better)
***************************************************************************************************
***************************************************************************************************
---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          1827510024      1830857010      3.35    2987762.72
 1      PJWHash         1830857110      1835761855      4.90    2038841.98
 2      ELFHash         1835761941      1841158523      5.40    1853024.75
 3      BKDRHash        1841158561      1844364758      3.21    3118959.94
 4      SDBMHash        1844364856      1847230719      2.87    3489350.33
 5      DJBHash         1847230756      1849705349      2.47    4041068.57
 6      DEKHash         1849705388      1852061153      2.36    4244905.58
 7      BPHash          1852061191      1854463545      2.40    4162583.87
 8      FNVHash         1854463650      1858149102      3.69    2713371.39
 9      APHash          1858149205      1861730640      3.58    2792176.88
10      StpdHash        1861730676      1864166315      2.44    4105698.75
11      ThibHash        1864166397      1866202922      2.04    4910325.19
12      Pol7Hash        1866202994      1868951851      2.75    3637875.67
13      PolDHash        1868951935      1871123932      2.17    4604057.92
14      SqlyHash        1871124007      1873618514      2.49    4008808.15

PS: ma machine est un :

mtrapier@prod500 ~/Desktop/test $ cat /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 15
model           : 4
model name      : Intel(R) Pentium(R) D CPU 2.80GHz
stepping        : 7
cpu MHz         : 2793.356
cache size      : 1024 KB
physical id     : 0
siblings        : 2
core id         : 0
cpu cores       : 2
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 5
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe lm constant_tsc pni monitor ds_cpl cid cx16 xtpr lahf_lm
bogomips        : 5591.27
clflush size    : 64

processor       : 1
vendor_id       : GenuineIntel
cpu family      : 15
model           : 4
model name      : Intel(R) Pentium(R) D CPU 2.80GHz
stepping        : 7
cpu MHz         : 2793.356
cache size      : 1024 KB
physical id     : 0
siblings        : 2
core id         : 1
cpu cores       : 2
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 5
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe lm constant_tsc pni monitor ds_cpl cid cx16 xtpr lahf_lm
bogomips        : 5586.38
clflush size    : 64

(pour situer les perfs en temps)

Merci pour tout

Comment expliquer le fait que la fonction de squalyl (qui multiplie par 31 en pleine boucle) soit plus rapide que la version du PJD optimisée par Pollux (qui ne fait que 2 additions) ? Tu optimises à la compilation ? Je me demande si c'est pas parceque le compilo fout les variables sur la pile au lieu d'utiliser 2 registres.

Sinon on peut voir que la fonction de Pollux ne renvoie pas le même hash que la fonction de DJB.

Hébé je sais pas, ça me pose question... Enfin si GCC doit optmiser la multiplication. Et puis apres tout les décalages sont plus forcement aussi rapide qu'avant (comprendre que les multiplications on bien été amélioré par rapport a il y a 20ans..)

A vrai dire la version de pollux me pose vraiment des questions. Ce n'est pas l'algo DJB de base, il est pas implémenté pareil, il ne donne pas le même resultat, donc ce n'est pas exactement le meme quoi..

moi j'aimerais voir des résultats avec différents switchs d'optimisation, genre sans rien, O2 et O3.

squalyl (./139) :
moi j'aimerais voir des résultats avec différents switchs d'optimisation, genre sans rien, O2 et O3.

Résultat vitesses ?

Pauvre Godzil, on le fait bosser ! Courage !

Bof c'est pas dur a faire

(par contre je garantit pas les resultat de HPS quand on tombe en dessous de la seconde...)

mtrapier@prod500 ~/Desktop/test $ ./GPHFATest -s
General Purpose Hash Function Algorithms Test
By Arash Partow - 2002
Moded by Manoel Trapier - 2007
---------------------------------------------------------------------------------------------------
                                   HASH SPEED TEST
---------------------------------------------------------------------------------------------------
***************************************************************************************************
***************************************************************************************************
   Definitions:

   STM:     Start time in microsecond
   ETM:     End time in microsecond
   EXT:     Execution Time in second (lower is better)
   HPS:     Hash per second (higher is better)
***************************************************************************************************
***************************************************************************************************
---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          2864781883      2868061688      3.28    3048961.75
 1      PJWHash         2868061779      2872932404      4.87    2053124.60
 2      ELFHash         2872932481      2878197041      5.26    1899493.97
 3      BKDRHash        2878197113      2881342864      3.15    3178891.15
 4      SDBMHash        2881342936      2884170013      2.83    3537222.37
 5      DJBHash         2884170083      2886573096      2.40    4161442.32
 6      DEKHash         2886573175      2888925066      2.35    4251897.73
 7      BPHash          2888925137      2891278456      2.35    4249317.67
 8      FNVHash         2891278556      2894851404      3.57    2798887.61
 9      APHash          2894851485      2898304226      3.45    2896249.68
10      StpdHash        2898304305      2900669172      2.36    4228567.61
11      ThibHash        2900669250      2902698838      2.03    4927108.36
12      Pol7Hash        2902698916      2905432446      2.73    3658273.37
13      PolDHash        2905432517      2907601385      2.17    4610700.14
14      SqlyHash        2907601459      2910089059      2.49    4019938.90
mtrapier@prod500 ~/Desktop/test $ ./GPHFATest.Os -s
General Purpose Hash Function Algorithms Test
By Arash Partow - 2002
Moded by Manoel Trapier - 2007
---------------------------------------------------------------------------------------------------
                                   HASH SPEED TEST
---------------------------------------------------------------------------------------------------
***************************************************************************************************
***************************************************************************************************
   Definitions:

   STM:     Start time in microsecond
   ETM:     End time in microsecond
   EXT:     Execution Time in second (lower is better)
   HPS:     Hash per second (higher is better)
***************************************************************************************************
***************************************************************************************************
---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          2916352773      2918880563      2.53    3956024.83
 1      PJWHash         2918880678      2921237045      2.36    4243821.10
 2      ELFHash         2921237128      2923538197      2.30    4345806.23
 3      BKDRHash        2923538291      2926092739      2.55    3914740.09
 4      SDBMHash        2926092826      2928666684      2.57    3885218.22
 5      DJBHash         2928666777      2931220723      2.55    3915509.57
 6      DEKHash         2931220819      2932775084      1.55    6433909.28
 7      BPHash          2932775165      2934322338      1.55    6463401.31
 8      FNVHash         2934322420      2936868050      2.55    3928300.66
 9      APHash          2936868121      2938949082      2.08    4805472.09
10      StpdHash        2938949164      2940447570      1.50    6673758.65
11      ThibHash        2940447640      2941778674      1.33    7512956.09
12      Pol7Hash        2941778751      2943541657      1.76    5672452.19
13      PolDHash        2943541730      2944901669      1.36    7353270.99
14      SqlyHash        2944901749      2947433310      2.53    3950131.95
mtrapier@prod500 ~/Desktop/test $ ./GPHFATest.O2 -s
General Purpose Hash Function Algorithms Test
By Arash Partow - 2002
Moded by Manoel Trapier - 2007
---------------------------------------------------------------------------------------------------
                                   HASH SPEED TEST
---------------------------------------------------------------------------------------------------
***************************************************************************************************
***************************************************************************************************
   Definitions:

   STM:     Start time in microsecond
   ETM:     End time in microsecond
   EXT:     Execution Time in second (lower is better)
   HPS:     Hash per second (higher is better)
***************************************************************************************************
***************************************************************************************************
---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          2949701082      2951482728      1.78    5612787.28
 1      PJWHash         2951482841      2953119408      1.64    6110351.73
 2      ELFHash         2953119504      2954855712      1.74    5759678.56
 3      BKDRHash        2954855798      2956590380      1.73    5765077.70
 4      SDBMHash        2956590457      2958275611      1.69    5934175.75
 5      DJBHash         2958275696      2959219183      0.94    10598980.17
 6      DEKHash         2959219271      2960052627      0.83    11999673.61
 7      BPHash          2960052706      2960891786      0.84    11917814.75
 8      FNVHash         2960891873      2962639155      1.75    5723174.62
 9      APHash          2962639234      2963893788      1.25    7970960.20
10      StpdHash        2963893871      2964663832      0.77    12987670.80
11      ThibHash        2964663908      2965200197      0.54    18646662.53
12      Pol7Hash        2965200281      2966006577      0.81    12402393.17
13      PolDHash        2966006659      2966645915      0.64    15643185.20
14      SqlyHash        2966645991      2967584260      0.94    10657924.33
mtrapier@prod500 ~/Desktop/test $ ./GPHFATest.O3 -s
General Purpose Hash Function Algorithms Test
By Arash Partow - 2002
Moded by Manoel Trapier - 2007
---------------------------------------------------------------------------------------------------
                                   HASH SPEED TEST
---------------------------------------------------------------------------------------------------
***************************************************************************************************
***************************************************************************************************
   Definitions:

   STM:     Start time in microsecond
   ETM:     End time in microsecond
   EXT:     Execution Time in second (lower is better)
   HPS:     Hash per second (higher is better)
***************************************************************************************************
***************************************************************************************************
---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          2980666088      2982426700      1.76    5679843.15
 1      PJWHash         2982426758      2984027764      1.60    6246072.78
 2      ELFHash         2984027796      2985769844      1.74    5740369.96
 3      BKDRHash        2985769880      2987505011      1.74    5763253.61
 4      SDBMHash        2987505048      2989196792      1.69    5911059.83
 5      DJBHash         2989196827      2990143239      0.95    10566222.74
 6      DEKHash         2990143276      2990977590      0.83    11985895.00
 7      BPHash          2990977618      2991820839      0.84    11859287.19
 8      FNVHash         2991820867      2993587071      1.77    5661860.12
 9      APHash          2993587100      2994882810      1.30    7717776.35
10      StpdHash        2994882847      2995648952      0.77    13053041.03
11      ThibHash        2995648982      2996185932      0.54    18623707.98
12      Pol7Hash        2996185958      2996986636      0.80    12489415.22
13      PolDHash        2996986662      2997628761      0.64    15573922.40
14      SqlyHash        2997628787      2998566077      0.94    10669056.54

Le gain de vitesse est remarquable entre -Os et -O2 Le classement de rapidité redevient cohérent par rapport aux algos (3)squalyl, 2)Pollux, 1)stupide).

Il reste juste la question de la différence de valeur entre DJB et Pollux à régler. A ce propos, sur ma moulinette, qui bosse sur des mots de longueur inférieure à ~10 lettres je pense, l'algo de Pollux et celui de DJB donnaient la même chose.

Thibaut (./137) :
Merci pour tout

Comment expliquer le fait que la fonction de squalyl (qui multiplie par 31 en pleine boucle) soit plus rapide que la version du PJD optimisée par Pollux (qui ne fait que 2 additions) ? Tu optimises à la compilation ? Je me demande si c'est pas parceque le compilo fout les variables sur la pile au lieu d'utiliser 2 registres.

Sinon on peut voir que la fonction de Pollux ne renvoie pas le même hash que la fonction de DJB.

La version que j'ai donnée est optimisée en vue des 68k : un décalage par 5 coûte assez cher, donc ma version est nettement plus rapide sur 68k. Par contre sur un x86 moderne ça doit pas améliorer bcp ^^ (les shifts et les multiplications sont hyper rapides)

Et puis elle renvoie pas le même hash modulo 2^32, par contre elle renvoie bien le même hash modulo 2^10 : 0x7E6BB1 vs 0x2B7757B1

Donc tous les modulos au-dessous de 1024 donnent la même chose ? (par exemple sur une table de hachage de 317 éléments ?)

Pollux (./144) :
Par contre sur un x86 moderne ça doit pas améliorer bcp ^^ (les shifts et les multiplications sont hyper rapides)

D'après les benchs de Godzill, ça améliore un peu, donc autant garder ta version optimisée

Donc tous les modulos au-dessous de 1024 donnent la même chose ? (par exemple sur une table de hachage de 317 éléments ?)

Je viens de tester et la réponse est non avec 317
La réponse est oui pour 256 et 512. Donc ton optimisation ne fonctionne pas avec des nombres premiers. Je vais noter ça dans la conclusion alors.

(tiens je vais lancer la suite sur un truc a base d'ARM ^^)

deja sur un PIII @ 1Ghz :

---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          1846466196      1853296775      6.83    1464004.74
 1      PJWHash         1853297009      1865629544      12.33   810863.30
 2      ELFHash         1865629860      1878974355      13.34   749372.68
 3      BKDRHash        1878974693      1885322602      6.35    1575321.89
 4      SDBMHash        1885322879      1891407312      6.08    1643538.52
 5      DJBHash         1891407510      1897427578      6.02    1661110.80
 6      DEKHash         1897427861      1903018743      5.59    1788626.55
 7      BPHash          1903018959      1908791079      5.77    1732465.71
 8      FNVHash         1908791283      1916729612      7.94    1259710.95
 9      APHash          1916729871      1925735437      9.01    1110424.38
10      StpdHash        1925735645      1931125107      5.39    1855472.77
11      ThibHash        1931125314      1936727434      5.60    1785038.52
12      Pol7Hash        1936727623      1942771419      6.04    1654589.27
13      PolDHash        1942771592      1948574019      5.80    1723416.77
14      SqlyHash        1948574192      1955564973      6.99    1430455.34

et en O3 :

---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          2009344046      2012094739      2.75    3635447.50
 1      PJWHash         2012094993      2016598273      4.50    2220603.65
 2      ELFHash         2016598466      2021288956      4.69    2131973.42
 3      BKDRHash        2021289223      2024251806      2.96    3375432.86
 4      SDBMHash        2024252029      2028234865      3.98    2510773.73
 5      DJBHash         2028235118      2030795693      2.56    3905372.82
 6      DEKHash         2030795867      2032698209      1.90    5256678.35
 7      BPHash          2032698380      2034599210      1.90    5260859.73
 8      FNVHash         2034599399      2037336034      2.74    3654122.67
 9      APHash          2037336214      2041161970      3.83    2613862.46
10      StpdHash        2041162234      2042895091      1.73    5770816.63
11      ThibHash        2042895246      2044604106      1.71    5851854.45
12      Pol7Hash        2044604242      2046551017      1.95    5136700.44
13      PolDHash        2046551179      2048015544      1.46    6828898.53
14      SqlyHash        2048015753      2050606689      2.59    3859609.04

(thibaut: 256 et 512 sont des puissance de 2...)

Thibaut (./145) :
Donc tous les modulos au-dessous de 1024 donnent la même chose ? (par exemple sur une table de hachage de 317 éléments ?)

Non, ça marche seulement pour les modulos qui divisent 1024 ^^

OK. La nouvelle conclusion vous paraît elle bonne ?

(aie aie aie sur arm... sa ram... !)

la machine de test :

Nokia-N800-26:~# cat /proc/cpuinfo 
Processor       : Some Random V6 Processor rev 2 (v6l)
BogoMIPS        : 320.37
Features        : swp half thumb fastmult vfp edsp java 
CPU implementer : 0x41
CPU architecture: 6TEJ
CPU variant     : 0x0
CPU part        : 0xb36
CPU revision    : 2
Cache type      : write-back
Cache clean     : cp15 c7 ops
Cache lockdown  : format C
Cache format    : Harvard
I size          : 32768
I assoc         : 4
I line length   : 32
I sets          : 256
D size          : 32768
D assoc         : 4
D line length   : 32
D sets          : 256

Hardware        : Nokia N800
Revision        : 24202524
Serial          : 0000000000000000
Nokia-N800-26:~#