09:13 Mot de passe oublié ?

1

Allez, je vais solliciter votre aide pour franchir les 60ko/s avec STZ,
et vous demander un petit coup de pouce afin d'optimiser une
fonction clé dans ce programme smile

Alors avis aux 68k addict !

Donc le petit jeu consiste à écrire cette fonction de hashage pour qu'elle soit
la plus rapide possible :

hash = (((A<<4) + (B<<2) + C) & 0xFFF) << 2;
resultat = p + hash;

ou A, B et C représentent 3 octets successifs dans le buffer.
Le buffeur n'est pas forcément aligné.

Vous disposez des registres a0,a1,d0 et d1 pour effectuer les opérations
Les autres registres ne doivent pas être modifié, ou alors il faut restituer
leurs états.

en entré vous avez le pointeur sur le buffer dans a2 (pointeur sur ABC), et 'p' dans a6

en sortie a1 doit contenir 'resultat'

Indiquez le nombre de cycles qu'il vous est nécessaire pour votre routine smile
Pour l'instant ma fonction fait 100 cycles, je travaille sur une version 96 cycles.

Voilà, c'est une bonne occasion pour moi d'en apprendre plus sur le 68k,
alors à vos claviers ! oui

2

int hash(char*) ....

gcc -S -O3 ...
avatar

3

Je ne sais pas quel sont ces commutateurs, mais je pense que tu es hors sujet wink
Le petit jeu consiste en une série d'environ 10 instructions asm qui répondent à ce problème pencil

EDIT : Ok, j'ai compris, c'est une bonne idée de faire travailler le compilateur
pour nous, c'est vrai smile

4

Ce qu'il te dit, c'est de regarder ce que GCC produit quand tu compiles le code C que tu as posté wink

Non testé, cycles non évalués:
move.b (a2)+,d0
lsl.w #2,d0 | A * 4
add.b (a2)+,d0 | A * 4 + B
lsl.w #2,d0 | A * 16 + B * 4, si je ne suis pas trop bourré grin
add.b (a2)+,d0 | A * 16 + B * 4 + C; peut-être que le "+" n'est pas nécessaire, suivant comment tu lis le buffer.
andi.w #0x0FFF,d0
lsl.w #2,d0
lea 0(a6,d0.w),a1 | On peut n'utiliser que d0.w, parce que les deux instructions précédentes forcent le MSB sur 16 bits à 0.

[EDIT: nan, les add.b sont faux...]
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

5

Je ne connais pas l'assembleur mais j'essaye quand même (en espérant que l'équivalent de ces instructions existent tricol) 
d0 = a2[0]
d0 <<= 2
d0 += a2[1]
d0 <<= 2
d0 += a2[2]
d0 &= 0xFFF
d0 <<= 2
a1 = a6
a6 += d0


(sinon au début j'avais écrit *a2++ avec à la fin a2 -= 2 pour restaurer, mais je ne sais pas lequel existe en assembleur entre *a2++ et a2[i] cheeky)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

6

moveq #0,d0
move.b (a2)+,d0
lsl.w #2,d0 | A * 4
moveq #0,d1
move.b (a2)+,d1 | B
add.w d1,d0 | A * 4 + B
lsl.w #2,d0 | A * 16 + B * 4
move.b (a2)+,d1 | peut-être que le "+" n'est pas nécessaire, suivant comment tu lis le buffer.
add.w d1,d0 | A * 16 + B * 4 + C
andi.w #0x0FFF,d0
lsl.w #2,d0
lea 0(a6,d0.w),a1 | On peut n'utiliser que d0.w, parce que les deux instructions précédentes forcent le MSB sur 16 bits à 0.
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

7

Tu ne respectes pas la spécification, a2 n'est pas restauré embarrassed
edit : comme je l'ai dit je ne comprends pas l'assembleur, mais pourquoi tu mets des 0 confus
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

8

Tu ne respectes pas la spécification, a2 n'est pas restauré embarrassed

Mouais, pas faux...
Peut-être veut-il réellement l'incrémenter pour avancer dans le buffer, mais si ce n'est pas le cas, utiliser successivement (a2), 1(a2) et 2(a2) à la place des trois (a2)+.

./7: je mets des 0 pour nettoyer les registres smile
Il est impossible de faire des additions seulement sur les 8 bits de poids le plus faible (c'est ce que fait ./4, mais ça produit des additions tronquées: code incorrect). Il faut donc utiliser des opérations 16 bits, mais comme on ne charge que 8 bits à la fois depuis a2, et qu'on ne peut pas faire la supposition que les bits 8 à 15 valent 0, il faut effacer ces bits explicitement, pour être sûr qu'ils ne vont pas fausser l'addition.
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

9

Bon j'essaye de deviner la signification du code de Lionel et de l'améliorer trigic (je suppose que si tu mets des 0 c'est parce que le move.b ne modifie pas l'octet du haut ? edit : cross ^^) 
moveq #0,d0 
move.b (a2)+,d0 
lsl.w #4,d0 | A * 16 
moveq #0,d1 
move.b (a2)+,d1 | B
move.b (a2)+,d0 | donc si j'ai bien compris ça fait A * 16 + C
[edit : en fait non, il faudrait que ça soit 256 pour que ça marche, pas 16 :D]
lsl.w #2, d1 | B * 4
add.w d1,d0 | A * 16 + B * 4 + C
andi.w #0x0FFF,d0 
lsl.w #2,d0 
lea 0(a6,d0.w),a1
Et hop !
edit : ah non merde 16 c'est un demi-octet seulement triso (j'oublie toujours qu'un octet = DEUX chiffres hexa cheeky)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

10

Je propose une table pré-calculée tripo (pas de contrainte de mémoire si j'ai bien lu le post 0 gni)

Sinon, sérieusement : es-tu bien certain que cette routine est celle à optimiser ? Ça serait peut être plus profitable d'utiliser une fonction de hashage plus efficace par exemple (je dis ça comme ça, elle est peut être déjà très bonne)

11

Wouaou !! Bravo Lionel, même en ajoutant un move.l a2,a0 au début pour préserver a2,
j'arrive à 90 cycles, génial smile

Avec le compilo j'arrive à 106cycles, bofbof :/

Sally -> c'est la bonne logique, mais tout se joue sur l'asm justement smile

12

Voila comment GCC optimisé ça en -O3 : 

void _main(void)
{
	unsigned short hash;
	unsigned char *buffer;
	unsigned long resultat;
	unsigned long p = 0;
	
	hash = (((buffer[0]<<4) + (buffer[1]<<2) + buffer[2]) & 0xFFF) << 2;
	resultat = p + hash; 
}

>>
resultat

__main:
	rts

trigic cheeky
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.

13

trilove
avatar

14

Pen^2 (./10) :
Je propose une table pré-calculée tripo (pas de contrainte de mémoire si j'ai bien lu le post 0 gni)

Sinon, sérieusement : es-tu bien certain que cette routine est celle à optimiser ? Ça serait peut être plus profitable d'utiliser une fonction de hashage plus efficace par exemple (je dis ça comme ça, elle est peut être déjà très bonne)


lol, oui, y'a peut-être mieu comme fonction de hashage, mais celle que j'ai créé
est déjà bien optimisée, les meilleures que j'ai trouvé sur le net
et qui rentrent dans mes critères pesaient 170 cycles !!!

15

move.b (a2)+,d0 | donc si j'ai bien compris ça fait A * 16 + C
Non, ça remplace les 8 bits de poids faible de d0 par la valeur de C wink
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

16

oui oui, cf. edit, j'ai juste confondu 4 et 8 triso (ça marcherait si A avait été décalé de 8 et non de 4, c'est bien ça ?)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

17

En effet smile
Mais de toute façon, vu que les shifts ne sont pas très rapides sur cette ISA (contrairement à l'ARM, par exemple), il est probablement mieux de faire deux lsl.w #2, comme je l'ai fait.
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

18

Bon et sérieusement gcc -O3 genere ça : 

#include <tigcclib.h>

// Main Function

long hash(char *buffer asm("%a2"), long p asm("%a6"))
{
	volatile unsigned short hash;
	hash = (((buffer[0]<<4) + (buffer[1]<<2) + buffer[2]) & 0xFFF) << 2;
	return p + hash; 
}

void _main(void)
{
	
}


>>> 

hash:
	subq.w #4,%sp
	move.l %a2,-(%sp)
	move.b 1(%a2),%d0
	ext.w %d0
	add.w %d0,%d0
	add.w %d0,%d0
	move.b (%a2),%d1
	ext.w %d1
	lsl.w #4,%d1
	move.b 2(%a2),%d2
	ext.w %d2
	add.w %d2,%d1
	add.w %d1,%d0
	and.w #4095,%d0
	add.w %d0,%d0
	add.w %d0,%d0
	move.w %d0,6(%sp)
	move.w 6(%sp),%d0
	and.l #65535,%d0
	moveq #8,%d1
	add.l %sp,%d1
	add.l %d1,%d0
	move.l (%sp)+,%a2
	addq.w #4,%sp
	rts
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.

19

Tu es sûr de vouloir utiliser (signed) char ?
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

20

Lionel Debroux (./17) :
En effet smile
Mais de toute façon, vu que les shifts ne sont pas très rapides sur cette ISA (contrairement à l'ARM, par exemple), il est probablement mieux de faire deux lsl.w #2, comme je l'ai fait.


Et le compilateur nous dit qu'on peut faire encore mieu avec 2 add smile
En théorie on peut faire descendre ta solution à 86 cycles, extra !!!

21

./17 > ok happy

Par contre j'ai l'impression que le premier moveq #0 est superflu, parce que les bits en trop sont de toute façon nettoyés par le andi de la fin, non ? Edit 2 : oui si il me semble que ça marche...
stfox (./20) :
Et le compilateur nous dit qu'on peut faire encore mieu avec 2 add smile.gif
Ah carrément ? le shift doit être vraiment lent alors, en effet cheeky
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

22

Lionel Debroux (./19) :
Tu es sûr de vouloir utiliser (signed) char ?

Non c'est une erreur

Edit: c'est pas mieux
Result
Signed                        		|		Unsigned
					|
hash:                        		|		hash:
	subq.w #4,%sp            	|			move.l %a2,-(%sp)
	move.l %a2,-(%sp)        	|			move.b 1(%a2),%d0
	move.b 1(%a2),%d0        	|			lsl.w #2,%d0
	ext.w %d0                	|			and.w #1020,%d0
	add.w %d0,%d0            	|			clr.w %d1
	add.w %d0,%d0            	|			move.b (%a2),%d1
	move.b (%a2),%d1         	|			lsl.w #4,%d1
	ext.w %d1                	|			clr.w %d2
	lsl.w #4,%d1             	|			move.b 2(%a2),%d2
	move.b 2(%a2),%d2        	|			add.w %d2,%d1
	ext.w %d2                	|			add.w %d1,%d0
	add.w %d2,%d1            	|			and.l #4095,%d0
	add.w %d1,%d0            	|			moveq #4,%d1
	and.w #4095,%d0          	|			add.l %sp,%d1
	add.w %d0,%d0            	|			add.l %d1,%d0
	add.w %d0,%d0            	|			lsl.l #2,%d0
	move.w %d0,6(%sp)        	|			move.l (%sp)+,%a2
	move.w 6(%sp),%d0        	|			rts
	and.l #65535,%d0         	|		
	moveq #8,%d1             	|		
	add.l %sp,%d1            	|		
	add.l %d1,%d0            	|		
	move.l (%sp)+,%a2        	|		
	addq.w #4,%sp            	|		
	rts


le code en C :
code
unsigned long hash(unsigned char *buffer asm("%a2"), unsigned long p asm("%a6"))
{
	return p + (((buffer[0]<<4) + (buffer[1]<<2) + buffer[2]) & 0xFFF) << 2; 
}
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.

23

oui, bien vu sally !

24

C'est ma question ou ma réponse à moi-même (edit) qui est bien vue ? cheeky
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

25

lol -> bien vu pour le moveq en trop ,

alors en regroupant toutes les propositions, on arrive à ce code qui fait 80 cycles !!!

move.l a2,a0
move.b (a0)+,d0
add.w d0,d0
add.w d0,d0
moveq #0,d1
move.b (a0)+,d1 ; B
add.w d1,d0 ; A * 4 + B
add.w d0,d0
add.w d0,d0
move.b (a0),d1
add.w d1,d0 ; A * 16 + B * 4 + C
andi.w #$0FFF,d0
add.w d0,d0
add.w d0,d0
lea 0(a6,d0.w),a1

26

Le résultat de gcc est quand meme interessant : 

hash:
	move.b 1(%a2),%d0
	lsl.w #2,%d0
	and.w #1020,%d0
	clr.w %d1
	move.b (%a2),%d1
	lsl.w #4,%d1
	clr.w %d2
	move.b 2(%a2),%d2
	add.w %d2,%d1
	add.w %d1,%d0
	and.l #4095,%d0
	moveq #4,%d1
	add.l %sp,%d1
	add.l %d1,%d0
	lsl.l #2,%d0

	rts


(je vais l'optimiser un poil)
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.

27

ouai, y'a de bonnes idées, mais il utilise des instructions trop lourdes : lsl, and.l
ca coute cher !

28

Avec cette optimisation de Lionel, Sally et gcc, on approche les 58ko/s au lieu de 55ko/s smile
C'est excellent pour ce simple petit morceaux de code.

29

add.w dn,dn + add.w dn,dn c'est pas plus rapide qu'un lsl.w #2,dn ? 4+4 vs 6+2+2 ? A vérifier (68kum.pdf), ch'sui pas un spécialiste des cycles.

30

./20 ? cheeky
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#
Aide Charte Contacts Crédits Réalisé avec yAronet 56 ms