Sieve en Javascript

La Criba de Eratóstenes, más conocido por su nombre anglosajón de Sieve of Eratostenes, o simplemente Sieve, es un algoritmo matemático para el cálculo de números primos, descubierto por el griego que le dio nombre, allá por el años 200 AC.

Como es lógico, es la época de Eratóstenes, no había ordenadores, por lo que poco podía imaginarse del éxito que tendría su idea en este campo… Durante los 80 y los 90, Sieve era uno de los algoritmos que se utilizaba para verificar el rendimiento de compiladores y hardware, vendría a ser similar a los benchmarks que hacen hoy día los entusiastas con Prime95.

La ventaja de Sieve es que resultaba fácil de implementar, y por tanto se portó a multitud de lenguajes de programación y plataformas, por lo que era una herramienta comparativa entre equipos heterogeneos.

Por otro lado, estaba cansado de mi algoritmo de cálculo de números primos, así que lo que hoy veremos, es una implementación de Sieve sobre Javascript (es fácil encontrarlo en otros lenguajes, pero no en éste). Basicamente he portado el código de Sieve.c que vi cuando hablé de Miracle C Compiler, y lo he ejecutado en un mismo equipo, usando varios navegadores con sus correspondientes intérpretes/ejecutores de Javascript. No me he molestado en optimizarlo manualmente, ya que considero que de esta manera se resaltarán más claramente las diferencias de cada navegador.

Por motivos prácticos, lo he configurado a 10.000 iteraciones, y los resultados obtenidos han sido los siguientes:

Navegador Plataforma Tiempo de ejecución (ms)
Chromium 6.0.479 (53979) x86 14.142
Firefox 4.0b3 (Gecko/20100731) x86 11.187
Firefox 4.0b3 (Gecko/20100731) x64 13.443
Internet Explorer 8.0.7600.16385 x86 ~200.000
Internet Explorer 8.0.7600.16385 x86 ~200.000
Opera 10.70.3468 x86 18.052
Safari 5.0.1 (7533.17.8) x86 6.042

Los resultados obtenidos, son sin duda extraños. Para algunos de ellos, tengo explicación, y para otros no. Veamos…

Nitro el compilador JIT de Javascript de Safari se coloca líder, superando a los que a priori deberían estar en cabeza: Chromium y Opera.

Le sigue a mucha diferencia, TraceMonkey de Firefox, donde la versión x86 supera a la x64, en parte debido a que Sieve, tiene bastante con enteros de 32 bits, y en parte a que las compilaciones x64, no son todavía tan maduras, ni están tan optimizadas como las x86.

De cerca está V8 de Chromium, y después Carakan de Opera. Los reyes de Peacekeeper, SunSpider, y otros tests, no puede más que hacer un 4º y 5º puestos.

En la cola, tenemos a Internet Explorer, el bajísimo rendimiento de ejecución de Javascript, tanto para la versión de 32 bits, como de 64 bits, es algo que no debería extrañar a nadie, siendo unas 10 veces más lento que el más lento. Las cosas, van a cambiar radicalmente con Internet Explorer 9.

Puedes revisar el código, y ejecutarlo tu mismo aquí (1 Kb. en formato HTML).

Actualizado a viernes 01 de octubre de 2010. 17:29:
Para darle una vuelta de tuerca más, tras pasar el código con Closure Compiler Service de Google, la optimización simple, no ha dado mejoras en ninguno de los casos, y si lo han sido, eran menores al 0,1%. El modo avanzado, generaba un código no funcional.

2 comentarios en “Sieve en Javascript”

  1. Javier Gutiérrez Chamorro (Guti)

    Gracias por la prueba david. Creo que aún y la aceleración por hardware de IE 9, mucho le va a quedar para dar una mejoría de rendimiento competitiva.

    Obviamente Sieve, es puramente sintético, y apenas relevante sobre las aplicaciones reales que usa el usuario, aunque si que es un buen indicativo de la prestación pura.

Deja un comentario