Интерпретация тестов на 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 (нестабильная гость Amd64 Debian, хост Windows 7 x64) ЦП: 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))))))

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

Фактор

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, добавив объявления типов? Это поможет?

Грубые ответы:

1. Статическая типизация Scala здесь немало помогает - это означает, что он довольно эффективно использует JVM без особых дополнительных усилий.
2. Я не совсем уверен в разнице между Ruby / Python, но подозреваю, что (2...n).all?эта функция is-prime?, вероятно, будет довольно хорошо оптимизирована в Ruby (EDIT: звучит так, как будто это действительно так, см. Ответ Джулиана для более подробной информации ...)
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, завершающий 10k за 0,635 секунды (т.е. второй по скорости в вашем списке, опережающий Scala)

PS обратите внимание, что в некоторых случаях у вас есть код печати внутри вашего теста - не очень хорошая идея, поскольку это исказит результаты, особенно если использование функции, например, printвпервые вызывает инициализацию подсистем ввода-вывода или что-то в этом роде!

Вот быстрая версия 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 раз быстрее, чем ваш оригинал. На моей машине это 100k за 1,5 секунды.

Отвечу просто # 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делает 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 дает ему 0,3 секунды для 10K и 21 секунду для 100K.

Вы можете сделать Scala намного быстрее, изменив свой isPrimeметод на

  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 версия.

См. Также: Как оптимизировать выражения for и циклы в Scala?

Вот моя версия 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))
  }
}

РЕДАКТИРОВАТЬ: Согласно предложению Эмиля Х , я изменил свой код, чтобы избежать эффектов 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, но может работать с более старым 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)))

Вышеупомянутое редактирование заняло очень мало времени. Я решил пойти еще дальше и сделать тест на простые делители только с использованием простых делителей и только с точностью до квадратного корня из проверяемого числа. То, как я это сделал, работает только в том случае, если вы проверяете числа по порядку, поэтому он может накапливать все простые числа по ходу; но эта проблема уже заключалась в проверке номеров по порядку, так что это было нормально.

На моем ноутбуке (ничего особенного; процессор - AMD Turion II «K625» с тактовой частотой 1,5 ГГц) эта версия выдала ответ для 100K менее чем за 8 секунд.

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). Заявления с восклицательными знаками необязательны, но в хорошем стиле. ( !является комментарием в 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

Я не мог устоять перед некоторыми из наиболее очевидных оптимизаций для версии C, из-за которой тест 100k теперь занимает 0,3 секунды на моей машине (в 5 раз быстрее, чем версия C в вопросе, обе скомпилированы с 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. Клиентская или серверная виртуальная машина не показывает большой разницы, за исключением того, что обучение JIT, похоже, немного помогает серверной виртуальной машине (~ 3%), в то время как на клиентской виртуальной машине оно почти не влияет. Вывод в Java кажется медленнее, чем в C. Если вывод заменен статическим счетчиком в обеих версиях, версия Java работает немного быстрее, чем версия C.

Вот мои времена для бега на 100 км:

• 319 мсек C скомпилирован с / Ox и выведен в> NIL:
• 312 мс C, скомпилированный с / Ox и статическим счетчиком
• Клиентская виртуальная машина Java 324 мс с выводом на> NIL:
• Клиентская виртуальная машина Java 299 мс со статическим счетчиком

и пробег 1М (16386 результатов):

• 24.95s C скомпилирован с / Ox и статическим счетчиком
• 25.08с Java-клиентская виртуальная машина со статическим счетчиком
• Виртуальная машина Java-сервера 24,86 с со статическим счетчиком

Хотя это на самом деле не отвечает на ваши вопросы, но показывает, что небольшие изменения могут оказать заметное влияние на производительность. Поэтому, чтобы действительно сравнивать языки, вы должны стараться избегать всех алгоритмических различий, насколько это возможно.

Это также подсказывает, почему Scala кажется довольно быстрой. Он работает на виртуальной машине Java и, следовательно, имеет впечатляющую производительность.

В Scala попробуйте использовать Tuple2 вместо List, он должен работать быстрее. Просто удалите слово «Список», поскольку (x, y) является Tuple2.

Tuple2 специализируется на Int, Long и Double, что означает, что ему не нужно упаковывать / распаковывать эти необработанные типы данных. Источник 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,1 ГГц, 2 МБ кэш-памяти L2, частота системной шины 800 МГц. 4 ГБ оперативной памяти

Версия 100k: C: 2.723s Go: 2.743s

С 1000000 (1M вместо 100K): C: 3m35.458s Go: 3m36.259s

Но я думаю, что было бы справедливо использовать встроенные в Go возможности многопоточности и сравнить эту версию с обычной версией C (без многопоточности) просто потому, что многопоточность с Go сделать почти слишком просто.

Обновление: я сделал параллельную версию с использованием горутин в 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
}

Распараллеленная версия использовала в среднем 2,743 секунды, то есть то же время, что и обычная версия.

Распараллеленная версия завершилась за 1,706 секунды. Использовалось менее 1,5 Мб ОЗУ.

Одна странность: мой двухъядерный 64-битный кубунту никогда не работал с обоими ядрами. Похоже, что Go использует только одно ядро. Исправлено звонком наruntime.GOMAXPROCS(4)

Обновление: я прогнал параллельную версию до 1 миллиона чисел. Одно из ядер моего процессора все время было на 100%, а другое вообще не использовалось (странно). Это заняло на минуту больше, чем у C и обычных версий Go. :(

С 1000000 (1M вместо 100K):

C: 3m35.458s Go: 3m36.259s Go using goroutines:3 мин. 27,137 сек.2m16.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

На моем MacBook Air с Core i5 1,8 ГГц результаты производительности следующие:

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

Похоже, что JIT JVM дает Ruby хороший прирост производительности в случае по умолчанию, в то время как настоящая многопоточность помогает JRuby работать на 50% быстрее в многопоточном случае. Что еще интереснее, JRuby 1.7 улучшает оценку JRuby 1.6 на целые 17%!

Основываясь на ответе x4u , я написал версию scala с использованием рекурсии, и я улучшил ее, перейдя только к sqrt вместо x / 2 для функции простой проверки. Я получаю ~ 250 мс для 100k и ~ 600 мс для 1M. Я пошел дальше и достиг 10M за ~ 6 секунд.

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

Я также вернулся и написал версию CoffeeScript (V8 JavaScript), которая дает ~ 15 мс для 100k, 250 мс для 1M и 6 с для 10M, используя счетчик (игнорируя ввод / вывод). Если я включаю выход, это занимает ~ 150 мс для 100k, 1 с для 1M и 12 с для 10M. К сожалению, здесь не удалось использовать хвостовую рекурсию, поэтому мне пришлось преобразовать ее обратно в циклы.

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 в долгосрочной перспективе, возможно, даже быстрее, чем «нормальный» язык ассемблера. Конечно, вы всегда можете вручную оптимизировать сборку, чтобы превзойти что угодно, выполнив ручное профилирование времени выполнения и создав отдельную версию для каждого процессора, вы просто должны быть потрясающе хорошими и знающими.

Причины скорости Java:

JVM может анализировать ваш код во время его выполнения и вручную оптимизировать его - например, если у вас был метод, который можно было статически проанализировать во время компиляции, чтобы быть истинной функцией, и JVM заметила, что вы часто вызываете его с тем же параметры, он МОЖЕТ фактически полностью исключить вызов и просто ввести результаты последнего вызова (я не уверен, действительно ли Java делает это точно, но она делает много таких вещей).

Благодаря статической типизации JVM может многое узнать о вашем коде во время компиляции, что позволяет предварительно оптимизировать довольно много вещей. Это также позволяет компилятору оптимизировать каждый класс индивидуально, не зная, как другой класс планирует его использовать. Кроме того, Java не имеет произвольных указателей на ячейку памяти, она ЗНАЕТ, какие значения в памяти могут и не могут быть изменены, и может соответствующим образом оптимизироваться.

Распределение кучи НАМНОГО эффективнее, чем C, выделение кучи в Java больше похоже на выделение стека C по скорости - но более универсально. Много времени было потрачено на различные алгоритмы, используемые здесь, это искусство - например, все объекты с коротким сроком службы (например, переменные стека C) размещаются в "известном" свободном месте (поиск свободного места не требуется. с достаточным пространством), и все они освобождаются за один шаг (как всплывающий стек).

JVM может знать особенности архитектуры вашего процессора и генерировать машинный код специально для данного процессора.

JVM может ускорить ваш код еще долго после того, как вы его отправили. Подобно тому, как перемещение программы на новый ЦП может ускорить ее, перенос ее на новую версию JVM также может дать вам огромную производительность скорости, привязанную к ЦП, которой даже не существовало, когда вы изначально скомпилировали свой код, что-то c физически не может обойтись без перекомпоновки.

Между прочим, большая часть плохой репутации скорости java связана с долгим временем запуска для загрузки JVM (когда-нибудь кто-нибудь встроит JVM в ОС, и это исчезнет!) И тем фактом, что многие разработчики действительно плохо пишут Код графического интерфейса пользователя (особенно многопоточный), из-за которого графические интерфейсы Java часто перестали отвечать на запросы и глючили. Недостатки простых в использовании языков, таких как Java и VB, усугубляются тем фактом, что возможности среднего программиста обычно ниже, чем у более сложных языков.