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)
Ответ на: комментарий от x4DA

Даже так

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 3000000

 static double mass[SIZE],
               result=0;

  int main(void)
  {
    

    srand(time(NULL));
    
    for(long int j=0; j!=SIZE ;j++)
    {  
       mass[j] = (rand() % 1000) ;
    };

    clock_t start = clock();

    for( register long int j=0; j!=SIZE ;j++)
    {  
      result += ( (mass[j] * mass[j]) * (mass[j] * mass[j]) );  
    };

    clock_t end = clock();

    double time = (double)(end - start) / CLOCKS_PER_SEC;

    printf("result=%lf\n",result);
    printf("time=%lfs\n",time);
    return 0;
  }
dron@gnu:~$ gcc-4.8  -std=c99 -o test ./main.c
dron@gnu:~$ ./test 
result=598953554469164032.000000
time=0.010000s
dron@gnu:~$ 

Либо 0.01 и более , либо по нулям.

А ты зачем полученное время ещё преобразуешь? тогда у меня time=0.000010s будет :)

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

К чему это задротство? из дизассембла на SBCL понятно что в sequential-вариации кода то, что выдает лисп - предел.

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

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

А вдруг :)

P.S. Просто забыл убрать, осталось от прошлых экспериментов.

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

я как бы про векторизацию и намекаю.

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

300000000 6.705
haskell(fusion) автоматически фьюзит массив, соответственно генерация случайных чисел вихрем Мерсенна тоже входит в считаемое время.

Во время входит, да «в память» не входит. Создай реальный массив и расскажи как хаскель будет «напроч завешивать систему»

> dooo.data <- function(data) {
+   n <- length(data)
+   nn <- 3000000
+   k <-floor(n/nn) 
+   if(k > 0) sum(sapply(1:k, function(i) sum(data[(i*nn-nn+1):(i*nn)]^2 ))) + sum(data[(nn*k):n]^2) else sum(data^2)
+ }

> ddd<-runif(300000000)

> system.time(dooo.data(ddd))
пользователь      система       прошло 
       2.632        0.180        2.819 

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

fail....

ddd<-runif(300000000)

Error: cannot allocate vector of size 2.2 Gb

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

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

если ты не понял, то проблема в вычислении последнего случая была как раз в том, что память не выделить, т.к. столько в системе нет (или ограничение ulimit, я не помню уже ставил ли). Про тормозить, R вешал систему там, где все остальные языки отрабатывали нормально, я пока не вижу ни одной причины, почему ситуация в области «сверх-больших» массивов будет другой.

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

Error: cannot allocate vector of size 2.2 Gb

Ну и кто тебе виноват? Заниматься «пузомерками», задавая как можно более длинный вектор, на 32 разрядной версии?

Если что, у меня копипаста из консоли была... Твоим табличкам все верить должны получается, а тут «я проверю»(С)? Будь последователен :)

Какое там время на проверку нужно? Аллоцировать память под массив (одна строчка) и пойти курить пока машинка будет «стоять колом с хаскелем»? :)

В R проблем посчитать нет даже на 32 разрядной версии :)

> library(ff)
> a<- ff(0, 300000000, filename    = "./temp")
> a<-runif(300000000)
> str(a)
 num [1:300000000] 0.34 0.819 0.16 0.766 0.135 ...
> dooo.data <- function(data) {
+    n <- length(data)
+    nn <- 3000000
+    k <-floor(n/nn) 
+    if(k > 0) sum(sapply(1:k, function(i) sum(data[(i*nn-nn+1):(i*nn)]^2 ))) + sum(data[(nn*k):n]^2) else sum(data^2)
+  }
> dooo.data(a)
[1] 99998021

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

Ну и кто тебе виноват?

никто не виноват.

Заниматься «пузомерками», задавая как можно более длинный вектор, на 32 разрядной версии?

строить догадки не в вопросительной форме категорически не рекомендуется; система 64 разрядная.

Если что, у меня копипаста из консоли была... Твоим табличкам все верить должны получается, а тут «я проверю»(С)?

Код всех программ в моих табличках приведен в этом треде, взять и проверить никто не запрещает. Оформлять на гист с автоскриптами мне лень. Я абсолютно последователен, я проверяю все коды приведенные в треде, и делаю какие либо утверждения после только проверки, в отличии от теоретиков.

Будь последователен :)

Какое там время на проверку нужно? Аллоцировать память под массив (одна строчка) и пойти курить пока машинка будет «стоять колом с хаскелем»? :)

разверни мысль, я не понял про что ты.. Если, что «код R при работе с 30000000 ставил колом всю систему, в отличии от других, так же выделяющих полный массив», можешь пытаться опровергать или говорить, как поправить.

> library(ff)
Error in library(ff) : there is no package called ‘ff’

мануал, как ставить пожалуйста (хост ось гента).

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

тьфу, немного не так :)

> a<- ff(runif(300000000), filename    = "./temp1")
> gc()
         used (Mb) gc trigger   (Mb)  max used   (Mb)
Ncells 234350  6.3     467875   12.5    350000    9.4
Vcells 215551  1.7  252399775 1925.7 444515319 3391.4
> system.time(dooo.data(a))
пользователь      система       прошло 
       7.869        6.316       96.989 

Это на моём замученном ноуте, больше 30 мегабайт/c он не читает :)

Для чего стрип райды из 4 - 6 дисков собирают, или что такое ssd рассказывать? :)

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

разверни мысль, я не понял про что ты.. Если, что «код R при работе с 30000000 ставил колом всю систему, в отличии от других, так же выделяющих полный массив», можешь пытаться опровергать или говорить, как поправить.

Угу

haskell(fusion) автоматически фьюзит массив, соответственно генерация случайных чисел вихрем Мерсенна тоже входит в считаемое время.

Когда «колом система ставится», это попытка выделить больше памяти чем есть реально свободной. Если в каком то языке можно хранить вектор более экономно, она будет «ставиться колом» немного позже (при попытке считать «в лоб»). Если считать блочно, и читать объект с диска (стрипнутого массива, или ssd), никаких тормозов и «вставаний колом» не будет нигде и никогда. Пока не кончится арифметика выбранного типа хранения вектора.

Длинная арифметика давно оптимальным образом реализована и доступна везде. Хочешь посоревноваться насколько быстро её использовать из разных языков? :)

anonymous
()
Ответ на: комментарий от anonymous
>  a<- ff(runif(300000000), filename    = "./temp1")
Error: cannot allocate vector of size 2.2 Gb

следующая попытка будет? :) В R есть аналог Data.Vector.Lazy? должно сработать, если gc умеет вызываться при аллокациях требующих расширения выделенной памяти, правда, насколько я знаю, он не умеет.

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

ладно не слишком это важно, мои фразы про R говорят о том, что там больше накладных расходов на хранение данных и применение примитивных операций, так же то, что там дурацкая рантайм система (точнее интерпретатор, со странным GC, я если честно немного задолбался читать ограничения на работу при создании своего пакета (на сях)). Из-за этих пунктов R не может быть языком общего назначения (в отличии от других участников бенчмарка, кроме J), и будет сливать на подобных бенчмарках, но сила R не в этом, а в большом кол-ве библиотек, и не сложном апи для работы со статистикой, тут он сильнее, т.к. на других языках относительно R нужно переизобретать велосипед, что нужно далеко не всегда.

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

Конечно будет... хотя начинаю сомневаться что у тебя хоть что то работает :)

>  a<- ff(0, 300000000, filename    = "./temp2")
> ffvecapply(a[i1:i2]<-runif(length(i1:i2)), X=a, BATCHSIZE=10000000)
> ffvecapply(sum(a[i1:i2]^2) , X=a, BATCHSIZE=10000000, RETURN=T, CFUN = "sum")
[1] 99996044

Для удовлетворения надо запускать на ssd или стрипнутом райде

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

Надо просто не льстить себе, а «подойти поближе»(С). Это означает не забывать когда пишешь приложения вставлять вызовы gc() явно, а не ждать когда наступит закономерный финал :).

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

Самописная блочная функция тоже работает на ff объекте. Только происходит наверное более бестолковое кеширование. Время которое пишет system.time() именно такое, какое получится в пределе при использовании быстрого ssd или дискового рейда.

> system.time(dooo.data(a))
пользователь      система       прошло 
       8.173        6.540      120.080 
> system.time(ffvecapply(sum(a[i1:i2]^2) , X=a, BATCHSIZE=10000000, RETURN=T, CFUN = "sum"))
пользователь      система       прошло 
       7.480        6.732      120.940 
> system.time(ffvecapply(sum(a[i1:i2]^2) , X=a, BATCHSIZE=100000000, RETURN=T, CFUN = "sum"))
пользователь      система       прошло 
       7.341        6.589      119.783 

Именно 7 секунд и будет. Чтобы системное время отобрать у ядра придется где то искать одноядерный проц :)

Так что размер задачи может быть любым помещающимся в память.

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

Ну чтож - сильно лучше:

1). 38 секунд против 34 haskell+mmap если считать полное время

2). 8 против 3 если считать user time.

а на промежутке, (30000000-90000000) работает с той же скоростью, что и haskell(fusion).

P.S. оказывается vector.lazy по аналогии с bytestring.lazy нету, видимо не особо нужно.

P.P.S haskell не умеет полноценно в SIMD(sse в данном случае), видимо llvm backend помог, можно помочь руками заменив U.sum на векторизуемую, хотя это скорее всего релеватно только для случая с fusion.

P.P.P.S. для полноты кладу haskell(mmap) версию (пришлось Storable использовать, отсюда относительные тормоза):

{-# LANGUAGE PackageImports #-}
import qualified Data.Vector.Storable as S
import qualified Data.Vector.Storable.Mutable as M
import System.Random.Mersenne
import qualified Data.Vector.Random.Mersenne as G
import Control.Monad
import Control.DeepSeq
import Control.Exception
import Data.Array.Repa.IO.Timing
import System.IO.MMap

import Foreign

main = do
    let n = 300000000
    (foreignPtr, offset, size) <- mmapFileForeignPtr "./tmp" ReadWriteEx (Just (0,n*sizeOf(undefined::Double)))
    let mvec = M.unsafeFromForeignPtr0 foreignPtr n :: M.MVector s  Double
    g   <- newMTGen Nothing
    t   <- randoms g
    forM_ (take n $ zip [0..] t) $ uncurry (M.unsafeWrite mvec)
    vec <- S.unsafeFreeze mvec
    (r,t) <- time $ evaluate $ force . S.sum . S.map (^2) $ vec
    print r
    putStr (prettyTime t)
qnikst ★★★★★
()
Ответ на: комментарий от qnikst

скорости работы, возможностей, проблем с рантаймом (а частности взаимодействие с GC и concurrency)

Так одно из двух.

1. Управление со стороны лиспа: тогда это такой FFI но со статической библиотекой.

2. Управление со стороны C: тогда все указатели заворачиваются в специальные структуры. Вместо malloc/free вызываются функции из библиотеки лиспа и т.д. В общем, как в питоне.

Второй вариант, разумеется, быстрее, но писать очень много.

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

Интересно, существует ли инструмент который смог бы такую задачу аналитически решить? При хорошем ГСЧ и большом массиве результат стремится к сумме квадратов [0..n]/length(array)/n. На массиве из 10**8 элементов (и rand() % 100) у меня отличия в 6-м знаке.

От нечего делать немного повекторизировал вручную, код стал чуть побыстрее (и потерял читабельность):

/*
        for (i=0; i<ALEN; i++) {
                res += array[i] * array[i];
        }
*/
        for (i=0; i<ALEN/4; i++) {
                double r;
                __m128d mm_ab, mm_cd, mm_mab, mm_mcd, mm_sumsh, mm_sum;

                mm_ab = _mm_loadu_pd(&array[i*4]);     /*   a | b */
                mm_mab = _mm_mul_pd(mm_ab, mm_ab);     /* a*a | b*b */

                mm_cd = _mm_loadu_pd(&array[i*4 + 2]); /*   c | d */
                mm_mcd = _mm_mul_pd(mm_cd, mm_cd);     /* c*c | d*d */

                mm_sum = _mm_add_pd(mm_mab, mm_mcd);   /* a*a + c*c | b*b + d*d */

                mm_sumsh = _mm_shuffle_pd(mm_sum, mm_sum, 1); /* b*b + d*d | a*a + c*c */
                mm_sum = _mm_add_pd(mm_sumsh, mm_sum);        /* a*a + b*b + c*c + d*d */

                _mm_store_sd(&r, mm_sum);
                res += r;
        }
FPU:	res 328349035229.000000, elapsed 0.151734
SSE2:	res 328349035229.000000, elapsed 0.143386

AVX-ом теоретически должно быть еще быстрее. Но это, конечно, бессмысленные оптимизации, просто из любопытства поковырялся

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

Интересно, существует ли инструмент который смог бы такую задачу аналитически решить?

если нужен точный результат, то нельзя =)

При хорошем ГСЧ и большом массиве результат стремится к сумме квадратов [0..n]/length(array)/n. На массиве из 10**8 элементов (и rand() % 100) у меня отличия в 6-м знаке.

rand() %100 это ОЧЕНЬ плохой ГСЧ, т.к. rand генерирует случайные данные с очень плохими свойствами в последних битах, а ты тольно их и оставляешь, тогда уж ((double)rand()/(double)RAND_MAX)*100

AVX-ом теоретически должно быть еще быстрее.

прикольно, надо будет потом посмотреть это внимательнее, сейчас уже лень этим заниматься. Поидее одна из след версий ghc будет уметь, что-то подобное делать, но пока соотв ветку ещё не влили, а учитывая, что окно принятия фич закрывается на этой неделе, то скорее всего уже в 7.9 это будет.

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

1). 38 секунд против 34 haskell+mmap если считать полное время

2). 8 против 3 если считать user time.

Ерго — R никакой не тормоз, в мало мальски не «сферических в вакууме» условиях использования. Все данные которые может сохранить пользователь всегда будут обработаны практически с такой же скоростью как низкоуровневое решение написанное «на злобу дня».

Более того, две строчки на R явно поменьше занимают времени, внимания (простора для совершения ошибок) и умения для написания, чем решение на хаскеле (куда тоже пришлось загрузить много кода).

anonymous
()

А уже предлагали для рэкета код заменить на unsafe-*, потом посмотреть raco decompile (во что получается лисп), а потом ещё сделать disassemble и забить на рэкет, так как детская игрушка с одним майнтейнером.

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

детская игрушка с одним майнтейнером.

Зачем говорить, о чем не знаешь?

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

30 Day Summary Aug 12 2013 — Sep 11 2013

686 Commits
17 Contributors

TR и так меняет код на unsafe. В этом тесте по производительности отстает от sbcl в 2 раза/

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

При этом если хотя бы не указать :element-type у вектора, то sbcl сразу начинает просасывать варианту на racket безо всех оптимизаций - с untyped кодом, обычными векторами и обычными +/*. Короче костыльная игрушка, которая что-то может только на синтетических бенчмарках.

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

JIT в рэкете слабее sbcl компилятора. И весь рэкетовский движок, если что, пилит один только Мэтью. И используют они патченый GNU Lightning. И в случае сложной функций (тригонометрия например) в своём JIT просто генерят вызов сишной обёртки. А сишная обёртка сделана хитро и для того, чтобы не реализовывать полноценный протокол вызова функции (ну там регистры, стек), параметры и результаты прокидываются через глобальные переменные (они локальные для тредов,конечно). Короче, рэкет не для скорости.

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

JIT в рэкете слабее sbcl компилятора.

Да с этим никто и не спорит.

Короче, рэкет не для скорости.

Ну это не мешает ему работать на идеоматическом коде быстрее sbcl.

anonymous
()

CuisSmalltalk 4.2.1824

Наивный код (да простит меня йогурт, если я неоптимально создаю массив случайных чисел, давно не брался за смоллток):

| a r |
a := FloatArray new: 3000000.
r := Random new.
a := a collect: [ :x | r next ].
TimeProfileBrowser onBlock: [ a squaredLength ].

4 миллисекунды.

30000000: 32 миллисекунды
60000000: 64 миллисекунды

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

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

Куда более печальны результаты Factor.

Код:

USING: io present
       kernel 
       specialized-arrays sequences
       math.vectors math.parser 
       tools.time 
       command-line ;
FROM: alien.c-types => float ;
FROM: random => uniform-random-float ;

IN: bench

SPECIALIZED-ARRAY: float

<PRIVATE
: random   ( e -- ne ) drop 0 1 uniform-random-float ;
: get-size ( -- i ) (command-line) second string>number ;
: generate ( -- a ) get-size <float-array> [ random ] map ;
PRIVATE>

: main ( -- ) [ generate norm-sq ] time present print ;

MAIN: main
[ generate norm-sq ] time present print

3000000: 0.29 сек
30000000: 4.41 сек
60000000: 8.41 сек

Плюс, оно почему-то не деплоится. Может быть запилю потом реализацию с SIMD

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