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

---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          476430186       533643137       57.21   174785.60
 1      PJWHash         533657511       602847239       69.19   144530.12
 2      ELFHash         602861674       671987559       69.13   144663.61
 3      BKDRHash        672001627       714779642       42.78   233764.94
 4      SDBMHash        714794230       764368998       49.57   201715.52
 5      DJBHash         764374857       809475352       45.10   221727.06
 6      DEKHash         809489360       850175394       40.69   245784.59
 7      BPHash          850187540       890872080       40.68   245793.61
 8      FNVHash         890885844       938394694       47.51   210487.10
 9      APHash          938408701       1018625498      80.22   124662.17
10      StpdHash        1018638987      1054689890      36.05   277385.56
11      ThibHash        1054704081      1090144083      35.44   282167.03
12      Pol7Hash        1090158030      1131233622      41.08   243453.58
13      PolDHash        1131247904      1164848613      33.60   297612.77
14      SqlyHash        1164862803      1204231486      39.37   254009.01

Godzil (./131) :
cc -std=c99 -pedantic -Wall -o GPHFATest GPHFATest.c

Godzil (./138) :
Enfin si GCC doit optmiser la multiplication.

Kevin Kofler (./152) :
Un test de vitesse sans flags d'optimisation??? C'est n'importe quoi.

Kevin Kofler (./153) :

Godzil (./138) :
Enfin si GCC doit optmiser la multiplication.

GCC n'optimise rien du tout si tu ne lui donnes pas de flags d'optimisation. Le niveau d'optimisation par défaut est -O0, qui veut dire "aucune optimisation".

---------------------------------------------------------------------------------------------------
Speed test with 10000000 loop
Key is: 'abcdefghijklmnopqrstuvwxyz1234567890'
Index   Hash Name       STM             ETM             EXT     HPS
 0      RSHash          1231645182      1244214793      12.57   795569.57
 1      PJWHash         1244229319      1260052134      15.82   631998.79
 2      ELFHash         1260066447      1275883250      15.82   632239.02
 3      BKDRHash        1275897502      1286046091      10.15   985358.65
 4      SDBMHash        1286060404      1298382609      12.32   811543.06
 5      DJBHash         1298396800      1308514536      10.12   988363.40
 6      DEKHash         1308528971      1318611063      10.08   991857.64
 7      BPHash          1318625193      1329810343      11.19   894042.55
 8      FNVHash         1329824747      1342241984      12.42   805332.14
 9      APHash          1342256205      1363729258      21.47   465699.96
10      StpdHash        1363734263      1373828989      10.09   990616.29
11      ThibHash        1373843180      1384925547      11.08   902334.31
12      Pol7Hash        1384931559      1398545054      13.61   734565.22
13      PolDHash        1398551341      1409040324      10.49   953381.28
14      SqlyHash        1409054484      1421471567      12.42   805342.12

Kevin Kofler (./10) :

squalyl (./8) :
et il est ou le hachage la dedans?

Justement, il n'y en a pas.
Tout ça pour montrer que ça ne sert pas à grand chose d'optimiser le lookup d'un symbole, ld-tigcc fait une recherche linéaire et ça marche aussi.

int fast_and_perfect_hash(const char *str, int length)  // works only with HASH_TABLE_SIZE = 256 or 512 or 1024
{   // very good Daniel Julius Bernstein's algorithm
    // speed optimized by Pollux
    // unrolled by Thibaut for more speed
    // generates very uniform hash tables even with non prime modulos

    register unsigned int hash = 5381; // DJB Hash
    register unsigned int hash5 = 0;
    register const char   *s;
    register int          ir;
    int                   i4;


    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;
}

int fast_and_perfect_hash(const char *str, int length)  // works only with HASH_TABLE_SIZE = 256 or 512 or 1024 
{   // very good Daniel Julius Bernstein's algorithm 
    // speed optimized by Pollux
    // unrolled by Thibaut for more speed 
    // generates very uniform hash tables even with non prime modulos 
 
    register unsigned int hash = 5381; // DJB Hash 
    register unsigned int hash5 = 0; 
    register const char   *s; 
    register int          i; 
 
 
    s = str-sizeof(char); 
    i= (length / 4)+sizeof(char); 
 
    while (--i > 0) { 
        hash5+= hash;  hash+= *++s; 
        hash5+= hash;  hash+= *++s; 
        hash5+= hash;  hash+= *++s; 
        hash5+= hash;  hash+= *++s; 
    } 
 

    i= (length % 4)+sizeof(char); 
    while (--i > 0) { 
        hash5+= hash; 
        hash+= *++s; 
    } 
 
    return (hash + (hash5<<5)) % HASH_TABLE_SIZE; 
}

Pen^2 (./161) :
c'est pas mieux de passer i4 en registre à la place de ir, si vraiment on considère qu'on n'a pas assez de registres ?

4 A declaration of an identifier for an object with storage-class specifier register suggests that access to the object be as fast as possible. The extent to which such suggestions are effective is implementation-defined.100)

100) The implementation may treat any register declaration simply as an auto declaration. However, whether or not addressable storage is actually used, the address of any part of an object declared with storage-class specifier register cannot be computed, either explicitly (by use of the unary & operator as discussed in 6.5.3.2) or implicitly (by converting an array name to a pointer as discussed in 6.3.2.1). Thus, the only operator that can be applied to an array declared with storage-class specifier register is sizeof.

c'est pas mieux de passer i4 en registre à la place de ir, si vraiment on considère qu'on n'a pas assez de registres ?

Thibaut (./167) :
La pré décrémentation suivie d'un test est plus rapide que le test post décrémenté ?

Thibaut (./167) :
Voilà ce qui me fait penser qu'il vaut mieux que ce soit ir la variable register.

int fast_and_perfect_hash(const char *str, int length)  // works only with HASH_TABLE_SIZE = 256 or 512 or 1024 
{   // very good Daniel Julius Bernstein's algorithm
    // speed optimized by Pollux
    // unrolled by Thibaut for more speed
    // some other speed optimizations by Pen^2
    // generates very uniform hash tables even with non prime modulos

    register unsigned int hash = 5381; // DJB Hash
    register unsigned int hash5 = 0;
    register const char  *s;
    register int          i;


    s = str;

    i= (unsigned)length / 4;
    while (i--) {
        hash5+= hash;  hash+= *s++;
        hash5+= hash;  hash+= *s++;
        hash5+= hash;  hash+= *s++;
        hash5+= hash;  hash+= *s++;
    }

    i= (unsigned)length % 4;
    while (i--) {
        hash5+= hash;
        hash+= *s++;
    }

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

Kevin Kofler (./164) :

Pen^2 (./161) :
c'est pas mieux de passer i4 en registre à la place de ir, si vraiment on considère qu'on n'a pas assez de registres ?

register est totalement ignoré par GCC de toute façon.

et dans la mienne :clr.w   d0
move.b  (a0)

m'enfin si tu regardes jusque là, le mieux ça reste de faire un cas généralement meilleur en C, et de faire une version asm spécifique pour quelques plateformes, je crois.

Thibaut (./173) :
J'aimerai faire un programme portable à 100%, mais c'est sûr que si je m'aperçoit que ni GTC ni TIGCC ne donnent un code assembleur correct, je pourrai pas m'empêcher de coder ça directement en assembleur si ça peut faire doubler la vitesse

Pen^2 (./168) :
je savais que "register" n'était qu'une suggestion à cause de la portabilité (pas forcément assez de registres dispos sur la plateforme) mais c'est quand même dommage de l'ignorer volontairement (le coup du standard, c'était qu'une boutade )

Thibaut (./176) :
Les cyles... j'ai tout oublié à ce niveau

Mais ce serait bête que Motorola ait inventé add (an)+,dn si add (an),dn suivit de add #1,an est plus rapide.