150

(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:~# 
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

151

(je poste au fur et a mesure pasque bon grin)

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


Sans optimisation compilo
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

152

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

Un test de vitesse sans flags d'optimisation??? eek C'est n'importe quoi. sick Les résultats d'après avec -Os/-O2/-O3 sont bons, mais ceux sans optimisation (que tu t'es amusés à refaire sur d'autres machines en plus) sont à jeter. Tous les développeurs de GCC te diront qu'il ne faut jamais compiler sans optimisations, sauf si c'est pour déboguer, et même là, ça devrait marcher avec optimisation aussi avec des GCC et GDB récents.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

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".
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

154

Kevin Kofler (./152) :
Un test de vitesse sans flags d'optimisation??? eek.gif C'est n'importe quoi. sick.gif
Un peu de politesse SVP ! smile
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

155

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".

bla bla bla bla bla bla bla

En gros
ta gueule merci



meme machine sous ARM en -O3
---------------------------------------------------------------------------------------------------
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
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

156

157

lol

Ouai sur ARM c'est pas génial. Mais au pire on doit pouvoir améliorer de quelques pourcents la vitesse en codant tout ceci en ASM (ce que je dis va faire rire Martial).

Sinon, au niveau de la recherche par arbres, il y a peut-être intérêt à voir ce que ça donne ? Il y a peut-être des comparaisons et des débats intéressants à faire par rapport aux résultats de ce topic.
Dans ce cas on ouvre un nouveau topic ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

158

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

Justement, il n'y en a pas. gni
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.
J'espère que tu optimiseras quand même un peu tes algos le jour où tu créeras par exemple des applications de simulation pour la recherche scientifique ou l'ingénierie.

Quand on a beaucoup de symboles, je préfère que le temps passé à chercher un symbole soit de 1 seconde avec une table de hash de dimension 1024, plutôt que 17 minutes (1024 secondes) avec ta méthode ultra subtile wink

Je vois bien tes futures applications de météorologie qui mettront 3 ans (1024 jours) à prévoir le temps du lendemain au lieu de 24h... trioui KK, l'inventeur de la rétro-prévision sur 3 ans ! Exceptionnel !
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

159

Donc voici la fonction retenue pour mon programme :

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;
}
Y a-t-il des gens qui trouvent des optimisations de vitesse supplémentaires à y faire ? (à part coder en assembleur tongue)
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

160

./158 > rotfl
Bien sûr, tout dépend du contexte. Mais pour reprendre ton exemple, ça ne sert à rien de faire descendre le temps pour la prévision pour dans 3 jours d'une microseconde à une nanoseconde. grin Il faut optimiser en vitesse ce qui met trop longtemps, mais pour le reste, c'est peine perdue, la taille du code, la facilité de codage etc., tout ça, c'est plus important si le temps d'exécution est déjà suffisamment bas sans les optimisations.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

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 ?

162

Au fait, est-ce que quelqu'un saurait prouver que le résultat de la fonction est le même quand le type int est sur 16 bits au lieu de 32 bits ?
J'ai fait un test sur megamix.txt en remplaçant int par short, et il n'y a pas de différence d'après ce test. Mais ça ne prouve pas que les deux fonctions (l'une avec int, l'autre avec short) retournent toujours la même valeur...
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

163

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

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.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

165

spa de ma faute s'il ne respecte pas le standard embarrassed (tongue)

166

Le standard ISO C99 dit ça:
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.

Et GCC implémente exactement la note 100. L'allocation de registres décide automatiquement ce qui va dans un registre et ce qui n'y va pas.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

167

Pen^2 : Merci smile

La pré décrémentation suivie d'un test est plus rapide que le test post décrémenté ?
[edit] après réflexion, oui en effet smile
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 ?
Ben, sachant que mon programme travaillera sur des mots d'une longueur en général inférieure à 10 lettres, la boucle avec i4 se répétera pas plus de 2 fois en moyenne (10/4), alors que la boucle avec ir pourra s'exécuter jusqu'à 3 fois (3%4, 7%4). Voilà ce qui me fait penser qu'il vaut mieux que ce soit ir la variable register.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

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 wink)

169

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

c'est surtout important avec les objets c++ (copie de l'objet avec l'operator unaire post)
Thibaut (./167) :
Voilà ce qui me fait penser qu'il vaut mieux que ce soit ir la variable register.

ok, mais en utilisant une seule variable i comme je l'ai fait, tu règles la question wink

170

Oui, ta version est plus pertinente smile Je l'ai adoptée, en mettant à ma sauce :

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;
}
Comme tu le vois, je préfère laisser *s++ car il me semble que sur 68k cela correspondra à un add (an)+,dn alors que *++s risque de produire un code moins rapide, non ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

171

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.
C'est bien pour cette raison que je compte utiliser GTC. Mon programme aura besoin de vitesse et on a prouvé ailleurs qu'un programme codé avec attention se révèle 10% plus rapide avec GTC qu'avec TIGCC.
Mais GTC vs GCC n'est pas le sujet.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

172

je ne sais plus : ça dépend des cycles avec le type d'adressage ((an)++ ça doit être assez lent, non ?)

(bien vu pour le >=0)


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.

173

le :clr.w d0 addq.l #1,a0 move.b (a0),d0 add.w d0,d1A priori, le code généré dans ta version serait de ce sty+,d0 add.w d0,d1
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.
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 fait doubler la vitesse smile
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

174

et les cycles ? (m'enfin le mieux c'est le bench)

175

(addq.w c'était pas suffisant pour je ne sais plus quelle raison ? (ou alors je dis n'importe quoi, c'est très possible))

176

Les cyles... j'ai tout oublié à ce niveau smile Mais ce serait bête que Motorola ait inventé add (an)+,dn si add (an),dn suivit de add #1,an est plus rapide.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

177

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 smile



ben
type maFonction(...)
{
#if defined(_ti68k) //y'a bien un symbole, non ?
#elif define(_arm)

#else
//code c portable
#endif
}
et puis c'est réglé, non ?

178

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 wink)

L'allocateur de registres sait mieux que toi quand il faut utiliser un registre et quand il ne faut pas.

Pour ton "_ti68k", ça s'appelle __TIGCC_ENV__.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

179

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

moi aussi (et comme le bench c'est plus fiable..)
Mais ce serait bête que Motorola ait inventé add (an)+,dn si add (an),dn suivit de add #1,an est plus rapide.

bof, y'a la compacité du code, aussi (qui peut d'ailleurs jouer sur la vitesse, aussi)

180

Et addq.l #1,%an et addq.w #1,%an reviennent exactement au même. Même taille, même nombre de cycles, même effet.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité