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

lol

Dis, ça existe move.b 3(an),an ?

J'espérais que le processeur étendrait automatiquement l'octet (a0) sur les 32 bits du registre a1. On peut toujours rêver

Je crois que je gagnerai pas énormément de temps d'exécution en codant en assembleur. Finalement je vais peut-être garder le code C.
Au fait, est-ce que l'instruction move.b 2(a0),d1 est plus rapide que l'instruction move.b (a0)+,d1 ? (je demande pas si elles sont équivalentes, non, il est juste question du nombre de cycles de l'une et de l'autre)

J'ai l'impression que move.b 2(a0),d1 est plus lente, et pourtant TIGCC génère ça dans le while déroulé.

Oui, c'est plus lent.
Normalement, GCC est censé reconnaître les postincrémentations, je ne sais pas pourquoi exactement ça ne fonctionne pas ici. Le support de GCC pour les postincrémentations n'est pas parfait.

Thibaut (./193) :
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é Avec un modulo premier, ça change que dalle.

Je viens de refaire le test. Oui, la fonction DJBHash produit une variance meilleure sur un modulo 257 que sur un modulo 256. Mais l'écart n'est que de 2 points (la variance tourne autour de 27). Je trouve que c'est vraiment pas grand chose.

lo 1024 : Fonction 2 | moyenne : 7.03 | variance : 7.39

Les résultats avec un modulo 1021 sont encore plus serrés :modulo 1021 :
Fonction 2  |  moyenne : 7.05  |  variance : 7.54
modu

(attention les numéros des fonctions ont changés, téléchargez hashtest.zip dans le post ./1 si vous voulez la dernière version)

Voilà, apparemment un modulo sur une puissance de 2 (et donc ta super optimisation vitesse) produit des tables très homogènes quand on travaille sur du texte. Je ne vois donc pas à priori de raison pour utiliser la version lente de l'algo DJB.

Thibaut (./201) :
pilateurs 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 commoins ça : subq.w #1,d4 bgt .L4Je pensais obtenir au Ou 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 )

Si tu veux un dbf, il faut utiliser while (i--), pas while (--i >= 0) ; normalement en mode -O2 ça marche, aussi bien sur TIGCC que GTC ^^

A mon avis avec cette fonction-là le seul intérêt de l'assembleur c'est que tu peux faire l'extension de signe avec un simple move.b plutôt qu'avec un clr.w+move.b ; donc en gros tu gagneras 4 cycles sur une boucle de 30 cycles, je suis pas sûr que ça vaille vraiment la peine

Oui finalement je vais rester en C, c'est plus élégant

Si ça intéresse des gens, je suis en train d'écrire un gestionnaire de mémoire ultra rapide, qui permettra d'allouer & libérer des zones de mémoire très rapidement. C'est une surcouche au système classique malloc/free (càd qu'il utilise ces fonctions, mais par blocs de 16 ko, et il gère leur organisation interne avec ses propres méthodes).

J'ai pas encore vraiment d'idée sur quoi ça va aboutir. J'espère y arriver. Pour GTC j'imagine que tu as du écrire un gestionnaire de cette sorte ? Si oui, tu t'es organisé comment ?

En gros tu recodes un malloc; tu te bases sur quel(s) algo(s), si ton objectif est d'avoir quelque chose de plus efficace que l'implémentation d'AMS ? (je n'ai aucune idée de ce qu'ils utilisent, eux, ni de si c'est optimisé ou non)

Évidemment que non, rien n'est optimisé chez TI.

Thibaut (./218) :
J'ai pas encore vraiment d'idée sur quoi ça va aboutir. J'espère y arriver. Pour GTC j'imagine que tu as du écrire un gestionnaire de cette sorte ? Si oui, tu t'es organisé comment ?

Il y avait déjà un gestionnaire de mémoire, avec un fonctionnement très simple : il n'y a jamais de libération de mémoire, il n'y a que deux "tas" qu'on peut libérer en bloc (un tas local à chaque fonction, et un qui n'est libéré qu'une fois la compilation terminée). Donc ça marche bien parce que c'est rapide et parce qu'il y a pas trop de création d'objets "inutiles"... Du coup j'y ai pas trop touché, j'ai juste amélioré un peu la granularité ^^


Mais ça dépend de ce que tu veux faire, quelle est la taille de ce que tu veux allouer, quelle est la durée de vie de tes objets, etc...

Oui, je recode un malloc et un free.
L'objectif est bien d'aller plus vite (beaucoup plus vite, le but est que ces actions soient faites en quelques opérations).
Celui de l'OS des TI68k est pas top et c'est même pas la peine d'essayer d'allouer 1000 blocs


Le mien :
- pourra allouer jusqu'à 24576 blocs presqu'instantanément,
- la taille maximale d'un bloc sera de 16 ko,
- le total maximal allouable sur l'ensemble des blocs sera de 96 ko.


Pour l'algo, c'est encore flou, je vais voir au fur et à mesure. Pour le moment, je peux dire que le gestionnaire utilise les fonctions de l'OS (malloc) pour allouer des plages de 16 ko. Ca paraît énorme mais il est réservé à certaines applications c'est pour ça.
Il découpe ces plages en "clusters" de 4 octets. L'état de ces clusters (vide, occupé) est indiqué par un immense champ de bits (pas d'esprit tordu svp ) de 4 ko.

Mais tout ceci risque d'évoluer, je commence seulement à réfléchir et à coder.

Pollux (./221) :
Il y avait déjà un gestionnaire de mémoire, avec un fonctionnement très simple : il n'y a jamais de libération de mémoire, il n'y a que deux "tas" qu'on peut libérer en bloc (un tas local à chaque fonction, et un qui n'est libéré qu'une fois la compilation terminée). Donc ça marche bien parce que c'est rapide et parce qu'il y a pas trop de création d'objets "inutiles"... Du coup j'y ai pas trop touché, j'ai juste amélioré un peu la granularité ^^

Ça ressemble aux obstacks des anciens GCC, ton histoire.

Thibaut (./218) :
Oui finalement je vais rester en C, c'est plus élégant

Si ça intéresse des gens, je suis en train d'écrire un gestionnaire de mémoire ultra rapide, qui permettra d'allouer & libérer des zones de mémoire très rapidement. C'est une surcouche au système classique malloc/free (càd qu'il utilise ces fonctions, mais par blocs de 16 ko, et il gère leur organisation interne avec ses propres méthodes).

J'ai pas encore vraiment d'idée sur quoi ça va aboutir. J'espère y arriver. Pour GTC j'imagine que tu as du écrire un gestionnaire de cette sorte ? Si oui, tu t'es organisé comment ?

Tiens ca me rappelle ~technic/

c'est ce que j'allais répondre à ./222

Kevin Kofler (./223) :

Pollux (./221) :
Il y avait déjà un gestionnaire de mémoire, avec un fonctionnement très simple : il n'y a jamais de libération de mémoire, il n'y a que deux "tas" qu'on peut libérer en bloc (un tas local à chaque fonction, et un qui n'est libéré qu'une fois la compilation terminée). Donc ça marche bien parce que c'est rapide et parce qu'il y a pas trop de création d'objets "inutiles"... Du coup j'y ai pas trop touché, j'ai juste amélioré un peu la granularité ^^

Ça ressemble aux obstacks des anciens GCC, ton histoire.

et ils font comment maintenant ?

Pollux (./225) :

c'est ce que j'allais répondre à ./222

Ca me rajeunit pas, çà

Genalib utilisait le même principe ? (je regarderai les sources demain)

Pollux (./225) :
et ils font comment maintenant ?

Garbage collection.

Thibaut (./222) :
Pour l'algo, c'est encore flou, je vais voir au fur et à mesure.

Bonne chance alors

Plus sérieusement, je ne sais pas quel usage tu comptes en faire, et peut-être que les besoins de ton application seront tels que ton malloc te conviendra parfaitement. Mais faire un "vrai" malloc (cad qui ne fragmente pas complètement ta mémoire au bout de 10 secondes, qui ne bouffe pas le double de ce dont tu as besoin, et qui reste relativement rapide) ça me semble suffisamment complexe pour mériter de googliser un peu sur le sujet : même si celui d'AMS est vraiment pourri et pas bien difficile à dépasser (encore une fois, ça reste une supposition), faire quelque chose de vraiment efficace est loin d'être évident

Elles ne sont plus valables

Je suis parti sur autre chose, en réfléchissant. De la manière dont je conçois son fonctionnement actuellement, il pourra allouer ~16300 blocs au maximum (de 4 octets chacun). La taille maximale des blocs sera de 254 octets (on est vachement retombé par rapport aux 16 ko d'hier soir ). Si uniquement des blocs de cette taille sont alloués, le nombre de blocs allouables est de 384.
Dans tous les cas, il consommera entre 8,5 ko et 102 ko (selon la quantité de blocs alloués) par tranches de 8,5 ko.

Zephir : oué

Godzil : Tu as ajouté à ton pogramme la possibilité de lire des fichiers externes ? J'aimerais bien voir les stats qu'il sort quand on lui fait traiter des données réelles.

Si ça peut te faciliter la tâche, je peux te fournir un fichier de 7000 mots séparés par des espaces et tous différents (ce sera les mots du fichier megamix.txt "parsé" par ma moulinette).

et si tu veut j'ai la liste de mot de mon motus

http://procvor.free.fr/upload/french.dco

5 letter -> [4910]
6 letter -> [10193]
7 letter -> [15990]
8 letter -> [20504]
9 letter -> [21693]
[73290] words

mais il n'y a pas d'espaces entre les mots :P

non pas encore, pas eu le temps

J'ai ajouté un paragraphe dans le post ./1 pour mieux justifier l'intérêt d'un modulo premier :

Quel est l'intérêt d'avoir une table de hachage dont la taille est une puissance de 2 ?
Cela accélère énormément le calcul final, celui que vous trouverez à la fin de chaque fonction. Le calcul d'un modulo est parmi les instructions les plus lentes à réaliser pour un microprocesseur. Quand le dénominateur d'un modulo est une puissance de 2, le calcul est sensiblement accéléré (on passe de 70 cycles processeur à 4 ou 6 cycles). Certes, la table est légèrement moins homogène, donc la recherche linéaire est un peu plus longue en moyenne (en pratique la différence d'homogénéité est très très faible, cf le comparatif du post ./216). Mais le temps gagné lors du calcul compense le temps perdu dans la recherche linéaire.Cela est particulièrement vrai quand le nombre de collisions est raisonnable, par exemple quand 10.000 chaînes ou moins sont réparties sur une table de taille 1024. D'une manière générale, il semblerait que plus la table de hachage est grande, plus on a intérêt à lui donner une taille puissance de 2. En effet, le nombre moyen de collisions diminuant, la recherche linéaire est plus rapide et le léger défaut d'homogénéité est moins sensible, donc le temps gagné dans le calcul du modulo est plus flagrant.

Dites moi si je raconte de la merde