суббота, 23 апреля 2011 г.

Тест производительности (updation 2)




Решил протестировать производительность различных языков программирования на факториале от 50000, и вот что у меня получилось.

Scheme (racket 5.1) – 8s
Clojure 1.2 – 23s
Java 1.7 – 17s
Sbcl 1.0.43 – 7s
Ruby 1.9.2 -- 10s.
Parallel Clojure -- 3s.

Функция на Clojure выглядит следующим образом.

(defn fact!
  ([num]
    (fact! num 1))
  ([num result]
    (if (zero? num)
      result
      (recur (dec num) (* result num)))))

Ответ на функцию (fact! 50000) не привожу, потому что он занимает в OpenOffice 52 страницы шрифтом Liberation Serif 12.

Вывод из этого эксперимента следующий: самый быстрый язык для вычислений с большими числами в одном потоке – это Common Lisp (sbcl). С/C++ в расчет не берем, т. к. в его стандарте вообще нет средств для работы с числами такого размера. Java более чем в два раза медленнее; реализация алгоритма факториала не через рекурсию, а с помощью цикла. Это связано с тем, что в Java нет оптимизации хвостовой рекурсии, и рекурсивная реализация на Java просто вылетает с ошибкой StackOverflow. Хотя все реализации осуществляют именно итеративный процесс.
Clojure на 35% медленее Java, но тоже, в принципе, достаточно быстр.
Racket, запущенный без дебужных опций, оказался тоже достаточно шустрым и справился с заданием всего за 8 секунд, заняв почетное второе место. На третьем месте -- Ruby 1.9.2.

По предложению Vinzent'а,  решил протестировать еще и параллельную реализацию на Clojure. Учитывая, что "параллельность" в Clojure из коробки, сделать это оказалось очень просто. Vinzent прислал очень идиоматичный исходник, за что большое ему спасибо. Привожу его (исходник) ниже.

Результат вычислений был выше всяких похвал. Clojure справился с факториалом 50000 всего за 3 секунды!

(defn chunks [x n]
  (take n
    (partition 2 1
           (iterate
              (partial + (/ x n)) 1))))

(defn pfact [chunks]
  (reduce * (pmap
         (fn [[from to]]
           (reduce * (range from to)))
         chunks)))

(time (pfact (chunks 50000 10)))

17 комментариев:

  1. Yea, right. sbcl is a definitly way to go...


    f' :: Integer -> Integer -> Integer
    f' 1 a = a
    f' x a = f' (x - 1) (a * x)

    main = print $ f' 50000 1


    home% ghc --make -O2 fact.hs
    home% time ./fact > /dev/null
    ./fact > /dev/null 0.28s user 0.01s system 98% cpu 0.292 total

    home% time runhaskell fact.hs > /dev/null
    runhaskell fact.hs > /dev/null 0.44s user 0.02s system 99% cpu 0.468 tota

    ОтветитьУдалить
  2. main = print $ product [1..50000]

    home% ghc --make -O2 fact2.hs && time ./fact2 > /dev/null
    ./fact2 > /dev/null 0.26s user 0.00s system 98% cpu 0.261 total

    ОтветитьУдалить
  3. sbcl 1.0.45:


    (defun factorial (x)
    (labels ((helper (current accum)
    (if (= current 1)
    accum
    (helper (1- current)
    (* current accum)))))
    (helper x 1)))

    0.611 seconds of real time
    0.612038 seconds of total run time (0.596037 user, 0.016001 system)

    ОтветитьУдалить
  4. Для рекурсивной версии java можно -Xms поставить побольше.

    ОтветитьУдалить
  5. Это не тест языков, это тест их библиотек для работы с большими целыми числами.

    ОтветитьУдалить
  6. Scala оказалась быстрее Clojure выдает 21s.

    ОтветитьУдалить
  7. dream-x: Ну это еще от компьютера зависит. Я тестирую на Intel Core i5 430M (2.26GHz, 3Mb L3 cache), 4Gb Memory.
    Кстати, что интересно, Ruby 1.9.2 справился с тестом за 10с.

    ОтветитьУдалить
  8. Как обычно, забыли в Racket отключить debug mode и трассировку стека? У меня ~18 секунд Racket и Clojure, причем на аргументах до 40000 Racket стабильно вдвое быстрее. И да, там jit, а не интерпретатор.

    ОтветитьУдалить
  9. Попробуйте посчитать на Factor'е

    : factorial ( n -- n! )
    [1,b] product ;

    [ 50000 factor drop ] time

    На моей Core i7 760QM (1.6GHz) считает за 1.4 секунды..

    ОтветитьУдалить
  10. Поправочка:

    : factorial ( n -- n! )
    [1,b] product ;

    [ 50000 factorial drop ] time

    ОтветитьУдалить
  11. Gambit-C

    $ cat fg.scm
    (define (f n acc)
    (if (= n 0)
    acc
    (f (- n 1) (* acc n))))

    (with-output-to-file "f.txt" (lambda () (display (f 50000 1))))

    ...интерпретируем-интерпретируем...

    $ time ./a.out
    ./a.out 2,30s user 0,02s system 99% cpu 2,325 total

    $ wc -c f.txt
    213237 f.txt

    ОтветитьУдалить
  12. user> (defn factorial [x] (reduce * (range 1 (inc x))))
    user> (time (factorial 50000))
    "Elapsed time: 17841.878475 msecs"

    на старом Athlon 1.8 ггц.

    Кстати, восклицательный знак в конце ставится у функций, которые небезопасны при вызове из стм-транзакции.

    ОтветитьУдалить
  13. а почему факториал считается в одном трэде? ведь параллелится же "на ура"...

    ОтветитьУдалить
  14. Vinzent: знаю, просто хотелось сделать типа как в математике n!
    Alkhimov: распараллеливание здесь ничего не покажет, достаточно просто посмотреть, как язык считает на одном треде.

    ОтветитьУдалить
  15. Кстати да:
    (defn chunks [x n] (take n (partition 2 1 (iterate (partial + (/ x n)) 1))))

    (defn pfact [chunks]
    (reduce * (pmap (fn [[from to]] (reduce * (range from to)))
    chunks)))

    user> (time (pfact (chunks 50000 10)))
    "Elapsed time: 6152.770221 msecs"

    Думаю было бы неплохо добавить эти примеры в статью.

    ОтветитьУдалить
  16. Вот вариант на Racket, раз пошла такая пляска:
    (define (fac n fn)
    (define len (add1 (truncate (/ n fn))))
    (apply *
    (map (λ (x) (apply * x))
    (for/list ([i (in-range (add1 fn))])
    (for/list ([j (stop-before (in-range 1 (add1 len))
    (λ (j) (> (+ j (* i len)) n)))])
    (+ j (* i len)))))))

    ОтветитьУдалить