Interpretation eines Benchmarks in C, Clojure, Python, Ruby, Scala und anderen [geschlossen]

91

Haftungsausschluss

Ich weiß, dass künstliche Benchmarks böse sind. Sie können Ergebnisse nur für eine ganz bestimmte enge Situation anzeigen. Ich gehe nicht davon aus, dass eine Sprache wegen der dummen Bank besser ist als die andere. Ich frage mich jedoch, warum die Ergebnisse so unterschiedlich sind. Bitte sehen Sie meine Fragen unten.

Beschreibung des mathematischen Benchmarks

Benchmark ist eine einfache mathematische Berechnung, um Paare von Primzahlen zu finden, die sich um 6 unterscheiden (sogenannte sexy Primzahlen ). ZB wären sexy Primzahlen unter 100:(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)

Ergebnistabelle

In Tabelle: Berechnungszeit in Sekunden Ausführen: Alle außer Factor wurden in VirtualBox ausgeführt (Debian instabiler amd64-Gast, Windows 7 x64-Host). 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] - Ich habe Angst, mir vorzustellen, wie viel Zeit es dauern wird

Codeauflistungen

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

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 opimiert isPrime(die gleiche Idee wie bei der Clojure-Optimierung):

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

Faktor

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

Fragen

  1. Warum ist Scala so schnell? Liegt es an der statischen Eingabe ? Oder nutzt es JVM nur sehr effizient?
  2. Warum so ein großer Unterschied zwischen Ruby und Python? Ich dachte, diese beiden sind nicht ganz anders. Vielleicht ist mein Code falsch. Bitte erleuchte mich! Vielen Dank. UPD Ja, das war ein Fehler in meinem Code. Python und Ruby 1.9 sind ziemlich gleich.
  3. Wirklich beeindruckender Produktivitätssprung zwischen Ruby-Versionen.
  4. Kann ich Clojure-Code durch Hinzufügen von Typdeklarationen optimieren? Wird es helfen?
defhlt
quelle
6
@mgilson eigentlich bis zu, sqrt(n)aber das kann einige Zeit dauern, um zu berechnen. Außerdem druckt Ihr C-Code die Primzahlen so aus, wie sie gefunden werden, während Ihre anderen Sprachen sie in Listen berechnen und dann ausdrucken. Während C nicht überraschend das schnellste ist, können Sie es möglicherweise schneller bekommen.
Russ
2
(Und natürlich das Sieb von Eratosthenes . Aber dieser Mikro-Benchmark ist so ziemlich ein Stresstest für Iterations- und Mathematikoperationen. Sie sind jedoch immer noch nicht "fair", da einige fauler sind.)
2
Ich habe gerade sowohl meine Go-Version als auch Ihre C-Version (die sich sehr ähnlich sehen) ausgeführt und in beiden praktisch die gleiche Geschwindigkeit erreicht. Ich habe nur die 100k-Version ausprobiert : C: 2.723s Go: 2.743s.
Sebastián Grignoli
3
Sie müssen sqrtfür diese Prüfung nicht berechnen . Sie können das Quadrat von iwie infor (i = 2; i * i <= x; ++i) ...
ivant
3
Ich schlage vor, Sie kommentieren Scalas optimiert isPrimemit @tailrec, um sicherzustellen, dass Sie die Schwanzrekursion verwenden. Es ist leicht, versehentlich etwas zu tun, das eine Schwanzrekursion verhindert, und diese Anmerkung sollte Sie warnen, wenn dies passiert.
Daniel C. Sobral

Antworten:

30

Grobe Antworten:

  1. Die statische Eingabe von Scala hilft hier einiges - dies bedeutet, dass die JVM ohne großen Aufwand ziemlich effizient genutzt wird.
  2. Ich bin mir hinsichtlich des Unterschieds zwischen Ruby und Python nicht ganz sicher, aber ich vermute, dass (2...n).all?die Funktion is-prime?in Ruby wahrscheinlich recht gut optimiert ist (BEARBEITEN: Klingt so, als wäre dies tatsächlich der Fall, siehe Julians Antwort für weitere Einzelheiten ...)
  3. Ruby 1.9.3 ist einfach viel besser optimiert
  4. Clojure-Code kann sicherlich stark beschleunigt werden! Während Clojure standardmäßig dynamisch ist, können Sie Typhinweise, primitive Mathematik usw. verwenden, um in vielen Fällen bei Bedarf der Geschwindigkeit von Scala / reinem Java nahe zu kommen.

Die wichtigste Optimierung im Clojure-Code wäre die Verwendung von typisierter primitiver Mathematik is-prime?, etwa:

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

Mit dieser Verbesserung schaffe ich es, dass Clojure in 0,635 Sekunden 10 km zurücklegt (dh die zweitschnellste auf Ihrer Liste, die Scala besiegt).

PS: Beachten Sie, dass in einigen Fällen Druckcode in Ihrem Benchmark enthalten ist - keine gute Idee, da dies die Ergebnisse verfälscht, insbesondere wenn printdie erstmalige Verwendung einer Funktion die Initialisierung von E / A-Subsystemen oder Ähnlichem verursacht!

mikera
quelle
2
Ich denke nicht, dass das bisschen über Ruby und Python unbedingt wahr ist, aber +1 sonst ..
Die Eingabe zeigte kein messbares stabiles Ergebnis, aber Ihr neues is-prime?zeigt eine zweifache Verbesserung. ;)
defhlt
Könnte das nicht schneller gemacht werden, wenn es einen ungeprüften Mod gäbe?
Hendekagon
1
@Hendekagon - wahrscheinlich! Ich bin mir nicht sicher, wie gut dies vom aktuellen Clojure-Compiler optimiert wird. Es gibt wahrscheinlich Raum für Verbesserungen. Clojure 1.4 hilft im Allgemeinen definitiv viel für diese Art von Sachen, 1.5 wird wahrscheinlich noch besser sein.
Mikera
1
(zero? (mod n i))sollte schneller sein als(= (mod n i) 0)
Jonas
23

Hier ist eine schnelle Clojure-Version, die dieselben grundlegenden Algorithmen verwendet:

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

Es läuft ungefähr 20x schneller als Ihr Original auf meinem Computer. Und hier ist eine Version, die die neue Reduziererbibliothek in 1.5 nutzt (erfordert Java 7 oder 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)))

Dies läuft etwa 40x schneller als Ihr Original. Auf meinem Computer sind das 100.000 in 1,5 Sekunden.

Justin Kramer
quelle
2
Die Verwendung von unchecked-remainder-intoder nur remanstelle von modstatischen Tippergebnissen führt zu einer 4-fachen Leistungssteigerung. Nett!
defhlt
22

Ich werde antworten nur # 2, da es das einzige , das ich etwas aus der Ferne , intelligent zu sagen haben, aber für Ihre Python - Code, du bist eine Zwischenliste bei der Erstellung is_prime, während Sie verwenden .mapin Ihrem allin Ruby , die gerade ist iterieren.

Wenn Sie Ihre ändern is_primezu:

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

Sie sind auf Augenhöhe.

Ich könnte Python weiter optimieren, aber mein Ruby ist nicht gut genug, um zu wissen, wann ich einen größeren Vorteil verschafft habe (z. B. xrangebringt Python Python auf meinem Computer zum Gewinnen, aber ich erinnere mich nicht, ob der von Ihnen verwendete Ruby-Bereich erstellt wurde ein ganzer Bereich im Speicher oder nicht).

EDIT: Ohne zu albern zu sein, lässt der Python-Code wie folgt aussehen:

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

Das ändert sich nicht viel mehr und bringt es für mich auf 1,5 Sekunden. Wenn ich es mit PyPy besonders albern mache, liegt es bei 0,3 Sekunden für 10.000 und 21 Sekunden für 100.000.

julianisch
quelle
1
Der Generator macht hier einen großen Unterschied, da die Funktion beim ersten Mal aussteigen kann False(guter Fang).
mgilson
Ich freue mich wirklich darauf, dass sie in PyPy taub werden ... Das wird großartig.
mgilson
Würden Sie bitte meine Antwort in PyPy ausführen? Ich bin gespannt, wie viel schneller das sein würde.
Steveha
1
Sie haben völlig Recht mit sowohl iterierenden als auch xrange! Ich habe behoben und jetzt zeigen Python und Ruby gleiche Ergebnisse.
defhlt
1
@steveha Ich mache das nur, wenn du versprichst, jetzt rauszugehen und PyPy selbst herunterzuladen :)! pypy.org/download.html enthält Binärdateien für alle gängigen Betriebssysteme, und Ihr Paketmanager verfügt zweifellos darüber. Wie auch immer, wie für Ihren Benchmark, mit einer zufälligen lru_cacheImplementierung für 2.7 auf AS läuft 100K in 2.3s.
Julian
16

Sie können die Scala viel schneller machen, indem Sie Ihre isPrimeMethode auf ändern

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

Nicht ganz so prägnant, aber das Programm läuft in 40% der Fälle!

Wir schneiden die überflüssigen Rangeund anonymen FunctionObjekte aus, der Scala-Compiler erkennt die Schwanzrekursion und wandelt sie in eine while-Schleife um, die die JVM in mehr oder weniger optimalen Maschinencode umwandeln kann, damit sie nicht zu weit vom C entfernt ist Ausführung.

Siehe auch: Wie kann ich das Verständnis und die Schleifen in Scala optimieren?

Luigi Plinge
quelle
2
2x Verbesserung. Und schöner Link!
defhlt
Übrigens ist dieser Methodenkörper identisch mit dem i == n || n % i != 0 && isPrime(n, i + 1), der kürzer ist, wenn auch etwas schwerer zu lesen
Luigi Plinge
1
Sie sollten die @tailrecAnmerkung hinzugefügt haben , um sicherzustellen, dass diese Optimierung durchgeführt wird.
Daniel C. Sobral
8

Hier ist meine Scala-Version sowohl parallel als auch nicht parallel, nur zum Spaß: (Bei meiner Dual-Core-Berechnung dauert die parallele Version 335 ms, während die nicht parallele Version 655 ms dauert.)

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

BEARBEITEN: Gemäß dem Vorschlag von Emil H habe ich meinen Code geändert, um die Auswirkungen des Aufwärmens von E / A und JVM zu vermeiden:

Das Ergebnis zeigt in meiner Berechnung:

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

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

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

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

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


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

  def main(args: Array[String]) {
    val xs = timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
             timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
             timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::
             timeOf(findPrimes(1000*1000))::timeOf(findPrimesPar(1000*1000))::Nil
    println(xs)
  }
}
Eastsun
quelle
1
Ist der Code von jvm warmup betroffen? ZB isSexyPrimekönnte (mehr) optimiert werden, wenn von angerufen findPrimesParund nicht so sehr, wenn von angerufenfindPrimes
Emil H
@EmilH Fair genug. Ich habe meinen Code geändert, um die Auswirkungen des Aufwärmens von io und jvm zu vermeiden.
Eastsun
Nur auf sqrt (n) aufzusteigen ist eine gute Optimierung, aber Sie vergleichen jetzt einen anderen Algorithmus.
Luigi Plinge
7

Kümmere dich nicht um die Benchmarks; Das Problem hat mich interessiert und ich habe einige schnelle Änderungen vorgenommen. Hierbei wird der lru_cacheDekorator verwendet, der eine Funktion auswendig lernt. Wenn wir also anrufen is_prime(i-6), bekommen wir diesen Prime Check im Grunde kostenlos. Diese Änderung halbiert die Arbeit ungefähr. Außerdem können wir die range()Anrufe nur durch die ungeraden Nummern führen und die Arbeit wieder ungefähr halbieren.

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

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

Dies erfordert Python 3.2 oder neuer, lru_cachekann aber mit einem älteren Python funktionieren, wenn Sie ein Python-Rezept installieren, das bereitstellt lru_cache. Wenn Sie Python 2.x verwenden, sollten Sie wirklich xrange()anstelle von verwenden 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)))

Die Bearbeitung der oben genannten Informationen dauerte nur sehr kurze Zeit. Ich beschloss, noch einen Schritt weiter zu gehen und den Primer-Test nur mit Primteilern und nur bis zur Quadratwurzel der getesteten Zahl durchzuführen. Die Art und Weise, wie ich es gemacht habe, funktioniert nur, wenn Sie die Zahlen in der richtigen Reihenfolge überprüfen, damit alle Primzahlen im Laufe der Zeit akkumuliert werden können. Aber dieses Problem überprüfte bereits die Nummern in der richtigen Reihenfolge, so dass das in Ordnung war.

Auf meinem Laptop (nichts Besonderes; Prozessor ist ein 1,5-GHz-AMD Turion II "K625") lieferte diese Version in weniger als 8 Sekunden eine Antwort für 100K.

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

Der obige Code ist ziemlich einfach in Python, Ruby usw. zu schreiben, würde aber in C eher schmerzhaft sein.

Sie können die Zahlen dieser Version nicht mit den Zahlen der anderen Versionen vergleichen, ohne die anderen neu zu schreiben, um ähnliche Tricks anzuwenden. Ich versuche hier nichts zu beweisen; Ich dachte nur, dass das Problem Spaß macht und ich wollte sehen, welche einfachen Leistungsverbesserungen ich finden kann.

steveha
quelle
lru_cacheist definitiv geschickt. Für bestimmte Problemklassen, wie das Erzeugen aufeinanderfolgender Fibonacci-Zahlen, kann dies eine enorme Beschleunigung bewirken, indem nur dieser eine Zeilendekorator zur Funktion hinzugefügt wird! Hier ist ein Link zu einem Vortrag von Raymond Hettinger, der lru_cacheungefähr 26 Minuten dauert. Blip.tv/pycon-us-videos-2009-2010-2011/…
steveha
3
Wenn Sie lru_cache verwenden, verwenden Sie tatsächlich einen anderen Algorithmus als den Rohcode. Bei der Leistung geht es also um den Algorithmus, aber nicht um die Sprache selbst.
Eastsun
1
@ Eastsun - Ich verstehe nicht, was du meinst. lru_cachevermeidet es, eine Berechnung zu wiederholen, die bereits kürzlich durchgeführt wurde, und das ist alles; Ich verstehe nicht, wie das "tatsächlich einen anderen Algorithmus verwendet". Und Python leidet darunter, langsam zu sein, profitiert aber von coolen Sachen wie lru_cache; Ich sehe nichts falsches daran, die nützlichen Teile einer Sprache zu verwenden. Und ich sagte, dass man die Laufzeit meiner Antwort nicht mit den anderen Sprachen vergleichen sollte, ohne ähnliche Änderungen an den anderen vorzunehmen. Ich verstehe also nicht, was du meinst.
Steveha
@Eastsun ist richtig, aber andererseits sollte die Bequemlichkeit einer höheren Sprache erlaubt sein, sofern keine zusätzlichen Einschränkungen angegeben sind. lru_cache opfert Speicher für Geschwindigkeit und passt die algorithmische Komplexität an.
Matt Joiner
2
Wenn Sie einen anderen Algorithmus verwenden, können Sie Sieve of Eratosthenes ausprobieren. Die Python-Version ergab eine Antwort für 100 KB in weniger als 0.03Sekunden ( 30ms) .
JFS
7

Vergiss Fortran nicht! (Meistens ein Scherz, aber ich würde eine ähnliche Leistung wie C erwarten). Die Anweisungen mit Ausrufezeichen sind optional, haben aber einen guten Stil. ( !ist ein Kommentarzeichen in 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
quelle
6

Ich konnte nicht widerstehen, einige der offensichtlichsten Optimierungen für die C-Version vorzunehmen, wodurch der 100k-Test auf meinem Computer jetzt 0,3 Sekunden dauerte (fünfmal schneller als die fragliche C-Version, beide mit MSVC 2010 / Ox kompiliert). .

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

Hier ist die identische Implementierung in 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" );
    }
}

Mit Java 1.7.0_04 läuft dies fast genauso schnell wie die C-Version. Die Client- oder Server-VM zeigt keinen großen Unterschied, außer dass das JIT-Training der Server-VM ein wenig zu helfen scheint (~ 3%), während es fast keine Auswirkungen auf die Client-VM hat. Die Ausgabe in Java scheint langsamer zu sein als in C. Wenn die Ausgabe in beiden Versionen durch einen statischen Zähler ersetzt wird, wird die Java-Version etwas schneller ausgeführt als die C-Version.

Dies sind meine Zeiten für den 100-km-Lauf:

  • 319ms C kompiliert mit / Ox und Ausgabe an> NIL:
  • 312ms C kompiliert mit / Ox und statischem Zähler
  • 324 ms Java-Client-VM mit Ausgabe an> NIL:
  • 299 ms Java-Client-VM mit statischem Zähler

und der 1M-Lauf (16386 Ergebnisse):

  • 24,95 s C kompiliert mit / Ox und statischem Zähler
  • 25.08s Java Client VM mit statischem Zähler
  • 24.86s Java Server VM mit statischem Zähler

Dies beantwortet Ihre Fragen zwar nicht wirklich, zeigt jedoch, dass kleine Änderungen einen bemerkenswerten Einfluss auf die Leistung haben können. Um Sprachen wirklich vergleichen zu können, sollten Sie versuchen, alle algorithmischen Unterschiede so weit wie möglich zu vermeiden.

Es gibt auch einen Hinweis, warum Scala ziemlich schnell scheint. Es läuft auf der Java VM und profitiert somit von seiner beeindruckenden Leistung.

x4u
quelle
1
Es ist schneller, für die Prime-Check-Funktion zu sqrt (x) anstatt zu x >> 1 zu wechseln.
Eve Freeman
4

Versuchen Sie in Scala, Tuple2 anstelle von List zu verwenden. Dies sollte schneller gehen. Entfernen Sie einfach das Wort 'Liste', da (x, y) ein Tupel2 ist.

Tuple2 ist auf Int, Long und Double spezialisiert, was bedeutet, dass diese Rohdatentypen nicht ein- und ausgepackt werden müssen. Tuple2-Quelle . Liste ist nicht spezialisiert. Liste Quelle .

Tomas Lazaro
quelle
Dann können Sie es nicht anrufen forall. Ich dachte auch, dass dies möglicherweise nicht der effizienteste Code ist (mehr, weil eine große strenge Sammlung für große erstellt wird, nanstatt nur eine Ansicht zu verwenden), aber es ist sicherlich kurz + elegant, und ich war überrascht, wie gut es trotz der Verwendung von a funktioniert viel funktionaler Stil.
0__
Du hast recht, ich dachte 'forAll' war da. Trotzdem sollte es eine große Verbesserung gegenüber List geben, und es wäre nicht so schlimm, diese beiden Anrufe zu haben.
Tomas Lazaro
2
es ist in der Tat schneller, mit def sexyPrimes(n: Int) = (11 to n).map(i => (i-6, i)).filter({ case (i, j) => isPrime(i) && isPrime(j) })etwa 60% schneller hier, sollte also den C-Code schlagen :)
0__
Hmm, ich bekomme nur eine Leistungssteigerung von 4 oder 5%
Luigi Plinge
1
Ich finde collectwesentlich langsamer. Schneller ist es, wenn Sie zuerst den Filter ausführen und dann zuordnen.withFilterist etwas schneller, da keine Zwischensammlungen erstellt werden. (11 to n) withFilter (i => isPrime(i - 6) && isPrime(i)) map (i => (i - 6, i))
Luigi Plinge
4

Hier ist der Code für die Go-Version (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)
        }
    }
}

Es lief genauso schnell wie die C-Version.

Verwenden eines Asus u81a Intel Core 2 Duo T6500 mit 2,1 GHz, 2 MB L2-Cache und 800 MHz FSB. 4 GB RAM

Die 100k-Version: C: 2.723s Go: 2.743s

Mit 1000000 (1M statt 100K): C: 3m35.458s Go: 3m36.259s

Aber ich denke, es wäre fair, die in Go integrierten Multithreading-Funktionen zu verwenden und diese Version mit der regulären C-Version (ohne Multithreading) zu vergleichen, nur weil es fast zu einfach ist, Multithreading mit Go durchzuführen.

Update: Ich habe eine parallele Version mit Goroutines in Go erstellt:

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
}

Die parallelisierte Version wurde in durchschnittlich 2,743 Sekunden verwendet, genau zur gleichen Zeit wie die reguläre Version.

Die parallelisierte Version wurde in 1.706 Sekunden fertiggestellt. Es wurden weniger als 1,5 MB RAM verwendet.

Eine seltsame Sache: Mein Dual-Core-Kubuntu 64-Bit hat in beiden Kernen nie einen Höhepunkt erreicht. Es sah so aus, als würde Go nur einen Kern verwenden.Behoben mit einem Anruf beiruntime.GOMAXPROCS(4)

Update: Ich habe die paralellisierte Version mit bis zu 1 Million Nummern ausgeführt. Einer meiner CPU-Kerne war die ganze Zeit zu 100% ausgelastet, während der andere überhaupt nicht verwendet wurde (ungerade). Es dauerte eine ganze Minute länger als die C- und die regulären Go-Versionen. :(

Mit 1000000 (1M statt 100K):

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

Die 100k-Version:

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

Sebastián Grignoli
quelle
Wie viele Kerne haben Sie übrigens verwendet?
Om-Nom-Nom
2
Ich habe ein Asus u81a Intel Core 2 Duo T6500 2,1 GHz, 2 MB L2-Cache, 800 MHz FSB. 4 GB RAM
Sebastián Grignoli
Haben Sie die C-Version tatsächlich mit aktivierten Optimierungen kompiliert? Der Standard-Go-Compiler ist nicht inline und erleidet bei solchen Vergleichen normalerweise einen massiven Leistungseinbruch gegenüber optimiertem C. Hinzufügen -O3oder besser.
Matt Joiner
Ich habe es gerade getan, nicht vorher, und die 100K-Version hat mit oder ohne -O3
Sebastián Grignoli
Gleiches gilt für die 1M-Version. Möglicherweise sind diese speziellen Vorgänge (wir testen eine sehr kleine Teilmenge) standardmäßig gut optimiert.
Sebastián Grignoli
4

Nur zum Spaß gibt es hier eine parallele Ruby-Version.

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

Auf meinem 1,8 GHz Core i5 MacBook Air sind die Leistungsergebnisse:

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

Es sieht so aus, als würde die JIT der JVM Ruby im Standardfall einen schönen Leistungsschub verleihen, während echtes Multithreading JRuby dabei hilft, im Thread-Fall 50% schneller zu arbeiten. Interessanter ist, dass JRuby 1.7 den JRuby 1.6-Score um gesunde 17% verbessert!

Georgios Gousios
quelle
3

Basierend auf der Antwort von x4u habe ich eine Scala-Version mit Rekursion geschrieben und sie verbessert, indem ich für die Prime-Check-Funktion nur zum sqrt anstelle von x / 2 gegangen bin. Ich bekomme ~ 250ms für 100k und ~ 600ms für 1M. Ich ging voran und ging in ~ 6s auf 10M.

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

Ich ging auch zurück und schrieb eine CoffeeScript (V8 JavaScript) -Version, die ~ 15 ms für 100.000, 250 ms für 1 Million und 6 Sekunden für 10 Millionen mit einem Zähler (ohne Berücksichtigung von E / A) erhält. Wenn ich den Ausgang einschalte, dauert es ~ 150 ms für 100k, 1s für 1M und 12s für 10M. Die Schwanzrekursion konnte hier leider nicht verwendet werden, daher musste ich sie wieder in Schleifen umwandeln.

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
quelle
2

Die Antwort auf Ihre Frage Nr. 1 lautet: Ja, die JVM ist unglaublich schnell und ja, statische Eingabe hilft.

Die JVM sollte auf lange Sicht schneller als C sein, möglicherweise sogar schneller als die Assemblersprache "Normal". Natürlich können Sie die Assemblierung jederzeit von Hand optimieren, um alles zu übertreffen, indem Sie eine manuelle Laufzeitprofilerstellung durchführen und für jede CPU eine separate Version erstellen müssen erstaunlich gut und kompetent sein.

Die Gründe für die Geschwindigkeit von Java sind:

Die JVM kann Ihren Code während der Ausführung analysieren und von Hand optimieren - zum Beispiel, wenn Sie eine Methode hatten, die zur Kompilierungszeit statisch analysiert werden konnte, um eine echte Funktion zu sein, und die JVM bemerkte, dass Sie sie häufig mit derselben aufgerufen haben Parameter, es KÖNNTE den Aufruf tatsächlich vollständig eliminieren und nur die Ergebnisse des letzten Aufrufs einspeisen (ich bin nicht sicher, ob Java dies tatsächlich genau tut, aber es macht eine Menge solcher Dinge).

Aufgrund der statischen Typisierung kann die JVM beim Kompilieren viel über Ihren Code wissen. Dadurch kann sie einige Dinge voroptimieren. Außerdem kann der Compiler jede Klasse einzeln optimieren, ohne zu wissen, wie eine andere Klasse sie verwenden möchte. Auch Java hat keine willkürlichen Zeiger auf den Speicherort, es weiß, welche Werte im Speicher geändert werden können und welche nicht und kann entsprechend optimiert werden.

Die Heap-Zuweisung ist VIEL effizienter als C, die Heap-Zuweisung von Java ähnelt eher der Stapelzuweisung von C in Bezug auf die Geschwindigkeit - und ist dennoch vielseitiger. Es wurde viel Zeit in die verschiedenen hier verwendeten Algroithims investiert, es ist eine Kunst - zum Beispiel werden alle Objekte mit einer kurzen Lebensdauer (wie die Stapelvariablen von C) einem "bekannten" freien Ort zugeordnet (keine Suche nach einem freien Platz) mit genügend Platz) und werden alle zusammen in einem einzigen Schritt freigegeben (wie ein Stack Pop).

Die JVM kann Macken über Ihre CPU-Architektur kennen und Maschinencode speziell für eine bestimmte CPU generieren.

Die JVM kann Ihren Code beschleunigen, lange nachdem Sie ihn versendet haben. Ähnlich wie das Verschieben eines Programms auf eine neue CPU es beschleunigen kann, kann das Verschieben auf eine neue Version der JVM auch enorme Geschwindigkeitsleistungen bringen, die auf CPUs zugeschnitten sind, die beim erstmaligen Kompilieren Ihres Codes noch nicht vorhanden waren, was physisch nicht möglich ist verzichten Sie auf ein Rezept.

Übrigens ist der größte Teil der schlechten Wiederholung der Java-Geschwindigkeit auf die lange Startzeit zum Laden der JVM zurückzuführen (eines Tages wird jemand die JVM in das Betriebssystem einbauen und dies wird verschwinden!) Und auf die Tatsache, dass viele Entwickler wirklich schlecht schreiben können GUI-Code (insbesondere mit Threads), der dazu führte, dass Java-GUIs häufig nicht mehr reagierten und fehlerhaft waren. Einfach zu verwendende Sprachen wie Java und VB werden durch die Tatsache verstärkt, dass die Fähigkeiten eines durchschnittlichen Programmierers tendenziell geringer sind als bei komplizierteren Sprachen.

Bill K.
quelle
Zu sagen, dass die Heap-Zuordnung von JVM viel effizienter ist als C, ist unsinnig, da JVM in C ++ geschrieben ist.
Daniel C. Sobral
5
@ DanielC.Sobral-Sprache ist nicht so wichtig wie Impelemntation - Javas "Heap" -Implementierungscode ist nichts anderes als Cs. Java ist ein austauschbares mehrstufiges System, das für verschiedene Ziele hochoptomierbar ist und über viele Jahre Forschungsarbeit verfügt, einschließlich modernster Techniken, die heute entwickelt werden. C verwendet einen Haufen - eine einfache Datenstruktur, die vor Jahrhunderten entwickelt wurde. Javas System ist für C nicht zu implementieren, da C Zeiger zulässt, so dass es niemals "sichere" Verschiebungen von willkürlich zugewiesenen Speicherblöcken ohne Sprachänderungen garantieren kann (wodurch es nicht mehr C wird)
Bill K
Sicherheit ist irrelevant - Sie haben nicht behauptet, es sei sicherer , Sie haben behauptet, es sei effizienter . Darüber hinaus hat Ihre Beschreibung im Kommentar, wie C "Heap" funktioniert, keinen Einfluss auf die Realität.
Daniel C. Sobral
Sie müssen meine Bedeutung von "Sicher" falsch verstanden haben - Java kann einen beliebigen Speicherblock jederzeit verschieben, da es dies weiß. C kann die Speicherzuordnung nicht optimieren, da möglicherweise ein Zeiger darauf verweist. Auch AC-Heap wird normalerweise als Heap implementiert, bei dem es sich um eine Datenstruktur handelt. C ++ - Heaps wurden früher mit Heap-Strukturen wie C implementiert (daher der Name "Heap"). Ich habe seit einigen Jahren nicht mehr in C ++ eingecheckt, daher ist dies möglicherweise nicht mehr der Fall, aber es ist immer noch begrenzt, weil ich es nicht kann Ordnen Sie kleine Teile des vom Benutzer zugewiesenen Speichers nach Belieben neu an.
Bill K