Concours Optimisation d'une routine - Page 1

Bon, je cherche des optimisations vitesse de cette routine (primordial), la taille je m'en fous un peu)

;==========================================================
;	CompareStrings
;
;	Check if the string RefString terminated by a char of SeparatorTable is contained
;	in the string table StringTable
;	Return #item in the table, or -1 if the string isn't in the table. First item is #0
;	Put in NextChar a ptr to the next char after RefString if NextChar != NULL
;
;	input	a0	StringTable
;		a1	SeparatorTable
;		a2	RefString
;		a3	**char (NextChar)
;	output	d0.w	#item, else <0
;		(a3)	updated if a3 != 0
;	destroy	d0-d2/a0
;==========================================================
butillib@0006:
	movem.l	a1/a4,-(sp)		; Save RefString
	moveq.l	#-1,d0			; #item
\ItemLoop:
	addq.w	#1,d0			; Update #item
	movea	a2,a1			; RefString
\Loop:	move.b	(a0)+,d1		; End of string in StringTable ?
	beq.s	\CheckSeparator		; Yes, so check the separator at -1(a0)
	cmp.b	(a1)+,d1		; Compare strings
	beq.s	\Loop			; Until mismatch
\NextString:
	tst.b	(a0)+			; Else skip current string
	bne.s	\NextString
\CheckEOT:
	tst.b	(a0)			; End of StringTable ?
	bne.s	\ItemLoop		; No, continue
		moveq.l	#-1,d0		; Else return error code
		bra.s	\NoSaveNextChar


\CheckSeparator:
	move.b	(a1),d1			; Current char of RefString
	beq.s	\Quit			; #0 ? So quit, EOF is always a valid separator
	movea.l	(sp),a4			; SeparatorTable
\LoopSeparator:
	move.b	(a4)+,d2		; End of SeparatorTable ?
	beq.s	\CheckEOT		; Yes, try with the next string
	cmp.b	d1,d2			; Equal ?
	bne.s	\LoopSeparator		; No, test with next char
\Quit:
	move.l	a3,d1			; Must save *NextChar ?
	beq.s	\NoSaveNextChar		; No
		move.l	a1,(a3)		; Else save it
\NoSaveNextChar:
	movem.l	(sp)+,a1/a4
	rts

Les règles :
- d0-d2/a0-a1 peuvent être détruits, mais le résultat doit être dans d0.
- pas de smc ou de relogement
- les romcalls sont utilisables (mais bon... on parle optimisation ici )

Les données :
a0 : StringTable -> une suite de chaines C suivies d'un 0 supplémentaires : dc.b "abc",0,"def",0,0
a1 : SeparatorTable -> une chaine C contenant les séparateurs acceptés : dc.b ":?!. \n",0. '\0' est toujours un séparateur valide.
a2 : RefString -> La chaine dont on cherche une correspondance dans StringTable
a3 : **char (NextChar) -> Adresse où l'on stocke l'adresse du séparateur marquant la fin de la chaine. On y enregistre rien si a3=NULL. On peut y stocker quelque chose même si on ne trouve pas de correspondance (ça sera donc invalide, mais le succès de la fonction est vérifié avec d0, ségatif si on a pas trouvé de chaine qui matche dans la table).

Bon d'après Zerosquare, c'est assez bien foutu, mais on pense pouvoir tirer encore quelques grammes ici ou là ^^

Folco (./1) :
a0 : StringTable -> une suite de chaines C suivies d'un 0 supplémentaires : dc.b "abc",0,"def",0,0

Tu n'as pas moyen d'organiser tes données mieux que ça ?
Parce que là, ça t'oblige à faire une recherche linéaire, alors que tu pourrais faire en sorte de converger bien plus vite.
Typiquement, tu aurais combien de chaînes dans ta StringTable ? (marrant, j'aurais plutôt appelé StringTable StringsReference )

Un nombre indéterminé, dans un ordre alphabétique indéterminé. On pourrait contraindre avec des chaines triées et de même longueur pour faire de la dichotomie par exemple, mais ça fait chier pour des questions de place. Ca irait bien pour une table d'opcode par exemple, mais je veux rester générique. Restons sur ça.

Tu pourrais utiliser une table à adressage dispersé ?
Ou un arbre de recherche.

Je connais pas tout ça, ça a des chances d'être plus efficace en terme de rapidité ?

Pour ce qui est des séparateurs tu peux aussi utiliser un tableau d’entiers tel que tab[':'] == 1, tab['?'] == 1, etc,

./3 OK. Mais si tu appelles souvent ta routine avec la même StringTable, tu peux précalculer à la volée des hashValues de tes chaines, ça pourrait aider aussi

En fait je n’ai pas saisi ce que fait ton code, j’ai la flemme de le lire et de l’analyser. Est-ce que tu peux m’expliquer quel problème il résout ?

Je crois qu'il veut savoir si une String est contenue dans un ensemble de Strings.

./6 -> Tu peux préciser stp ? En clair je comprends pas ton idée ^^

./7 -> tu veux dire que je calcule une somme quand j'ai trouvé un item, pour accélérer par la suite ?

./8 -> Le but est de rechercher si une chaine StringRef suivi par un séparateur contenu dans une chaine Separator fait partie d'une table StringTable faite de chaines C dont la dernière est terminée par 2 \0.

./9 -> vala

La StringTable est construite quand ? À l’exécution ?

Pour ./6, je pensais à un tableau indexé par des codes ASCII qui contient 0 si le caractère n’est pas un séparateur ou 1 s’il est un séparateur. Comme ça pour savoir si tu as un séparateur à la fin de ta chaîne, tu prends le caractère et tu l’utilise comme un index dans le tableau. Note tu peux coder d’autres informations dans le même tableau, en réservant un bit pour chacune d’elles.

Les arbres de recherche, c’est expliqué dans ton bouquin
Il y a plusieurs variantes, que j’ai oubliées, forcément… Faut voir laquelle irait bien. Mais l’avantage c’est que ça te permet de faire ta recherche en O(log(n)) contrairement à là où tu fais du O(n*m) (où m est la longueur moyenne de tes chaînes et n le nombre de chaînes).

A moins d'avoir tout un tas de tables de 256 bytes préparées pour différentes situations, ça oblige à préparer une table avant chaque comparaison, non ? C'est ça l'idée ?

Sasume (./11) :
La StringTable est construite quand ? À l’exécution ?

Ca pourrait, mais ordinairement non. Par exemple, je m'en sers pour identifier des swictches dans une ligne de commande. Evidemment, je connais ces swictches à l'avance, donc elle est codée en dur, genre :
dc.b "abc",0
dc.b "def", 0
dc.b 0

Il y a des programmes qui calculent une fonction de hachage parfaite pour tes chaînes, ensuite il suffit de calculer la valeur de cette fonction en t'arrêtant au séparateur et de faire un switch sur le code résultant. Particulièrement efficace si tu acceptes les faux positifs (chaînes nonsens qui sont acceptées comme la chaîne qui donne le même code de hachage). Si tu veux pouvoir détecter les erreurs, il faudra quand-même comparer explicitement avec la chaîne.

Je vois le principe, mais je veux 100% de résultat vrai. Par contre, ça ne laisse qu'une seule chaine à comparer, et ça c'est bien.

Multicross...

En gros, au lieu d'avoir une bête liste toute plate, tu utilises un tableau de sous-listes dont les Strings ont toutes la même hashValue.

Tu définis une fonction calculerHashValue qui te retourne une hashValue à partir d'une String :
calculerHashValue( string s ) { retourne une hashvalue sur un intervalle donné }

Ensuite tu l'utilises pour construire un tableau de sous listes de Strings regroupées par hashValues :
tab[ 0]= contient la liste des String qui ont pour hashvalue 0
tab[ 1]= contient la liste des String qui ont pour hashvalue 1
...
tab[maxHashValue]= contient la liste des String qui ont pour hashvalue maxHashValue


Et finalement, tu appliques ton algo de recherche de strings non pas sur la liste de String entière, mais uniquement sur la sous liste de strings dont la hashvalue est identique à la hashValue calculée sur la String à rechercher => cette sous liste est dans tab[calculerHashValue(s)]


Thibaut avait codé une fonction de hash sur des strings qui semblait intéressante, et rapide : topics/536-103443-efficacite-dun-algorithme-de-hachage-de-chaines-de-caracteres (j'ai jamais regardé en détail)

./14 Excellent, comment on calcule une fonction de hachage parfaite ?

Folco > Dans une table de 256 octets tu peux stocker 8 informations différentes sur les caractères ASCII, c’est souvent suffisant. Sinon tu peux passer à 2 octets par entrées, tu seras tranquille avec 16 bits.

Ah en fait parfaite ≠ minimale… J’espère que tu ne te trouveras pas avec trop de trous…

Sasume (./17) :
./14 Excellent, comment on calcule une fonction de hachage parfaite ?

Par exemple avec gperf. C'est un logiciel libre, tu peux regarder le code.

Intéressant cette histoire de fonction de hash parfaite, mais faut voir si le surcoût¹ (éventuel, j'en sais rien) vaut la peine vis à vis de la comparaison de deux ou trois String de temps en temps.

¹ C'est un surcoût lors du précalcul, certes, mais bon, il y a aussi la taille, la complexité du code, etc. Bref, à étudier, de toute façon

Merci, pratique ce logiciel

./20 Je ne comprends pas, la table est calculée avant l’exécution du programme de toute façon

PS : Folco > Naturellement, tout ce qu'on raconte est valable uniquement si le nombre de strings dans ta liste est grand. Sinon, ça peut être plus lent que ta routine linéaire...


cross : ./21 D'après ce que j'ai lu de gperf, oui, mais Folco a l'air de vouloir un truc qui fonctionne tout seul au runtime. (Cf ./3 : tout a l'air indéterminé.)

Il y a aussi le coût du calcul de la valeur de la fonction de hachage pour chaque chaîne à tester (genre chaque opcode d'un fichier source assembleur).

Mon but a été de minimiser les lectures en mémoire, partant du principe que c'était ça qui plombait les perfs.
Dans ce cas, je vais devoir lire la chaine en entier, en testant à chaque caractère si on a affaire à un séparateur, non ? Je vais vraiment gagner du temps ?

Et en plus de ça, il y a des lookups de tableau lors du calcul du hash.

Voir ici pour ma version, mais ce n'est pas en 68000
Cependant la modification du format de la table peut potentiellement être intéressante sur ta version aussi, ça évite de devoir sauter manuellement les caractères à la fin de la chaîne.

Une version un peu plus lisible de ton code pour les habitués du 68k (syntaxe AT&T de GNU as):

# Même fonction que le code de Folco, je répète pas les commentaires :) 
#  
# entrée :      %esi : StringTable 
#               %ebp : SeparatorTable 
#               %ebx : RegString 
#               %eax : **NextChar 
# 
# sortie :      %edx : numéro de la chaîne, -1 si elle n'a pas été trouvée 
#               *NextChar mis à jour s'il n'était pas nul 
# 
# registres détruits : %ecx, %edx, %esi, %edi 
# 
Comparaison_chaines: 
        cld                             # mode post-incrémentation 
        movl    $-1, %edx               # initialise le numéro de la chaîne 
 
Boucle_chaines: 
        incl    %edx                    # incrémente le numéro de la chaîne 
        movl    4(%esi), %ecx           # récupère la longueur de la chaîne dans StringTable  
        jecxz   Chaine_non_trouvee      # si nulle, fin de la table -> la chaîne n'a pas été trouvée 
        movl    %ebx, %edi              # pointeur de comparaison 1 = RefString  
        pushl   %esi                    # sauvegarde le pointeur sur StringTable  
        movl    (%esi), %esi            # pointeur de comparaison 2 = chaîne indiquée dans StringTable  
        repe    cmpsb                   # compare les chaînes 
        popl    %esi                    # restaure le pointeur sur StringTable  
        je      Verif_separateur        # chaînes identiques -> vérifie le séparateur 
Boucle_chaines_fin: 
        addl    $8, %esi                # passe à l'entrée suivante de StringTable  
        jmp     Boucle_chaines          # 
Chaine_non_trouvee:                      
        movl    $-1, %edx               # retourne le code d'erreur 
        ret                             # 
 
Verif_separateur: 
        movl    $nb_separateurs, %ecx   # initialise le nombre de boucles 
        pushl   %eax                    # sauvegarde **NextChar 
        movb    (%edi), %al             # caractère à rechercher : dernier caractère de RefString 
        pushl   %edi                    # sauvegarde le pointeur sur StringTable  
        movl    %ebp, %edi              # bloc dans lequel rechercher : SeparatorTable  
        repne   scasb                   # recherche le caractère 
        popl    %edi                    # restaure le pointeur sur StringTable  
        popl    %eax                    # restaure **NextChar 
        jne     Boucle_chaines_fin      # caractère non trouvé -> on passe à la chaîne suivante de StringTable 
        testl   %eax, %eax              # vérifie si **NextChar = NULL 
        jz      Chaine_trouvee          # si non, rien à faire 
        movl    %edi, (%eax)            # si oui, on enregistre l'adresse du séparateur trouvé  
Chaine_trouvee: 
        ret                             # retourne le numéro de la chaîne

on s'en %tape.

Clairement ^^
Sinon, pareil que les autres, j'utiliserais une table de hachage pour ça…
Si tes données sont statiques tu peux généralement arriver à trouver quelque chose de très optimisé pour ton (tes) cas.
De même, si tu connais à l'avance tes besoins, tu pourrais faire une conversion de jeux de caractères au début pour que ce soit plus avantageux à manipuler par la suite. (Mais il ne faut pas que la conversion te coûte plus cher que ce qu'elle te fait gagner, bien évidemment ^^)
Par exemple, classifier les caractères en "séparateurs" et "non séparateurs":
0 ≤ c ≤ 127: séparateurs (tu n'en as pas forcément 128 ^^)
128 ≤ c ≤ 256: caractères toujours valides
Ici, tester si un caractère est valide revient juste à tester le bit 7, puis si c'est dans la catégorie "séparateur", tester que c'est bel et bien un des séparateurs autorisés.
Bref, ta routine en elle même a sans doute peu d'optimisations possibles (j'avoue j'ai la flemme de déchiffrer ton assembleur, et les commentaires ne m'aident pas), mais une bonne optimisation peut impliquer de changer d'algorithme "entièrement".
D'ailleurs ça me rappelle un bon article que j'ai lu il y a quelque temps: http://blogs.msdn.com/shawnhar/archive/2009/12/14/algorithm-versus-implementation.aspx

GoldenCrystal (./29) :
et les commentaires ne m'aident pas

Ca veut dire que c'est mal commenté ? Je sais pas comment faire bien, donc je suis intéressé. Sauf si c'est tout simplement que tu n'as pas vraiment mis le nez dedans.

ps -> pour l'article, on est d'accord ou pas. Changer d'algo, pourquoi pas, mais pourquoi pas rester en asm pour conserver son facteur *2 sur le compilo ?