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

Kevin Kofler (./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 )

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

si tu le dis..

Pour ton "_ti68k", ça s'appelle __TIGCC_ENV__.

ok merci

Kevin Kofler (./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.

ok (et en benchant ? (mm, je sais, j'insiste avec mes benchs (mais c'est juste par curiosité)))


Thibaut > merci pour les crédits

La flemme
De rien Par contre j'ai du anonymer Pollux, il voulait pas (trop modeste peut-être )

Kevin Kofler (./178) :
L'allocateur de registres sait mieux que toi quand il faut utiliser un registre et quand il ne faut pas.

Ben voyons Depuis le début tu racontes plus ou moins n'importe quoi ici, alors arrête un peu. Si encore tu étais aimable, ça serait pas gênant.

arrête de le piquer toi aussi

crédits > ben je n'aime pas trop non plus le lien nom <-> login, mais bon... (sur un forum j'aime autant pas le vrai nom, à vrai dire)

allocateur de registres > nan mais c'est pas impossible, je suppose qu'il voulait dire que le compilo à une connaissance globale du code qu'il génère, et que le forcer à affecter tel registre à telle variable pourrait induire des effets de bords négatifs sur le reste.

Oui mais si je sais que ma variable a intérêt à être dans un registre parceque je sais que la boucle est susceptible de tourner beaucoup, je le sais, point.
Ce n'est pas sensé avoir d'effets négatifs en-dehors de la fonction. Si le compilateur ne met pas dans un registre ma variable qui a intérêt à y être, alors il est mauvais car il sacrifie la vitesse de ma fonction critique.

(je me faisais l'avocat du diable)

OK
Pour les crédits sur le forum, c'est arrangé. Peux-tu éditer ton message pour mettre Pollux dans le code que tu cites ? Par contre dans la source originale je garde les vrais noms ! A moins que vous vous y opposiez

ok pour l'édition, je m'en charge tout de suite
source original : nan au contraire, c'est parfait pour moi (même si y'a une publication sur le net, c'est juste le lien pseudo<->nom qui me dérange un peu)

sinon je reviens sur l'histoire du ">=0" : c'est pas mieux de laisser ">0", ie remplacer par "!=0", vu la décrémentation par pas de 1 ?
normalement on peut espérer qu'un test d'égalité à 0 est plus rapide qu'une comparaison

Thibaut (./159) :
// generates very uniform hash tables even with non prime modulos

faut pas s'enflammer non plus, les bench de godzil montrent bien que DjbHash (et donc ce hash) est très inefficace modulo une puissance de 2 donc c'est un hash rapide, OK, mais d'assez mauvaise qualité -- c'est vrai qu'avec tes données, c'est pas un problème d'utiliser un hash de mauvaise qualité (la preuve, même le hash tout con est aussi efficace qu'un hash idéal), mais ça n'en fait pas pour autant un hash "very uniform"

Pen^2 (./190) :
sinon je reviens sur l'histoire du ">=0" : c'est pas mieux de laisser ">0", ie remplacer par "!=0", vu la décrémentation par pas de 1 ?
normalement on peut espérer qu'un test d'égalité à 0 est plus rapide qu'une comparaison (genre un subq et derrière un beq.s pour le 68k)

oui, le test qui correspond à l'instruction dbf c'est "while (i--)" ^^ (par contre dans presque tous les autres cas une comparaison et un test d'égalité sont aussi rapides)

Sur une table de 1024, l'écart type est très très bon, excellent même. Je rappelle que les tests de Godzill sont prévus pour mettre à mal les fonctions, alors que hashtext.exe s'appuie sur la réalité

Je te laisse tester si tu veux voir par toi-même. Avec un modulo premier, ça change que dalle.

Kevin Kofler (./178) :
L'allocateur de registres sait mieux que toi quand il faut utiliser un registre et quand il ne faut pas.

En effet, c'est une excellente idée de la part de TIGCC d'ignorer mes directives register. Je viens de vérifier le .s...
Monsieur TIGCC travaille uniquement sur la pile dans la boucle !

En effet, il sait vachement mieux que le programmeur quand il faut placer des variables dans des registres


Je viens de regarder le code généré par GTC. OOOOHHH miracle !!! Tout est dans des registres !
C'est fabuleux hein Kevin

Non attention, je répond à Kevin. GCC a ses raisons sans doute très justifiées. Mais comme toute chose automatique, y'a des cas où c'est pas bon.
Je prends l'exemple des caméras numériques. C'est très bien en mode automatique, sauf quand il y a des contre-jours, c'est la cata. Quand on sait ce qu'on veut, il vaut mieux passer en manuel.

Bon, y'a du mieux avec -Os.
C'est quand même dingue que même sans optimisation (pas de -Ox) GCC ne prenne pas en compte les register si on le demande. Pourtant je vois pas le problème puisqu'il n'optimise rien d'après Kevin, donc pas d'effets de bord possibles.

Comment t'essaies de me convertir à ta religion !
Je ne me plains pas, je répond à Kevin qui disait sûr de lui que GCC sait toujours mieux que le programmeur.

Thibaut (./194) :

Kevin Kofler (./178) :
L'allocateur de registres sait mieux que toi quand il faut utiliser un registre et quand il ne faut pas.

En effet, c'est une excellente idée de la part de TIGCC d'ignorer mes directives register. Je viens de vérifier le .s...Monsieur TIGCC travaille uniquement sur la pile dans la boucle !

Bon, je vais demander l'évident: As-tu bien mis des flags d'optimisation?

Tu peux forcer (enfin, pas forcer, mais au moins ce sera pris en compte) GCC à utiliser un registre, mais il faudra lui dire lequel: http://tigcc.ticalc.org/doc/gnuexts.html#SEC99

Thibaut (./196) :
Bon, y'a du mieux avec -Os.

Donc tu as utilisé -O0 et tu t'étonnes que ce n'est pas optimisé?

C'est quand même dingue que même sans optimisation (pas de -Ox) GCC ne prenne pas en compte les register si on le demande.

Dans un ancien GCC (2.95 ou dans cet ordre de grandeur), ils ont fait ça, mais maintenant il est censé y avoir allocation de registres même en -O0. Mais évidemment pas optimale!

Je voulais juste te montrer que GCC ferait bien de suivre la directive register. Surtout quand il n'optimise pas, il pourrait au moins prendre en compte cette directive qu'on peut voir comme une optimisation manuelle. Enfin bref.

lateurs quand même, car ils traduisent le while comme ça : subq.w #1,d4 tst.w d4 bgt .L4Je suis un peu déçu des deux compioins ça : subq.w #1,d4 bgt .L4Je pensais obtenir au mOu encore mieux, un dbf
Martial, tu vas être content, je vais devoir coder la fonction en assembleur (d'autant plus que TIGCC produit un div dans le code )

Thibaut (./201) :
Surtout quand il n'optimise pas

Bah, tu t'attends un code optimisé en n'optimisant pas?
Il faut toujours donner un switch d'optimisation.

	subq.w #1,d4
	tst.w d4
	bgt .L4

Hmmmph, normalement GCC n'est pas censé génerer ça, le backend 68k se rappelle de ce qui est dans les registres de flags normalement. Je ne comprends pas ce qui se passe exactement, je vais devoir regarder les dumps.

(d'autant plus que TIGCC produit un div dans le code )

Tu utilises quoi comme HASH_TABLE_SIZE? Et si tu rajoutes un u (256 -> 256u)?

Bon, le div généré est attendu en -Os. Tu as écrit ça:
i= length / 4;
où length est signé, un shift n'a pas la même sémantique pour les nombres signés qu'une division. Mets length en non signé (i peut rester signé) et tu n'auras pas ce problème (j'ai vérifié, ça donne bien un lsr). Ou alors écris directement >>2 et pas /4 (mais si tu fais juste ça sans passer length en unsigned, ça fera que ton algo ne marchera pas pour les longeurs entre 32768 et 65535 (enfin, 65520, on ne peut pas avoir un bloc plus grand )). Ou les deux.

Quant à ton histoire de tst inutile pour la boucle, je ne peux pas la reproduire, avec TIGCC CVS HEAD et -Os, j'ai:

	subq.w #1,%d4
	jbpl .L3

Et en -O2, tu n'as pas de div même avec length signé, à la place tu as un code tordu de shifts et comparaisons, tout ça parce qu'il faut traîter le cas où length<0.

OK j'ai rajouté (unsigned). C'est vrai qu'un masquage ne suffit pas pour les nombres signés, j'y pensais plus. Merci

Regarde, je viens encore d'essayer à l'instant (j'ai TIGCC 0.96b8) : Fichier joint : hash_c.s

Martial Demolins (./206) :
Ya un label entre les deux

Effectivement, ce serait incorrect de virer le tst là.
Et puis de toute façon, la future bêta 9 ne génère pas ça (il n'y a pas ce label et donc pas le tst incriminé non plus), donc il n'a rien à corriger.

Martial Demolins (./207) :

__main:
	move.w #18,-(%sp)
	pea .LC0
	jbsr fast_and_perfect_hash
	addq.l #6,%sp
	rts

Quel intérêt de faire ça? Pourquoi empiler puis faire un saut pour s'empresser de dépiler à l'arrivée? Pourquoi pas mettre __main au début de la fonction principale et renseigner directment les registres?

Parce que c'est la convention d'appel.

Si on met static à de la fonction, elle sera automatiquement inlinée (même en -Os, étant donné qu'elle est appelée exactement une fois), ce qui fait essentiellement ce que tu proposes. (Mais dans ce cas, la fonction sera totalement éliminée vu qu'elle n'a pas d'effets collatéraux. C'est bien pour ça que je dis de toujours tester avec des entrées utilisateur et afficher le résultat!) Mais si elle n'est pas static, GCC ne peut pas savoir qu'il n'y a pas un autre fichier .c qui veut appeler la fonction! C'est bien pour ça que je dis de toujours mettre static pour les fonctions ou variables globales qui ne sont pas utilisées dans un autre .c. Même s'il y en a un seul! (GCC ne peut pas savoir.)

Oui oui oui
Mais là c'est un essai, pas un vrai programme, on s'en tape de ce genre de détail Encore une fois, c'était pour voir la gueule de l'ASM généré et l'allocation des registres.