Interpretación de un punto de referencia en C, Clojure, Python, Ruby, Scala y otros [cerrado]

Descargo de responsabilidad

Sé que los puntos de referencia artificiales son malos. Pueden mostrar resultados solo para situaciones estrechas muy específicas. No asumo que un idioma sea mejor que el otro debido al estúpido banco. Sin embargo, me pregunto por qué los resultados son tan diferentes. Por favor vea mis preguntas al final.

Descripción de la evaluación comparativa de matemáticas

El punto de referencia son cálculos matemáticos simples para encontrar pares de números primos que difieren en 6 (los llamados números primos sexy ). Por ejemplo, los números primos sexy por debajo de 100 serían:(5 11) (7 13) (11 17) (13 19) (17 23) (23 29) (31 37) (37 43) (41 47) (47 53) (53 59) (61 67) (67 73) (73 79) (83 89) (97 103)

Tabla de resultados

En la tabla: tiempo de cálculo en segundos En ejecución: todos excepto Factor se estaban ejecutando en VirtualBox (invitado amd64 inestable de Debian, host Windows 7 x64) CPU: AMD A4-3305M

  Sexy primes up to:        10k      20k      30k      100k               

  Bash                    58.00   200.00     [*1]      [*1]

  C                        0.20     0.65     1.42     15.00

  Clojure1.4               4.12     8.32    16.00    137.93

  Clojure1.4 (optimized)   0.95     1.82     2.30     16.00

  Factor                    n/a      n/a    15.00    180.00

  Python2.7                1.49     5.20    11.00       119     

  Ruby1.8                  5.10    18.32    40.48    377.00

  Ruby1.9.3                1.36     5.73    10.48    106.00

  Scala2.9.2               0.93     1.41     2.73     20.84

  Scala2.9.2 (optimized)   0.32     0.79     1.46     12.01

[* 1] - Me da miedo imaginar cuánto tiempo tomará

Listados de código

C:

int isprime(int x) {
  int i;
  for (i = 2; i < x; ++i)
    if (x%i == 0) return 0;
  return 1;
}

void findprimes(int m) {
  int i;
  for ( i = 11; i < m; ++i)
    if (isprime(i) && isprime(i-6))
      printf("%d %d\n", i-6, i);
}

main() {
    findprimes(10*1000);
}

Rubí:

def is_prime?(n)
  (2...n).all?{|m| n%m != 0 }
end

def sexy_primes(x)
  (9..x).map do |i|
    [i-6, i]
  end.select do |j|
    j.all?{|j| is_prime? j}
  end
end

a = Time.now
p sexy_primes(10*1000)
b = Time.now
puts "#{(b-a)*1000} mils"

Scala:

def isPrime(n: Int) =
  (2 until n) forall { n % _ != 0 }

def sexyPrimes(n: Int) = 
  (11 to n) map { i => List(i-6, i) } filter { _ forall(isPrime(_)) }

val a = System.currentTimeMillis()
println(sexyPrimes(100*1000))
val b = System.currentTimeMillis()
println((b-a).toString + " mils")

Scala opimized isPrime(la misma idea que en la optimización de Clojure):

import scala.annotation.tailrec

@tailrec // Not required, but will warn if optimization doesn't work
def isPrime(n: Int, i: Int = 2): Boolean = 
  if (i == n) true 
  else if (n % i != 0) isPrime(n, i + 1)
  else false

Clojure:

(defn is-prime? [n]
  (every? #(> (mod n %) 0)
    (range 2 n)))

(defn sexy-primes [m]
  (for [x (range 11 (inc m))
        :let [z (list (- x 6) x)]
        :when (every? #(is-prime? %) z)]
      z))

(let [a (System/currentTimeMillis)]
  (println (sexy-primes (* 10 1000)))
  (let [b (System/currentTimeMillis)]
    (println (- b a) "mils")))

Clojure optimizado is-prime?:

(defn ^:static is-prime? [^long n]
  (loop [i (long 2)] 
    (if (= (rem n i) 0)
      false
      (if (>= (inc i) n) true (recur (inc i))))))

Pitón

import time as time_

def is_prime(n):
  return all((n%j > 0) for j in xrange(2, n))

def primes_below(x):
  return [[j-6, j] for j in xrange(9, x+1) if is_prime(j) and is_prime(j-6)]

a = int(round(time_.time() * 1000))
print(primes_below(10*1000))
b = int(round(time_.time() * 1000))
print(str((b-a)) + " mils")

Factor

MEMO:: prime? ( n -- ? )
n 1 - 2 [a,b] [ n swap mod 0 > ] all? ;

MEMO: sexyprimes ( n n -- r r )
[a,b] [ prime? ] filter [ 6 + ] map [ prime? ] filter dup [ 6 - ] map ;

5 10 1000 * sexyprimes . .

Bash (zsh):

#!/usr/bin/zsh
function prime {
  for (( i = 2; i < $1; i++ )); do
    if [[ $[$1%i] == 0 ]]; then
      echo 1
      exit
    fi
  done
  echo 0
}

function sexy-primes {
  for (( i = 9; i <= $1; i++ )); do
    j=$[i-6]
    if [[ $(prime $i) == 0 && $(prime $j) == 0 ]]; then
      echo $j $i
    fi
  done
}

sexy-primes 10000

Preguntas

1. ¿Por qué Scala es tan rápido? ¿Es por escritura estática ? ¿O simplemente está usando JVM de manera muy eficiente?
2. ¿Por qué hay una diferencia tan grande entre Ruby y Python? Pensé que estos dos no son totalmente diferentes. Quizás mi código esté equivocado. ¡Por favor iluminame! Gracias. UPD Sí, eso fue un error en mi código. Python y Ruby 1.9 son bastante iguales.
3. Realmente impresionante salto en productividad entre las versiones de Ruby.
4. ¿Puedo optimizar el código de Clojure agregando declaraciones de tipo? ¿Ayudará?

Respuestas aproximadas:

1. La escritura estática de Scala lo está ayudando bastante aquí; esto significa que usa la JVM de manera bastante eficiente sin demasiado esfuerzo adicional.
2. No estoy exactamente seguro de la diferencia de Ruby / Python, pero sospecho que es probable que (2...n).all?la función is-prime?esté bastante bien optimizada en Ruby (EDITAR: parece que este es el caso, consulte la respuesta de Julian para obtener más detalles ...)
3. Ruby 1.9.3 está mucho mejor optimizado
4. ¡El código de Clojure ciertamente se puede acelerar mucho! Si bien Clojure es dinámico de forma predeterminada, puede usar sugerencias de tipo, matemáticas primitivas, etc. para acercarse a la velocidad de Scala / Java puro en muchos casos cuando lo necesite.

La optimización más importante en el código de Clojure sería usar matemáticas primitivas escritas dentro is-prime?, algo como:

(set! *unchecked-math* true) ;; at top of file to avoid using BigIntegers

(defn ^:static is-prime? [^long n]
  (loop [i (long 2)] 
    (if (zero? (mod n i))
      false
      (if (>= (inc i) n) true (recur (inc i))))))

Con esta mejora, obtengo que Clojure complete 10k en 0.635 segundos (es decir, el segundo más rápido en su lista, superando a Scala)

PD: tenga en cuenta que tiene código de impresión dentro de su punto de referencia en algunos casos, no es una buena idea ya que distorsionará los resultados, especialmente si el uso de una función como printla primera causa la inicialización de los subsistemas IO o algo así.

Aquí hay una versión rápida de Clojure, usando los mismos algoritmos básicos:

(set! *unchecked-math* true)

(defn is-prime? [^long n]
  (loop [i 2]
    (if (zero? (unchecked-remainder-int n i))
      false
      (if (>= (inc i) n)
        true
        (recur (inc i))))))

(defn sexy-primes [m]
  (for [x (range 11 (inc m))
        :when (and (is-prime? x) (is-prime? (- x 6)))]
    [(- x 6) x]))

Funciona unas 20 veces más rápido que el original en mi máquina. Y aquí hay una versión que aprovecha la nueva biblioteca de reductores en 1.5 (requiere Java 7 o JSR 166):

(require '[clojure.core.reducers :as r]) ;'

(defn sexy-primes [m]
  (->> (vec (range 11 (inc m)))
       (r/filter #(and (is-prime? %) (is-prime? (- % 6))))
       (r/map #(list (- % 6) %))
       (r/fold (fn ([] []) ([a b] (into a b))) conj)))

Funciona unas 40 veces más rápido que el original. En mi máquina, son 100k en 1,5 segundos.

Responderé solo el n. ° 2, ya que es el único que tengo algo remotamente inteligente que decir, pero para su código Python, está creando una lista intermedia en is_prime, mientras que está usando .mapen su allRuby, que es solo iterando.

Si cambia su is_primea:

def is_prime(n):
    return all((n%j > 0) for j in range(2, n))

están a la par.

Podría optimizar aún más Python, pero mi Ruby no es lo suficientemente bueno para saber cuándo he dado más ventaja (por ejemplo, usar xrangehace que Python gane en mi máquina, pero no recuerdo si el rango de Ruby que usaste crea un rango completo en la memoria o no).

EDITAR: Sin ser demasiado tonto, hacer que el código de Python se vea así:

import time

def is_prime(n):
    return all(n % j for j in xrange(2, n))

def primes_below(x):
    return [(j-6, j) for j in xrange(9, x + 1) if is_prime(j) and is_prime(j-6)]

a = int(round(time.time() * 1000))
print(primes_below(10*1000))
b = int(round(time.time() * 1000))
print(str((b-a)) + " mils")

lo que no cambia mucho más, lo pone en 1,5 segundos para mí y, siendo más tonto, ejecutarlo con PyPy lo pone en 0,3 segundos para 10K y 21 segundos para 100K.

Puede hacer que Scala sea mucho más rápido modificando su isPrimemétodo para

  def isPrime(n: Int, i: Int = 2): Boolean = 
    if (i == n) true 
    else if (n % i != 0) isPrime(n, i + 1)
    else false

No es tan conciso, pero el programa se ejecuta en el 40% del tiempo.

Recortamos Rangelos Functionobjetos superfluos y anónimos , el compilador de Scala reconoce la recursividad de la cola y la convierte en un bucle while, que la JVM puede convertir en un código máquina más o menos óptimo, por lo que no debería estar demasiado lejos de C versión.

Consulte también: ¿Cómo optimizar las comprensiones y los bucles en Scala?

Aquí está mi versión scala en paralelo y no paralelo, solo por diversión: (en mi computación de doble núcleo, la versión paralela toma 335ms mientras que la versión no paralela toma 655ms)

object SexyPrimes {
  def isPrime(n: Int): Boolean = 
    (2 to math.sqrt(n).toInt).forall{ n%_ != 0 }

  def isSexyPrime(n: Int): Boolean = isPrime(n) && isPrime(n-6)

  def findPrimesPar(n: Int) {
    for(k <- (11 to n).par)
      if(isSexyPrime(k)) printf("%d %d\n",k-6,k)
  }

  def findPrimes(n: Int) {
    for(k <- 11 to n)
      if(isSexyPrime(k)) printf("%d %d\n",k-6,k)
  }


  def timeOf(call : =>Unit) {
    val start = System.currentTimeMillis
    call
    val end = System.currentTimeMillis
    println((end-start)+" mils")
  }

  def main(args: Array[String]) {
    timeOf(findPrimes(100*1000))
    println("------------------------")
    timeOf(findPrimesPar(100*1000))
  }
}

EDITAR: De acuerdo con la sugerencia de Emil H , he cambiado mi código para evitar los efectos del calentamiento de IO y jvm:

El resultado se muestra en mi cálculo:

Lista (3432, 1934, 3261, 1716, 3229, 1654, 3214, 1700)

object SexyPrimes {
  def isPrime(n: Int): Boolean = 
    (2 to math.sqrt(n).toInt).forall{ n%_ != 0 }

  def isSexyPrime(n: Int): Boolean = isPrime(n) && isPrime(n-6)

  def findPrimesPar(n: Int) {
    for(k <- (11 to n).par)
      if(isSexyPrime(k)) ()//printf("%d %d\n",k-6,k)
  }

  def findPrimes(n: Int) {
    for(k <- 11 to n)
      if(isSexyPrime(k)) ()//printf("%d %d\n",k-6,k)
  }


  def timeOf(call : =>Unit): Long = {
    val start = System.currentTimeMillis
    call
    val end = System.currentTimeMillis
    end - start 
  }

  def main(args: Array[String]) {
    val xs = timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
             timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
             timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
             timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::Nil
    println(xs)
  }
}

No importa los puntos de referencia; el problema me interesó e hice algunos ajustes rápidos. Utiliza el lru_cachedecorador, que memoriza una función; así que cuando llamamos is_prime(i-6), básicamente obtenemos ese cheque principal gratis. Este cambio reduce el trabajo aproximadamente a la mitad. Además, podemos hacer que las range()llamadas pasen por los números impares, reduciendo el trabajo aproximadamente a la mitad nuevamente.

http://en.wikipedia.org/wiki/Memoization

http://docs.python.org/dev/library/functools.html

Esto requiere Python 3.2 o más reciente para obtenerlo lru_cache, pero podría funcionar con un Python más antiguo si instala una receta de Python que proporcione lru_cache. Si está usando Python 2.x, realmente debería usar en xrange()lugar de range().

http://code.activestate.com/recipes/577479-simple-caching-decorator/

from functools import lru_cache
import time as time_

@lru_cache()
def is_prime(n):
    return n%2 and all(n%i for i in range(3, n, 2))

def primes_below(x):
    return [(i-6, i) for i in range(9, x+1, 2) if is_prime(i) and is_prime(i-6)]

correct100 = [(5, 11), (7, 13), (11, 17), (13, 19), (17, 23), (23, 29),
        (31, 37), (37, 43), (41, 47), (47, 53), (53, 59), (61, 67), (67, 73),
        (73, 79), (83, 89)]
assert(primes_below(100) == correct100)

a = time_.time()
print(primes_below(30*1000))
b = time_.time()

elapsed = b - a
print("{} msec".format(round(elapsed * 1000)))

Lo anterior solo tomó muy poco tiempo para editarse. Decidí dar un paso más y hacer que la prueba de primos solo pruebe con divisores primos, y solo hasta la raíz cuadrada del número que se está probando. La forma en que lo hice solo funciona si verifica los números en orden, para que pueda acumular todos los números primos a medida que avanza; pero este problema ya estaba comprobando los números en orden, así que estaba bien.

En mi computadora portátil (nada especial; el procesador es un AMD Turion II "K625" de 1.5 GHz) esta versión produjo una respuesta de 100K en menos de 8 segundos.

from functools import lru_cache
import math
import time as time_

known_primes = set([2, 3, 5, 7])

@lru_cache(maxsize=128)
def is_prime(n):
    last = math.ceil(math.sqrt(n))
    flag = n%2 and all(n%x for x in known_primes if x <= last)
    if flag:
        known_primes.add(n)
    return flag

def primes_below(x):
    return [(i-6, i) for i in range(9, x+1, 2) if is_prime(i) and is_prime(i-6)]

correct100 = [(5, 11), (7, 13), (11, 17), (13, 19), (17, 23), (23, 29),
        (31, 37), (37, 43), (41, 47), (47, 53), (53, 59), (61, 67), (67, 73),
        (73, 79), (83, 89)]
assert(primes_below(100) == correct100)

a = time_.time()
print(primes_below(100*1000))
b = time_.time()

elapsed = b - a
print("{} msec".format(round(elapsed * 1000)))

El código anterior es bastante fácil de escribir en Python, Ruby, etc., pero sería más complicado en C.

No puede comparar los números de esta versión con los números de las otras versiones sin volver a escribir las otras para usar trucos similares. No estoy tratando de probar nada aquí; Simplemente pensé que el problema era divertido y quería ver qué tipo de mejoras de rendimiento fáciles podía obtener.

¡No te olvides de Fortran! (Mayormente bromeando, pero esperaría un desempeño similar al de C). Las declaraciones con signos de exclamación son opcionales, pero de buen estilo. ( !es un personaje de comentario en fortran 90)

logical function isprime(n)
IMPLICIT NONE !
integer :: n,i
do i=2,n
   if(mod(n,i).eq.0)) return .false.
enddo
return .true.
end

subroutine findprimes(m)
IMPLICIT NONE !
integer :: m,i
logical, external :: isprime

do i=11,m
   if(isprime(i) .and. isprime(i-6))then
      write(*,*) i-6,i
   endif
enddo
end

program main
findprimes(10*1000)
end

No pude resistirme a hacer algunas de las optimizaciones más obvias para la versión C que hicieron que la prueba de 100k ahora tomara 0.3s en mi máquina (5 veces más rápido que la versión C en la pregunta, ambas compiladas con MSVC 2010 / Ox) .

int isprime( int x )
{
    int i, n;
    for( i = 3, n = x >> 1; i <= n; i += 2 )
        if( x % i == 0 )
            return 0;
    return 1;
}

void findprimes( int m )
{
    int i, s = 3; // s is bitmask of primes in last 3 odd numbers
    for( i = 11; i < m; i += 2, s >>= 1 ) {
        if( isprime( i ) ) {
            if( s & 1 )
                printf( "%d %d\n", i - 6, i );
            s |= 1 << 3;
        }
    }
}

main() {
    findprimes( 10 * 1000 );
}

Aquí está la implementación idéntica en Java:

public class prime
{
    private static boolean isprime( final int x )
    {
        for( int i = 3, n = x >> 1; i <= n; i += 2 )
            if( x % i == 0 )
                return false;
        return true;
    }

    private static void findprimes( final int m )
    {
        int s = 3; // s is bitmask of primes in last 3 odd numbers
        for( int i = 11; i < m; i += 2, s >>= 1 ) {
            if( isprime( i ) ) {
                if( ( s & 1 ) != 0 )
                    print( i );
                s |= 1 << 3;
            }
        }
    }

    private static void print( int i )
    {
        System.out.println( ( i - 6 ) + " " + i );
    }

    public static void main( String[] args )
    {
        // findprimes( 300 * 1000 ); // for some JIT training
        long time = System.nanoTime();
        findprimes( 10 * 1000 );
        time = System.nanoTime() - time;
        System.err.println( "time: " + ( time / 10000 ) / 100.0 + "ms" );
    }
}

Con Java 1.7.0_04, esto se ejecuta casi exactamente tan rápido como la versión C. La máquina virtual cliente o servidor no muestra mucha diferencia, excepto que el entrenamiento JIT parece ayudar un poco a la máquina virtual del servidor (~ 3%) mientras que casi no tiene ningún efecto con la máquina virtual cliente. La salida en Java parece ser más lenta que en C. Si la salida se reemplaza con un contador estático en ambas versiones, la versión de Java se ejecuta un poco más rápido que la versión C.

Estos son mis tiempos para la carrera de 100k:

• 319ms C compilado con / Ox y salida a> NIL:
• 312ms C compilado con / Ox y contador estático
• VM de cliente Java de 324ms con salida a> NIL:
• VM cliente Java de 299 ms con contador estático

y la carrera de 1 M (16386 resultados):

• 24.95s C compilado con / Ox y contador estático
• 25.08s Java cliente VM con contador estático
• 24.86s Java Server VM con contador estático

Si bien esto no responde realmente a sus preguntas, muestra que los pequeños ajustes pueden tener un impacto notable en el rendimiento. Entonces, para poder comparar realmente idiomas, debe intentar evitar todas las diferencias algorítmicas tanto como sea posible.

También da una pista de por qué Scala parece bastante rápido. Se ejecuta en Java VM y, por lo tanto, se beneficia de su impresionante rendimiento.

En Scala, intente usar Tuple2 en lugar de List, debería ir más rápido. Simplemente elimine la palabra 'Lista' ya que (x, y) es un Tuple2.

Tuple2 está especializado para Int, Long y Double, lo que significa que no tendrá que empaquetar / desempaquetar esos tipos de datos sin procesar. Fuente Tuple2 . List no está especializado. Fuente de la lista .

Aquí está el código para la versión de Go (golang.org):

package main

import (
    "fmt"
)


func main(){
    findprimes(10*1000)
}

func isprime(x int) bool {
    for i := 2; i < x; i++ {
        if x%i == 0 {
            return false
        }
    }
    return true
}

func findprimes(m int){
    for i := 11; i < m; i++ {
        if isprime(i) && isprime(i-6) {
            fmt.Printf("%d %d\n", i-6, i)
        }
    }
}

Funcionó tan rápido como la versión C.

Usando un Asus u81a Intel Core 2 Duo T6500 2.1GHz, 2MB de caché L2, 800MHz FSB. 4 GB de RAM

La versión 100k: C: 2.723s Go: 2.743s

Con 1000000 (1 M en lugar de 100 K): C: 3m35.458s Go: 3m36.259s

Pero creo que sería justo usar las capacidades integradas de subprocesos múltiples de Go y comparar esa versión con la versión C normal (sin subprocesos múltiples), solo porque es casi demasiado fácil realizar subprocesos múltiples con Go.

Actualización: hice una versión paralela usando Goroutines en Go:

package main

import (
  "fmt"
  "runtime"
)

func main(){
    runtime.GOMAXPROCS(4)
    printer := make(chan string)
    printer2 := make(chan string)
    printer3 := make(chan string)
    printer4 := make(chan string)
    finished := make(chan int)

    var buffer, buffer2, buffer3 string

    running := 4
    go findprimes(11, 30000, printer, finished)
    go findprimes(30001, 60000, printer2, finished)
    go findprimes(60001, 85000, printer3, finished)
    go findprimes(85001, 100000, printer4, finished)

    for {
      select {
        case i := <-printer:
          // batch of sexy primes received from printer channel 1, print them
          fmt.Printf(i)
        case i := <-printer2:
          // sexy prime list received from channel, store it
          buffer = i
        case i := <-printer3:
          // sexy prime list received from channel, store it
          buffer2 = i
        case i := <-printer4:
          // sexy prime list received from channel, store it
          buffer3 = i
        case <-finished:
          running--
          if running == 0 {
              // all goroutines ended
              // dump buffer to stdout
              fmt.Printf(buffer)
              fmt.Printf(buffer2)
              fmt.Printf(buffer3)
              return
          }
      }
    }
}

func isprime(x int) bool {
    for i := 2; i < x; i++ {
        if x%i == 0 {
            return false
        }
    }
    return true
}

func findprimes(from int, to int, printer chan string, finished chan int){
    str := ""
    for i := from; i <= to; i++ {
        if isprime(i) && isprime(i-6) {
            str = str + fmt.Sprintf("%d %d\n", i-6, i)
      }
    }
    printer <- str
    //fmt.Printf("Finished %d to %d\n", from, to)
    finished <- 1
}

La versión paralelizada usó un promedio de 2.743 segundos, exactamente el mismo tiempo que usó la versión regular.

La versión paralelizada se completó en 1.706 segundos. Utilizaba menos de 1,5 Mb de RAM.

Una cosa extraña: mi kubuntu de 64 bits de doble núcleo nunca alcanzó su punto máximo en ambos núcleos. Parecía que Go estaba usando solo un núcleo. Fijo con una llamada aruntime.GOMAXPROCS(4)

Actualización: Ejecuté la versión paralelizada hasta 1 millón de números. Uno de los núcleos de Mi CPU estuvo al 100% todo el tiempo, mientras que el otro no se usó en absoluto (extraño). Tomó un minuto más que las versiones C y Go normales. :(

Con 1000000 (1 M en lugar de 100 K):

C: 3m35.458s Go: 3m36.259s Go using goroutines:3 min 27,137 s2m16.125s

La versión 100k:

C: 2.723s Go: 2.743s Go using goroutines: 1.706s

Solo por el gusto de hacerlo, aquí hay una versión paralela de Ruby.

require 'benchmark'

num = ARGV[0].to_i

def is_prime?(n)
  (2...n).all?{|m| n%m != 0 }
end

def sexy_primes_default(x)
    (9..x).map do |i|
        [i-6, i]
    end.select do |j|
        j.all?{|j| is_prime? j}
    end
end

def sexy_primes_threads(x)
    partition = (9..x).map do |i|
        [i-6, i]
    end.group_by do |x|
        x[0].to_s[-1]
    end
    threads = Array.new
    partition.each_key do |k|
       threads << Thread.new do
            partition[k].select do |j|
                j.all?{|j| is_prime? j}
            end
        end
    end
    threads.each {|t| t.join}
    threads.map{|t| t.value}.reject{|x| x.empty?}
end

puts "Running up to num #{num}"

Benchmark.bm(10) do |x|
    x.report("default") {a = sexy_primes_default(num)}
    x.report("threads") {a = sexy_primes_threads(num)}
end

En mi MacBook Air Core i5 de 1.8GHz, los resultados de rendimiento son:

# Ruby 1.9.3
$ ./sexyprimes.rb 100000
Running up to num 100000
                 user     system      total        real
default     68.840000   0.060000  68.900000 ( 68.922703)
threads     71.730000   0.090000  71.820000 ( 71.847346)

# JRuby 1.6.7.2 on JVM 1.7.0_05
$ jruby --1.9 --server sexyprimes.rb 100000
Running up to num 100000
                user     system      total        real
default    56.709000   0.000000  56.709000 ( 56.708000)
threads    36.396000   0.000000  36.396000 ( 36.396000)

# JRuby 1.7.0.preview1 on JVM 1.7.0_05
$ jruby --server sexyprimes.rb 100000
Running up to num 100000
             user     system      total        real
default     52.640000   0.270000  52.910000 ( 51.393000)
threads    105.700000   0.290000 105.990000 ( 30.298000)

Parece que el JIT de JVM le está dando a Ruby un buen aumento de rendimiento en el caso predeterminado, mientras que el verdadero multiproceso ayuda a JRuby a funcionar un 50% más rápido en el caso de subprocesos. ¡Lo que es más interesante es que JRuby 1.7 mejora la puntuación de JRuby 1.6 en un saludable 17%!

Basado en la respuesta de x4u , escribí una versión de scala usando recursividad, y la mejoré yendo solo a sqrt en lugar de x / 2 para la función de verificación principal. Obtengo ~ 250ms por 100k y ~ 600ms por 1M. Seguí adelante y pasé a 10M en ~ 6s.

import scala.annotation.tailrec

var count = 0;
def print(i:Int) = {
  println((i - 6) + " " + i)
  count += 1
}

@tailrec def isPrime(n:Int, i:Int = 3):Boolean = {
  if(n % i == 0) return false;
  else if(i * i > n) return true;
  else isPrime(n = n, i = i + 2)
}      

@tailrec def findPrimes(max:Int, bitMask:Int = 3, i:Int = 11):Unit = {
  if (isPrime(i)) {
    if((bitMask & 1) != 0) print(i)
    if(i + 2 < max) findPrimes(max = max, bitMask = (bitMask | (1 << 3)) >> 1, i = i + 2)
  } else if(i + 2 < max) {
    findPrimes(max = max, bitMask = bitMask >> 1, i = i + 2)
  }
}

val a = System.currentTimeMillis()
findPrimes(max=10000000)
println(count)
val b = System.currentTimeMillis()
println((b - a).toString + " mils")

También volví y escribí una versión de CoffeeScript (V8 JavaScript), que obtiene ~ 15ms para 100k, 250ms para 1M y 6s para 10M, usando un contador (ignorando E / S). Si enciendo la salida, toma ~ 150ms para 100k, 1s para 1M y 12s para 10M. No se pudo usar la recursividad de cola aquí, desafortunadamente, así que tuve que convertirlo nuevamente en bucles.

count = 0;
print = (i) ->
  console.log("#{i - 6} #{i}")
  count += 1
  return

isPrime = (n) ->
  i = 3
  while i * i < n
    if n % i == 0
      return false
    i += 2
  return true

findPrimes = (max) ->
  bitMask = 3
  for i in [11..max] by 2
    prime = isPrime(i)
    if prime
      if (bitMask & 1) != 0
        print(i)
      bitMask |= (1 << 3)
    bitMask >>= 1
  return

a = new Date()
findPrimes(1000000)
console.log(count)
b = new Date()
console.log((b - a) + " ms")

La respuesta a su pregunta n. ° 1 es que Sí, la JVM es increíblemente rápida y sí, la escritura estática ayuda.

La JVM debería ser más rápida que C a largo plazo, posiblemente incluso más rápida que el lenguaje ensamblador "Normal". Por supuesto, siempre puede optimizar manualmente el ensamblaje para vencer cualquier cosa haciendo un perfil de tiempo de ejecución manual y creando una versión separada para cada CPU, simplemente tiene que ser increíblemente bueno y conocedor.

Las razones de la velocidad de Java son:

La JVM puede analizar su código mientras se ejecuta y optimizarlo manualmente, por ejemplo, si tuviera un método que pudiera analizarse estáticamente en el momento de la compilación para ser una función verdadera y la JVM notó que a menudo lo llamaba con el mismo parámetros, en realidad PODRÍA eliminar la llamada por completo y simplemente inyectar los resultados de la última llamada (no estoy seguro de si Java realmente hace esto exactamente, pero hace muchas cosas como esta).

Debido a la escritura estática, la JVM puede saber mucho sobre su código en tiempo de compilación, esto le permite optimizar previamente algunas cosas. También permite que el compilador optimice cada clase individualmente sin saber cómo otra clase planea usarla. Además, Java no tiene punteros arbitrarios a la ubicación de la memoria, SABE qué valores en la memoria pueden y no pueden cambiarse y puede optimizar en consecuencia.

La asignación de pila es MUCHO más eficiente que C, la asignación de pila de Java se parece más a la asignación de pila de C en velocidad, pero más versátil. Se ha dedicado mucho tiempo a los diferentes algoritmos utilizados aquí, es un arte; por ejemplo, todos los objetos con una vida útil corta (como las variables de pila de C) se asignan a una ubicación libre "conocida" (sin buscar un lugar libre con suficiente espacio) y se liberan todos juntos en un solo paso (como una pila emergente).

La JVM puede conocer las peculiaridades de la arquitectura de su CPU y generar código de máquina específicamente para una CPU determinada.

La JVM puede acelerar su código mucho después de que lo envió. Al igual que mover un programa a una nueva CPU puede acelerarlo, moverlo a una nueva versión de la JVM también puede brindarle rendimientos de gran velocidad adaptados a CPU que ni siquiera existían cuando compiló inicialmente su código, algo que c físicamente no puede prescindir de un recomiple.

Por cierto, la mayor parte de la mala reputación de la velocidad de Java proviene del largo tiempo de inicio para cargar la JVM (¡Algún día alguien integrará la JVM en el sistema operativo y esto desaparecerá!) Y el hecho de que muchos desarrolladores son realmente malos para escribir. Código de GUI (especialmente subprocesado) que causaba que las GUI de Java a menudo dejaran de responder y presentaran fallas. Los lenguajes simples de usar como Java y VB tienen sus fallas amplificadas por el hecho de que las capacidades del programador promedio tienden a ser más bajas que los lenguajes más complicados.