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

91

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?
defhlt
źródło
6
@mgilson faktycznie działa, sqrt(n)ale obliczenie może zająć trochę czasu. Również twój kod C wypisuje liczby pierwsze, gdy je znajdzie, podczas gdy inne języki przetwarzają je na listy, a następnie wypisują. Chociaż C jest nieoczekiwanie najszybsze, możesz być w stanie to zrobić szybciej.
Russ,
2
(I oczywiście Sito Eratostenesa ... ale ten mikro-test porównawczy jest właściwie testem warunków skrajnych dla iteracji i operacji matematycznych. Jednak nadal nie są one „sprawiedliwe”, ponieważ niektórzy są bardziej leniwi.)
2
Po prostu uruchomiłem zarówno moją wersję Go, jak i wersję C (które wyglądają bardzo podobnie) i praktycznie uzyskałem tę samą prędkość w obu. Ja tylko próbowałem wersji 100k: C: 2.723s Go: 2.743s.
Sebastián Grignoli,
3
Nie musisz obliczać sqrttego sprawdzenia. Możesz obliczyć kwadrat ijak wfor (i = 2; i * i <= x; ++i) ...
ivant
3
Sugeruję, abyś opatrzył zoptymalizowaną wersją Scala za isPrimepomocą @tailrec, aby upewnić się, że używasz rekurencji ogonowej. Łatwo jest omyłkowo zrobić coś, co zapobiega rekurencji ogona, a ta adnotacja powinna Cię ostrzec, jeśli tak się stanie.
Daniel C. Sobral

Odpowiedzi:

30

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!

mikera
źródło
2
Nie sądzę, żeby fragment o Rubim i Pythonie był koniecznie prawdziwy, ale +1 poza tym ..
Wpisywanie nie pokazało żadnego mierzalnego stabilnego wyniku, ale nowy is-prime?pokazuje 2x poprawę. ;)
defhlt
czy nie można tego zrobić szybciej, gdyby istniał niezaznaczony mod?
Hendekagon,
1
@Hendekagon - prawdopodobnie! Nie jestem pewien, jak dobrze zostanie to zoptymalizowane przez obecny kompilator Clojure, prawdopodobnie jest miejsce na ulepszenia. Clojure 1.4 zdecydowanie pomaga ogólnie w tego typu rzeczach, 1.5 prawdopodobnie będzie jeszcze lepszy.
mikera
1
(zero? (mod n i))powinno być szybsze niż(= (mod n i) 0)
Jonas.
23

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.

Justin Kramer
źródło
2
Używanie unchecked-remainder-intlub po prostu remzamiast modstatycznego pisania powoduje czterokrotny wzrost wydajności. Ładny!
defhlt
22

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.

juliański
źródło
1
Generator robi tutaj dużą różnicę, ponieważ pozwala funkcji wyskoczyć za pierwszym False(dobry chwyt).
mgilson
Naprawdę nie mogę się doczekać, aż odrętwiały się w PyPy ... To będzie niesamowite.
mgilson
Czy mógłbyś uruchomić moją odpowiedź w PyPy? Ciekaw jestem, o ile szybciej to by się stało.
steveha
1
Masz całkowitą rację zarówno co do iteracji, jak i xrange! Naprawiłem i teraz Python i Ruby pokazują równe wyniki.
defhlt
1
@steveha Zrobię to tylko wtedy, gdy obiecasz, że teraz wyjdziesz i sam pobierzesz PyPy :)! pypy.org/download.html zawiera pliki binarne dla wszystkich popularnych systemów operacyjnych, a Twój menedżer pakietów bez wątpienia je ma. W każdym razie, jeśli chodzi o twój test porównawczy, z losową lru_cacheimplementacją 2.7 znalezioną w AS, 100K działa w 2.3s.
Julian
16

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?

Luigi Plinge
źródło
2
2x poprawa. I fajny link!
defhlt
przy okazji ta metoda jest identyczna z i == n || n % i != 0 && isPrime(n, i + 1)
treścią
1
Powinieneś był dodać @tailrecadnotację, aby upewnić się, że dokona optymalizacji.
Daniel C. Sobral
8

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)
  }
}
Eastsun
źródło
1
Czy kod ma wpływ na rozgrzewkę jvm? Np. isSexyPrimeMoże być (bardziej) zoptymalizowany, gdy zostanie wywołany z, findPrimesPara nie tak bardzo, gdy zostanie wywołany zfindPrimes
Emil H
@EmilH Fair wystarczająco. Zmieniłem kod, aby uniknąć efektu rozgrzewki io ​​i jvm.
Eastsun
Tylko przejście do sqrt (n) to dobra optymalizacja, ale teraz testujesz porównawczy inny algorytm.
Luigi Plinge
7

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ć.

steveha
źródło
lru_cachejest zdecydowanie fajny. W przypadku pewnych klas problemów, takich jak generowanie kolejnych liczb Fibonacciego, może to dać ogromne przyspieszenie, po prostu dodając ten jeden dekorator linii do funkcji! Tutaj jest link do wykładu Raymonda Hettingera, który obejmuje lru_cacheokoło 26 minut w. Blip.tv/pycon-us-videos-2009-2010-2011/ ...
steveha
3
Używając lru_cache, w rzeczywistości używasz innego algorytmu zamiast surowego kodu. Tak więc wydajność dotyczy algorytmu, a nie samego języka.
Eastsun
1
@Eastsun - Nie rozumiem, co masz na myśli. lru_cacheunika powtarzania obliczeń, które zostały już wykonane niedawno, i to wszystko; Nie rozumiem, jak to jest „w rzeczywistości wykorzystujemy inny algorytm”. Python cierpi na powolność, ale korzysta z fajnych rzeczy, takich jak lru_cache; Nie widzę nic złego w używaniu pożytecznych części języka. I ja powiedział , że nie należy porównywać czas pracy moją odpowiedź wobec innych językach bez dokonywania podobnych zmian w innych. Więc nie rozumiem, co masz na myśli.
steveha
@Eastsun ma rację, ale z drugiej strony wygoda języka wyższego poziomu powinna być dozwolona, ​​chyba że zostaną podane dodatkowe ograniczenia. lru_cache poświęci pamięć dla szybkości i dostosuje złożoność algorytmiczną.
Matt Joiner,
2
jeśli użyjesz innego algorytmu, możesz wypróbować Sieve of Eratostenes. Wersja Pythona wygenerowała odpowiedź dla 100K w mniej niż 0.03kilka sekund ( 30ms) .
jfs
7

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
mgilson
źródło
6

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.

x4u
źródło
1
Szybciej jest przejść do sqrt (x) zamiast x >> 1 dla funkcji sprawdzania głównego.
Eve Freeman,
4

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 .

Tomas Lazaro
źródło
Więc nie możesz tego wezwać forall. Pomyślałem też, że to może nie być najbardziej wydajny kod (tym bardziej, że duża ścisła kolekcja jest tworzona dla dużych, na nie tylko widoku), ale z pewnością jest krótki + elegancki i byłem zaskoczony, jak dobrze się spisał pomimo użycia dużo funkcjonalnego stylu.
0__
Masz rację, pomyślałem, że jest tam „forAll”. Wciąż jednak powinna być duża poprawa w porównaniu z Listą i nie byłoby tak źle mieć te 2 wywołania.
Tomas Lazaro,
2
jest rzeczywiście szybszy, tutaj def sexyPrimes(n: Int) = (11 to n).map(i => (i-6, i)).filter({ case (i, j) => isPrime(i) && isPrime(j) })jest około 60% szybszy, więc powinien pokonać kod C :)
0__
Hmm, dostaję tylko wzrost wydajności o 4 lub 5%
Luigi Plinge,
1
Uważam, że collectznacznie wolniej. Szybciej jest, jeśli najpierw wykonasz filtr, a następnie mapujesz. withFilterjest nieco szybszy, ponieważ w rzeczywistości nie tworzy kolekcji pośrednich. (11 to n) withFilter (i => isPrime(i - 6) && isPrime(i)) map (i => (i - 6, i))
Luigi Plinge
4

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

Sebastián Grignoli
źródło
Ile rdzeni wykorzystałeś przy okazji?
om-nom-nom
2
Mam Asus u81a Intel Core 2 Duo T6500 2,1 GHz, pamięć podręczną L2 2 MB, magistralę FSB 800 MHz. 4 GB pamięci RAM
Sebastián Grignoli,
Czy faktycznie skompilowałeś wersję C z włączonymi optymalizacjami? Domyślny kompilator Go nie jest wbudowany i zwykle będzie miał ogromny wpływ na wydajność zoptymalizowanego C w tego rodzaju porównaniach. Dodaj -O3lub lepiej.
Matt Joiner
Po prostu to zrobiłem, nie wcześniej, a wersja 100K zajęła tyle samo czasu z -O3 lub bez
Sebastián Grignoli
To samo dotyczy wersji 1M. Może te konkretne operacje (testujemy bardzo mały podzbiór) są domyślnie dobrze zoptymalizowane.
Sebastián Grignoli
4

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%!

Georgios Gousios
źródło
3

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")
Eve Freeman
źródło
2

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.

Bill K.
źródło
Powiedzenie, że alokacja sterty maszyny JVM jest znacznie bardziej wydajna niż C jest pozbawiona sensu, biorąc pod uwagę, że JVM jest napisana w C ++.
Daniel C. Sobral
5
@ DanielC.Sobral nie jest tak ważny jak impelemntation - kod implementacji „Heap” w Javie w niczym nie przypomina języka C. Java to wymienny, wielostopniowy system, wysoce optomizowalny dla różnych celów, z wieloletnim wysiłkiem badawczym, w tym najnowocześniejszymi technikami opracowywanymi obecnie, C używa sterty - prostej struktury danych opracowanej przed wiekami. System Java jest niemożliwy do zaimplementowania dla C, biorąc pod uwagę, że C zezwala na wskaźniki, więc nigdy nie może zagwarantować „bezpiecznych” przenoszenia dowolnie przydzielonych fragmentów pamięci bez zmian językowych (nie renderuje go już C)
Bill K
Bezpieczeństwo nie ma znaczenia - nie twierdziłeś, że jest bezpieczniejszy , twierdzisz, że jest bardziej wydajny . Ponadto, opis w komentarzu, jak działa „sterta” C, nie ma związku z rzeczywistością.
Daniel C. Sobral
Musiałeś źle zrozumieć moje znaczenie słowa „bezpieczny” - Java jest w stanie przenieść dowolny blok pamięci w dowolnym momencie, ponieważ wie, że tak. C nie jest w stanie zoptymalizować połączenia pamięci, ponieważ może istnieć wskaźnik, który może się do niego odwoływać. Również sterta AC jest zwykle implementowana jako sterta, która jest strukturą danych. C ++ sterty były implementowane ze strukturami sterty, takimi jak C było (stąd nazwa „Sterta”) Nie sprawdzałem C ++ przez kilka lat, więc może to już nie być prawdą, ale nadal jest ograniczone przez brak możliwości dowolnie porządkuj małe fragmenty pamięci przydzielonej przez użytkownika.
Bill K,