解释C,Clojure,Python,Ruby,Scala等基准测试

Question

放弃

我知道人工基准是邪恶的.他们只能针对非常具体的狭隘情况显示结果.我不认为一种语言比另一种语言更好,因为有些愚蠢的替补.但我想知道为什么结果如此不同.请在底部查看我的问题.

数学基准描述

基准测试是简单的数学计算,可以找到相差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)

结果表

在表中:以秒为单位的计算时间 运行:所有除了因子在VirtualBox中运行(Debian unstable amd64 guest,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] - 我不敢想象需要多长时间

代码清单

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

红宝石:

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

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优化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 . .

巴什(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代码吗？会有帮助吗？

Answer 1

粗糙的答案:

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(即你名单上第二快,击败Scala)

PS请注意,在某些情况下,您在基准测试中打印代码 - 这不是一个好主意,因为它会扭曲结果,特别是如果print首次使用类似功能导致IO子系统初始化或类似的事情!

Answer 2

这是一个快速的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中新的reducers库的版本(需要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秒内的100k.

Answer 3

我将回答#2,因为它是唯一一个我有任何远程智能地说,但对于Python代码,您是在创建一个中间表is_prime,而你使用.map你all在Ruby中这仅仅是迭代.

如果您将您更改is_prime为:

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

他们是平等的.

我可以进一步优化Python,但是我的Ruby不够好,不知道什么时候我给了我更多的优势(例如,xrange在我的机器上使用make make win,但我不记得你使用的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运行它将它放在.3s为10K,21s为100K.

Answer 4

通过修改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编译器识别尾递归并将其转换为while循环,JVM可以将其转换为或多或少的最佳机器代码,因此它不应该离C太远版.

另请参见:如何在Scala中优化for-understanding和循环？

Answer 5

这是我的并行和非并行scala版本,只是为了好玩:(在我的双核计算中,并行版本需要335毫秒而非并行版本需要655毫秒)

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

Answer 6

别介意基准; 问题让我感兴趣,我做了一些快速调整.这使用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,但如果您安装提供的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.5 GHz 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语言中会更加痛苦.

您无法将此版本的数字与其他版本的数字进行比较,而无需重写其他版本以使用类似的技巧.我不想在这里证明什么; 我只是觉得问题很有趣,我想看看我能收集哪些简单的性能改进.

Answer 7

别忘了Fortran!(大多是开玩笑,但我希望与C相似).带感叹号的语句是可选的,但风格很好.(!是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

Answer 8

我无法抗拒为C版本进行一些最明显的优化,这使得100k测试现在在我的机器上花费0.3秒(比问题中的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版本快一些.

这些是我运行100k的时间:

• 用/ Ox编译319ms C并输出到> NIL:
• 312ms C用/ Ox和静态计数器编译
• 324ms Java客户端VM,输出为> NIL:
• 带有静态计数器的299ms Java客户端VM

和1M运行(16386结果):

• 24.95s C用/ Ox和静态计数器编译
• 带有静态计数器的25.08s Java客户端VM
• 24.86s带有静态计数器的Java服务器VM

虽然这并没有真正回答你的问题,但它表明小的调整会对性能产生值得注意的影响.因此,为了能够真正比较语言,您应尽量避免所有算法差异.

它还提示了为什么Scala看起来相当快.它在Java VM上运行,因此可以从其令人印象深刻的性能中受益.