Tamis à octets

Byte Sieve est une implémentation informatique du crible d'Ératosthène publiée par Byte en tant que test de performance des langages de programmation . Il est apparu pour la première fois dans l'édition de septembre 1981 du magazine et a été revisité à l'occasion. Bien qu'il soit destiné à comparer les performances de différents langages sur les mêmes ordinateurs, il est rapidement devenu un test de performance machine largement utilisé.

Le Sieve était l'un des tests de performance les plus populaires de l' ère de l'informatique domestique , après le Creative Computing Benchmark de 1983 et les tests de performance Rugg/Feldman , principalement utilisés au Royaume-Uni à cette époque. Byte a ensuite publié le NBench, plus complet, en 1995 pour le remplacer.

Jim Gilbreath, du Naval Ocean System Center, envisageait depuis un certain temps l'idée d'écrire un petit programme d'évaluation comparative des langages, souhaitant un programme qui soit portable entre les langages, suffisamment petit pour que le code du programme tienne sur une seule page imprimée et qui ne repose pas sur des fonctionnalités spécifiques comme la multiplication ou la division matérielle. La solution a été inspirée par une rencontre avec Chuck Forsberg lors de la réunion USENIX de janvier 1980 à Boulder, CO , où Forsberg a mentionné une implémentation du tamis écrite par Donald Knuth .

Gilbreath a estimé que le tamis serait une référence idéale car il évitait les tests indirects sur les performances arithmétiques, qui variaient considérablement d'un système à l'autre. L'algorithme met principalement l'accent sur les performances de recherche de tableau et sur les capacités de logique et de ramification de base. Il ne nécessite pas non plus de fonctionnalités de langage avancées telles que la récursivité ou les types de collection avancés. La seule modification par rapport à la version originale de Knuth était de supprimer une multiplication par deux et de la remplacer par une addition. Avec la version originale, les machines équipées de multiplicateurs matériels fonctionneraient autrement tellement plus rapidement que le reste des performances serait masqué.

Après six mois d'efforts pour le porter sur autant de plateformes auxquelles il avait accès, les premiers résultats furent présentés dans l'édition de septembre 1981 de Byte dans un article intitulé « A High-Level Language Benchmark ». Gilbreath fut prompt à souligner que :

Je dois souligner que ce benchmark n’est pas le seul critère permettant de juger un langage ou un compilateur.

L'article fournit des implémentations de référence dans dix langages, y compris des sélections plus populaires comme BASIC , C , Pascal , COBOL et FORTRAN , et quelques exemples moins connus comme Forth , ZSPL , Ratfor , PL/1 et PLMX .

Des exemples d'exécution ont été fournis pour une variété de machines, principalement basées sur Zilog Z80 ou MOS 6502. Le meilleur temps était initialement de 16,5 secondes, réalisé par Ratfor sur une machine Z80 à 4 MHz, mais Gary Kildall a personnellement fourni une version dans la version prototype de PL/1 de Digital Research qui a été exécutée en 14 secondes et a établi la marque pour cette première collection. Le plus lent était Microsoft COBOL sur la même machine, qui a pris 5115 secondes (près d'une heure et demie), plus longtemps même que les langages interprétés comme BASIC. Une caractéristique notable de cette première exécution était que C, Pascal et PL/1 ont tous produit des performances à peu près similaires qui ont facilement battu les différents interpréteurs.

Une deuxième série de tests a été réalisée sur des machines plus puissantes, avec le langage assembleur Motorola 68000 qui a réalisé les temps les plus rapides avec 1,12 seconde, surpassant légèrement le C sur un PDP-11/70 et presque deux fois plus rapide que l'assembleur 8086. La plupart des temps sur PDP-11 et HP-3000 étaient beaucoup plus lents, de l'ordre de 10 à 50 secondes. Les tests sur ces machines utilisant uniquement des langages de haut niveau ont été menés par NBS Pascal sur le PDP-11, à 2,6 secondes.

Le Pascal de l'UCSD a fourni un autre ensemble de résultats intéressants, car le même programme peut être exécuté sur plusieurs machines. Exécuté sur la machine dédiée Ithaca InterSystems Pascal-100, un ordinateur basé sur Pascal MicroEngine , il a été exécuté en 54 secondes, alors que sur le Z80 il était de 239 et 516 sur l'Apple II.

Gilbreath, cette fois-ci avec son frère Gary, a revisité le code dans l'édition de janvier 1983 de Byte . Cette version a supprimé la plupart des langages les moins populaires, laissant Pascal, C, FORTRAN IV et COBOL, tout en ajoutant Ada et Modula-2 . Grâce aux lecteurs fournissant des échantillons supplémentaires, le nombre de machines, de systèmes d'exploitation et de langages comparés dans les tableaux résultants a été considérablement augmenté.

Le processeur Motorola 68000 (68k) est resté le plus rapide, presque trois fois plus rapide que le processeur Intel 8086 fonctionnant à la même fréquence d'horloge de 8 MHz. En utilisant des langages de haut niveau, les deux étaient plus proches en termes de performances, le 8086 étant généralement plus rapide que la moitié du 68k et souvent beaucoup plus proche. Une plus grande variété de mini-ordinateurs et de mainframes était également incluse, avec des temps que le 68k battait généralement, à l'exception des machines les plus rapides comme l' IBM 3033 et les modèles haut de gamme du VAX . Les machines plus anciennes comme le Data General Nova , le PDP-11 et le HP-1000 n'étaient pas aussi rapides que le 68k.

Le deuxième article de Gilbreath est paru alors que le benchmark devenait de plus en plus courant comme moyen de comparer les performances de diverses machines, sans parler des langages. Malgré son avertissement initial de ne pas le faire, il a rapidement commencé à apparaître dans les publicités des magazines comme un moyen de comparer les performances avec la concurrence, et comme un benchmark général.

Byte a de nouveau revisité le tamis plus tard en août 1983 dans le cadre d'une série d'articles sur le langage C. Dans ce cas, l'utilisation était plus conforme à l'intention initiale, en utilisant un seul code source et en l'exécutant sur une seule machine pour comparer les performances des compilateurs C sur le système d'exploitation CP/M-86 , sur CP/M-80 , et pour l' IBM PC .

Malgré les inquiétudes de Gilbreath dans l'article original, à cette époque, le code était devenu presque universel pour les tests, et l'un des articles remarquait que « Le crible d'Ératosthène est un test de performance obligatoire ». Il a été inclus dans la suite Byte UNIX Benchmark introduite en août 1984.

De nouvelles versions du code continuent d'apparaître pour de nouveaux langages, par exemple Rosetta Code et GitHub ont de nombreuses versions disponibles. Il est souvent utilisé comme exemple de programmation fonctionnelle même si la version courante n'utilise pas réellement l'algorithme de criblage.

L'implémentation fournie calculait uniquement les nombres premiers impairs, de sorte que le tableau de 8191 éléments représentait en réalité les nombres premiers inférieurs à 16385. Comme indiqué dans un tableau latéral, le 0e élément représentait 3, le 1er élément 5, le 2e élément 7, et ainsi de suite.

Il s'agit de la version BASIC originale du code présentée en 1981. Le dialecte n'est pas spécifié, mais un certain nombre de détails signifient qu'il ne fonctionne pas sous les premières versions de Microsoft BASIC (4.x et antérieures), parmi lesquels l'utilisation de noms de variables longs comme SIZEet FLAGS. L'absence de numéros de ligne peut suggérer une variante de mini-ordinateur qui lit la source à partir d'un fichier texte, mais il peut également s'agir d'une erreur d'impression.

REM Programme des nombres premiers du crible d'Ératosthène en BASIC 
1 TAILLE = 8190 2 DIM FLAGS ( 8191 ) 3 PRINT "1 seule itération" 5 COUNT = 0 6 POUR I = 0 À TAILLE 7 FLAGS ( I ) = 1 8 SUIVANT I 9 POUR I = 0 À TAILLE 10 SI FLAGS ( I ) = 0 ALORS 18 11 PRIME = I + I + 3 12 K = I + PRIME 13 SI K > TAILLE ALORS 17 14 FLAGS ( K ) = 0 15 K = K + PRIME 16 GOTO 13 17 COUNT = COUNT + 1 18 SUIVANT I 19 PRINT COUNT , " PRIMES"

Et en C, avec quelques ajustements d'espaces par rapport à l'original :

#define true 1 
#define false 0 
#define size 8190 
#define sizepl 8191 
char flags [ sizepl ]; main () { int i , prime , k , count , iter ; printf ( "10 itérations " ); for ( iter = 1 ; iter <= 10 ; iter ++ ) { count = 0 ; for ( i = 0 ; i <= size ; i ++ ) flags [ i ] = true ; for ( i = 0 ; i <= size ; i ++ ) { if ( flags [ i ]) { prime = i + i + 3 ; k = i + prime ; while ( k <= size ) { flags [ k ] = false ; k += prime ; } count = count + 1 ; } } } printf ( " %d nombres premiers" , count ); }