LINUX.ORG.RU

Скорость обработки массивов в разных лиспах и прочих яп

 , , , ,


5

9

Задача - создать массив случайных чисел на 3000000 элементов и замерить сколько времени займет нахождение суммы квадратов.

SBCL:

(defconstant +size+ 3000000)

(defparameter *vector* (map-into (make-array +size+ :element-type 'double-float) (lambda () (random 1.0d0))))

(defun sum-vec (v &aux (s 0.0d0))
  (declare (optimize speed (safety 0) (debug 0))
           (type (simple-array double-float (*)) v)
           (type double-float s))
  (dotimes (i (length v) s)
    (incf s (expt (elt v i) 2))))

(time (sum-vec *vector*))
$ sbcl --load bench.lisp
Evaluation took:
  0.009 seconds of real time
  0.012001 seconds of total run time (0.012001 user, 0.000000 system)

Racket

#lang typed/racket
(require racket/flonum)

(define Sz 3000000)
(define test-vec 
    (for/flvector #:length Sz ([i (in-range Sz)]) (random)))

(: sum-vec : FlVector -> Flonum)
(define (sum-vec v)
  (for/fold ([S 0.0]) ([e (in-flvector v)]) 
    (fl+ (fl* e e) S)))

(time (sum-vec test-vec))
$ raco exe bench.rkt
$ ./bench
cpu time: 20 real time: 22 gc time: 0

1. Можно ли код на racket еще улучшить?

2. Сколько времени занимает обработка в ваших языках? Особенно интересует ocaml и haskell

UPD. Думаю стоит пририсовать два нуля к размеру массивов, чтобы они не влезали целиком в кеши, олсо подумать там более произвольным доступом в к элементам.

★★★★★

Последнее исправление: x4DA (всего исправлений: 2)

Ответ на: комментарий от qnikst

в смысле random() и вычисление квадрата будет вычисляться сразу? это не интересно.

x4DA ★★★★★
() автор топика
Ответ на: комментарий от x4DA

Не, просто значение на грани точности, ещё 0.9 секунды куда ни шло, а тут что угодно повлияет.

unC0Rr ★★★★★
()
Ответ на: комментарий от x4DA

Можно, если не ошибаюсь, но только после школы^W рабства.

anonymous
()
Ответ на: комментарий от x4DA

отдельно чего? нету никакого отдельно. Погоди я scbl соберу, чтобы мог относительно результы смотреть. Можно без -O , но какой тогда смысл?

qnikst ★★★★★
()
Ответ на: комментарий от unC0Rr

можно и троллейбус из буханки сделать..

qnikst ★★★★★
()
import qualified Data.Vector.Unboxed as U
import Control.Applicative
import System.Random.Mersenne

main = do
    gen <- newMTGen Nothing
    rs <- randoms gen
    let vec = U.fromList (take  rs) :: U.Vector Int
    print $ U.sum $ U.map (^2) $ vec

сборка:

ghc -O2 2.hs -ddump-simpl -dsuppress-uniques -dsuppress-module-prefixes -fforce-recomp -ddump-to-file

все опции проме -O2 нужны чтобы поглядеть в simpl версию создаваемую при генерации..

результаты:

qnikst@thinkpad ~/tmp/lor/sumk $ \time ./2
7419632219866927510
0.30user 0.00system 0:00.30elapsed 100%CPU (0avgtext+0avgdata 8608maxresident)k
0inputs+0outputs (0major+594minor)pagefaults 0swaps

 \time sbcl --load bench.lisp 
fatal error encountered in SBCL pid 32605(tid 140737353918208):
can't find core file at /usr/local/lib/sbcl//sbcl.core


Command exited with non-zero status 1
0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 4224maxresident)k
0inputs+0outputs (0major+575minor)pagefaults 0swaps

lisp отработал быстрее, только какую-то чушь выдал.

P.S. Опс константа не та, ща поменяю.. P.P.S. обновил

qnikst ★★★★★
()
Последнее исправление: qnikst (всего исправлений: 3)
Ответ на: комментарий от qnikst

Чувак, у тебя лисп не отработал быстрее, а запуститься не смог, на что как бы намекает «fatal error».

Линукс - не оффтопик. Читай что тебе программы пишут.

По логам диагностирую неправильную установку. Если ставил из реп - пиши баг репорт в свой дистр.

naryl ★★★★★
()
Ответ на: комментарий от naryl

Чувак, у тебя лисп не отработал быстрее, а запуститься не смог, на что как бы намекает «fatal error».

:данеужели.lisp: и чтоб я без тебя такого умного делал?

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

А, да. Ещё time sbcl - не интересно, т.к. включает время компиляции сорца. Там замер времени в самом коде есть.

naryl ★★★★★
()
Ответ на: комментарий от qnikst

Скорее всего продолжал бы не читая тыкать в OK, как в оффтопике, судя по

lisp отработал быстрее, только какую-то чушь выдал.

naryl ★★★★★
()
Ответ на: комментарий от naryl

мне если честно не сильно лисп интересен, а проблема т.к. лисп нормально не работает на hardened системе.

UPD. это поправлено, я не обновил env.

qnikst ★★★★★
()
Последнее исправление: qnikst (всего исправлений: 1)
Ответ на: комментарий от naryl

табличка сарказм в теме слева, поищи пожалуйста.

qnikst ★★★★★
()

создать массив случайных чисел на 3000000 элементов и замерить сколько времени займет нахождение суммы квадратов

Лучше не случайными цифрами, а последовательностью какой-то, чтобы можно было проверить результат.

goingUp ★★★★★
()
Ответ на: комментарий от goingUp

лучше вообще своё время на это не тратить, честно.

вот код получше:

import qualified Data.Vector.Unboxed as U
import System.Random.Mersenne.Pure64
import qualified Data.Vector.Random.Mersenne as G

main = do
    g   <- newPureMT
    let vec = G.randoms g 3000000 :: (U.Vector Double) 
    print . U.sum $ U.map (^2) vec

qnikst ★★★★★
()
Последнее исправление: qnikst (всего исправлений: 2)

Обалдеть, лисп довольно быстр:

bash-3.2$ sbcl --load bench.lisp
This is SBCL 1.1.8.0-19cda10, an implementation of ANSI Common Lisp.
...
Evaluation took:
  0.003 seconds of real time
  0.003179 seconds of total run time (0.003171 user, 0.000008 system)
  100.00% CPU
  9,187,864 processor cycles
  1 page fault
  0 bytes consed

Хаскельную версию проверять лень и неинтересно сейчас, но она должна быть медленнее, очевидно. Да, qnikst, время надо явно замерять после инициализации массива.

dave ★★★★★
()

1. Можно ли код на racket еще улучшить?

У тебя и так 0+погрешность, куда быстрее? Запусти хотя бы раз по сто код.

anonymous
()

ну а вообще в схемах не бывает (optimize speed (safety 0) (debug 0)), только (optimize speed (safety 1) (debug 1))

anonymous
()

Подозреваю, что ocaml будет безнадежен, если только его не отучили от boxing для вещественных чисел, что сильно вряд ли.

dave ★★★★★
()
Ответ на: комментарий от dave

а, qnikst, время надо явно замерять после инициализации массива.

это да, но тут особой разницы нет, ибо задача абсолютно не интересная. Вот например наличие fusion-а уже было бы интересно поменять, если напр. заменив 3000000 на 300000000000.

Или там скорость генерации случайных чисел при этом с хорошими свойствами.

или например запуск под ulimit чтобы потребляемая память не увеличивалась с размером задачи.

qnikst ★★★★★
()
Последнее исправление: qnikst (всего исправлений: 1)
> ddd<-runif(3000000)
> system.time(sum(ddd^2))
пользователь      система       прошло 
       0.008        0.000        0.008 
> system.time(sum(ddd^2))
пользователь      система       прошло 
       0.008        0.000        0.009 
> system.time(sum(ddd^2))
пользователь      система       прошло 
       0.008        0.000        0.008 
> system.time(sum(ddd^2))
пользователь      система       прошло 
       0.008        0.000        0.008 

psv1967 ★★★★★
()
Ответ на: комментарий от true_admin

Это скорее тест на то, есть боксинг или нет. В ocaml он должен присутствовать, как и во многих других реализациях лиспа.

Вот, тут у меня 32-битный LispWorks на 64-битной Win8. Я добавил декларацию (float 0), но все равно не избавился от boxing (см. показатель «allocation»). Поэтому получилось сильно медленнее, чем для SBCL.

CL-USER 1 > (lisp-implementation-type)
"LispWorks"

CL-USER 2 > (lisp-implementation-version)
"6.1.1"

CL-USER 3 > (compiled-function-p #'sum-vec)
T

CL-USER 4 > (time (sum-vec *vector*))
Timing the evaluation of (SUM-VEC *VECTOR*)

User time    =        0.578
System time  =        0.000
Elapsed time =        0.591
Allocation   = 240047740 bytes
0 Page faults
1001169.7095752516D0

Честно говоря, я уже немного подзабыл эту тему избавления от boxing. Да и по хорошему надо проверять на 64-битном LispWorks, но у меня его нет.

dave ★★★★★
()
Ответ на: комментарий от dave

Переписал, и стало совсем по-другому в 32-битном LispWorks (просто expt вызывало boxing, но от последнего полностью не избавился):

CL-USER 9 > (time (sum-vec *vector*))
Timing the evaluation of (SUM-VEC *VECTOR*)

User time    =        0.062
System time  =        0.000
Elapsed time =        0.056
Allocation   = 48046336 bytes
0 Page faults
1000222.4835098522D0

Сам код:

(defconstant +size+ 3000000)

(defparameter *vector* 
  (map-into (make-array +size+ :element-type 'double-float) (lambda () (random 1.0d0))))

(defun sum-vec (v &aux (s 0.0d0))
  (declare (optimize (speed 3) (float 0) (safety 0) (debug 0))
           (type (simple-array double-float (*)) v)
           (type double-float s))
  (dotimes (i (length v) s)
    (let ((x (elt v i)))
      (declare (type double-float x))
      (incf s (* x x)))))

;; (time (sum-vec *vector*))
dave ★★★★★
()

Опять лисперы упоролись и сравнивают производетельность одной программы на разных конфигурациях.

cdshines ★★★★★
()
Ответ на: комментарий от dave

В ocaml он должен присутствовать

Тут только тест покажет. В чейнжлоге для 4.00 заявлен better auto unboxing, но без тестов я бы не доверял этому.

true_admin ★★★★★
()
Ответ на: комментарий от dave

можно expt заменить на умножение в этом случае

x4DA ★★★★★
() автор топика
Ответ на: комментарий от dave

Дальше. Заменил elt на более специфичный aref, и уже 32-битный LispWorks не так сильно отстает от SBCL:

CL-USER 1 > (time (sum-vec *vector*))
Timing the evaluation of (SUM-VEC *VECTOR*)

User time    =        0.015
System time  =        0.000
Elapsed time =        0.015
Allocation   = 42956 bytes
0 Page faults
999531.3856503042D0

Но надо сравнивать с 64-битным LispWorks, как я уже заметил выше. Там значения double-float являются immediate objects.

dave ★★★★★
()
Ответ на: комментарий от dave

Ну вот я, сколько бы раз не запускал, сумма одинакова, во всех знаках.

buddhist ★★★★★
()
Ответ на: комментарий от buddhist
(defparameter *vector* (map-into (make-array +size+ :element-
type 'double-float) (lambda () (random 1.0d0))))

 (defparameter *vector2* (map-into (make-array +size+ :element-type 'double-float) (lambda () (random 1.0d0))))

* (sum-vec *vector*)

999638.4871802685d0

* (sum-vec *vector2*)

999983.9109388306d0

Со всей очевидностью суммы разные.

harm
()
Ответ на: комментарий от buddhist

А, вот ты о чем. Сумма одинаковая в пределах сессии. Инициализируется вектор один раз случайным образом. У меня просто были разные сессии. Я запускал по новой.

dave ★★★★★
()
Последнее исправление: dave (всего исправлений: 1)
Ответ на: комментарий от dave

Но надо сравнивать с 64-битным LispWorks, как я уже заметил выше. Там значения double-float являются immediate objects.

Черт, перепутал c single-float. Так что, лучше вряд ли будет.

dave ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.