Hispanopedia Wiki
Articulo de referencia

Tamiz de bytes

Byte Sieve es una implementación informática de la Criba de Eratóstenes, publicada por Byte como una herramienta de evaluación comparativa del rendimiento de lenguajes de progra...

Hispanopedia WikiContenido en espanolLectura gratuita

Byte Sieve es una implementación informática de la Criba de Eratóstenes, publicada por Byte como una herramienta de evaluación comparativa del rendimiento de lenguajes de programación . Apareció por primera vez en la edición de septiembre de 1981 de la revista y se retomó en varias ocasiones. Aunque su objetivo era comparar el rendimiento de diferentes lenguajes en los mismos ordenadores, rápidamente se convirtió en una herramienta de evaluación comparativa muy utilizada.

El Sieve fue uno de los benchmarks más populares de la era de los ordenadores domésticos , junto con el Creative Computing Benchmark de 1983 y los benchmarks Rugg/Feldman , que se veían principalmente en el Reino Unido en esa época. Posteriormente, en 1995, Byte publicó el más completo NBench para reemplazarlo.

Historia

Orígenes

Jim Gilbreath, del Centro de Sistemas Oceánicos Navales, llevaba tiempo considerando la idea de escribir un pequeño programa de evaluación comparativa de lenguajes, deseando uno que fuera portable entre lenguajes, lo suficientemente pequeño como para que el código cupiera en una sola página impresa y que no dependiera de características específicas como la multiplicación o la división por hardware. La solución se inspiró en una reunión con Chuck Forsberg en la reunión de USENIX de enero de 1980 en Boulder, Colorado , donde Forsberg mencionó una implementación del algoritmo de criba escrita por Donald Knuth . [ 1 ] [ 2 ]

Gilbreath consideró que el tamiz sería un punto de referencia ideal, ya que evitaba las pruebas indirectas sobre el rendimiento aritmético, que variaba considerablemente entre sistemas. El algoritmo se centra principalmente en el rendimiento de búsqueda en matrices y en las capacidades básicas de lógica y ramificación. Tampoco requiere características de lenguaje avanzadas como la recursión o tipos de colección avanzados. La única modificación respecto a la versión original de Knuth fue eliminar una multiplicación por dos y sustituirla por una suma. Con la versión original, las máquinas con multiplicadores de hardware funcionarían mucho más rápido, ocultando así el resto del rendimiento. [ 1 ]

Después de seis meses de esfuerzo por adaptarlo a tantas plataformas como le fue posible, los primeros resultados se presentaron en la edición de septiembre de 1981 de Byte en un artículo titulado "Un benchmark de lenguaje de alto nivel". [ 1 ] Gilbreath se apresuró a señalar que:

Debo enfatizar que este punto de referencia no es el único criterio para juzgar un lenguaje o compilador. [ 1 ]

El artículo proporcionó implementaciones de referencia en diez lenguajes, incluyendo selecciones más populares como BASIC , C , Pascal , COBOL y FORTRAN , y algunos ejemplos menos conocidos como Forth , ZSPL , Ratfor , PL/1 y PLMX . [ 3 ]

Se proporcionaron ejemplos de ejecución para una variedad de máquinas, principalmente Zilog Z80 o basadas en MOS 6502. El mejor tiempo inicial fue de 16,5 segundos, logrado por Ratfor en una  máquina Z80 de 4 MHz, pero Gary Kildall proporcionó personalmente una versión en el prototipo de PL/1 de Digital Research [ 4 ] que se ejecutó en 14 segundos y estableció la marca para esta primera colección. El más lento fue Microsoft COBOL en la misma máquina, que tardó la friolera de 5115 segundos (casi una hora y media), incluso más que lenguajes interpretados como BASIC. [ 5 ] Una característica notable de esta primera ejecución fue que C, Pascal y PL/1 arrojaron un rendimiento bastante similar que superó fácilmente a los diversos intérpretes. [ 4 ]

Se realizó una segunda serie de pruebas en máquinas más potentes, donde el lenguaje ensamblador Motorola 68000 arrojó los tiempos más rápidos con 1,12 segundos, superando ligeramente a C en un PDP-11/70 y casi el doble de rápido que el ensamblador 8086. La mayoría de los tiempos en PDP-11 y HP-3000 fueron mucho más lentos, del orden de 10 a 50 segundos. [ 6 ] Las pruebas en estas máquinas utilizando solo lenguajes de alto nivel fueron lideradas por NBS Pascal en el PDP-11, con 2,6 segundos. [ 7 ]

UCSD Pascal proporcionó otro conjunto interesante de resultados, ya que el mismo programa se puede ejecutar en varias máquinas. Al ejecutarse en la máquina dedicada Ithaca InterSystems Pascal-100, una computadora basada en Pascal MicroEngine , se ejecutó en 54 segundos, mientras que en la Z80 tardó 239 segundos y en la Apple II, 516 segundos. [ 7 ]

Desparramar

Gilbreath, esta vez junto con su hermano Gary, revisó el código en la edición de enero de 1983 de Byte . Esta versión eliminó la mayoría de los lenguajes menos populares, dejando Pascal, C, FORTRAN IV y COBOL, y añadiendo Ada y Modula-2 . Gracias a que los lectores aportaron muestras adicionales, el número de máquinas, sistemas operativos y lenguajes comparados en las tablas resultantes se amplió considerablemente. [ 8 ]

El ensamblador Motorola 68000 (68k) siguió siendo el más rápido, casi tres veces más rápido que el Intel 8086 funcionando a la misma  frecuencia de reloj de 8 MHz. Usando lenguajes de alto nivel, ambos tenían un rendimiento similar, con el 8086 generalmente más de la mitad de la velocidad del 68k y a menudo mucho más cerca. [ 9 ] También se incluyó una mayor variedad de minicomputadoras y mainframes , con tiempos que el 68k generalmente superaba, excepto en las máquinas más rápidas como el IBM 3033 y los modelos de gama alta del VAX . Las máquinas más antiguas como el Data General Nova , el PDP-11 y el HP-1000 no eran ni de lejos tan rápidas como el 68k. [ 8 ]

El segundo artículo de Gilbreath apareció cuando el benchmark se estaba volviendo bastante común como una forma de comparar el rendimiento de varias máquinas, por no hablar de lenguajes. A pesar de su advertencia inicial de no hacerlo, pronto comenzó a aparecer en anuncios de revistas como una forma de comparar el rendimiento con la competencia, [ 10 ] [ 11 ] y como un benchmark general. [ 12 ]

Byte volvió a tratar el tema del tamiz a finales de agosto de 1983 como parte de una serie de artículos de la revista sobre el lenguaje C. En este caso, el uso se ajustaba más a la intención original, utilizando un único código fuente y ejecutándolo en una sola máquina para comparar el rendimiento de los compiladores de C en el sistema operativo CP/M-86 , [ 13 ] en CP/M-80 , [ 14 ] y para el IBM PC . [ 15 ]

A pesar de la preocupación expresada por Gilbreath en el artículo original, para entonces el código se había vuelto prácticamente universal para las pruebas, y uno de los artículos señalaba que «La criba de Eratóstenes es una prueba de rendimiento obligatoria». [ 13 ] Se incluyó en el conjunto de pruebas de rendimiento Byte UNIX, presentado en agosto de 1984. [ 16 ]

Hoy

Siguen apareciendo nuevas versiones del código para nuevos lenguajes, [ 17 ] por ejemplo, Rosetta Code y GitHub tienen muchas versiones disponibles. [ 18 ] A menudo se utiliza como ejemplo de programación funcional a pesar de que la versión común no utiliza realmente el algoritmo de la criba. [ 19 ]

Implementación

La implementación proporcionada calculaba solo números primos impares, por lo que la matriz de 8191 elementos representaba en realidad números primos menores que 16385. Como se muestra en una tabla lateral, el elemento 0 representaba 3, el elemento 1 5, el elemento 2 7, y así sucesivamente.

Esta es la versión BASIC original del código presentado en 1981. [ 20 ] [ a ] ​​No se especifica el dialecto, pero varios detalles indican que no se ejecuta en versiones antiguas de Microsoft BASIC (4.x y anteriores), entre ellos el uso de nombres de variables largos como SIZEy FLAGS. La falta de números de línea puede sugerir una variante de minicomputadora que lee el código fuente desde un archivo de texto, pero también podría haber sido un error de impresión.

REM Programa de números primos de la criba de Eratóstenes en BASIC 1 SIZE = 8190 2 DIM FLAGS ( 8191 ) 3 PRINT "Solo 1 iteración" 5 COUNT = 0 6 FOR I = 0 TO SIZE 7 FLAGS ( I ) = 1 8 NEXT I 9 FOR I = 0 TO SIZE 10 IF FLAGS ( I ) = 0 THEN 18 11 PRIME = I + I + 3 12 K = I + PRIME 13 IF K > SIZE THEN 17 14 FLAGS ( K ) = 0 15 K = K + PRIME 16 GOTO 13 17 COUNT = COUNT + 1 18 NEXT I 19 PRINT COUNT , " PRIMES"

Y en C, con algunos ajustes de espacios en blanco respecto al original: [ 21 ]

#define true 1 #define false 0 #define size 8190 #define sizepl 8191 char flags [ sizepl ]; main () { int i , prime , k , count , iter ; printf ( "10 iteraciones \n " ); 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 ( " \n %d primos" , count ); }

Notas

  1. ↑ Tenga en cuenta que falta el número de línea de la primera línea en el listado de la fuente original.

Referencias

Citas

  1. 1 2 3 4 Gilbreath 1981 , pág. 180.
  2. ↑ Knuth 1969 , págs. 416, 658.
  3. ↑ Gilbreath 1981 , págs. 181–190.
  4. 1 2 Gilbreath 1981 , págs. 194.
  5. ↑ Gilbreath 1981 , págs. 195.
  6. ↑ Gilbreath 1981 , págs. 193.
  7. 1 2 Gilbreath 1981 , págs. 196.
  8. 1 2 Gilbreath y Gilbreath 1983 , pág. 294.
  9. ↑ Gilbreath y Gilbreath 1983 , pág. 292.
  10. ↑ "HS/FORTH (anuncio)" (PDF) . PC Tech Journal . Octubre de 1985. pág.  132.
  11. ↑ "FORTH ahora es muy rápido (anuncio)" (PDF) . Dimensiones de FORTH . Noviembre-diciembre de 1985. pág. 2. 
  12. ↑ Ciarcia, Steve (1979). Ciarcia's Circuit Cellar, Volumen 6. Circuit Cellar. pág. 133. ISBN  9780070109681.
  13. 1 2 Houston, Jerry; Brodrick, Jim; Kent, Les (agosto de 1983). "Comparación de compiladores C para CP/M-86" . Byte . págs. 82–106 . 
  14. ↑ Kern, Christopher (agosto de 1983). "Cinco compiladores C para CP/M-80" . Byte . págs. 110–130 . 
  15. ↑ Phraner, Ralph (agosto de 1983). "Nueve compiladores de C para la IBM PC" . Byte . págs. 134–168 . 
  16. ↑ Hinnant, David (agosto de 1984). "Benchmarking UNIX Systems: UNIX performance on microcomputers and minicomputers" . Byte . págs. 132–135 , 400–409 . 
  17. ↑ "El rápido tamiz de Eratóstenes" . 27 de julio de 2015.
  18. ↑ "Criba de Eratóstenes" . GitHub . Consultado el 2 de mayo de 2019 .
  19. ↑ O'Neill, Melissa (enero de 2009). "El auténtico tamiz de Eratóstenes" . Journal of Functional Programming . 19 (1): 95– 106. doi : 10.1017/S0956796808007004 . S2CID 1309380 . 
  20. ↑ Gilbreath 1981 , pág. 188.
  21. ↑ Gilbreath 1981 , pág. 186.

Bibliografía

  • Gilbreath, Jim (septiembre de 1981). "Un punto de referencia para lenguajes de alto nivel" . Byte . págs. 180–198 . 
  • Gilbreath, Jim; Gilbreath, Gary (enero de 1983). "Eratóstenes revisitado: una vez más a través del tamiz" . Byte . págs. 283–325 . 
  • Knuth, Donald (1969). El arte de la programación informática Volumen 2: Algoritmos seminuméricos . Addison-Wesley. ISBN 978-0-201-89684-8.