Archéologie, Bill Gates et benchmarking, voici le menu !
Le but de cet article est de donner un aperçu de l'évolution des performances des ordinateurs au fil des ans, de prendre conscience des contraintes qui existaient il y a 40 ans pour les programmeurs et d'aborder d'une manière différente le tri par sélection.
Il y a trois parties:
1. Présentation des algorithmes
2. Présentation de l'émulateur BlueMsx
3. Comparaison des algorithmes
-----------------------------------------------------------------------------------------------------------------------------------
Dans un article précédent, j'avais évoqué le livre de Jean MEEUS.
Je vais vous parler d'un temps que les moins de 40 ans ne peuvent pas connaître ...
Dans son livre, l'auteur nous propose plusieurs algorithmes de tri et compare leurs performances à l'aide de différents terminaux.
Les programmes sont écrits en langage BASIC. A droite on peut observer un bel exemple de programmation dite "spaghetti" (Je vous laisse deviner d'où vient ce qualificatif !)
En analysant le premier code, le SIMPLE SORT apparaît comme étant l'ancêtre du tri par sélection !
Il manque au BETTER un petit test sur la variable K pour en faire un tri par sélection.
Voici les résultats des tests de Jean MEEUS :
Les résultats peuvent déconcerter mais ces tests ont eu lieu à l'aube des années 80,
c'est à dire il y a plus de 40 ans !
Je vous propose donc un saut dans le passé en codant sur une machine de l'époque, le MSX (le plus doué des ordinateurs 8 bits grand public de l'époque (avis personnel !!!)).
L'histoire du MSX débute en automne 1983. Ordinateur personnel basé sur un processeur Zilog Z80, le standard MSX est le fruit de la coopération entre un japonais, Kazuhiko Nishi, ingénieur chez ASCII, et un américain, Bill Gates, dirigeant de Microsoft qu'on ne présente plus. Une alliance, qui aujourd'hui, serait plus qu'improbable…
Le marché de la micro-informatique, à cette époque, fourmille de systèmes tous différents et totalement incompatibles entre eux et c'est pour aboutir à une standardisation que le MSX voit le jour. Ce micro-ordinateur 8 bits est en quelque sorte l'ancêtre du PC, il est en effet doté du MSX Basic fourni par Microsoft (MSX : Machines with Software eXchangeability).
Il existe 5 évolutions officielles du MSX.
Trois 8 bits (MSX, MSX2 et MS2+) et deux 16 bits (MSX Turbo-R : ST et GT)
Voici la norme MSX-1 telle qu'annoncée en juin 1983 :
- Z80A CPU à 3.58 MHz
- 6 Ko RAM (au minimum)
- 32 Ko ROM (au minimum) avec BASIC Microsoft
- 8 Ko RAM pour les programmes MSX-BASIC, 16 Ko pour la vidéo
- Port cartouche (1 ou 2)
- Port joystick (1 ou 2)
- Port magnétocassette 1200 - 2400 bauds
- Port Centronics
- Entrées/ sorties compatibles Intel 8255
- Son compatible General Instrument 8910 (Yamaha YM 2149 par exemple)
- Générateurs de son en 3 canaux à 8 octaves
- Chip vidéo compatible Texas Instruments TMS 9918, 32 sprites
- Résolution graphique 64 x 48 / 256 x 192 en 16 couleurs
- Mode texte : 40 x 24 / 32 x 24
- Clavier 72 touches avec 5 touches de fonction, flèches, et 3 touches spécialisées.
(Source : https://www.planetemu.net/article/l-histoire-du-msx)
L'ordinateur utilisé par Jean MEEUS est le HP-85
(Source http://oldcomputers.net/hp85.html)
Grâce à un émulateur, le BlueMsx nous allons pouvoir tester les codes proposés.
Exemple de code ("FROGGER", le jeu qui a inspiré les créateurs de CROSSY ROAD en version BASIC
en 150 lignes de code ! >>>FROGGER<<<)
Pour coder en langage BASIC MSX, nous allons utiliser le livre de Jacques BOISGONTIER :
Voici quelques extraits qui vont nous être utiles :
Nous reviendrons plus tard sur cet encadré mais pour l'instant passons aux codes.
Nous allons mesurer des temps d'exécution , pour le MSX, cela se fera avec la variable TIME, en python, il existe une fonction dédiée dans la bibliohèque time :
- perf_counter() : Performance counter for benchmarking (extrait de l'aide d'Edupython).
Remarque : En informatique, un benchmark est un banc d'essai permettant de mesurer les performances d'un système pour le comparer à d'autres.
Les codes :
SIMPLE SORT
Version BASIC MSX
10 PRINT "MSX POWER!"
20 INPUT "NOMBRE D'ENTREES";N : VM=2000
30 DIM X(N)
40 NMESURES=15
50 TT=0
60 FOR NBTRI=1 TO NMESURES
70 FOR I=1 TO N
80 V=INT(RND(-TIME)*VM)+1
90 X(I)=V
100 NEXT I
110 REM ***SIMPLE***
120 TIME=0
130 FOR I=1 TO N-1
140 FOR J=I+1 TO N
150 IF X(J)>=X(I)THEN 190
160 A=X(I)
170 X(I)=X(J)
180 X(J)=A
190 NEXT J
200 NEXT I
210 TEMPS=TIME/50
220 TT=TT+TEMPS
230 NEXT NBTRI
240 TA=TT/NMESURES
250 PRINT "J'AI TRIE PENDANT ENVIRON:";TA;"S"
260 FOR I=1 TO N : PRINT X(I) : NEXT I
Version python
from time import perf_counter
from random import randint
n=int(input("Combien d'entrées ?"))
nb_mesures=100
somme_durees=0
for nb in range(nb_mesures):
x = [randint(1,2000) for i in range(n)]
#print("x = ",x)
#SIMPLE SORT JEAN MEEUS
t_debut=perf_counter()
for i in range(0,n-1):
for j in range(i+1,n):
if x[j] < x[i]:
a = x[i]
x[i] = x[j]
x[j] = a
#endif
#next j
#next i
t_fin=perf_counter()
duree=t_fin-t_debut
somme_durees=somme_durees+duree
duree_moyenne=somme_durees/nb_mesures
#print("x = ",x)
print("durée moyenne du tri:",duree_moyenne)
BETTER SIMPLE SORT
Version BASIC MSX
10 PRINT "MSX POWER!"
20 INPUT "NOMBRE D'ENTREES";N : VM=2000
30 DIM X(N)
40 NMESURES=15
50 TT=0
60 FOR NBTRI=1 TO NMESURES
70 FOR I=1 TO N
80 V=INT(RND(-TIME)*VM)+1
90 X(I)=V
100 NEXT I
110 REM ***BETTER***
120 TIME=0
130 FOR I=1 TO N-1
140 M=X(I)
150 K=I
160 FOR J=I+1 TO N
170 IF X(J) < M THEN M=X(J) : K=J
180 NEXT J
190 A=X(I):X(I)=M:X(K)=A
200 NEXT I
210 TEMPS=TIME/50
220 TT=TT+TEMPS
230 NEXT NBTRI
240 TA=TT/NMESURES
250 PRINT "J'AI TRIE PENDANT ENVIRON:";TA;"S"
260 FOR I=1 TO N : PRINT X(I) : NEXT I
Version python
from time import perf_counter
from random import randint
n=int(input("Combien d'entrées ?"))
x = [randint(1,2000) for i in range(n)]
#print("x = ",x)
nb_mesures=100
somme_durees=0
for nb in range(nb_mesures):
#BETTER SIMPLE SORT JEAN MEEUS
t_debut=perf_counter()
for i in range(0,n-1):
m=x[i]
k=i
for j in range(i+1,n):
if x[j] < m :
m = x[j]
k = j
#endif
#next j
a = x[i]
x[i]=m
x[k]=a
#next i
t_fin=perf_counter()
duree=(t_fin-t_debut)
somme_durees=somme_durees+duree
duree_moyenne=somme_durees/nb_mesures
#print("x = ",x)
print("durée moyenne du tri:",duree_moyenne)
Quelques remarques sur les codes :
>>>Pour obtenir des résultats reproductibles, les durées sont le résultat de plusieurs mesures (minimum 15 pour le MSX).
Cette petite opération, même si elle ne se trouve pas dans la zone de mesure diminue d'environ 5% les capacités du MSX !!
>>>Les indices des tableaux commencent à 1, c'est normal ! A l'époque, la fonction len() n'existait pas et on
avait pour habitude de stocker la longueur du tableau à l'indice 0.
>>>Vous pouvez remarquer que l'algorithme nommé BETTER par Jean MEEUS ressemble à celui du tri par sélection, à l'exception d'une ligne.
A la ligne 190, la permutation devrait être soumise à la condition :
190 IF K<>J THEN A=X(I):X(I)=M:X(K)=A
Comme précédemment, il semblerait que le gain découlant de la présence de ce test ne soit pas suffisamment intéressant pour les machines de l'époque.
Un autre exemple confirme cela. On a vu plus haut que la variable TIME était limitée à 65535 cinquantième de seconde, c'est à dire 1310 secondes or, certains tests dépassent cette durée.
On peut remedier à cela en ajoutant un compteur pour réinitialiser toutes les 1000 secondes la variable TIME
TIME=0 : C=0
...
...
IF TIME>50000 THEN TIME=0 : C=C+1
....
TEMPS=TIME/50+C*1000
...
Cela fonctionne, cependant, l'ajout de ce simple test dans la boucle de mesure,
diminue de 40% les performances du MSX !!!
Voici les résultats obtenus (l'auteur a également testé ses programmes sur un ordinateur plus puissant) :
On peut vérifier que la complexité temporelle est bien en ?(n2) en s'intéressant à l'évolution des données.
C'est l'occasion également de faire des prévisions sachant que le coefficient de correlation est plutôt bon :
Pour 2000 entrées :
- Pour le HP-85 : 44446,6773 s soit environ 12 h 20 min 47 s
- pour le MSX : 27600,8028 s soit environ 7 h 40 min 1 s
Remarque : les tests python ont été effectués avec un ordinateur de bureau d'entrée de gamme (le mien !) à 1,4GHz et un indice de performance de 4,4 (Depuis Windows 8, et pour Windows 10, l'échelle de l'indice de performance va de 1,0 à 9,9).