Interpretacja testu porównawczego w C, Clojure, Python, Ruby, Scala i innych [zamknięte]

Zrzeczenie się

Wiem, że sztuczne wzorce są złe. Mogą pokazywać wyniki tylko dla bardzo konkretnej wąskiej sytuacji. Nie zakładam, że jeden język jest lepszy od drugiego z powodu jakiejś głupiej ławki. Zastanawiam się jednak, dlaczego wyniki są tak różne. Zobacz moje pytania na dole.

Opis testu porównawczego matematyki

Benchmark to proste obliczenia matematyczne w celu znalezienia par liczb pierwszych różniących się o 6 (tzw. Seksowne liczby pierwsze ) Np. Seksowne liczby pierwsze poniżej 100 to:(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 wyników

W tabeli: czas obliczeń w sekundach Uruchomiony: wszystko oprócz Factor działało w VirtualBox (gość Debiana niestabilnego amd64, host Windows 7 x64) Procesor: 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] - boję się sobie wyobrazić, ile czasu to zajmie

Lista kodów

DO:

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

Rubin:

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 zoptymalizowana isPrime(ten sam pomysł jak w optymalizacji 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 zoptymalizowany 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))))))

Pyton

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

Czynnik

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

pytania

1. Dlaczego Scala jest taka szybka? Czy to z powodu statycznego pisania ? A może po prostu bardzo wydajnie wykorzystuje JVM?
2. Skąd taka ogromna różnica między Rubim a Pythonem? Myślałem, że te dwa nie są zupełnie inne. Może mój kod jest zły. Proszę, oświeć mnie! Dzięki. UPD Tak, to był błąd w moim kodzie. Python i Ruby 1.9 są dość równe.
3. Naprawdę imponujący skok produktywności między wersjami Rubiego.
4. Czy mogę zoptymalizować kod Clojure, dodając deklaracje typu? Czy to pomoże?

Zgrubne odpowiedzi:

1. Statyczne typowanie Scali pomaga mu w tym przypadku - oznacza to, że używa maszyny JVM dość wydajnie bez zbytniego dodatkowego wysiłku.
2. Nie jestem do końca pewien co do różnicy Ruby / Python, ale podejrzewam, że (2...n).all?funkcja is-prime?prawdopodobnie będzie dość dobrze zoptymalizowana w Rubim (EDYCJA: brzmi tak, jakby tak było, zobacz odpowiedź Juliana po więcej szczegółów ...)
3. Ruby 1.9.3 jest po prostu znacznie lepiej zoptymalizowany
4. Kod Clojure z pewnością można znacznie przyspieszyć! Chociaż Clojure jest domyślnie dynamiczny, możesz użyć wskazówek dotyczących typów, prymitywnych matematyki itp., Aby zbliżyć się do szybkości Scala / czystej Javy w wielu przypadkach, gdy zajdzie taka potrzeba.

Najważniejszą optymalizacją w kodzie Clojure byłoby użycie w nim prymitywnych operacji matematycznych is-prime?, na przykład:

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

Dzięki temu ulepszeniu Clojure kończy 10k w 0,635 sekundy (tj. Drugi najszybszy na twojej liście, pokonując Scalę)

PS zwróć uwagę, że w niektórych przypadkach masz wydrukowany kod wewnątrz swojego benchmarku - nie jest to dobry pomysł, ponieważ zniekształci to wyniki, zwłaszcza jeśli użycie funkcji takiej jak printpo raz pierwszy spowoduje inicjalizację podsystemów IO lub coś w tym rodzaju!

Oto szybka wersja Clojure, wykorzystująca te same podstawowe algorytmy:

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

Działa około 20 razy szybciej niż oryginał na moim komputerze. A oto wersja, która wykorzystuje nową bibliotekę reduktorów w 1.5 (wymaga Java 7 lub 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)))

Działa to około 40 razy szybciej niż oryginał. Na moim komputerze to 100k w 1,5 sekundy.

Odpowiem tylko # 2, ponieważ jest to tylko jeden ja mam coś zdalnie inteligentnego do powiedzenia, ale dla kodu Pythona, tworzysz listę półprodukt w is_prime, podczas gdy używasz .mapw twojej allw Ruby, który jest po prostu iterowanie.

Jeśli zmienisz is_primena:

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

są na równi.

Mógłbym dalej zoptymalizować Pythona, ale mój Ruby nie jest wystarczająco dobry, aby wiedzieć, kiedy dałem większą przewagę (np. Użycie xrangesprawia , że Python wygrywa na mojej maszynie, ale nie pamiętam, czy zakres Ruby, którego użyłeś, tworzy cały zakres w pamięci, czy nie).

EDYCJA: Bez bycia zbyt głupim, sprawienie, by kod Pythona wyglądał następująco:

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

co nie zmienia się dużo bardziej, stawia go na 1,5 s dla mnie i, będąc wyjątkowo głupim, uruchomienie go z PyPy ustawia go na 0,3 s dla 10 KB i 21 s dla 100 KB.

Możesz znacznie przyspieszyć działanie Scali, modyfikując swoją isPrimemetodę na

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

Nie tak zwięzły, ale program działa w 40% przypadków!

Wycinamy zbędne Rangei anonimowe Functionobiekty, kompilator Scala rozpoznaje rekurencję ogonową i zamienia ją w pętlę while, którą JVM może przekształcić w mniej lub bardziej optymalny kod maszynowy, więc nie powinien być zbyt daleko od C wersja.

Zobacz też: Jak zoptymalizować interpretacje i pętle w Scali?

Oto moja wersja scala, zarówno równoległa, jak i nierównoległa, dla zabawy: (w moich obliczeniach dwurdzeniowych wersja równoległa zajmuje 335 ms, podczas gdy wersja bez równoległości zajmuje 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))
  }
}

EDYCJA: Zgodnie z sugestią Emila H , zmieniłem kod, aby uniknąć efektów rozgrzewki IO i jvm:

Wynik pokazuje w moim obliczeniu:

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

Mniejsza o benchmarki; problem mnie zainteresował i szybko wprowadziłem poprawki. Wykorzystuje lru_cachedekorator, który zapamiętuje funkcję; więc kiedy dzwonimy is_prime(i-6), otrzymujemy ten czek główny za darmo. Ta zmiana skraca pracę mniej więcej o połowę. Możemy również sprawić, że range()wywołania będą przechodzić tylko przez liczby nieparzyste, ponownie przecinając pracę mniej więcej o połowę.

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

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

Wymaga to Pythona 3.2 lub nowszego lru_cache, ale może działać ze starszym Pythonem, jeśli zainstalujesz przepis Pythona, który zapewnia lru_cache. Jeśli używasz Pythona 2.x, naprawdę powinieneś używać xrange()zamiast 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)))

Powyższe edytowanie zajęło bardzo krótko. Postanowiłem pójść o krok dalej i sprawić, by test liczb pierwszych sprawdzał tylko dzielniki liczb pierwszych i tylko do pierwiastka kwadratowego z testowanej liczby. Sposób, w jaki to zrobiłem, działa tylko wtedy, gdy sprawdzasz liczby po kolei, więc może gromadzić wszystkie liczby pierwsze na bieżąco; ale ten problem polegał już na sprawdzaniu numerów w kolejności, więc było dobrze.

Na moim laptopie (nic specjalnego; procesor to 1,5 GHz AMD Turion II „K625”) ta wersja dała odpowiedź 100K w mniej niż 8 sekund.

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

Powyższy kod jest dość łatwy do napisania w Pythonie, Ruby itp., Ale byłby bardziej uciążliwy w C.

Nie możesz porównać liczb w tej wersji z liczbami z innych wersji bez przepisywania innych, aby zastosować podobne sztuczki. Nie próbuję tu niczego udowadniać; Po prostu pomyślałem, że problem jest fajny i chciałem zobaczyć, jakie łatwe ulepszenia wydajności mogę uzyskać.

Nie zapomnij o Fortranie! (Głównie żartuję, ale spodziewałbym się podobnej wydajności do C). Instrukcje z wykrzyknikami są opcjonalne, ale w dobrym stylu. ( !jest znakiem komentarza w 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

Nie mogłem się powstrzymać przed wykonaniem kilku najbardziej oczywistych optymalizacji dla wersji C, która sprawiła, że ​​test 100k zajmuje teraz 0,3 s na moim komputerze (5 razy szybciej niż wersja C w pytaniu, obie skompilowane z 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 );
}

Oto identyczna implementacja w Javie:

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

W Javie 1.7.0_04 działa to prawie tak samo szybko, jak wersja C. Maszyna wirtualna klienta lub serwera nie wykazuje dużej różnicy, z wyjątkiem tego, że szkolenie JIT wydaje się pomagać maszynie wirtualnej serwera (~ 3%), podczas gdy prawie nie ma wpływu na maszynę wirtualną klienta. Wydaje się, że dane wyjściowe w Javie są wolniejsze niż w C. Jeśli dane wyjściowe zostaną zastąpione licznikiem statycznym w obu wersjach, wersja Java działa trochę szybciej niż wersja C.

Oto moje czasy na bieg na 100 km:

• 319 ms C skompilowane z / Ox i wyjście do> NIL:
• 312 ms C skompilowane z / Ox i licznikiem statycznym
• Maszyna wirtualna klienta Java 324 ms z wyjściem do> NIL:
• Maszyna wirtualna klienta Java 299 ms z licznikiem statycznym

i przebieg 1M (16386 wyników):

• 24,95s C skompilowane z / Ox i licznikiem statycznym
• 25,08 s Maszyna wirtualna klienta Java z licznikiem statycznym
• 24,86 s Maszyna wirtualna serwera Java z licznikiem statycznym

Chociaż to naprawdę nie odpowiada na twoje pytania, pokazuje, że drobne poprawki mogą mieć znaczący wpływ na wydajność. Aby móc naprawdę porównać języki, powinieneś starać się unikać wszystkich różnic algorytmicznych w jak największym stopniu.

Daje też wskazówkę, dlaczego Scala wydaje się raczej szybka. Działa na maszynie wirtualnej Java i korzysta z imponującej wydajności.

W Scali spróbuj użyć Tuple2 zamiast List, powinno to działać szybciej. Po prostu usuń słowo „List”, ponieważ (x, y) to Tuple2.

Tuple2 specjalizuje się w Int, Long i Double, co oznacza, że ​​nie będzie musiał pudełkować / rozpakowywać tych surowych typów danych. Źródło Tuple2 . Lista nie jest wyspecjalizowana. Źródło listy .

Oto kod wersji 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)
        }
    }
}

Działał tak samo szybko jak wersja C.

Korzystanie z Asus u81a procesora Intel Core 2 Duo T6500 GHz, 2 MB pamięci podręcznej L2, magistrali FSB 800 MHz. 4 GB pamięci RAM

Wersja 100k: C: 2.723s Go: 2.743s

Przy 1000000 (1 mln zamiast 100 tys.): C: 3m35.458s Go: 3m36.259s

Ale myślę, że byłoby uczciwe użycie wbudowanych w Go możliwości wielowątkowości i porównanie tej wersji ze zwykłą wersją C (bez wielowątkowości), tylko dlatego, że wielowątkowość w Go jest prawie zbyt łatwa.

Aktualizacja: Zrobiłem wersję równoległą używając Goroutines in 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
}

Wersja zrównoleglona była używana średnio przez 2,743 sekundy, czyli dokładnie w tym samym czasie, co wersja zwykła.

Wersja równoległa zakończyła się w 1,706 sekundy. Zużywał mniej niż 1,5 Mb pamięci RAM.

Jedna dziwna rzecz: mój dwurdzeniowy kubuntu 64-bitowy nigdy nie osiągnął szczytu w obu rdzeniach. Wyglądało na to, że Go używa tylko jednego rdzenia. Naprawiono z wezwaniem doruntime.GOMAXPROCS(4)

Aktualizacja: uruchomiłem paralelizowaną wersję do 1M numerów. Jeden z rdzeni mojego procesora był cały czas w 100%, podczas gdy drugi w ogóle nie był używany (dziwne). Zajęło to całą minutę więcej niż wersja C i zwykła wersja Go. :(

Przy 1000000 (1 mln zamiast 100 tys.):

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

Wersja 100k:

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

Dla zabawy, oto równoległa wersja Rubiego.

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

Na moim MacBooku Air z procesorem Core i5 1,8 GHz wyniki wydajności są następujące:

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

Wygląda na to, że JVM JVM daje Ruby'emu niezły wzrost wydajności w domyślnym przypadku, podczas gdy prawdziwa wielowątkowość pomaga JRuby działać 50% szybciej w przypadku wątków. Co ciekawe, JRuby 1.7 poprawia wynik JRuby 1.6 o zdrowe 17%!

Opierając się na odpowiedzi x4u , napisałem wersję scala przy użyciu rekurencji i ulepszyłem ją, przechodząc tylko do sqrt zamiast x / 2 dla funkcji sprawdzania głównego. Dostaję ~ 250 ms dla 100k i ~ 600 ms dla 1M. Poszedłem do przodu i osiągnąłem 10M w ~ 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")

Wróciłem również i napisałem wersję CoffeeScript (V8 JavaScript), która przy użyciu licznika (ignorując I / O) pobiera ~ 15 ms dla 100 kB, 250 ms dla 1 MB i 6 s dla 10 MB. Jeśli włączę wyjście, zajmie to ~ 150 ms dla 100k, 1s dla 1M i 12s dla 10M. Nie mogłem tutaj niestety użyć rekurencji ogonowej, więc musiałem przekształcić ją z powrotem w pętle.

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

Odpowiedź na Twoje pytanie nr 1 brzmi: Tak, maszyna JVM jest niesamowicie szybka i tak, statyczne pisanie pomaga.

Na dłuższą metę JVM powinna być szybsza niż C, prawdopodobnie nawet szybsza niż "Normalny" język asemblera - Oczywiście zawsze możesz ręcznie zoptymalizować assembler, aby pokonać cokolwiek, wykonując ręczne profilowanie środowiska uruchomieniowego i tworząc oddzielną wersję dla każdego procesora, po prostu muszą być niezwykle dobre i kompetentne.

Przyczyny szybkości Javy to:

JVM może analizować Twój kod podczas jego działania i ręcznie go optymalizować - na przykład, jeśli masz metodę, którą można przeanalizować statycznie w czasie kompilacji, aby była prawdziwą funkcją, a maszyna JVM zauważyła, że ​​często wywołujesz ją z tym samym parametrów, faktycznie MOŻE całkowicie wyeliminować wywołanie i po prostu wstrzyknąć wyniki z ostatniego wywołania (nie jestem pewien, czy Java faktycznie robi to dokładnie, ale robi wiele takich rzeczy).

Ze względu na statyczne typowanie JVM może dużo wiedzieć o kodzie w czasie kompilacji, co pozwala jej wstępnie zoptymalizować całkiem sporo rzeczy. Pozwala także kompilatorowi na optymalizację każdej klasy indywidualnie bez wiedzy o tym, jak inna klasa planuje jej używać. Ponadto Java nie ma arbitralnych wskaźników do lokalizacji pamięci, WIE, jakie wartości w pamięci mogą, a które nie mogą zostać zmienione, i może odpowiednio zoptymalizować.

Alokacja sterty jest DUŻO bardziej wydajna niż C, alokacja sterty w Javie jest bardziej podobna do alokacji stosu C pod względem szybkości - ale jest bardziej wszechstronna. Wiele czasu poświęcono różnym algroithimom używanym tutaj, to sztuka - na przykład wszystkie obiekty o krótkiej żywotności (takie jak zmienne stosu C) są przydzielane do „znanej” wolnej lokalizacji (bez wyszukiwania wolnego miejsca z wystarczającą ilością miejsca) i wszystkie są zwalniane razem w jednym kroku (jak wyskakujący stos).

JVM może znać dziwactwa dotyczące architektury procesora i generować kod maszynowy specjalnie dla danego procesora.

JVM może przyspieszyć twój kod długo po jego wysłaniu. Podobnie jak przeniesienie programu na nowy procesor może go przyspieszyć, przeniesienie go do nowej wersji JVM może również zapewnić ogromną szybkość działania podobną do procesorów, które nie istniały nawet podczas początkowej kompilacji kodu, czego fizycznie nie można obejść się bez recomiple.

Nawiasem mówiąc, większość złej reputacji dla szybkości javy wynika z długiego czasu uruchamiania, aby załadować JVM (pewnego dnia ktoś zbuduje JVM w systemie operacyjnym i to zniknie!) Oraz fakt, że wielu programistów jest naprawdę kiepskich w pisaniu Kod GUI (szczególnie wielowątkowy), który powodował, że GUI języka Java często przestały reagować i przestały reagować. Proste w użyciu języki, takie jak Java i VB, mają swoje wady potęgowane przez fakt, że możliwości przeciętnego programisty są zwykle mniejsze niż w przypadku bardziej skomplikowanych języków.