Interpretando um benchmark em C, Clojure, Python, Ruby, Scala e outros [fechado]

aviso Legal

Eu sei que benchmarks artificiais são ruins. Eles podem mostrar resultados apenas para situações estreitas muito específicas. Não presumo que uma língua seja melhor que a outra por causa de algum banco estúpido. No entanto, eu me pergunto por que os resultados são tão diferentes. Por favor, veja minhas perguntas no final.

Descrição de benchmark matemático

A referência consiste em cálculos matemáticos simples para encontrar pares de números primos que diferem por 6 (os chamados primos sexy ). Por exemplo, primos sexy abaixo de 100 seriam:(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)

Tabela de resultados

Na tabela: tempo de cálculo em segundos Executando: todos, exceto Factor, estavam em execução no VirtualBox (Debian instável amd64 convidado, 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] - Tenho medo de imaginar quanto tempo vai demorar

Listagens 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);
}

Rubi:

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")

Escala otimizada isPrime(a mesma ideia da otimização 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 otimizado 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ão

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")

Fator

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

Questões

1. Por que o Scala é tão rápido? É por causa da digitação estática ? Ou está apenas usando o JVM de forma muito eficiente?
2. Por que essa diferença tão grande entre Ruby e Python? Achei que esses dois não eram totalmente diferentes. Talvez meu código esteja errado. Por favor me esclareça! Obrigado. UPD Sim, foi um erro no meu código. Python e Ruby 1.9 são praticamente iguais.
3. Salto realmente impressionante na produtividade entre as versões Ruby.
4. Posso otimizar o código Clojure adicionando declarações de tipo? Isso vai ajudar?

Respostas gerais:

1. A tipagem estática do Scala está ajudando bastante aqui - isso significa que ele usa a JVM de maneira bastante eficiente, sem muito esforço extra.
2. Não tenho certeza da diferença Ruby / Python, mas suspeito que (2...n).all?a função is-prime?provavelmente seja muito bem otimizada em Ruby (EDITAR: parece que é esse o caso, veja a resposta de Julian para mais detalhes ...)
3. Ruby 1.9.3 é muito melhor otimizado
4. O código Clojure certamente pode ser muito acelerado! Embora o Clojure seja dinâmico por padrão, você pode usar dicas de tipo, matemática primitiva etc. para chegar perto da velocidade do Scala / Java puro em muitos casos, quando necessário.

A otimização mais importante no código Clojure seria usar matemática primitiva digitada 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))))))

Com essa melhoria, eu faço o Clojure completar 10k em 0,635 segundos (ou seja, o segundo mais rápido da sua lista, batendo o Scala)

PS, note que você tem código de impressão dentro de seu benchmark em alguns casos - não é uma boa ideia, pois isso distorce os resultados, especialmente se usar uma função como printpela primeira vez causa a inicialização de subsistemas IO ou algo parecido!

Esta é uma versão rápida do Clojure, usando os mesmos 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]))

Ele roda cerca de 20x mais rápido do que o original na minha máquina. E aqui está uma versão que aproveita a nova biblioteca de redutores em 1.5 (requer Java 7 ou 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)))

Ele é executado cerca de 40 vezes mais rápido do que o original. Na minha máquina, isso dá 100k em 1,5 segundos.

Eu vou responder apenas # 2, já que é o único que eu tenho qualquer coisa remotamente inteligente para dizer, mas para o seu código Python, você está criando uma lista intermediária is_prime, enquanto você está usando .mapem sua allem Ruby que é apenas iterando.

Se você mudar is_primepara:

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

eles estão no mesmo nível.

Eu poderia otimizar o Python ainda mais, mas meu Ruby não é bom o suficiente para saber quando eu dei mais uma vantagem (por exemplo, usando xrangefaz Python ganhar na minha máquina, mas não me lembro se o intervalo de Ruby que você usou cria um intervalo inteiro na memória ou não).

EDIT: Sem ser muito bobo, fazendo o código Python parecer:

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")

o que não muda muito mais, coloca-o em 1.5s para mim e, por ser muito bobo, executá-lo com PyPy o coloca em 0,3s para 10K e 21s para 100K.

Você pode tornar o Scala muito mais rápido, modificando seu 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

Não é tão conciso, mas o programa funciona em 40% do tempo!

Cortamos Rangeos Functionobjetos supérfluos e anônimos , o compilador Scala reconhece a recursão final e a transforma em um loop while, que a JVM pode transformar em um código de máquina mais ou menos ideal, por isso não deve estar muito longe do C versão.

Veja também: Como otimizar para compreensões e loops no Scala?

Aqui está minha versão do scala em paralelo e não paralelo, apenas por diversão: (Na minha computação dual core, a versão paralela leva 335ms enquanto a versão não paralela leva 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 acordo com Emil H a sugestão de , mudei meu código para evitar os efeitos de IO e aquecimento jvm:

O resultado mostra em meu cálculo:

List (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)
  }
}

Não importa os benchmarks; o problema me interessou e fiz alguns ajustes rápidos. Isso usa o lru_cachedecorador, que memoriza uma função; então, quando ligamos is_prime(i-6), basicamente recebemos aquele cheque principal de graça. Essa mudança reduz o trabalho aproximadamente pela metade. Além disso, podemos fazer as range()chamadas passarem apenas pelos números ímpares, reduzindo o trabalho pela metade novamente.

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

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

Isso requer Python 3.2 ou mais recente para obter lru_cache, mas pode funcionar com um Python mais antigo se você instalar uma receita Python que forneça lru_cache. Se você estiver usando Python 2.x, você realmente deve usar em xrange()vez 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)))

O texto acima demorou muito pouco para ser editado. Decidi dar um passo adiante e fazer o teste dos primos tentar apenas os divisores primos, e apenas até a raiz quadrada do número que está sendo testado. A maneira como fiz isso só funciona se você verificar os números em ordem, de modo que pode acumular todos os primos à medida que avança; mas esse problema já era verificar os números em ordem, então tudo bem.

No meu laptop (nada de especial; o processador é um AMD Turion II "K625" de 1,5 GHz) esta versão produziu uma resposta para 100K em 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)))

O código acima é muito fácil de escrever em Python, Ruby, etc., mas seria mais problemático em C.

Você não pode comparar os números desta versão com os números das outras versões sem reescrever as outras para usar truques semelhantes. Não estou tentando provar nada aqui; Achei que o problema era divertido e queria ver que tipo de melhorias fáceis de desempenho eu poderia obter.

Não se esqueça do Fortran! (Principalmente brincando, mas eu esperaria um desempenho semelhante ao C). As declarações com pontos de exclamação são opcionais, mas são de bom estilo. ( !é um caractere de comentário no 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

Não pude resistir a fazer algumas das otimizações mais óbvias para a versão C que fez o teste de 100k agora levar 0.3s na minha máquina (5 vezes mais rápido do que a versão C em questão, ambas compiladas com 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 );
}

Aqui está a implementação idêntica em 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" );
    }
}

Com o Java 1.7.0_04, ele funciona quase tão rápido quanto a versão C. Cliente ou servidor VM não mostra muita diferença, exceto que o treinamento JIT parece ajudar o servidor VM um pouco (~ 3%) enquanto quase não tem efeito com o cliente VM. A saída em Java parece ser mais lenta do que em C. Se a saída for substituída por um contador estático em ambas as versões, a versão Java é executada um pouco mais rápido do que a versão C.

Estes são os meus tempos para a corrida de 100k:

• 319ms C compilado com / Ox e saída para> NIL:
• 312ms C compilado com / Ox e contador estático
• VM cliente Java de 324ms com saída para> NIL:
• 299ms Java cliente VM com contador estático

e a execução de 1M (16386 resultados):

• 24.95s C compilado com / Ox e contador estático
• 25.08s Java cliente VM com contador estático
• 24.86s Java servidor VM com contador estático

Embora isso não responda realmente às suas perguntas, mostra que pequenos ajustes podem ter um impacto notável no desempenho. Portanto, para realmente comparar as linguagens, você deve tentar evitar todas as diferenças algorítmicas tanto quanto possível.

Também dá uma dica por que Scala parece bastante rápido. Ele é executado no Java VM e, portanto, se beneficia de seu desempenho impressionante.

No Scala, tente usar Tuple2 em vez de List, deve ser mais rápido. Apenas remova a palavra 'Lista', pois (x, y) é uma Tupla2.

Tuple2 é especializado para Int, Long e Double, o que significa que não terá que encaixotar / desencaixotar esses tipos de dados brutos. Fonte Tuple2 . A lista não é especializada. Fonte da lista .

Este é o código para a versão 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)
        }
    }
}

Funcionou tão rápido quanto a versão C.

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

A versão 100k: C: 2.723s Go: 2.743s

Com 1000000 (1 milhão em vez de 100 K): C: 3m35.458s Go: 3m36.259s

Mas acho que seria justo usar os recursos de multithreading integrados do Go e comparar essa versão com a versão C normal (sem multithreading), só porque é quase muito fácil fazer multithreading com Go.

Atualização: fiz uma versão paralela usando Goroutines no 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
}

A versão paralelizada utilizou em média 2,743 segundos, exatamente o mesmo tempo que a versão regular utilizou.

A versão paralelizada foi concluída em 1.706 segundos. Ele usava menos de 1,5 Mb de RAM.

Uma coisa estranha: meu dual core kubuntu 64bit nunca atingiu o pico em ambos os núcleos. Parecia que Go estava usando apenas um núcleo. Corrigido com uma chamada pararuntime.GOMAXPROCS(4)

Atualização: Executei a versão paralelizada até 1M de números. Um dos núcleos da Minha CPU estava 100% o tempo todo, enquanto o outro não era usado (ímpar). Demorou um minuto inteiro a mais do que as versões C e Go regulares. :(

Com 1000000 (1 milhão em vez de 100 K):

C: 3m35.458s Go: 3m36.259s Go using goroutines:3m27.137s2m16.125s

A versão 100k:

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

Só por diversão, aqui está uma versão 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

No meu MacBook Air Core i5 de 1,8 GHz, os resultados de desempenho são:

# 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 o JIT da JVM está dando ao Ruby um bom aumento de desempenho no caso padrão, enquanto o multithreading verdadeiro ajuda o JRuby a executar 50% mais rápido no caso de encadeamento. O que é mais interessante é que o JRuby 1.7 melhora a pontuação do JRuby 1.6 em 17%!

Com base na resposta de x4u , escrevi uma versão de scala usando recursão e a aprimorei indo apenas para sqrt em vez de x / 2 para a função de verificação principal. Obtenho ~ 250ms para 100k e ~ 600ms para 1M. Eu fui em frente e fui para 10 milhões em ~ 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")

Também voltei e escrevi uma versão do CoffeeScript (V8 JavaScript), que obtém ~ 15ms para 100k, 250ms para 1M e 6s para 10M, usando um contador (ignorando E / S). Se eu ligar a saída, leva ~ 150ms para 100k, 1s para 1M e 12s para 10M. Não foi possível usar recursão de cauda aqui, infelizmente, então tive que convertê-la de volta em loops.

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")

A resposta à sua pergunta nº 1 é que sim, a JVM é incrivelmente rápida e sim a digitação estática ajuda.

A JVM deve ser mais rápida do que C a longo prazo, possivelmente ainda mais rápida do que a linguagem assembly "Normal" - Claro, você sempre pode otimizar manualmente o assembly para vencer qualquer coisa, fazendo o perfil de tempo de execução manual e criando uma versão separada para cada CPU, você apenas tem que ser incrivelmente bom e qualificado.

As razões para a velocidade do Java são:

A JVM pode analisar seu código enquanto é executado e otimizá-lo manualmente - por exemplo, se você tivesse um método que pudesse ser analisado estaticamente no momento da compilação para ser uma função verdadeira e a JVM percebesse que você costumava chamá-lo com a mesma parâmetros, ele PODERIA realmente eliminar a chamada completamente e apenas injetar os resultados da última chamada (não tenho certeza se o Java realmente faz isso exatamente, mas ele faz muitas coisas assim).

Devido à tipagem estática, a JVM pode saber muito sobre o seu código em tempo de compilação, o que permite que ela pré-otimize várias coisas. Também permite que o compilador otimize cada classe individualmente, sem conhecimento de como outra classe está planejando usá-la. Além disso, o Java não tem ponteiros arbitrários para a localização da memória, ele SABE quais valores na memória podem e não podem ser alterados e pode otimizar de acordo.

A alocação de heap é MUITO mais eficiente do que C, a alocação de heap do Java é mais parecida com a alocação de pilha do C em velocidade - ainda mais versátil. Muito tempo foi gasto nos diferentes algroítimos usados ​​aqui, é uma arte - por exemplo, todos os objetos com uma vida útil curta (como as variáveis ​​da pilha de C) são alocados em um local livre "conhecido" (sem busca por um local livre com espaço suficiente) e são todos liberados juntos em uma única etapa (como uma pilha pop).

A JVM pode conhecer peculiaridades sobre a arquitetura de sua CPU e gerar código de máquina especificamente para uma determinada CPU.

A JVM pode acelerar seu código muito depois de você o enviar. Assim como mover um programa para uma nova CPU pode acelerá-lo, movê-lo para uma nova versão da JVM também pode fornecer desempenhos de grande velocidade planejados para CPUs que nem existiam quando você inicialmente compilou seu código, algo c fisicamente não pode fazer sem um recomiple.

A propósito, a maior parte da má reputação para a velocidade do java vem do longo tempo de inicialização para carregar o JVM (algum dia alguém irá construir o JVM no sistema operacional e isso irá embora!) E o fato de que muitos desenvolvedores são realmente ruins em escrever Código GUI (especialmente encadeado) que fazia com que as GUIs Java muitas vezes parassem de responder e apresentassem falhas. Linguagens simples de usar como Java e VB têm suas falhas amplificadas pelo fato de que as capacidades do programador médio tendem a ser menores do que as linguagens mais complicadas.