IT story

C, Clojure, Python, Ruby, Scala 등의 벤치 마크 해석

hot-time 2020. 9. 3. 23:46
반응형

C, Clojure, Python, Ruby, Scala 등의 벤치 마크 해석


부인 성명

나는 인위적인 벤치 마크가 악하다는 것을 알고 있습니다. 매우 구체적인 좁은 상황에 대해서만 결과를 표시 할 수 있습니다. 나는 어리석은 벤치 때문에 한 언어가 다른 언어보다 낫다고 생각하지 않습니다. 그러나 결과가 왜 그렇게 다른지 궁금합니다. 하단의 내 질문을 참조하십시오.

수학 벤치 마크 설명

벤치 마크는 6만큼 다른 소수 쌍을 찾기위한 간단한 수학 계산입니다 ( 섹시 소수 라고 ). 예를 들어 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)

결과 표

표에서 : 계산 시간 (초) 실행 중 : Factor를 제외한 모든 것이 VirtualBox에서 실행 중임 (Debian 불안정한 amd64 게스트, 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]-시간이 얼마나 걸릴지 상상이됩니다

코드 목록

씨:

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

루비:

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"

스칼라 :

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 최적화 isPrime(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

클로저 :

(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 최적화 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))))))

파이썬

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

인자

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

질문

  1. Scala가 왜 그렇게 빠른가요? 정적 타이핑 때문 입니까? 아니면 JVM을 매우 효율적으로 사용하고 있습니까?
  2. Ruby와 Python의 차이점은 무엇일까요? 저는이 두 가지가 완전히 다르지 않다고 생각했습니다. 내 코드가 잘못되었을 수 있습니다. 저를 깨달으십시오! 감사. UPD 예, 내 코드에 오류가 있습니다. Python과 Ruby 1.9는 거의 동일합니다.
  3. Ruby 버전 간의 생산성이 정말 인상적입니다.
  4. 유형 선언을 추가하여 Clojure 코드를 최적화 할 수 있습니까? 도움이 될까요?

대략적인 답변 :

  1. Scala의 정적 타이핑은 여기에서 상당히 도움이됩니다. 이것은 너무 많은 추가 노력없이 JVM을 매우 효율적으로 사용한다는 것을 의미합니다.
  2. Ruby / Python 차이에 대해 정확히 확신하지는 못하지만 (2...n).all?함수 is-prime?가 Ruby에서 매우 잘 최적화 될 가능성이 있다고 생각합니다 (편집 : 실제로 이것이 사실 인 것처럼 들립니다. 자세한 내용은 Julian의 대답을 참조하십시오 ...)
  3. Ruby 1.9.3은 훨씬 더 최적화되었습니다.
  4. Clojure 코드는 확실히 많이 가속화 될 수 있습니다! Clojure는 기본적으로 동적이지만 필요한 경우 많은 경우에 유형 힌트, 기본 수학 등을 사용하여 Scala / 순수 Java 속도에 근접 할 수 있습니다.

Clojure 코드에서 가장 중요한 최적화는 is-prime?다음과 같이 형식화 된 기본 수학을 사용하는 것입니다.

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

이 개선으로 Clojure가 0.635 초 만에 10k를 완료하게되었습니다 (즉, 목록에서 두 번째로 빠른 스칼라를 이겼습니다).

추신 : 어떤 경우에는 벤치 마크 내부에 코드를 인쇄하고 있다는 점에 유의하십시오. 특히 print처음 과 같은 기능을 사용하면 IO 하위 시스템이 초기화 되는 등 결과가 왜곡되므로 좋은 생각이 아닙니다 !


다음은 동일한 기본 알고리즘을 사용하는 빠른 Clojure 버전입니다.

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

내 컴퓨터에서 원본보다 약 20 배 빠르게 실행됩니다. 다음은 1.5에서 새로운 감속기 라이브러리를 활용하는 버전입니다 (Java 7 또는 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)))

이것은 원본보다 약 40 배 빠르게 실행됩니다. 내 컴퓨터에서는 1.5 초에 10 만입니다.


나는 단지 # 2에 대답 할 것이다. 왜냐하면 내가 원격으로 말할 수있는 유일한 것이기 때문이다. 그러나 당신의 파이썬 코드의 경우, 당신은 중간 목록을에서 만들고있는 is_prime반면, 당신은 루비에서 사용 .map하고있다. all반복.

다음으로 변경하는 경우 is_prime:

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

그들은 동등합니다.

Python을 더 최적화 할 수는 있지만, Ruby는 내가 더 많은 이점을 제공했는지 알기에 충분하지 않습니다 (예 : 사용 xrange하면 Python이 내 컴퓨터에서 승리하지만 사용했던 Ruby 범위가 다음을 생성하는지 기억하지 못합니다. 메모리의 전체 범위).

편집 : 너무 어리석지 않고 Python 코드를 다음과 같이 만듭니다.

import time

def is_prime(n):
    return all(n % j for j in xrange(2, n))

def primes_below(x):
    return [(j-6, j) for j in xrange(9, x + 1) if is_prime(j) and is_prime(j-6)]

a = int(round(time.time() * 1000))
print(primes_below(10*1000))
b = int(round(time.time() * 1000))
print(str((b-a)) + " mils")

더 이상 변하지 않는데, 나를 위해 1.5 초로 설정하고, 매우 어리석게도 PyPy로 실행하면 10K의 경우 .3s, 100K의 경우 21 초가됩니다.


isPrime방법을 다음과 같이 수정하여 Scala를 훨씬 빠르게 만들 수 있습니다.

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

간결하지는 않지만 프로그램은 40 %의 시간에 실행됩니다!

불필요한 Range익명 Function객체를 잘라 내고 Scala 컴파일러는 tail-recursion을 인식하고이를 while-loop로 변환합니다. JVM이 어느 정도 최적의 기계 코드로 바뀔 수 있으므로 C에서 너무 멀리 떨어져서는 안됩니다. 버전.

참고 항목 : Scala에서 for-comprehensions 및 루프를 최적화하는 방법은 무엇입니까?


재미를 위해 병렬 및 비 병렬의 스칼라 버전은 다음과 같습니다. (듀얼 코어 컴퓨팅에서 병렬 버전은 335ms, 병렬 버전은 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))
  }
}

편집 : Emil H 의 제안에 따라 IO 및 jvm 워밍업의 영향을 피하기 위해 코드를 변경했습니다.

결과는 내 계산에 표시됩니다.

목록 (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)
  }
}

벤치 마크는 신경 쓰지 마십시오. 이 문제에 관심이 생겼고 빠르게 조정했습니다. 이것은 lru_cache함수를 메모하는 데코레이터를 사용합니다 . 전화를 걸면 is_prime(i-6)기본적으로 프라임 수표를 무료로받습니다. 이 변경은 작업을 대략 절반으로 줄입니다. 또한 range()홀수로만 전화를 걸 있으므로 작업을 다시 대략 절반으로 줄일 수 있습니다.

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

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

이를 위해서는 Python 3.2 이상이 필요 lru_cache하지만 .NET Framework를 제공하는 Python 레시피를 설치하면 이전 Python과 함께 작동 할 수 있습니다 lru_cache. Python 2.x를 사용 xrange()하는 경우 실제로 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)))

위의 내용은 편집하는 데 매우 짧은 시간이 걸렸습니다. 나는 한 단계 더 나아가 소수 테스트가 소수만 시도하고 테스트되는 숫자의 제곱근까지만 시도하도록 결정했습니다. 내가 한 방식은 순서대로 숫자를 확인하는 경우에만 작동하므로 진행되는 동안 모든 소수를 누적 할 수 있습니다. 하지만이 문제는 이미 순서대로 숫자를 확인하고 있었으므로 괜찮 았습니다.

내 노트북에서 (특별한 것은 없습니다. 프로세서는 1.5GHz AMD Turion II "K625"임)이 버전은 8 초 이내에 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)))

위의 코드는 Python, Ruby 등으로 작성하기가 매우 쉽지만 C에서는 더 고통 스러울 것입니다.

유사한 트릭을 사용하도록 다른 버전을 다시 작성하지 않고는이 버전의 숫자를 다른 버전의 숫자와 비교할 수 없습니다. 나는 여기서 아무것도 증명하려는 것이 아닙니다. 나는 문제가 재미 있다고 생각했고 어떤 종류의 쉬운 성능 향상을 얻을 수 있는지보고 싶었습니다.


포트란을 잊지 마세요! (대부분 농담이지만 ​​C와 비슷한 성능을 기대합니다). 느낌표가있는 문장은 선택 사항이지만 좋은 스타일입니다. ( !포트란 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

100k 테스트를 내 컴퓨터에서 0.3 초가 걸리게 만든 C 버전에 대한 가장 분명한 최적화 몇 가지를 거부 할 수 없었습니다 (문제의 C 버전보다 5 배 빠르며 둘 다 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 );
}

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

Java 1.7.0_04에서는 C 버전과 거의 동일하게 빠르게 실행됩니다. 클라이언트 또는 서버 VM은 JIT 교육이 서버 VM에 약간 (~ 3 %) 도움이되는 것처럼 보이지만 클라이언트 VM에는 거의 영향을 미치지 않는 것 외에는 큰 차이가 없습니다. Java의 출력은 C보다 느린 것 같습니다. 출력이 두 버전 모두에서 정적 카운터로 대체되면 Java 버전은 C 버전보다 약간 빠르게 실행됩니다.

다음은 10 만 번의 실행 시간입니다.

  • / Ox로 컴파일 된 319ms C 및> NIL로 출력 :
  • / Ox 및 정적 카운터로 컴파일 된 312ms C
  • > NIL로 출력되는 324ms Java 클라이언트 VM :
  • 정적 카운터가있는 299ms Java 클라이언트 VM

및 1M 실행 (16386 개의 결과) :

  • / Ox 및 정적 카운터로 컴파일 된 24.95s C
  • 정적 카운터가있는 25.08s Java 클라이언트 VM
  • 정적 카운터가있는 24.86s Java 서버 VM

이것은 실제로 귀하의 질문에 대한 답은 아니지만 작은 조정이 성능에 주목할만한 영향을 미칠 수 있음을 보여줍니다. 따라서 실제로 언어를 비교할 수 있으려면 모든 알고리즘 차이를 최대한 피해야합니다.

또한 Scala가 왜 다소 빠른지 힌트를줍니다. Java VM에서 실행되므로 인상적인 성능의 이점을 누릴 수 있습니다.


Scala에서 List 대신 Tuple2를 사용하면 더 빨라질 것입니다. (x, y)는 Tuple2이므로 'List'라는 단어를 제거하십시오.

Tuple2는 Int, Long 및 Double에 특화되어있어 원시 데이터 유형을 box / unbox 할 필요가 없습니다. Tuple2 소스 . 목록은 전문적이지 않습니다. 목록 소스 .


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

C 버전만큼 빠르게 실행되었습니다.

Asus u81a Intel Core 2 Duo T6500 2.1GHz, 2MB L2 캐시, 800MHz FSB 사용. 4GB RAM

100k 버전 : C: 2.723s Go: 2.743s

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

하지만 Go에 내장 된 멀티 스레딩 기능을 사용하고 해당 버전을 멀티 스레딩없이 일반 C 버전과 비교하는 것이 공정하다고 생각합니다. Go로 멀티 스레딩을 수행하는 것이 거의 너무 쉽기 때문입니다.

업데이트 : Go에서 Goroutines를 사용하여 병렬 버전을 수행했습니다.

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
}

병렬 버전은 평균 2.743 초로 일반 버전과 정확히 같은 시간에 사용되었습니다.

병렬화 된 버전은 1.706 초 만에 완료되었습니다. 1.5MB 미만의 RAM을 사용했습니다.

한 가지 이상한 점은 내 듀얼 코어 kubuntu 64 비트가 두 코어에서 정점을 찍지 못했습니다. Go가 하나의 코어 만 사용하는 것처럼 보였습니다. 전화로 해결되었습니다.runtime.GOMAXPROCS(4)

업데이트 : 최대 1M 번호까지 병렬화 된 버전을 실행했습니다. 내 CPU 코어 중 하나는 항상 100 % 였고 다른 하나는 전혀 사용되지 않았습니다 (홀수). C 및 일반 Go 버전보다 1 분 더 걸렸습니다. :(

1000000 (100K 대신 1M) :

C: 3m35.458s Go: 3m36.259s Go using goroutines:3 : 27.1372m16.125s

100k 버전 :

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


재미를 위해 여기 병렬 Ruby 버전이 있습니다.

require 'benchmark'

num = ARGV[0].to_i

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

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

def sexy_primes_threads(x)
    partition = (9..x).map do |i|
        [i-6, i]
    end.group_by do |x|
        x[0].to_s[-1]
    end
    threads = Array.new
    partition.each_key do |k|
       threads << Thread.new do
            partition[k].select do |j|
                j.all?{|j| is_prime? j}
            end
        end
    end
    threads.each {|t| t.join}
    threads.map{|t| t.value}.reject{|x| x.empty?}
end

puts "Running up to num #{num}"

Benchmark.bm(10) do |x|
    x.report("default") {a = sexy_primes_default(num)}
    x.report("threads") {a = sexy_primes_threads(num)}
end

1.8GHz Core i5 MacBook Air에서 성능 결과는 다음과 같습니다.

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

JVM의 JIT는 기본 케이스에서 Ruby에 멋진 성능 향상을 제공하는 반면, 진정한 멀티 스레딩은 JRuby가 스레드 케이스에서 50 % 더 빠르게 수행 할 수 있도록 도와줍니다. 더 흥미로운 점은 JRuby 1.7이 JRuby 1.6 점수를 17 % 향상 시킨다는 것입니다!


x4u의 답변을 기반으로 재귀를 사용하여 스칼라 버전을 작성했으며 프라임 체크 기능을 위해 x / 2 대신 sqrt로만 이동하여 개선했습니다. 나는 100k에 ~ 250ms, 1M에 ~ 600ms를 얻습니다. 나는 6 초 만에 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")

또한 카운터를 사용하여 (I / O 무시) 100k의 경우 ~ 15ms, 1M의 경우 250ms, 10M의 경우 6s를 얻는 CoffeeScript (V8 JavaScript) 버전을 작성했습니다. 출력을 켜면 100k에는 ~ 150ms, 1M에는 1 초, 10M에는 12 초가 걸립니다. 불행히도 여기서 꼬리 재귀를 사용할 수 없어서 다시 루프로 변환해야했습니다.

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

귀하의 질문 # 1에 대한 대답은 예, JVM이 매우 빠르며 예 정적 입력이 도움이된다는 것입니다.

JVM은 장기적으로 C보다 빠르며 "일반"어셈블리 언어보다 더 빠를 수 있습니다. 물론 수동 런타임 프로파일 링을 수행하고 각 CPU에 대해 별도의 버전을 생성하여 모든 것을 이길 수 있도록 어셈블리를 수동으로 최적화 할 수 있습니다. 놀랍도록 훌륭하고 지식이 있어야합니다.

Java의 속도에 대한 이유는 다음과 같습니다.

JVM은 실행되는 동안 코드를 분석하고 수동으로 최적화 할 수 있습니다. 예를 들어, 컴파일 시간에 정적으로 분석하여 진정한 함수가 될 수있는 메서드가 있고 JVM이이를 동일한 코드로 호출하는 경우가 많다는 사실을 알게 된 경우 매개 변수를 사용하면 실제로 호출을 완전히 제거하고 마지막 호출의 결과를 삽입 할 수 있습니다 (Java가 실제로이 작업을 정확히 수행하는지 확실하지 않지만 이와 같은 많은 작업을 수행하지 않음).

정적 타이핑으로 인해 JVM은 컴파일 타임에 코드에 대해 많은 것을 알 수 있으며이를 통해 상당히 많은 것을 사전 최적화 할 수 있습니다. 또한 컴파일러가 다른 클래스가이를 사용하는 방법에 대한 지식없이 각 클래스를 개별적으로 최적화 할 수 있습니다. 또한 Java에는 메모리 위치에 대한 임의의 포인터가 없으므로 메모리의 값이 변경 될 수 있고 변경되지 않을 수 있으며 그에 따라 최적화 할 수 있습니다.

힙 할당은 C보다 훨씬 효율적이며 Java의 힙 할당은 속도면에서 C의 스택 할당과 비슷하지만 더 다양합니다. 여기에 사용 된 다양한 알고리즘에 많은 시간이 소요되었습니다. 예술입니다. 예를 들어 수명이 짧은 모든 개체 (예 : C의 스택 변수)는 "알려진"자유 위치에 할당됩니다 (자유 지점을 검색하지 않음). (스택 팝처럼) 한 번에 모두 함께 해제됩니다.

JVM은 CPU 아키텍처에 대한 단점을 알고 특정 CPU에 대한 기계 코드를 생성 할 수 있습니다.

JVM은 코드를 출시 한 후에도 오랫동안 코드 속도를 높일 수 있습니다. 프로그램을 새 CPU로 이동하면 속도가 빨라지는 것과 마찬가지로 새 버전의 JVM으로 이동하면 처음에 코드를 컴파일 할 때도 존재하지 않았던 CPU에 맞는 엄청난 속도 성능을 얻을 수 있습니다. 반복하지 않고 수행하십시오.

그건 그렇고, 자바 속도에 대한 대부분의 나쁜 rep은 JVM을로드하는 데 긴 시작 시간에서 비롯됩니다 (언젠가 누군가가 JVM을 OS에 빌드하고 이것은 사라질 것입니다!). Java GUI가 종종 응답하지 않고 결함이있는 GUI 코드 (특히 스레드). Java 및 VB와 같이 사용하기 쉬운 언어는 일반 프로그래머의 능력이 더 복잡한 언어보다 낮은 경향이 있다는 사실로 인해 결함이 증폭됩니다.

참고 URL : https://stackoverflow.com/questions/11641098/interpreting-a-benchmark-in-c-clojure-python-ruby-scala-and-others

반응형