C-64 vs CPC vs Atari vs MSX vs autres 8bits

J’ouvre ici le post pour éviter de polluer l’autre   Heu, je ne savais pas quoi donner comme titre …

 

edit Jim : Ce sujet est un split du sondage ‘Quels étaient les meilleurs ordinateurs 8 bits et pourquoi ?‘ qui commençait à devenir compliqué à suivre.

Sujet

[hlide Level 2Messages : 53]

Juste histoire de m’amuser un peu, j’ai récris en C/C++ le programme :
– avec un algorithme de recherche de nombre premier optimisé pour virer le calcul du SQR qui est à mon avis pas nécessaire (parce que ça revient au même de vérifier que le quotient devient plus petit que le diviseur pour valider un nombre premier),  et pour ne pas à avoir à diviser pas des nombres non premier (à condition de stocker les nombres premiers dans un tableau). A noter que SQR(1000) fait un peu moins de 32 donc une division 16-bit par un diviseur 8-bit fera largement l’affaire à coder en assembleur. Cet algorithme devrait être plus facile à réécrire en assembleur.
– en gardant l’algorithme utilisé en BASIC pour servir de comparaison lors de la mise au point.
– le reste en C++ pour lancer les tests qui vérifie la validité de l’algorithme optimisé.
– Les deux algorithmes sont écrits comme du C avec des GOTO pour être le plus proche de ce que ce serait traduit en assembleur – il manque juste l’implémentation de la division 16-bit par 8-bit que l’on peut trouver sur Internet pour les différents processeurs.

Probable que personne ne viendra relever le défi en assembleur et que gibs gardera bien ses 500 € 

Le code : retiré parce que ce forum n’est pas f*tu de le présenter correctement. Voilà, je boude !  

[gibs Level 9Messages : 978]

@hlide

Ahah
Mais sinon, vous pensez que le CPU du C64 est plus performant que celui de l’Amstrad en dehors de ce test ?

Team Apollo

[hlide Level 2Messages : 53]

Je n’en pense rien. Je connais moins bien le 6510 que le Z80. Je sais que le Z80 bouffe énormément de cycles par instructions faute d’avoir un pipeline. Le 6809 est clairement plus rapide que le Z80 à fréquence égale grâce à son séquenceur qui est cablé (comme les RISC) et non micro-programmé (comme les CISC) et en plus il incorpore une instruction de multiplication en hardware.

Par exemple un ADDA 16 en 6809 prend 3 cycles alors qu’un ADD A, 16 en Z80 prend 7 cycles. De même, l’accès mémoire ne prend qu’un cycle avec le 6800/6809, contrairement au Z80.

Pour revenir au 6510 du C64 et au Z80 du CPC :

– BNE nécessite 2 cycles sans saut si la condition est fausse sinon 3 avec saut. JP NZ nécessite 4 cycles sans saut sinon 10 avec saut : BNE / 2 et 3 cycles à 982 kHz, soit 2.03 ns et 3.05 ns. JP NZ / 4 et 10 cycles à 4 MHz, soit 1 ns et 2.5 ns.  Il faut mentionner qu’un saut « BNE » qui franchit une limite de 256 octets, nécessite un cycle d’horloge supplémentaire.

– « INC $ nnnn » ne nécessiste que 6 cycles alors que les deux instructions Z80 nécessaires pour le simuler, « LD HL, $ nnnn; INC (HL) » nécessiste 21 cycles : INC / 6 cycles à 982 kHz, soit 6.11 ns. LD;INC / 21 cycles à 4 MHz, soit 5.25 ns. Mais si le premier « LD » peut être seulement fait au moment de l’initialisation comme en début d’une séquence d’incrémentation de 2 par exemple : INC;INC / 12 cycles à 982kHz, soit 12.22 ns. LD;INC;INC / 32 cycles à 4 MHz, soit 8 ns.

Conclusion : il semblerait bien que la fréquence du Z80 du CPC l’emporte sur les cycles plus courts du 6510 du C64. Mais une fois de plus, c’est sans compter sur la qualité du code et l’ingéniosité de son développeur.

[PZAWA Level 6Messages : 316]

hlide wrote:

Probable que personne ne viendra relever le défi en assembleur et que gibs gardera bien ses 500 € Le code : retiré parce que ce forum n’est pas f*tu de le présenter correctement. Voilà, je boude !

Si si moi je relève le défi !! 1000 premier nombre premier à la volée et table de precalcule dans l’exécutable interdit. il faut juste que je trouve le temps espérons que cette semaine (avec ce premier Mai ça va peut-être le faire) enfin toujours est t-il que j’utiliserai une autre approche que toi. Non pas que je veuille que gibs perde ces 500 euros mais si ensuite quelqu’un corrige la version Z80 (qui par moi sera forcement pourri) ça peut devenir intéressant ….

[PZAWA Level 6Messages : 316]

hlide wrote:

Ca biaise parce que c’est un test idiot qui mélange algorithme et présentation du résultat. Un test plus intelligent aurait séparé l’algorithme en enregistrant les résultats dans un tableau (ici, 1000 élément) pour pouvoir en mesurer le temp pris, puis on présente le résultat dans un deuxième temps. On veut un algorithme qui calcule le plus vite, et après un IHM pour consulter les résultats le temps qu’on a besoin. Je ne comprends pas en quoi le fait de faire un PRINT devrait compter dans la performance globale… tu fais des jeux avec des PRINT ?

Évidement que c’est un test idiot mais moi je m’en fiche je le prend comme un benchmark BASIC (où l’instruction PRINT est plus que courante). Et puis oui j’ai du faire des jeux avec des PRINT et pourquoi pas ?

hlide wrote:

avec un algorithme de recherche de nombre premier optimisé pour virer le calcul du SQR qui est à mon avis pas nécessaire (parce que ça revient au même de vérifier que le quotient devient plus petit que le diviseur pour valider un nombre premier), et pour ne pas à avoir à diviser pas des nombres non premier (à condition de stocker les nombres premiers dans un tableau)

Je viens de faire quelques tests un peu comme toi (c’est a dire tenter divers implémentation dans un langage de haut niveau pour voir quelques approches) et, selon moi, SQRT est indispensable pour aller vite … mais comme je n’ai pas vu ton code je peux me planter Sinon, je viens d’ouvrir mon bouquin de référence d’Algo: pour les 1000 nombres premier et avec l’approche tableau, il existe un grand classique: le crible d’Ératosthène et il est relativement simple à implémenter en ASM et sera sans doute le plus rapide (ou pas ?) mais je préfère garder l’approche du prog basic plus marrant et qui selon moi est correct il faut juste modifier les deux boucles FOR pour sauter les nombre paires et si on veut afficher que  les nombres en dessous de 1000 rajouter ton approche tableau comme optimisation supplémentaire.  Toujours est-il que j’ai presque tout pour tenter maintenant l’implémentation en ASM. Demain, cela risque d’être dure donc plutôt pour le weekend prochain je devrais avoir une première esquisse sous c-64

gibs wrote:

Ahah Mais sinon, vous pensez que le CPU du C64 est plus performant que celui de l’Amstrad en dehors de ce test ?

Perso dire que l’un est plus performant que l’autre me gonfle: ce sont vraiment deux approches différentes l’un est orienté registre (le Z80) et l’autre orienté mémoire (Le 6502). Théoriquement un z80 à 4mhz sera plus rapide qu’un 6502 à 1mhz, en pratique ça dépends de ce que l’on fait et comment on le fait et là je ne suis pas assez expérimenté en z80 pour pouvoir juger. Ce qui est certain c’est que le jeu d’instruction du Z80 est plus puissant là il n’y aucun doute. Par contre l’approche mémoire du 6502 donne des possibilités d’optimisations assez extraordinaire. Mais quand on commence avec ce processeur alors qu’on en a connu d’autres plus orientés registres, il y a vraiment de quoi s’arracher les cheveux

[hlide Level 2Messages : 53]

Programme tel que fait celui en basic :

int compute_n()
{
    int calculations = 0;

    unsigned short n = 1; // number of found primes
    unsigned short i = 3; // dividend
    unsigned short j;     // divisor
    unsigned short q;     // quotient
    unsigned short r;     // remainder
    unsigned short m;     // limiter

    prime_n[0] = 2;

next_dividend:
    j = 2;

    m = unsigned short(sqrt(i)) + 1;

next_divisor:
    // both should be doable with one "function" returning both q and r
    q = i / j;
    r = i % j;

    ++calculations;

    if (r == 0) goto skip_dividend;

    if (++j <= m) goto next_divisor;

    prime_n[n++] = i;

skip_dividend:
    if (i++ < MAX) goto next_dividend;

    count_n = n;

    return calculations;
}

Résultat sur mon PC :
Starting naive algorithm... 1229 primes, 118755 calculations within 456882 ns.

Et enfin le programme optimisé :

int compute_o()
{
    int calculations = 0;

    unsigned short n = 1; // number of found primes
    unsigned short i = 3; // dividend
    unsigned short j = 0; // prime index
    unsigned short d;     // divisor
    unsigned short q;     // quotient
    unsigned short r;     // remainder

    prime_o[0] = 2;

next_dividend:
    j = 0;

next_divisor:
    d = prime_o[j];

    // both should be doable with one "function" returning both q and r
    q = i / d;
    r = i % d;

    ++calculations;

    if (r == 0) goto skip_dividend;

    // quotient smaller than divisor? no need to continue with next divisor (equivalent to 'd > sqrt(i) + 1')
    if (q <= d) goto keep_dividend;

    ++j;

    goto next_divisor;

keep_dividend:
    prime_o[n++] = i;

skip_dividend:
    if (i++ < MAX) goto next_dividend;

    count_o = n;

    return calculations;
}

Résultat sur mon PC :
Starting optimized algorithm... 1229 primes, 44848 calculations within 240464 ns.

Comme tu peux voir moins de calculs et je n’ai pas SQR à faire parce que ça revient à s’assurer que le quotient devient plus petit que le diviseur pour dire que ce n’est plus la peine de tester avec des diviseurs plus grands dans la boucle de division. Un simple CMP contre un SQR pour le même résultat, il n’y a pas photo.

ATTENTION, 1229 c’est pour 10000 nombres et non 1000 ! 10000, c’est pour mieux mettre en évidence le gain acquis en temps et la réduction des calculs avec la version optimisée.

[PZAWA Level 6Messages : 316]

ok merci hlide   Je suis bête: j’aurai du lire plus attentivement ton explication   Lorsque j’aurai fait l’implémentation j’essaierai egalement ton approche et a ce moment on verra si je me suis planter ou pas car dans mon approche j’évite la division euclidienne (vraiment trop coûteuse) et un sqrt me sera dans ce cas indispensable mais il est fort possible que ton approche l’emporte  

PS: beein il est bien présenté le code sur ce forum …

[hlide Level 2Messages : 53]

Oui, bizarement, il n’a pas fait trop de chichi pour cette fois quand j’ai retenté avec un bout de code seulement.

Je n’ai pas poussé le vice à éviter la division car il faut bien leur faire quelque chose à ces bougres d’ordinosaures. Autant le SQR me semblait superflu et casse-noisette à faire pour justifier son débarras, autant le fait d’éviter de diviser par des nombres non premiers n’est pas aussi justifié mais bon autant avoir un algorithme sans calcul superflu pour permettre aux CPU de donner le meilleur d’eux-même sans être pénalisés à cause des parties superflues du code et de garder la division.

Comme j’expliquais, le diviseur peut tenir sur 8-bit car durant le calcul, il sera compris entre [0, n] où n = sqrt(1000)+1], soit 32.

Pour le Z80, voici une division de 16-bit sur 8-bit (trouvée sur Internet) :

HL_Div_C:
;Inputs:
;     HL is the numerator
;     C is the denominator
;Outputs:
;     A is the remainder
;     B is 0
;     C is not changed
;     DE is not changed
;     HL is the quotient
;
       ld b,16			; 10	, 10 --- ce qui donne n = 16 
       xor a			; 4	, 14
         add hl,hl		; 11	, 14 + n x 11
         rla			; 4	, 14 + n x 15
         cp c			; 4	, 14 + n x 19
         jr c,$+4		; 12|7	, 14 + n x 31|26
           inc l		; 4	, 14 + n x 31|30
           sub c		; 4	, 14 + n x 31|34 
         djnz $-7		; 13|8	, 14 + n x 44|42 
       ret

Au mieux, on a donc 686 cycles et au pire 798 cycles si on l’inclut direct dans le code au lieu de l’appeler comme une fonction. Je vois des possibles optimisations à faire.

En déroulant la boucle :

       xor a			; 4	, 4
.repeat 16
         add hl,hl		; 11	, 4 + n x 11
         rla			; 4	, 4 + n x 15
         cp c			; 4	, 4 + n x 19
         jr c,$+4		; 12|7	, 4 + n x 31|26
           inc l		; 4	, 4 + n x 31|30
           sub c		; 4	, 4 + n x 31|34 
.rend

Au mieux, on a donc 500 cycles et au pire 548 cycles.

Ce ‘jr’ m’ennuie, je sais qu’un ‘jp’ fait 10|1 (pas sûr pour le 1 mais c’est ce qui est indiqué sur une page).

       xor a			; 4	, 4
.repeat 16
         add hl,hl		; 11	, 4 + n x 11
         rla			; 4	, 4 + n x 15
         cp c			; 4	, 4 + n x 19
         jp c,$+4		; 10|1	, 4 + n x 29|20
           inc l		; 4	, 4 + n x 29|24
           sub c		; 4	, 4 + n x 29|28 
.rend

Au mieux, on aurait donc 452 cycles et au pire 468 cycles.

Reste à bien intégrer ça dans le code sans trop de dégât sur les registres.

Ah oui, le self-modified-code devrait être autorisé aussi – c’est très utilisé car ça permet de transformer des « constantes » en « variables » à même le code.

EDIT: OOPS, je me suis vautré dans les calculs en prenant des cycles en trop après un saut du ‘jr’/’jp’ que je m’empresse de corriger !

[hlide Level 2Messages : 53]

EDIT: là j’ai vraiment fumé de l’herbe donc j’ai retiré les codes de ce post.

[PZAWA Level 6Messages : 316]

@hlide
Merci Hlide:-) En général, je déteste regarder le code des autres avant d’avoir tenter d’abord par moi même ensuite je compare et je corrige: c’est pour moi la meilleur façon d’apprendre. Mais très souvent je me contente de ce que je fais: j’ai une version de division 16/8 qui prenait 800/900 cycles et en regardant ton exemple d’implémentation z80 je suis arrivé à 362/444 cycles. Moralité je devrais finalement plus souvent regarder comment font les autres .
Une optimisation évidente est de ramener la boucle à 10 passes (étant donné que l’on veut que les nombres premier inférieur à 1000):

ld b,10 ; a=10 bits max
xor a ; a=0 ->reste
add hl,hl
add hl,hl
add hl,hl
add hl,hl
add hl,hl
add hl,hl ; Q = A <<6
.loop:
add hl,hl ; Q=A*2
rla ; reste<<1 with carry cp c ; Reste>=B ?
jr c,skip1 ; non saute
inc l ; Oui rajoute au quotient
sub c ; Reste = reste - b
.skip:
djnz loop1 ; bit suivants
ret

Je n’ai pas dérouler les boucles et je n’ai pas compter les cycles.

ma version 6502 mais sans déroulage ni l’optimisation 10bits et puis comme souvent on peut peut-être mieux faire

Div16_8Funct:
;Entrée:
; $FB/$FC numerateur a
; $FD denominateur b
;Sortie:
; Registre A Reste
; $FB/$FC Quotient
ldx #$10
lda #$00
.loopbit:
asl $fb ; AL=*2
rol $fc ; AH=*2
rol ; r<<1 <-c cmp $fd ; r >= b ?
bcc .skipq ; non on saute
inc $fb ; sinon incrémente quotient
sbc $fd ; et r = r - b
.skipq:
dex ; bit suivant
bne .loopbit
rts

Si on s’en tient a la version de base le z80 l’emporte haut la main et en plus le déroulage de boucle sur z80 est beaucoup plus bénéfique que sur 6502 le rendant théoriquement plus de 2 fois plus rapide mais mais…
il faut faire attention avec le comptage de cycles cela peut être extrêmement piégeux :ce serait trop long à expliquer mais les processeurs genre 8080,z80 et 8088 souffrent en général plus de vol de cycle en système à mémoire partagée que les 65xx: il faut impérativement mesurer la vitesse du code sur une vrai machine pour donner un verdict final. Malgré cela le Z80 du CPC devrait quand même être largement devant le 65xx du C64. Par contre je serais curieux de voir ce que cela donne contre un Atari 8bits …

Sinon j’ai envie d’utiliser l’approche sans tableau et pour cela il me semble que j’ai besoin d’un sqrt et j’utilise ca très simple à implementer (mais encore une fois j’ai peut-être complètement faux ).
Par contre même si je voulais la division, je me rends maintenant compte que c’était stupide de ma part: mon approche sans division est débile et tombe complètement à l’eau

Donc au final je m’en tiendrais au Prog Basic (corrigé évidement) et sans oublier ton approche par tableau même si je pense que dans ce cas, le Crible Grec sera difficilement surpassable

PS: effectivement elle déconne cette balise code …

[hlide Level 2Messages : 53]

Tu n’as pas besoin de SQR avec ou sans tableau des nombre premiers. Avec, tu diminues le nombre de calculs en ne divisant que par des nombres premiers. Sans le tableau, ben tu divises par des nombre compris entre 2 et SQRT(1000)+1. Mais dans les deux cas, tu n’as pas besoin de SQR car tu as juste besoin d’arrêter la division dès que le quotient est plsu petite que le diviseur. Sinon, je proposais de faire 10 boucles au lieu de 16 puisque log2(1000) < 10 mais j’ai eu un doute et j’ai considéré que j’avais « fumé de l’herbe » et j’ai donc supprimé les codes en rapport. En effet, je ne suis pas sûr que le reste dans A soit correct si on s’arrête après la 10ème itération parce qu’il y a cette rotation ‘RLA’ par itération donc il en faut bien 16. Après il y a ce ‘CP C’ qui peut encore entraîner un ‘INC L’ et un ‘SUB C’ qui peut encore modifier le registre A au-delà de 10 itérations. Je n’en suis pas certain. Bref, s’il le ‘CP C’ fait que le saut a lieu, alors on peut faire suivre 6 ‘RLA’ juste après la sortie de 10 itérations. Si par contre, il se peut que ‘CP C’ ne fasse pas le saut au moins une fois après la dixième itération, ben du coup tu n’as pas d’autre choix que de faire les 16 itérations. J’avais beaucoup de mal à visualiser ça et à conclure sur ce point – donc j’ai zappé la version que je proposais avec 10 itérations seulement.

EDIT: ah je vois, tu fais 6 ‘ADD HL, HL’ avant d’entrer dans la boucle. C’est le truc que j’avais raté. Ben, en déroulant la boucle, tu vas descendre à moins de 200 cycles là.

[hlide Level 2Messages : 53]

Je vois ‘JR C, skip1’. Essaye plutôt ‘JP C, skip1’, il prend une octet de plus mais il est plus rapide.

[gibs Level 9Messages : 978]

Très intéressant tout ça.
Sinon, qui avait tenu le pari deja, afin que je puisse lui faire parvenir mon IBAN ?

Team Apollo

[PZAWA Level 6Messages : 316]

Ok Merci hlide tu dois sans doute avoir raison    j’ai du moi aussi trop fumé  mais comme je suis têtu je re-regarderais ca ce soir

@gibs: ce qui me fait peur c’est au moment de l’affichage: j’ai l’impression qu’au final on va se retrouvais avec un résultat proche: le cpc calculera tout plus vite mais le c64 compensera à l’affichage…   on verra … et c’est pour cela que je préfère ne pas parié 

[hlide Level 2Messages : 53]

Donc, j’ai vérifié avec le programme sur PC en simulant la division div16_8 du Z80 et je te confirme que ça ne fonctionne pas avec 10 itérations.

[EDIT]en fait si ça fonctionne, j’avais juste oublié de réduire la recherche des nombres premiers sur les premiers mille entiers. [/EDIT]

Voici la fonction qui fonctionne avec 16 itérations :

void z80_div16_8(unsigned short p1, unsigned short p2, unsigned short& q, unsigned short& r)
{
	unsigned int HL = p1;
	unsigned int C  = p2 & 255;
	unsigned int A;
	bool         CF;

	// XOR A
	A = 0;

	// à "dérouler" 16 fois
	for (int i = 0; i < 16; ++i)
	{
		// ADD HL,HL <- notez bien bit 0 de HL à 0 !
		CF  = (HL += HL) >> 16;
		HL &= 65535;

		// RLA
		A = +CF | (A << 1) & 255;

		// CP C
		CF = (A < C);

		// JP C, $+4
		if (CF == false)
		{
			// INC L <- ça met juste à 1 le bit 0 de HL
			// qui était à 0 à cause du ADD HL,HL précédent
			HL |= 1;

			// SUB C
			A = (A - C)&255;
		}
	}

	q = HL;
	r = A;
}

Par contre, si je mets que 10 itérations et que je fais la même chose que toi ou que ce que je croyais pouvoir faire, ça fait n’importe quoi et je ne retrouve pas quelque chose qui « matche » les nombres premiers retournés par la fonction de référence.

[Auteur]

Réponses