Interpréter un benchmark en C, Clojure, Python, Ruby, Scala et autres [fermé]

Avertissement

Je sais que les repères artificiels sont mauvais. Ils ne peuvent montrer des résultats que pour une situation étroite très spécifique. Je ne suppose pas qu'une langue est meilleure que l'autre à cause d'un banc stupide. Cependant, je me demande pourquoi les résultats sont si différents. S'il vous plaît voir mes questions en bas.

Description du benchmark mathématique

Le benchmark est de simples calculs mathématiques pour trouver des paires de nombres premiers qui diffèrent de 6 (appelés nombres premiers sexy ) Par exemple, les nombres premiers sexy inférieurs à 100 seraient:(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)

Tableau des résultats

Dans le tableau: temps de calcul en secondes En cours d'exécution: tous sauf Factor s'exécutaient dans VirtualBox (invité amd64 instable Debian, hôte 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] - J'ai peur d'imaginer combien de temps cela prendra

Listes de codes

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

Rubis:

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 optimisé isPrime(la même idée que dans l'optimisation 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 optimisé 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))))))

Python

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

Facteur

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

Des questions

1. Pourquoi Scala est si rapide? Est-ce à cause du typage statique ? Ou il utilise simplement JVM de manière très efficace?
2. Pourquoi une telle différence entre Ruby et Python? Je pensais que ces deux n'étaient pas totalement différents. Peut-être que mon code est erroné. Veuillez m'éclairer! Merci. UPD Oui, c'était une erreur dans mon code. Python et Ruby 1.9 sont assez égaux.
3. Saut de productivité vraiment impressionnant entre les versions de Ruby.
4. Puis-je optimiser le code Clojure en ajoutant des déclarations de type? Cela aidera-t-il?

Réponses approximatives:

1. Le typage statique de Scala l'aide pas mal ici - cela signifie qu'il utilise la JVM assez efficacement sans trop d'effort supplémentaire.
2. Je ne suis pas tout à fait sûr de la différence Ruby / Python, mais je soupçonne que (2...n).all?dans la fonction is-prime?est susceptible d'être assez bien optimisée dans Ruby (EDIT: cela semble être le cas, voir la réponse de Julian pour plus de détails ...)
3. Ruby 1.9.3 est juste beaucoup mieux optimisé
4. Le code de Clojure peut certainement être beaucoup accéléré! Bien que Clojure soit dynamique par défaut, vous pouvez utiliser des indices de type, des mathématiques primitives, etc. pour vous rapprocher de la vitesse Scala / Java pure dans de nombreux cas lorsque vous en avez besoin.

L'optimisation la plus importante dans le code Clojure serait d'utiliser des mathématiques primitives typées à l'intérieur is-prime?, quelque chose comme:

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

Avec cette amélioration, Clojure termine 10 km en 0,635 secondes (c'est-à-dire le deuxième plus rapide de votre liste, battant Scala)

PS notez que vous avez l'impression de code dans votre benchmark dans certains cas - ce n'est pas une bonne idée car cela déformera les résultats, surtout si l'utilisation d'une fonction comme printpour la première fois provoque l'initialisation des sous-systèmes IO ou quelque chose du genre!

Voici une version rapide de Clojure, utilisant les mêmes algorithmes de base:

(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]))

Il fonctionne environ 20 fois plus vite que votre original sur ma machine. Et voici une version qui exploite la nouvelle bibliothèque de réducteurs en 1.5 (nécessite 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)))

Cela fonctionne environ 40 fois plus vite que votre original. Sur ma machine, c'est 100k en 1,5 seconde.

Je répondrai juste n ° 2, car c'est le seul que j'ai quelque chose d'intelligent à dire à distance, mais pour votre code Python, vous créez une liste intermédiaire dans is_prime, alors que vous utilisez .mapdans votre alldans Ruby qui est juste itération.

Si vous changez votre is_primeen:

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

ils sont à égalité.

Je pourrais optimiser davantage Python, mais mon Ruby n'est pas assez bon pour savoir quand j'ai donné plus d'avantage (par exemple, utiliser xrangefait gagner Python sur ma machine, mais je ne me souviens pas si la gamme Ruby que vous avez utilisée crée une plage entière en mémoire ou non).

EDIT: Sans être trop ridicule, faire ressembler le code Python à:

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

ce qui ne change pas beaucoup plus, le met à 1,5 s pour moi, et, en étant très ridicule, l'exécuter avec PyPy le met à 0,3s pour 10K et 21s pour 100K.

Vous pouvez rendre la Scala beaucoup plus rapide en modifiant votre isPrimeméthode pour

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

Pas aussi concis mais le programme fonctionne dans 40% du temps!

Nous supprimons les objets superflus Rangeet anonymes Function, le compilateur Scala reconnaît la récursion de queue et la transforme en une boucle while, que la JVM peut transformer en code machine plus ou moins optimal, donc il ne devrait pas être trop éloigné du C version.

Voir aussi: Comment optimiser les for-compréhensions et les boucles dans Scala?

Voici ma version scala à la fois parallèle et non parallèle, juste pour le plaisir: (Dans mon calcul dual core, la version parallèle prend 335 ms tandis que la version non parallèle prend 655 ms)

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

EDIT: Selon la suggestion d' Emil H , j'ai changé mon code pour éviter les effets du préchauffage IO et jvm:

Le résultat s'affiche dans mon calcul:

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

Peu importe les repères; le problème m'a intéressé et j'ai fait quelques ajustements rapides. Cela utilise le lru_cachedécorateur, qui mémorise une fonction; Ainsi, lorsque nous appelons, is_prime(i-6)nous obtenons ce chèque de premier ordre gratuitement. Ce changement réduit le travail à peu près de moitié. En outre, nous pouvons faire passer les range()appels uniquement par les nombres impairs, ce qui réduit le travail à peu près de moitié.

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

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

Cela nécessite Python 3.2 ou plus récent pour obtenir lru_cache, mais pourrait fonctionner avec un ancien Python si vous installez une recette Python qui fournit lru_cache. Si vous utilisez Python 2.x, vous devriez vraiment utiliser à la xrange()place 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)))

Ce qui précède n'a pris que très peu de temps à modifier. J'ai décidé d'aller plus loin et de faire en sorte que le test des nombres premiers n'essaie que les diviseurs premiers, et seulement jusqu'à la racine carrée du nombre testé. La façon dont je l'ai fait ne fonctionne que si vous vérifiez les nombres dans l'ordre, afin qu'il puisse accumuler tous les nombres premiers au fur et à mesure; mais ce problème vérifiait déjà les nombres dans l'ordre, donc c'était bien.

Sur mon ordinateur portable (rien de spécial; le processeur est un AMD Turion II "K625" 1,5 GHz), cette version a produit une réponse pour 100K en moins de 8 secondes.

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

Le code ci-dessus est assez facile à écrire en Python, Ruby, etc. mais serait plus pénible en C.

Vous ne pouvez pas comparer les chiffres de cette version avec les chiffres des autres versions sans réécrire les autres pour utiliser des astuces similaires. Je n'essaye pas de prouver quoi que ce soit ici; Je pensais juste que le problème était amusant et je voulais voir quel genre d'améliorations de performances faciles je pourrais glaner.

N'oubliez pas Fortran! (Surtout en plaisantant, mais je m'attendrais à des performances similaires à C). Les instructions avec des points d'exclamation sont facultatives, mais de bon style. ( !est un caractère de commentaire dans 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

Je n'ai pas pu résister à quelques-unes des optimisations les plus évidentes pour la version C qui faisaient que le test de 100k prenait maintenant 0,3 s sur ma machine (5 fois plus rapide que la version C de la question, toutes deux compilées avec 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 );
}

Voici l'implémentation identique 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" );
    }
}

Avec Java 1.7.0_04, cela fonctionne presque exactement aussi vite que la version C. La VM cliente ou serveur ne montre pas beaucoup de différence, sauf que la formation JIT semble aider un peu la VM serveur (~ 3%) alors qu'elle n'a presque aucun effet avec la VM cliente. La sortie en Java semble être plus lente qu'en C. Si la sortie est remplacée par un compteur statique dans les deux versions, la version Java s'exécute un peu plus vite que la version C.

Voici mes temps pour la course de 100 km:

• 319ms C compilé avec / Ox et sortie vers> NIL:
• 312ms C compilé avec / Ox et compteur statique
• VM client Java 324 ms avec sortie vers> NIL:
• VM cliente Java 299 ms avec compteur statique

et la course 1M (16386 résultats):

• 24.95s C compilé avec / Ox et compteur statique
• 25.08s VM cliente Java avec compteur statique
• Machine virtuelle serveur Java 24.86s avec compteur statique

Bien que cela ne réponde pas vraiment à vos questions, cela montre que de petites modifications peuvent avoir un impact notable sur les performances. Donc, pour pouvoir vraiment comparer les langues, vous devez essayer d'éviter autant que possible toutes les différences algorithmiques.

Cela donne également une idée des raisons pour lesquelles Scala semble plutôt rapide. Il fonctionne sur la machine virtuelle Java et bénéficie ainsi de ses performances impressionnantes.

Dans Scala, essayez d'utiliser Tuple2 au lieu de List, cela devrait aller plus vite. Supprimez simplement le mot 'List' puisque (x, y) est un Tuple2.

Tuple2 est spécialisé pour Int, Long et Double, ce qui signifie qu'il n'aura pas à boxer / déballer ces types de données bruts. Source Tuple2 . La liste n'est pas spécialisée. Liste source .

Voici le code de la version 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)
        }
    }
}

Il a fonctionné aussi vite que la version C.

Utilisation d'un Asus u81a Intel Core 2 Duo T6500 2,1 GHz, 2 Mo de cache L2, bus frontal à 800 MHz. 4 Go de RAM

La version 100k: C: 2.723s Go: 2.743s

Avec 1000000 (1M au lieu de 100K): C: 3m35.458s Go: 3m36.259s

Mais je pense qu'il serait juste d'utiliser les capacités multithreading intégrées de Go et de comparer cette version avec la version C standard (sans multithreading), simplement parce qu'il est presque trop facile de faire du multithreading avec Go.

Mise à jour: j'ai fait une version parallèle en utilisant Goroutines dans 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 version parallélisée utilisée en moyenne 2,743 secondes, exactement le même temps que la version régulière utilisée.

La version parallélisée s'est terminée en 1,706 secondes. Il a utilisé moins de 1,5 Mo de RAM.

Une chose étrange: mon kubuntu 64 bits à double cœur n'a jamais atteint un sommet dans les deux cœurs. Il semblait que Go n'utilisait qu'un seul noyau. Fixé avec un appel àruntime.GOMAXPROCS(4)

Mise à jour: j'ai exécuté la version paralellisée jusqu'à 1M de numéros. L'un de mes cœurs de processeur était à 100% tout le temps, tandis que l'autre n'était pas du tout utilisé (étrange). Cela a pris une minute entière de plus que le C et les versions régulières de Go. :(

Avec 1000000 (1M au lieu de 100K):

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

La version 100k:

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

Juste pour le plaisir, voici une version parallèle 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

Sur mon MacBook Air Core i5 à 1,8 GHz, les performances sont les suivantes:

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

Il semble que le JIT de la JVM donne à Ruby une belle amélioration des performances dans le cas par défaut, tandis que le véritable multithreading aide JRuby à être 50% plus rapide dans le cas fileté. Ce qui est plus intéressant, c'est que JRuby 1.7 améliore le score de JRuby 1.6 de 17%!

Sur la base de la réponse de x4u , j'ai écrit une version scala en utilisant la récursivité, et je l'ai améliorée en allant uniquement dans sqrt au lieu de x / 2 pour la fonction de vérification principale. J'obtiens ~ 250ms pour 100k et ~ 600ms pour 1M. Je suis allé de l'avant et je suis allé à 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")

Je suis aussi retourné et j'ai écrit une version CoffeeScript (V8 JavaScript), qui obtient ~ 15ms pour 100k, 250ms pour 1M et 6s pour 10M, en utilisant un compteur (en ignorant les E / S). Si j'active la sortie, cela prend environ 150 ms pour 100k, 1s pour 1M et 12s pour 10M. Impossible d'utiliser la récursivité de la queue ici, malheureusement, j'ai donc dû la reconvertir en boucles.

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 réponse à votre question n ° 1 est que oui, la JVM est incroyablement rapide et oui, la saisie statique aide.

La JVM devrait être plus rapide que C à long terme, peut-être même plus rapide que le langage d'assemblage "normal" - Bien sûr, vous pouvez toujours optimiser l'assemblage pour battre n'importe quoi en effectuant un profil d'exécution manuel et en créant une version distincte pour chaque processeur, il vous suffit doivent être incroyablement bons et bien informés.

Les raisons de la vitesse de Java sont:

La JVM peut analyser votre code pendant son exécution et l'optimiser manuellement - par exemple, si vous aviez une méthode qui pouvait être analysée statiquement au moment de la compilation pour être une vraie fonction et que la JVM a remarqué que vous l'appeliez souvent avec le même paramètres, il POURRAIT en fait éliminer complètement l'appel et injecter simplement les résultats du dernier appel (je ne sais pas si Java fait exactement cela, mais il fait beaucoup de choses comme ça).

En raison du typage statique, la JVM peut en savoir beaucoup sur votre code au moment de la compilation, ce qui lui permet de pré-optimiser un peu de choses. Il permet également au compilateur d'optimiser chaque classe individuellement sans savoir comment une autre classe envisage de l'utiliser. De plus, Java n'a pas de pointeurs arbitraires vers l'emplacement de la mémoire, il SAIT quelles valeurs en mémoire peuvent et ne peuvent pas être modifiées et peut optimiser en conséquence.

L'allocation de tas est BEAUCOUP plus efficace que C, l'allocation de tas de Java ressemble plus à l'allocation de pile de C en vitesse - mais plus polyvalente. Beaucoup de temps a été consacré aux différentes algroithmes utilisées ici, c'est un art - par exemple, tous les objets à courte durée de vie (comme les variables de pile de C) sont alloués à un emplacement libre "connu" (pas de recherche de place libre avec suffisamment d'espace) et sont tous libérés ensemble en une seule étape (comme une pile pop).

La JVM peut connaître les particularités de l'architecture de votre CPU et générer du code machine spécifiquement pour un CPU donné.

La JVM peut accélérer votre code longtemps après l'avoir expédié. Tout comme déplacer un programme vers un nouveau processeur peut l'accélérer, le déplacer vers une nouvelle version de la JVM peut également vous donner des performances de vitesse énormes adaptées à des processeurs qui n'existaient même pas lorsque vous avez initialement compilé votre code, quelque chose que c ne peut physiquement pas faire sans un recomiple.

À propos, la plupart des mauvaises représentants de la vitesse java proviennent du long temps de démarrage pour charger la JVM (un jour, quelqu'un construira la JVM dans le système d'exploitation et cela disparaîtra!) Et du fait que de nombreux développeurs sont vraiment mauvais en écriture Code GUI (en particulier threadé) qui faisait que les interfaces graphiques Java devenaient souvent insensibles et glitchy. Les langages simples à utiliser comme Java et VB ont leurs défauts amplifiés par le fait que les capacités du programmeur moyen ont tendance à être inférieures à celles des langages plus compliqués.