Re: Meilleurs algo d'un test par bouding box

[Stef]

Bon fano, laisse le z80 de côté, et mets toi à la PCE   

Le pipeline comme tu l'appelles existe sur quasi tout les CPU, sur Z80, sur 68000... je dois admettre que je suis étonné cependant qu'il y ait autant de niveau sur le 6502 vu la simplicité de celui ci, je vois mal comment tu peux faire rentrer 5 stages de pipeline dans un CPU qui contient 3000 transistors tout compris.
Et puis pour le rapport de 1/4 comparé au Z80, ils y sont allé un peu fort non  


J'ai trouvé ça, tiré du site C= Hacking (une vrai bible pour tout développeur) et donc par des pro du 6502 :

The 6502 CPU was designed to be a low cost 8 bit CPU. It is fairly
cheap to interface to and will quickly access cheap "slow" memory. It
is also very quick and responsive to interrupts. It can perform 8 bit
binary and BCD addition with carry. The Z80 CPU was designed to be the
ultimate 8 bit CPU. It has several 8 bit internal registers which can
be used in 16 bit pairs. It has a full instruction set that includes
some nibble oriented instructions and a 16 bit add. On average a 1 Mhz
6502 is about as effective as a 2 Mhz Z80, and Z80s are generally
available in faster speeds. The C128 has a Z80 CPU that could be used
for numerical work, but it was poorly integrated into the C128 and
offers us no advantage over the 6502 (other than executing CP/M and
other Z80 code). Neither CPU has a multiply instruction. The fastest
way to multiply with a Z80 is with the simple binary shift and add
method. However, this is not true with the 6502! The fastest way to do
math on a 6502 is by using table look ups. This opens the door for
creative programming solutions.

[Invité]

Le pipeline comme tu l'appelles existe sur quasi tout les CPU, sur Z80, sur 68000... je dois admettre que je suis étonné cependant qu'il y ait autant de niveau sur le 6502 vu la simplicité de celui ci, je vois mal comment tu peux faire rentrer 5 stages de pipeline dans un CPU qui contient 3000 transistors tout compris.
Et puis pour le rapport de 1/4 comparé au Z80, ils y sont allé un peu fort non   

Je ne prends pas ça au pied de la lettre, je l'ai posté car pour une foi, je trouve un truc "officiel" sur ce sujet ..
Ils parlent du pipe du 65xx comme une exécution en parallèle, et non comme de la prédiction . 
Je pense que le facteur 1/4 est vrai dans certains cas, mais pas en général,ça semble être surtout pour les lectures/écritures dans la ram ..

On average a 1 Mhz 
6502 is about as effective as a 2 Mhz Z80, and Z80s are generally 
available in faster speeds.

Je pense que ce facteur est bcp plus réaliste aussi pour une estimation générale.

[fanoplusplus64K]

Et puis pour le rapport de 1/4 comparé au Z80, ils y sont allé un peu fort non  

Réponse en dessous  

On average a 1 Mhz
6502 is about as effective as a 2 Mhz Z80, and Z80s are generally
available in faster speeds.

Façon, il est très difficile de comparer deux CPU sans tenir compte du contexte machine.Si tu veux vraiment comparer Z80 et 6502 de génération équivalente, tu les mets sur un montage équivalent avec une flash de 16K (pour stocker prog et resultats), 16K de SRAM (pour simplifier le montage), un compteur temps et un petit display (une LED suffit) pour indiquer la complétion du code.Tu leur fais faire diverses bouts de code comparatifs et là tu peux vraiment avoir un point de comparaison...

The fastest
way to multiply with a Z80 is with the simple binary shift and add
method. However, this is not true with the 6502! The fastest way to do
math on a 6502 is by using table look ups. This opens the door for
creative programming solutions.

Ha, bon ?! il n'est pas possible d'utiliser des LUT pour accélerer les multiplication sur Z80 ?  Des LUT t'en mange à toutes les sauces sur Z80, justement car tu as des registres 16bits faciles à utiliser (notamment le très efficace jp (HL).Ce sont des pros de 6502, pas sur que ça soit le cas pour le Z80.

[Invité]

je pensais que les accès ram/rom étaient lents sur le z80 ??
Ils disent pas que c'est pas possible, juste que c'est pas la méthode la plus rapide sur le z80 .

[Invité]

@fano: tu as reçu la doc ??

[fanoplusplus64K]

Tu peux faire plus rapide avec des jump tables, il y a un exemple sur cpcwiki.

Oui, j'ai bien reçu ça , je viens de te répondre par MP   
Amusante comme machine, la DMA vram/vram ne coute rien au CPU si j'ai bien compris, on sait à peu près le débit qu'elle a par canal ?

[Stef]

Tu peux faire plus rapide avec des jump tables, il y a un exemple sur cpcwiki.

Oui, j'ai bien reçu ça , je viens de te répondre par MP   
Amusante comme machine, la DMA vram/vram ne coute rien au CPU si j'ai bien compris, on sait à peu près le débit qu'elle a par canal ?

Je pense qu'ils veulent surtout dire que c'est difficilement imaginable sans lookup table sur 6502 (trop long) contrairement au Z80. Et les accés mémoires sont quand même très rapide sur le 6502 mais je dois admettre avoir un peu de mal à comprendre comment les lookup tables peuvent être si efficace avec des registres d'index 8 bits :-/

[fanoplusplus64K]

C'est une question que je me pose depuis le début, il est possible de faire un adressage indirect avec l'accumulateur sur un registre d'index ?

[Invité]

Oui, j'ai bien reçu ça , je viens de te répondre par MP   

Oui j'ai vu   

Amusante comme machine, la DMA vram/vram ne coute rien au CPU si j'ai bien compris, on sait à peu près le débit qu'elle a par canal ?

A ce niveau la MD est mieux car le DMA peux aussi faire des transferts rom/ram -> VRAM
Mais elle est bcp plus limité hors vblanc .
Je connais pas les débits, et ils sont dépendants de la réso, 
256 = 5.369mhz 
320 = 7.159mhz
512 = 10.739mhz
Et sont surement inférieurs à 6 cycles/byte (il me semble que c'est 4 cycles) .
Une astuce consiste à Faire du DMA pendant le vblanc et passer la réso @512 pixel pour accélerer les accès/transferts vers la VRAM .

Je pense qu'ils veulent surtout dire que c'est difficilement imaginable sans lookup table sur 6502 (trop long) contrairement au Z80. Et les accés mémoires sont quand même très rapide sur le 6502 mais je dois admettre avoir un peu de mal à comprendre comment les lookup tables peuvent être si efficace avec des registres d'index 8 bits :-/

En les décomposant en parties HIGH/LOW si sur 16 bit je suppose .
Ca te donne un tableau en 2D sur 8 bit .

C'est une question que je me pose depuis le début, il est possible de faire un adressage indirect avec l'accumulateur sur un registre d'index ?

Si j'ai bien compris ta question ,c'est oui:
lda ( ZP ) , Y
lda ( ZP , X )
ZP étant une variable en zero page et contenant une adresse 16 bit.

[fanoplusplus64K]

Au pire , si le code est en ram , il n'est pas possible de faire une automodification du code ?

Tiens , un exemple de multiplication avec lut sur 6502 , je dois avouer que je suis perdu avec la syntaxe   
Si j'ai compris , il utilise une variable en page 0 pour faire la partie basse de l'adresse.

http://everything2.com/title/Fast+6502+multiplication

Et un exemple sur Z80 avec des jump tables :

http://www.cpcwiki.eu/index.php/Programming:Ultrafast_Multiplication

[Invité]

Au pire , si le code est en ram , il n'est pas possible de faire une automodification du code ?

Bien sur, et c'est encore plus efficace si ton projet est sur CD, car là les données sont sur les 64/128/256 ko de RAM(tout dépend de la version du CD-ROM), et c'est encore plus simple et rapide .

Tiens , un exemple de multiplication avec lut sur 6502 , je dois avouer que je suis perdu avec la syntaxe   
Si j'ai compris , il utilise une variable en page 0 pour faire la partie basse de l'adresse.

Là je pouvais pas vous en dire plus, j'ai pas eu encore à faire de vrais mul/div dans mes projets .

Tiens , un exemple de multiplication avec lut sur 6502 , je dois avouer que je suis perdu avec la syntaxe 

Normal, c'est très différent d'un type Z80/68000, mais on s'y fait vite.
Dés que tu es arrivé à te mettre en tête que la ram est ton amie   .

EDIT: C'est bien ce que je pensais, les tables sont séparées en partie LOW/HIGH .
Et 90 cycles max pour du 16x16 bit, c'est pas mal je trouve .

[Stef]

Normal, c'est très différent d'un type Z80/68000, mais on s'y fait vite.
Dés que tu es arrivé à te mettre en tête que la ram est ton amie   .

EDIT: C'est bien ce que je pensais, les tables sont séparées en partie LOW/HIGH .
Et 90 cycles max pour du 16x16 bit, c'est pas mal je trouve .

Ce n'est pas du 16x16 ça serait trop beau, c'est 90 cycles pour du 8x8=16
C'est déjà pas mal je trouve !
J'ai du mal à comprendre la routine Z80, on dirait du 8x16=8 (ce qui n'est pas très pratique, j'aurais plutot vu du 8x16 = 16). Et c'est très compliué de compter les cycles avec la jump table dynamique...

Sinon sur 68000 c'est 72 cycles max (entre 30 et 72 il me semble selon le nombre de bits à 1 dans le facteur) pour du 16x16=32, ça parait long mais pas tant que ça vu la complexité de l'opération.

[Invité]

Ah oui effectivement c'est du 8x8=16   
Pour le 68000 je doutait qu'il serait plus rapide dans ce genre d'opérations, et j'avais d'ailleurs vu un 70 cycles pour du MULS/MULU ..

Le version Z80, est légèrement illisible  ..  
J'aimerai bien savoir combien de cycles elle prend, peut être que fano la connait celle là .

[fanoplusplus64K]

C'est difficile de dire le nombre de cycles car chaque nombre est un cas particulier.
Tu as aussi d'autres routines de multiplication ici , une version avec table de 16K qui fait 20µs soit 80 cycles CPC et 28µs (112 cycles CPC) avec une table de 1K (une adaptation de la version 6502 que j'ai posté).Sur CPC , le Z80 roule avec le frein à main,ce qui te coute entre 15% et 25% de plus que sur un Z80 en usage normal (rien à voir avec la fréquence, le Gate Array bloque le Z80 pendant certains cycles un peu comme sur MSX)

Pour revenir à ce qui est dit plus haut , ces versions avec lut sont nettement plus rapides que les version utilisant les décalages de bits.

[Stef]

Vraiment interessante toute ses routines de multiplication sur ces vieux CPU, le Z80 s'en sort pas mal on plus

[Invité]

Effectivement, c'est vraiment pas mal sur le Z80 ..

Pour les problèmes de cycles bloqués, je suppose que le spectrum n'a pas ce genre de soucis ??

[fanoplusplus64K]

de mémoire sur le spectrum, seule la vram est affectée hors vbl/hbl.sur le pcw, seuls les premiers 128k sont concernés.

[beddy]

Super intéressant merci pour ces trucs man

[Invité]

Je déterre un peu, j'ai trouvé sur un site dédié à la prog C64 une routine de détection comme celle de stef, mais pour 6502/6510 : http://codebase64.org/doku.php?id=base:sprite_collision_detection

Code:

ldx #$00
loop: lda spritey2
 cmp spritey1+1,x
 bcc skip //player above enemy
 
 lda spritey2+1,x
 cmp spritey1
 bcc skip //enemy above player
 
 lda spritex1+1,x
 sec
 sbc spritex2
 lda spritemsb1+1,x
 sbc spritemsb2
 bcs skip //enemy on player's left
 
 lda spritex1 //player on enemy's right?
 sec
 sbc spritex2+1,x
 lda spritemsb1
 sbc spritemsb2+1,x
 bcc hitbysprite //no, boxes hit each other
 
skip: inx
 cpx #$07
 bne loop
 rts

72 cycles(hu6280) max si détection, en cycles 6502 c'est moins (dans les 60),c'est sur 16 bits sur X .

Bon qui fait mieux ??

[Invité]

Code:

 rep #$20
 
 lda MEM_TEMP+14 ;position x
 sec
 sbc #32
 sta MEM_TEMP+4
 clc
 adc #48
 sta MEM_TEMP+6
 
 
 lda MEM_TEMP+12 ; position y
 sec
 sbc #32
 sta MEM_TEMP
 clc
 adc #32
 sta MEM_TEMP+2
 
 sep #$20

Code:

       ldy MEM_OAM+$10+\1
 lda s_perso+_y,y
 
 cmp MEM_TEMP
 bmi +
 
 cmp MEM_TEMP+2
 bpl +
 
 lda s_perso+_x,y
 cmp MEM_TEMP+4
 bmi +
 
 cmp MEM_TEMP+6
 bpl +

 stz MEM_TEMP+8
 sty MEM_TEMPFUNC
 rts
 +:

Voila mon code pour une Hitbox ou collision.
Pour les collisions c'est pareil mais je duplique le 'dernier code 4 fois' mais comme on peut aller que dans 2 direction en même temps le code est lu que 2 fois max.

Niveau cycle :
premier code : 26
deuxième code: 50
76 cycle pour une hitbox ou une collision (une direction) , collision deux direction (genre haut /droite) fait 126 cycle.
donc cela dépend si on compte initialisation des valeur ou pas
D'un coter on peut considérer 50 cycle comme le plus petit , si j’enlève les variables temporaires et que je met directement les valeurs que je stockerais en mémoire (en immediate ça réduit pas mal aussi).

[vingazole]

Le code que vous proposez, c'est pour des coordonnées x,y en 8 bits ou en 16 bits ?

[Invité]

Le mien marche avec les deux , je crois que je peux le transcrire en z80 (je crois que je l'avais deja fait ).

[Invité]

Le code que vous proposez, c'est pour des coordonnées x,y en 8 bits ou en 16 bits ?

X 16 bits et Y 8 bits, mais tu peux proposer aussi en 8 bit pour X/Y, ça permet de voir les gains si tu n'as pas besoin de 16 bits .

76 cycle pour une hitbox ou une collision (une direction) , collision deux direction (genre haut /droite) fait 126 cycle.
donc cela dépend si on compte initialisation des valeur ou pas 

il est là le dilemme,car même si il n'est pas dans ta routine de test, il est quelque part dans ton jeu, donc va forcement bouffer les cycles gagnés dans le test ailleurs dans la frame .
Donc pour moi ça compte, mais bon ..
Sur la routine que j'ai posté, le total est de 153 cycles Max avec l'init(hors boucle de test),mais même dans le min, tu prends en plus les 81 cycles d'init dans ta frame  .

L'idéal est de tout compter et d'expliquer, pour voir aussi les approches de chacun pour ce type de test .

[Stef]

Il me semblait qu'on avait déjà bien torché ces histoires d'algo de collision et qu'on avait obtenu des bons résultats avec différents CPU. Aussi l'init n'a aucun impact, je ne comprend pas pourquoi tu persistes a vouloir compter les cycles d'init. Le calcul des collisions n'est critique que si tu as beaucoup de collisions a calculer dans ton jeu (comme dans un shump) dans quel cas tu vas toujours traiter tes collisions par boucle... Donc je dirais même que ton calcul de cycle n'est valable que dans ce cas de gestion par loop. Si tu prends une collision isolée ça n'a aucun intérêt.

[Invité]

Il est vrai que l'init peut être compter entre parenthèse  mais le cas du shoot them up tu initialise qu'une fois pour test toute les possibilités , genre init + (hitbox)tir*10 (si tu as 10 objet a traiter).

[Stef]

Oui bien sur, et c'est toujours dans ce cadre qu'il est intéressant de comparer le nombre de cycle. On s'en fout de connaitre le nbr de cycles pour un test de collision isolé, ce qui est intéressant c'est d'avoir le coût d'un test de collision mais dans un cas où tu en as beaucoup (et donc avec une gestion par boucle)

[Invité]

Tout dépend de ce que vous entendez par init ??
Je parle pas du fait de charger les registres,mais des routines qui pré mâchent pour le test .
Un tri, se ferra à chaque frame, sur l'exemple que j'ai donné aussi, l'algo pre-calcule à chaque frame les box des sprites en fonction de leur position(d'où l'init de 81 cycles/frame) , pour simplifier le test par le suite .