Menafsirkan tolok ukur dalam C, Clojure, Python, Ruby, Scala, dan lainnya [tertutup]

Penolakan

Saya tahu bahwa tolok ukur buatan itu jahat. Mereka dapat menunjukkan hasil hanya untuk situasi sempit yang sangat spesifik. Saya tidak berasumsi bahwa satu bahasa lebih baik dari yang lain karena beberapa bangku bodoh. Namun saya heran mengapa hasilnya sangat berbeda. Silakan lihat pertanyaan saya di bagian bawah.

Deskripsi benchmark matematika

Tolok ukur adalah perhitungan matematika sederhana untuk mencari pasangan bilangan prima yang berbeda 6 (disebut bilangan prima seksi ) Misalnya bilangan prima seksi di bawah 100 adalah:(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)

Tabel hasil

Dalam tabel: waktu kalkulasi dalam detik Berjalan: semua kecuali Factor sedang berjalan di VirtualBox (Debian amd64 guest tidak stabil, host Windows 7 x64) CPU: AMD A4-3305M

  Sexy primes up to:        10k      20k      30k      100k               

  Bash                    58.00   200.00     [*1]      [*1]

  C                        0.20     0.65     1.42     15.00

  Clojure1.4               4.12     8.32    16.00    137.93

  Clojure1.4 (optimized)   0.95     1.82     2.30     16.00

  Factor                    n/a      n/a    15.00    180.00

  Python2.7                1.49     5.20    11.00       119     

  Ruby1.8                  5.10    18.32    40.48    377.00

  Ruby1.9.3                1.36     5.73    10.48    106.00

  Scala2.9.2               0.93     1.41     2.73     20.84

  Scala2.9.2 (optimized)   0.32     0.79     1.46     12.01

[* 1] - Saya takut membayangkan berapa banyak waktu yang dibutuhkan

Daftar kode

C:

int isprime(int x) {
  int i;
  for (i = 2; i < x; ++i)
    if (x%i == 0) return 0;
  return 1;
}

void findprimes(int m) {
  int i;
  for ( i = 11; i < m; ++i)
    if (isprime(i) && isprime(i-6))
      printf("%d %d\n", i-6, i);
}

main() {
    findprimes(10*1000);
}

Rubi:

def is_prime?(n)
  (2...n).all?{|m| n%m != 0 }
end

def sexy_primes(x)
  (9..x).map do |i|
    [i-6, i]
  end.select do |j|
    j.all?{|j| is_prime? j}
  end
end

a = Time.now
p sexy_primes(10*1000)
b = Time.now
puts "#{(b-a)*1000} mils"

Scala:

def isPrime(n: Int) =
  (2 until n) forall { n % _ != 0 }

def sexyPrimes(n: Int) = 
  (11 to n) map { i => List(i-6, i) } filter { _ forall(isPrime(_)) }

val a = System.currentTimeMillis()
println(sexyPrimes(100*1000))
val b = System.currentTimeMillis()
println((b-a).toString + " mils")

Scala opimized isPrime(ide yang sama seperti dalam optimasi 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 dioptimalkan 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

Pertanyaan

1. Mengapa Scala begitu cepat? Apakah karena pengetikan statis ? Atau hanya menggunakan JVM dengan sangat efisien?
2. Mengapa ada perbedaan besar antara Ruby dan Python? Saya pikir keduanya tidak terlalu berbeda. Mungkin kode saya salah. Tolong beri saya pencerahan! Terima kasih. UPD Ya, itu adalah kesalahan dalam kode saya. Python dan Ruby 1.9 cukup setara.
3. Peningkatan produktivitas yang sangat mengesankan antara versi Ruby.
4. Dapatkah saya mengoptimalkan kode Clojure dengan menambahkan deklarasi tipe? Akankah itu membantu?

Jawaban kasar:

1. Pengetikan statis Scala sedikit membantu di sini - ini berarti Scala menggunakan JVM dengan cukup efisien tanpa terlalu banyak usaha ekstra.
2. Saya tidak begitu yakin tentang perbedaan Ruby / Python, tapi saya menduga itu (2...n).all?dalam fungsinyais-prime? kemungkinan akan dioptimalkan dengan cukup baik di Ruby (EDIT: sepertinya memang demikian, lihat jawaban Julian untuk lebih detail ...)
3. Ruby 1.9.3 jauh lebih dioptimalkan
4. Kode Clojure pasti bisa banyak dipercepat! Meskipun Clojure dinamis secara default, Anda dapat menggunakan petunjuk tipe, matematika primitif, dll. Untuk mendekati kecepatan Scala / Java murni dalam banyak kasus saat diperlukan.

Pengoptimalan terpenting dalam kode Clojure adalah menggunakan matematika primitif yang diketik di dalamnya is-prime?, seperti:

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

Dengan peningkatan ini, saya mendapatkan Clojure menyelesaikan 10k dalam 0,635 detik (yaitu tercepat kedua di daftar Anda, mengalahkan Scala)

PS perhatikan bahwa Anda memiliki kode pencetakan di dalam tolok ukur Anda dalam beberapa kasus - bukan ide yang baik karena akan mendistorsi hasil, terutama jika menggunakan fungsi seperti printuntuk pertama kali menyebabkan inisialisasi subsistem IO atau semacamnya!

Ini adalah versi Clojure cepat, menggunakan algoritma dasar yang sama:

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

Ini berjalan sekitar 20x lebih cepat dari aslinya di mesin saya. Dan inilah versi yang memanfaatkan pustaka reduksi baru di 1.5 (memerlukan Java 7 atau 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)))

Ini berjalan sekitar 40x lebih cepat dari aslinya. Di mesin saya, itu 100k dalam 1,5 detik.

Aku akan menjawab hanya # 2, karena itu satu-satunya saya punya apa pun yang cerdas untuk mengatakan, tapi untuk kode Python Anda, Anda membuat daftar menengah dalam is_prime, sedangkan Anda menggunakan .mapdi Anda alldi Ruby yang hanya iterasi.

Jika Anda mengubah Anda is_primemenjadi:

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

mereka setara.

Saya dapat mengoptimalkan Python lebih lanjut, tetapi Ruby saya tidak cukup baik untuk mengetahui kapan saya telah memberikan lebih banyak keuntungan (misalnya, menggunakan xrangemembuat Python menang di mesin saya, tetapi saya tidak ingat apakah rentang Ruby yang Anda gunakan menciptakan seluruh rentang dalam memori atau tidak).

EDIT: Tanpa terlalu konyol, membuat kode Python terlihat seperti:

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

yang tidak banyak berubah, menempatkannya pada 1,5 detik untuk saya, dan, dengan menjadi sangat konyol, menjalankannya dengan PyPy menempatkannya pada 0,3s untuk 10K, dan 21s untuk 100K.

Anda dapat membuat Scala jauh lebih cepat dengan mengubah isPrimemetode Anda menjadi

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

Tidak sesingkat itu tetapi programnya berjalan 40% dari waktu!

Kami memotong yang berlebihan Rangedan anonimFunction , kompiler Scala mengenali tail-recursion dan mengubahnya menjadi while-loop, yang dapat diubah JVM menjadi kode mesin yang lebih atau kurang optimal, sehingga tidak boleh terlalu jauh dari C Versi: kapan.

Lihat juga: Bagaimana cara mengoptimalkan for-Comprehension dan loop di Scala?

Ini adalah versi scala saya secara paralel dan tanpa paralel, hanya untuk kesenangan: (Dalam komputasi inti ganda saya, versi paralel membutuhkan 335ms sedangkan versi tanpa paralel membutuhkan 655ms)

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

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

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

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


  def timeOf(call : =>Unit) {
    val start = System.currentTimeMillis
    call
    val end = System.currentTimeMillis
    println((end-start)+" mils")
  }

  def main(args: Array[String]) {
    timeOf(findPrimes(100*1000))
    println("------------------------")
    timeOf(findPrimesPar(100*1000))
  }
}

EDIT: Menurut saran Emil H , saya telah mengubah kode saya untuk menghindari efek pemanasan IO dan jvm:

Hasilnya menunjukkan dalam komputasi saya:

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

Lupakan tolok ukur; masalah ini membuat saya tertarik dan saya membuat beberapa perubahan cepat. Ini menggunakan lru_cachedekorator, yang mengingat suatu fungsi; jadi ketika kami menelepon is_prime(i-6)kami pada dasarnya mendapatkan cek utama itu secara gratis. Perubahan ini memotong pekerjaan menjadi setengahnya. Juga, kita bisa membuatrange() langkah panggilan hanya melalui angka ganjil, memotong pekerjaan kira-kira menjadi dua lagi.

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

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

Ini membutuhkan Python 3.2 atau yang lebih baru untuk mendapatkannya lru_cache, tetapi dapat bekerja dengan Python yang lebih lama jika Anda memasang resep Python yang menyediakan lru_cache. Jika Anda menggunakan Python 2.x Anda harus benar-benar menggunakan xrange()bukannyarange() .

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

Di atas hanya membutuhkan waktu yang sangat singkat untuk diedit. Saya memutuskan untuk mengambil satu langkah lebih jauh, dan membuat tes bilangan prima hanya mencoba pembagi prima, dan hanya sampai akar kuadrat dari bilangan yang diuji. Cara saya melakukannya hanya berfungsi jika Anda memeriksa nomor secara berurutan, sehingga dapat mengakumulasi semua bilangan prima seiring berjalannya waktu; tapi masalah ini sudah memeriksa nomor secara berurutan jadi tidak apa-apa.

Di laptop saya (tidak ada yang istimewa; prosesor adalah 1,5 GHz AMD Turion II "K625") versi ini menghasilkan jawaban untuk 100K dalam waktu kurang dari 8 detik.

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

Kode di atas cukup mudah untuk ditulis dengan Python, Ruby, dll. Tetapi akan lebih merepotkan di C.

Anda tidak dapat membandingkan angka-angka pada versi ini dengan angka-angka dari versi lain tanpa menulis ulang yang lain untuk menggunakan trik serupa. Saya tidak mencoba membuktikan apa pun di sini; Saya hanya berpikir masalahnya menyenangkan dan saya ingin melihat peningkatan kinerja seperti apa yang dapat saya kumpulkan.

Jangan lupakan Fortran! (Kebanyakan bercanda, tapi saya mengharapkan kinerja yang mirip dengan C). Pernyataan dengan tanda seru bersifat opsional, tetapi gayanya bagus. ( !adalah karakter komentar di 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

Saya tidak dapat menahan diri untuk melakukan beberapa pengoptimalan yang paling jelas untuk versi C yang membuat pengujian 100k sekarang memakan waktu 0,3 detik pada mesin saya (5 kali lebih cepat daripada versi C dalam pertanyaan, keduanya dikompilasi dengan 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 );
}

Berikut adalah implementasi yang identik di 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" );
    }
}

Dengan Java 1.7.0_04 ini berjalan hampir sama cepatnya dengan versi C. VM klien atau server tidak menunjukkan banyak perbedaan, kecuali bahwa pelatihan JIT tampaknya sedikit membantu VM server (~ 3%) sementara itu hampir tidak berpengaruh dengan VM klien. Keluaran di Java tampaknya lebih lambat daripada di C. Jika keluaran diganti dengan penghitung statis di kedua versi, versi Java berjalan sedikit lebih cepat daripada versi C.

Ini adalah waktu saya untuk lari 100k:

• 319ms C dikompilasi dengan / Ox dan output ke> NIL:
• 312ms C dikompilasi dengan / Ox dan penghitung statis
• 324ms VM klien Java dengan output ke> NIL:
• 299ms VM klien Java dengan penghitung statis

dan lari 1M (16386 hasil):

• 24,95s C dikompilasi dengan / Ox dan penghitung statis
• 25.08s VM klien Java dengan penghitung statis
• 24.86s server VM Java dengan penghitung statis

Meskipun ini tidak benar-benar menjawab pertanyaan Anda, ini menunjukkan bahwa perubahan kecil dapat berdampak besar pada kinerja. Jadi untuk dapat benar-benar membandingkan bahasa, Anda harus mencoba menghindari semua perbedaan algoritmik sebanyak mungkin.

Ini juga memberi petunjuk mengapa Scala tampak agak cepat. Ini berjalan pada Java VM dan karenanya mendapat keuntungan dari kinerjanya yang mengesankan.

Dalam Scala coba gunakan Tuple2 daripada List, ini akan bekerja lebih cepat. Hapus saja kata 'List' karena (x, y) adalah Tuple2.

Tuple2 dikhususkan untuk Int, Long dan Double yang berarti tidak perlu mengotak / membuka kotak tipe data mentah tersebut. Sumber tuple2 . Daftar tidak terspesialisasi. Daftar sumber .

Berikut kode untuk versi 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)
        }
    }
}

Itu berjalan secepat versi C.

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

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

Dengan 1000000 (1M, bukan 100K): C: 3m35.458s Go: 3m36.259s

Tapi saya pikir akan adil untuk menggunakan kemampuan multithreading bawaan Go dan membandingkan versi itu dengan versi C biasa (tanpa multithreading), hanya karena hampir terlalu mudah untuk melakukan multithreading dengan Go.

Pembaruan: Saya melakukan versi paralel menggunakan Goroutines di 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
}

Versi paralel digunakan dalam rata-rata 2,743 detik, waktu yang sama persis dengan versi biasa.

Versi paralel selesai dalam 1,706 detik. Ini menggunakan RAM kurang dari 1,5 Mb.

Satu hal yang aneh: kubuntu 64bit dual core saya tidak pernah mencapai puncak di kedua core. Sepertinya Go hanya menggunakan satu inti. Diperbaiki dengan panggilan keruntime.GOMAXPROCS(4)

Pembaruan: Saya menjalankan versi paraleli hingga 1 juta angka. Salah satu inti CPU saya berada di 100% sepanjang waktu, sementara yang lain tidak digunakan sama sekali (ganjil). Butuh satu menit lebih lama daripada versi C dan Go biasa. :(

Dengan 1000000 (1M, bukan 100K):

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

Versi 100k:

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

Hanya untuk bersenang-senang, ini adalah versi Ruby paralel.

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

Di 1.8GHz Core i5 MacBook Air saya, hasil kinerjanya adalah:

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

Sepertinya JIT JVM memberi Ruby peningkatan kinerja yang bagus dalam kasus default, sementara multithreading sejati membantu JRuby bekerja 50% lebih cepat dalam kasus berulir. Yang lebih menarik adalah JRuby 1.7 meningkatkan skor JRuby 1.6 menjadi 17%!

Berdasarkan jawaban x4u , saya menulis versi skala menggunakan rekursi, dan saya memperbaikinya dengan hanya menggunakan sqrt, bukan x / 2 untuk fungsi pemeriksaan utama. Saya mendapatkan ~ 250ms untuk 100k, dan ~ 600ms untuk 1M. Saya pergi ke depan dan pergi ke 10M dalam ~ 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")

Saya juga kembali dan menulis versi CoffeeScript (V8 JavaScript), yang mendapatkan ~ 15ms untuk 100k, 250ms untuk 1M, dan 6s untuk 10M, dengan menggunakan penghitung (mengabaikan I / O). Jika saya menyalakan output dibutuhkan ~ 150ms untuk 100k, 1s untuk 1M, dan 12s untuk 10M. Sayangnya, tidak dapat menggunakan rekursi ekor di sini, jadi saya harus mengubahnya kembali menjadi loop.

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

Jawaban atas pertanyaan Anda # 1 adalah Ya, JVM sangat cepat dan ya, pengetikan statis membantu.

JVM harus lebih cepat dari C dalam jangka panjang, bahkan mungkin lebih cepat daripada bahasa assembly "Normal" - Tentu saja Anda selalu dapat mengoptimalkan perakitan untuk mengalahkan apa pun dengan melakukan profil runtime manual dan membuat versi terpisah untuk setiap CPU, Anda cukup harus luar biasa baik dan berpengetahuan.

Alasan kecepatan Java adalah:

JVM dapat menganalisis kode Anda saat berjalan dan mengoptimalkannya secara manual - misalnya, jika Anda memiliki metode yang dapat dianalisis secara statis pada waktu kompilasi untuk menjadi fungsi yang sebenarnya dan JVM memperhatikan bahwa Anda sering memanggilnya dengan fungsi yang sama. parameter, itu BISA benar-benar menghilangkan panggilan sepenuhnya dan hanya menyuntikkan hasil dari panggilan terakhir (saya tidak yakin apakah Java benar-benar melakukan ini dengan tepat, tetapi itu melakukan banyak hal seperti ini).

Karena pengetikan statis, JVM dapat mengetahui banyak tentang kode Anda pada waktu kompilasi, ini memungkinkannya untuk melakukan pra-optimasi cukup banyak. Ini juga memungkinkan kompilator mengoptimalkan setiap kelas secara individual tanpa pengetahuan tentang bagaimana kelas lain berencana untuk menggunakannya. Juga Java tidak memiliki pointer sewenang-wenang ke lokasi memori, ia TAHU nilai apa dalam memori yang dapat dan tidak dapat diubah dan dapat dioptimalkan sesuai dengan itu.

Alokasi heap JAUH lebih efisien daripada C, alokasi heap Java lebih seperti alokasi tumpukan C dalam kecepatan - namun lebih fleksibel. Banyak waktu telah dihabiskan untuk algroithim berbeda yang digunakan di sini, ini adalah seni - misalnya, semua objek dengan umur yang pendek (seperti variabel tumpukan C) dialokasikan ke lokasi bebas yang "diketahui" (tidak mencari tempat kosong dengan ruang yang cukup) dan semuanya dibebaskan bersama dalam satu langkah (seperti tumpukan pop).

JVM dapat mengetahui kebiasaan tentang arsitektur CPU Anda dan menghasilkan kode mesin khusus untuk CPU tertentu.

JVM dapat mempercepat kode Anda lama setelah Anda mengirimkannya. Sama seperti memindahkan program ke CPU baru dapat mempercepatnya, memindahkannya ke versi baru JVM juga dapat memberi Anda kinerja kecepatan yang sangat besar yang disesuaikan dengan CPU yang bahkan tidak ada saat Anda pertama kali mengompilasi kode Anda, sesuatu yang secara fisik tidak dapat dilakukan. lakukan tanpa recomiple.

Omong-omong, sebagian besar reputasi buruk untuk kecepatan java berasal dari waktu startup yang lama untuk memuat JVM (Suatu hari seseorang akan membangun JVM ke dalam OS dan ini akan hilang!) Dan fakta bahwa banyak pengembang benar-benar buruk dalam menulis Kode GUI (terutama berulir) yang menyebabkan GUI Java sering menjadi tidak responsif dan bermasalah. Bahasa yang mudah digunakan seperti Java dan VB memiliki kesalahan yang diperkuat oleh fakta bahwa kemampuan rata-rata programmer cenderung lebih rendah daripada bahasa yang lebih rumit.