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

701. там косяки в системе сборки, непонятно откуда берущиеся.

0.0238864

и завтра патч с багрепортом пошлю, или сам применю

Скромный результат. Что ж, J никогда не отличался чудесами производительности (у K должно быть лучше с этим).

Ну тогда как-то так, вроде.

dron@gnu:~$ cat ./main.c 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

 long long int mass[3000000];
 long long int result;

  int main()
  {
    srand(time(NULL));
    //Заполнение массива мы не считаем как я понял.
    for(long int j=0; j!=3000000 ;j++)
    {  
       mass[j]=rand();  
    };

    clock_t start = clock();

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

    clock_t end = clock();

    printf("%fs\n",((float)(end-start)) / CLOCKS_PER_SEC);

    return 0;
  }
dron@gnu:~$ gcc -std=c99 ./main.c 
dron@gnu:~$ ./a.out 
0.020000s

Что-то долго. Какой у тебя калькулятор? Собери с -O2.

Варианты на racket, CL и R запусти еще для проверки.

Кстати, по хорошему бы надо выводить result, чтобы gcc не убрал его вычисление как dead code optimization.

Калькулятор amd phenom x6 2800Mhz

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

 long long int mass[3000000];
 long long int result=0;

  int main(void)
  {
    srand(time(NULL));
    
    for(long int j=0; j!=3000000 ;j++)
    {  
       mass[j] = rand()%99;//Ограничил двузначными
    };

    clock_t start = clock();

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

    clock_t end = clock();

    printf("result=%ld\ntime=%lfs",result,(double)(end - start) / CLOCKS_PER_SEC);
    return 0;
  }

dron@gnu:~$ gcc-4.8 -O2 -std=c99 ./main.c 
dron@gnu:~$ time ./a.out 
result=9655298464
time=0.010000s #не густо :(, я что-то делаю не так.

Твоё

dron@gnu:~$ sbcl --load ./bench.lisp 
This is SBCL 1.0.57.0.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
Evaluation took:
  0.005 seconds of real time
  0.008000 seconds of total run time (0.008000 user, 0.000000 system)
  

0.01 Си
0.008 СL

Блин, скажите мне что это не правда, молю!

Блин, скажите мне что это не правда, молю!

это не правда

А прогнать тест хотя бы тысячу раз и посмотреть среднее время?

Че там прогонять? SBCL на уровне Си, и всё.

Вон тут дизассембл для x86: http://paste.lisp.org/display/138879#1

let n = 3000000 in
  let _ = Random.self_init() and
      rarray = Array.init n (fun x -> Random.float (float x)) and
      t = Sys.time() in
    let r = Array.fold_left (fun a b -> a +. (b ** 2.0)) 0.0 rarray; in
      let new_t = Sys.time() in
        Printf.printf "Result: %f\n" r;
        Printf.printf "Took %fs\n" (new_t -. t);
;;

> ocamlc random_bench.ml
> time ./a.out

Result: 9002077513758873600.000000
Took 0.260000s
./a.out  1,90s user 0,01s system 99% cpu 1,910 total

?))

То, что время на уровне погрешности. Так что результат сишки тут может быть как в 100 раз быстрее sbcl, так и в 100 раз медленнее.

mass[j] *= mass[j]

А зачем *= если надо просто *?

для порядка:

import qualified Data.Vector.Unboxed as U
import System.Random.Mersenne.Pure64
import qualified Data.Vector.Random.Mersenne as G
import Control.DeepSeq
import Control.Exception
import Data.Time.Clock
import System.CPUTime
import Text.Printf

main = do
    g   <- newPureMT
    let vec = force $ G.randoms g 3000000 :: (U.Vector Double) 
    vecio <- evaluate vec
    t1 <- getCPUTime
    r  <- evaluate $ force . U.sum . U.map (^2) $ vecio
    t2 <- getCPUTime
    print r
    printf "Cpu time: %8.4fs\n" $ (fromIntegral (t2-t1) * 1e-12 :: Double)

куча evaluate и force добавлена для того, чтобы убить фьюжн и массив был бы таки выделен и заполнен до вычисления суммы квадратов (ценой 1.7 времени выполнения).

\time -v ./3
1000190.1420503161
Cpu time:   0.0100s
	Command being timed: "./3"
	User time (seconds): 0.08
	System time (seconds): 0.01
	Percent of CPU this job got: 93%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.09
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 104032
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 6626
	Voluntary context switches: 2
	Involuntary context switches: 2
	Swaps: 0
	File system inputs: 0
	File system outputs: 0
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 0
	Page size (bytes): 4096
	Exit status: 0

кстати только сейчас заметил, у лиспа 200.00% CPU, использовать больше 1 проца по умолчанию это хорошо. Но тогда получается, что haskell код я должен был в тех же условиях гонять, поэтому:

qnikst@thinkpad ~/tmp/lor/sumk $ ghc -O2 -fllvm -threaded 3.hs
qnikst@thinkpad ~/tmp/lor/sumk $ ./3 +RTS -N2
999866.4886005946
Cpu time:   0.0000s

Что за фигню ты тут намерял в последнем случае? Вероятно, компилятор sbcl просто распараллеливает компиляцию перед выполнением. Причем здесь сам тест?

Кстати, не удается установить vector-random:

$ cabal install vector-random
...
Downloading vector-random-0.2...
Configuring vector-random-0.2...
Building vector-random-0.2...
Preprocessing library vector-random-0.2...
[1 of 1] Compiling Data.Vector.Random.Mersenne ( Data/Vector/Random/Mersenne.hs, dist/build/Data/Vector/Random/Mersenne.o )

Data/Vector/Random/Mersenne.hs:85:5:
    The INLINE pragma for default method `random' lacks an accompanying binding
Failed to install vector-random-0.2
Updating documentation index /Users/david/Library/Haskell/doc/index.html
cabal: Error: some packages failed to install:
vector-random-0.2 failed during the building phase. The exception was:
ExitFailure 1

Что за фигню ты тут намерял в последнем случае?

тоже, что и в предпоследнем, но в 2 потока

Вероятно, компилятор sbcl просто распараллеливает компиляцию перед выполнением. Причем здесь сам тест?

честно не шарю. но если sbcl в 2 потока работает, то почему бы мне haskell-ный вариант в 2 потока не запустить.

про vector-random держи патч:

https://github.com/gentoo-haskell/gentoo-haskell/blob/master/dev-haskell/vect...

если не лень можешь в апстрим послать.

ну в 5 раз быстрее R. =)

Спасибо, кстати, благодаря этому тесту я пофиксил j в генте, на зеркалах в течении часа обновится где-то.

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

В общем подожду ещё полуофициального ответа и если он подтвердится, то в таком виде лор не нужен.

Попробуй ocamlopt

Не думаю, что код sbcl в самом тесте работает в два потока. Дизассемблерный листинг приводили выше. Хороший компилятор лиспа для этой конкретной задачи должен генерировать примерно такой же код, как и хороший компилятор Си или Си++. Странно, что для кого-то это является культурным шоком (здесь я не имею в виду тебя).

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

возможно, кстати, вот результаты с Репой:

-- random vector generation
import System.Random.Mersenne.Pure64
import qualified Data.Vector.Random.Mersenne as G
import qualified Data.Vector.Unboxed as U
-- repa
import Data.Array.Repa
import qualified Data.Array.Repa as R
import qualified Data.Array.Repa.Eval as R
import Data.Array.Repa.IO.Timing

main = do
    g   <- newPureMT
    vec <- R.now
            $ R.fromUnboxed (Z :. (3000000::Int))
            $ (G.randoms g 3000000 :: (U.Vector Double))
    (r,t) <- time $ R.sumP . R.map (^2) $ vec
    print r
    putStr $ prettyTime t

T<N> - threaded в N процессов S - non threaded O - старая версия на Unboxed.Vector, кол-во потоков и runtime не меняют время выполнения

                T1  T2  T3 T4(+llvm) S   OS  
elapsedTimeMS   14  7   6  3         14  9  
cpuTimeMS       20  20  20 20        10  10

UPD. с правильными опциями сборки -fno-liberate-case -funfolding-use-threshold1000 -funfolding-keeness-factor1000 -fllvm -optlo-O3 (подсмотрел в мануале) всё все получаются цифры уже совсем в рамках погрешности.

Бля сколько умных людей тут.

Дорисуйте несколько нулей к длине массива чтобы можно было хоть в чём-нибудь время считать. Такие занятые специалисты чтоле?

Если добавить ещё пару нулей, то J расскажет грустную историю про |out of memory.

Ты меряешь умножение целых, а не даблов.

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

double array[3000000];

int main(void)
{
	double result=0;

	srand(time(NULL));
	
	for(long int j=0; j!=3000000 ;j++)
	{  
		array[j] = (rand() % 1000000) / 1000000.0;
	};

	timespec time1, time2;
    	const int TRIES = 1000;

	clock_t start = clock();
	
	for (long int ntr; ntr < TRIES; ntr++) {
		for(long int j = 0; j < 3000000; j++) {  
			result += ( array[j] * array[j] ); 
		};
	}

	clock_t end = clock();
	double secs = (double) (end - start) / CLOCKS_PER_SEC;

	printf("result = %.2lf\navg time = %lf ms cpu time\n", result, secs / 1000 / TRIES);
	return 0;
}

у меня (core2 duo) показывает что-то вроде 0.000007 ms cpu time

Кстати, если собрать без -O2 то ваще в нули выходит.

ados держи

          lisp    j       R        c     haskell  haskell(fusion)
3000000   0.005   0.023  0.010+    0     0.002     0.066
30000000  0.048   0.328  0.140+    0.05  0.016     0.662
60000000  0.094   2.425  0.371+    0.10  0.038     1.326
300000000                                          6.705

примечания R первый раз считает в ~10 раз дольше чем во второй, я не знаю связано ли это с ленивостью, которая там используется или ещё с чем, в таблице приведено среднее время 2-го и последующих запусков, в отличии от других языков они сильно отличаются.

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

haskell и c считают даблы, lisp - флоаты, остальные дефолтный тип. Для сей использовалось только -O2.

В данные не входит, но j и R напроч вешали мне систему секунд на 10 на последнем запуске.

все, кто не фьюзит вычисления, её расскажут.

меряешь умножение целых, а не даблов.

теперь вы вместе измеряете ещё и скорость организации цикла по TRIES :)

for(long int j = 0; j < 3000000; j++) { result += ( array[j] * array[j] ); };

и неэффективные итерации

clock_t start = clock();

и неподходящим для этого средством (см http://stackoverflow.com/questions/12392278/measure-time-in-linux-getrusage-v... )

ps. даже несмотря на сказанное, если что-то ещё и может уделать тут C, то возможно Фортран - по идее математика и массивы/векторы/матрицы это его стезя :)

double-float в лиспе обычно и есть double из haskell или из си. Обычный для си float называется single-float.

А в таблице у тебя приведены для haskell те мухлеванные значения, которые используют параллельность?

double-float в лиспе обычно и есть double из haskell или из си. Обычный для си float называется single-float.

а ясно, тогда всё ок

А в таблице у тебя приведены для haskell те мухлеванные значения, которые используют параллельность?

да. без параллельности на уровне си и lisp.

P.S. перепроверил данные

          lisp    j       R     c       haskell  haskell(no-force)
3000000   0.005   0.022  0.010  0.00001 0.002     0.066
30000000  0.048   0.230  0.140  0.05    0.016     0.662
60000000  0.094   0.473  0.371  0.10    0.038     1.326
90000000  0.142   0.693  0.480  0.15    0.051     1.983
300000000   x     x      x      x       x         6.705

только R тут безбожно врёт, т.к. на самом деле там секунд 20 прошло, я успел чайник поставить, пока считалось..

прошу привести, программу на Си, которая уделывает haskell в данной задаче. Мне честно инетерсно насколько усложнится си код при добавлении в него многопоточности.

60000000: j — 2.425

Странно, у меня 0.66777(j64-701).
Код на j берёт среднее от 10-и запусков, поэтому, наверное, и вешает.

я поправился, не знаю почему такая фигня была.

Тред какой-то слегка, гм, норкоманский.

Вот код на С:

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

#define ALEN (100 * 1000 * 1000)

int
main()
{
        double *array, res = 0.0;
        int i;
        struct timeval begin, end;
        double elapsed;

        array = malloc(ALEN * sizeof(double));

        for (i=0; i<ALEN; i++) {
                array[i] = rand() % 100;
        }

        gettimeofday(&begin, NULL);
        #pragma omp parallel for reduction(+:res)
        for (i=0; i<ALEN; i++) {
                res += array[i] * array[i];
        }
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - begin.tv_sec) +
              ((end.tv_usec - begin.tv_usec)/1000000.0);

        free(array);
        printf("res %f, elapsed %f\n", res, elapsed);
        return EXIT_SUCCESS;
}

Чтобы получить обычный код (на FPU)

$ cc -Wall -pedantic -O3 30.c -o 30

Код с SSE2:

$ cc -Wall -pedantic -O3 30.c -mfpmath=sse -mmmx -msse -msse2 -o 30

SSE2 и многопоточность (OpenMP):

$ cc -Wall -pedantic -O3 30.c -mfpmath=sse -mmmx -msse -msse2 -fopenmp -o 30

Разница между однопоточным и многопоточным - «#pragma omp parallel for reduction(+:res)». У меня получается прирост производительности где-то в 2 раза (время 0.132 vs 0.057), но наверняка можно еще что-то потюнить

во первых топик «Скорость обработки массивов в разных лиспах и прочих яп» а не где удобнее делать многопоточность :) Кстати, про многопоточность, а где знатоки эрланга?

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

где-то так:

double f ( double x ) { return x * x ; }
...
sum=psum(NR_OF_WORKERS,f,array,array_size);

но наверняка можно еще что-то потюнить

double *v;
for (v=array,i=ALEN; i ; i--,v++) {
                res += (*v)*(*v);
        }

должно по идее быть быстрее..

Ох лол, у тебя даже копипасты на paste.lisp.org

во первых топик «Скорость обработки массивов в разных лиспах и прочих яп» а не где удобнее делать многопоточность :)

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

main = do
    vec <- R.now -- создаем массив
            $ R.fromUnboxed (Z :. (n::Int)) 
            $ (G.randoms g n :: (U.Vector Double))
    (r,t) <- time $ R.sumP . R.map (^2) $ vec --обрабатываем

дальше собраем с -threaded - получаем многопоточный рантайм и кол-во тредов регулируется опциями коммадной строки, собираем без -threaded получаем однопоточный рантайм.

Всё, больше никаких дополнительных действий не требуется. Т.е. данная вещь напрямую относится к обработке массивов.

Вообще скорость обработки зависит от следующих факторов:

1). структуре данных, boxed/unboxed, тут можно видеть разницу между j/R и другими языками.

2). являются ли данные в структуре вариативными или нет, т.е. нужны ли проверки тегов типа при каждой операции.

3). выделяется ли память при операциях с плавающей точкой (термин приводил dave). По результатам я не могу ответить на этот вопрос.

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

5). использование низкоуровневых инструкций типа SIMD. К сожалению, по этому пункту си есть мало где развернуться в связи с тривиальностью задачи. И все компиляторы делают сравнимый код (haskell/lisp).

6). дополнительные накладные расходы от RTS, система событий, GC...

где-то так:

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

эффективная реализация psum конечно «не пивка попить», но я же не прошу показать нутро хаскеля :)

я могу скинуть статьи или объяснить на пальцах, там всё элементарно :)

ты, это, вариант на скале давай.

Да вы что, оно же тормозить будет. Стыдно

haskell необогнан:

          lisp    j       R     R-1     c       haskell  haskell(no-force)  c-2     c-omp
3000000   0.005   0.022  0.010  0.040   0.00001 0.002     0.066             0.004   0.001
30000000  0.048   0.230  0.140  0.300   0.05    0.016     0.662             0.049   0.017
60000000  0.094   0.473  0.371  13.0    0.10    0.038     1.326             0.094   0.034
90000000  0.142   0.693  0.480  23.0    0.15    0.051     1.983A            0.141   0.060
300000000   x     x      x      x       x       x         6.705             x       x

ну тут есть J и R учитывая, что скалярные типы у явы unboxed (тавтология) всё может быть не так и плохо.

с funroll-loops обгоняет.

У Java да, если я напишу на Scala как на Java, то будет Java - может 60% от C. Это элементарно, есть способ получать Java производительность на низкоуровневых вычислениях. Но тогда даже «for» нельзя писать, только while. А если я напишут так как принятно в скале, до будет дохрена лямбд, боксинг и отстрел ног. А если не писать как на скале, то нафига ее вообще сюда приводить?

ок, довод принят.

Можно было бы бенчмарк без боксинговых типов, например обработка строк, массивов бинарных данных (когда передаются ссылки на большие сеты примитивных типов), тогда можно было бы погонять. И еще поверх параллельных коллекций или Akka, они работают поверх задротского Fork Join Pool

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

http://paste.lisp.org/display/

Made with LISP!