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

Потому что за такое малое время влияние самой ОС внесет серьезные искажения на результат. Обработчики прерываний, переключения на другие процессы с потерей данных из кеша цпу и пр.
Еще хочу добавить: попробуйте увеличить размер массива, чтобы данные в кеш не вместились целиком. Картина может значительно поменяться.

nerdogeek
()

Разве умножение/сложение плавучки не занимает разное количество тактов в зависимости от значений операндов? Если уж сравнивать, то с одинаковым генератором и сидом, не?

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

Это все фигня, когда одна реализация на плавающей арифметике работает с боксингом (racket, ocaml, python), а другая может пахать совсем без него (sbcl, lispworks). Только тут надо заметить, что лисп далеко не всегда умеет обходиться без боксинга. Так совпало, что некоторые реализации в этой конкретной задаче могут, но эта задача непоказательна, прямо скажем так и не будем обманывать. В общем случае, лисп тоже не может обходиться без боксинга, или надо так проектировать вычисления, чтобы мог. А такты, влияние ОС - это тут не главное.

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

Этот тест не катит. Нужен рандомный доступ к элементам массива и побольше данных в этом массиве. Можно например накатать heapsort для 100-1000мб массива. Тогда можно будет ясно увидеть различия.

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

Вроде хардверные FPU инструкции сложения/умножения занимаются всегда определенное количество времени.

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

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

Убил!!!!!!!!!!!!!!

- В резюме Вы написали что печатаете со скоростью 2000 знаков в минуту.
- Да.
- И что? Получается?
- Ой! Такая чушь получается!

ЗЫ. Может в цитатник?

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

Если более точно, то форма defparameter позволяет менять значение после каждой перекомпиляции. Необязательно закрывать редактор и заканчивать интерактивный сеанс работы с лисп-машиной. Есть еще defvar, который ведет себя по иному - его значение уже не меняется после перекомпиляции.

В качестве проверки можно поиграться с таким кодом (скомпилировал - проверил - проверил - перекомпилировал - проверил - и т.д.):

(defparameter *x* (random 1000))

(defvar *y* (random 1000))
dave ★★★★★
()
Ответ на: комментарий от nerdogeek

Еще раз повторяю, что настоящий тест проверяет, есть «consing» (выделение памяти из кучи) при плавающей арифметике или нет. Фактически массивы тут мало причем. Возможно, что у автора теста были совсем другие виды, и это получилось у него невзначай. Ну что же, бывает. А тесты можно разные сочинить, и они будут разные вещи проверять.

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

Фактически массивы тут мало причем

Это точно. Просто повезло что в SBCL в этом случае нет boxing'a. В ECL, например, есть.

Darkman ★★★
()
dron@nix:~$ cat ./test.c 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

  long int mass[3000000];

  int main()
  {
    srand(time(NULL));

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

    return 0;
  }
dron@nix:~$ gcc -std=c99 ./test.c
dron@nix:~$ time ./a.out 

real	0m0.154s
user	0m0.124s
sys	0m0.028s
dron@nix:~$ 

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

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

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

когда одна реализация на плавающей арифметике работает с боксингом (racket

unsafe операции в racket без боксинга работают.

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

Ой блин точно, пардон, про квадраты не дочитал.

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

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

Надеюсь, ты не будешь это отрицать?

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

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

11 лет назад OCaml под виндой на числодробилках был быстрее, чем VC7: http://www.balancer.ru/tech/forum/2002/10/t20331--meryane-pi-e-popugayami-bys...

Но только под Windows. Под Linux Ocaml у меня всегда какой-то тормозной был, даже тогда :-/

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

я просто оставлю это

----

Мощное расширение для параллельной работы с большими данными в R.

pbdDMAT сохраняет привычный синтаксис высокоуровневых операторов R, одновременно позволяя запускать код на выполнение параллельно. Кроме этого реализован процесс хранения в каждом выполняемом потоке вычисления только порции данных действительно необходимой для вычислений. Это приводит в результате к преодолению прежней ситуации, когда каждая из нитей получала свою полную копию всех данных. Так же этот подход преодолевает архитектурные ограничения на размер данных, поскольку теперь ограничение на длину вектора в R касается только порции данных приходящейся на один поток вычислений. Увеличиваем число потоков -> растет доступный объем адресуемой памяти!

Например «одним куском» R переварит матрицу 46, 340 × 46, 340, что составит 15.99934 Гб. Авторы в ходе тестирования обработали матрицу 100, 000 × 100, 000 общим объемом в 74.50581 Гб.

Для комфортной работы с терабайтом данных вам понадобится 1024 вычислительных узла. А для пентабайта понадобится 100,000 ядер в кластере. :)

основной пакет с высокоуровневыми функциями

http://cran.r-project.org/web/packages/pbdDMAT/index.html

примеры

http://cran.r-project.org/web/packages/pbdDEMO/index.html

чтение больших данных

http://cran.r-project.org/web/packages/pbdNCDF4/index.html

----

а ты того, выдыхай :)

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

Вообще, впечатляет, да.

library(Rcpp)
library(inline)

xorig <- c(1, -2, 3, -4, 5, -6, 7)

code <- '
    Rcpp::NumericVector x(xs);
    Rcpp::NumericVector xa = sapply( x, ::fabs );
    return(xa);
    '

xabs <- cxxfunction(signature(xs="numeric"),
                    plugin="Rcpp",
                    body=code)

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

читал, дальше, что я сказал, что это хорошо, но это есть везде. Или ты русский текст осилить не можешь?

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

ты всё ещё считаешь, что рантайм R от этого изменился?

Пожалуйста не путай библиотеки, и реализацию рантайма языка.

Наличие аналогичных библиотек возможно для всех языков и существует во многих, это не rocket science.

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

Интересный опыт. Судя по вашей переписке, у окамла получались более дешевые вызовы функций, чем у си++. А у вас были только целочисленные тесты или вещественную арифметику тоже меряли?

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

я не знаю ни один из диалектов лиспа. Но тут на лоре приводили пример FFI в лиспе, выглядело очень просто.

В haskell есть c--, есть вызов кода из FFI библиотек, и primops для инлайна си кода прямо в генерируемую программу без каких либо доп расходов.

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

Хаскель компилируется в сишку, поэтому такие вещи там возможны.

У SBCL свой оптимизирующий компилятор в ISA, поэтому сишка ему вообще не упала.

Про инлайнинг сишки в CL я слышал только у ECL, который тоже компилится в Си.

(defun sample (x)
  (ffi:c-inline (n1 n2) (:int :int) (values :int :int) "{
    int n1 = #0, n2 = #1, out1 = 0, out2 = 1;
    while (n1 <= n2) {
      out1 += n1;
      out2 *= n1;
      n1++;
    }
    @(return 0)= out1;
    @(return 1)= out2;
    }"
   :side-effects nil))

Есть реализации scheme, которые компилятся в Си, например chicken, там есть директива inline для этих вещей. http://wiki.call-cc.org/eggref/4/inline

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

У SBCL свой оптимизирующий компилятор в ISA, поэтому сишка ему вообще не упала.

пока, что ручная сишка написанная экспертом в проблемной области+си рвёт все оптимизирующие компиляторы. Исключения только в generative compilers/optimizers типа FFTW/ATLAS, которые генерят оптимальный код зависимости от платформы, и сложных случаев, где GC может спасти от фрагментации, что в случае ручного кода будет очень сложно. Поэтому возможность включать как просто ffi, так и FFI в виде inline-c это плюс.

Кстати, по этому примеру мне инетерсно, а есть ли разница в c-inline или в том, что ты соберёшь объектник gcc, подключишь его и будешь вызывать «sample» или сделаешь как в примере?

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

есть ли разница в c-inline или в том, что ты соберёшь объектник gcc, подключишь его и будешь вызывать «sample» или сделаешь как в примере

Если именно объектник, то нет, но подключать придётся только к ECL. А если через FFI, то добавь вызов dlopen.

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

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

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

Есть реализации scheme, которые компилятся в Си

Можно и на Racket.

#lang planet jaymccarthy/superc

@c{
#include <stdio.h>
 
int main(void)
{
    int x = 0;
    printf("hello, world\n");
    scanf("%d", &x);
    printf("you typed: %d\n", x);
    return 1;
}
}

(define main (get-ffi-obj-from-this 'main (_fun -> _int)))

(printf "The C program returned: ~a~n"
        (main))
monk ★★★★★
()
Ответ на: комментарий от qnikst

какие в пень «библиотеки»?! приводи _конкретные_ примеры таких «библиотек» сказочник ты наш.

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

2) никаких указанных тобой проблем в рантайме у R нет и в помине.

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

pbdDMAT это библиотека.

тест на умение читать:

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

где я писал про «наворачивание цикликов»?

2) никаких указанных тобой проблем в рантайме у R нет и в помине.

какие проблемы рантайма R я указал?

Пожалуйста, хватит спорить с альтернативной реальностью в твоей голове, или делай это не в ответах на мои сообщения, я тут ни при чем.

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

Нет, только целые. Я же поверхностно оценивал тогда. А скоро числодробилками совсем перестал тестировать.

KRoN73 ★★★★★
()
Ответ на: комментарий от psv1967
> ddd<-runif(3000000)
> system.time(sum(ddd^2))
   user  system elapsed 
  0.040   0.000   0.036 
> system.time(sum(ddd^2))
   user  system elapsed 
  0.010   0.000   0.018 
> system.time(sum(ddd^2))
   user  system elapsed 
  0.010   0.000   0.011 
> system.time(sum(ddd^2))
   user  system elapsed 
   0.01    0.00    0.01 
> system.time(sum(ddd^2))
   user  system elapsed 
  0.010   0.000   0.011 
> system.time(sum(ddd^2))
   user  system elapsed 
   0.01    0.00    0.01 

про скорость: это в 1.5 раз медленнее, программа на haskell, которая к тому же загружается и генерирует случайную последовательнотс в этом же замере. Кстати, R как-то смешно кеширует(?) результат, каждый второй запуск в 10 раз медленнее. Объяснишь почему?

qnikst ★★★★★
()

Числа от нуля до единицы подойдут?

    rand =: ? 3000000 # 0
    10 (6!:2) '([: +/ *:) rand'
0.0357144

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

А, ну, понятно. Просто я читал, что в окамле применяются тегированные указатели для представления объектов, примерно как в лиспе. При таком подходе максимум, чего можно добиться, это сделать так, чтобы в окамле было не хуже, чем в лиспе, но тут нужен такой же умный компилятор уровня sbcl, чтобы при компиляции тела функции можно было временно отойти от тегированного представления и использовать оптимизации, работая с вещественными числами напрямую, как поступают хорошие реализации лиспа. А другой путь для статически типизированного языка - отказаться от тегированного представления совсем.

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

блин.. я видел твой пример, но писать про него до этого было не интересно, т.к. практического интереса он не представляет.

После того, как тебе не понравилась моя фраза про скорость, я запустил твой код на своей машине, чтобы сравнить его с временем работы других программ тут же: 0.005 у лиспа (сама функция, аналогично R) и 0.07 haskell (запуск программы, загрузка so, генерация случайных чисел), чтобы тебе это продемонстрировать.

Это не особо относится к runtime R, только представление данных. А runtime R не относится к нужности и полезности R.

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

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

блин.. я видел твой пример, но писать про него до этого было не интересно, т.к. практического интереса он не представляет.

но зачем открой секрет ты его перепостил? :)

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

перечитывай мой пост до тех пор пока не найдешь там ответ на свой вопрос, он там есть.

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

lenovo thinkpad T420i:

processor	: 0
vendor_id	: GenuineIntel
cpu family	: 6
model		: 42
model name	: Intel(R) Core(TM) i3-2310M CPU @ 2.10GHz
stepping	: 7
microcode	: 0x15
cpu MHz		: 2100.000
cache size	: 3072 KB
physical id	: 0
siblings	: 4
core id		: 0
cpu cores	: 2
apicid		: 0
initial apicid	: 0
fpu		: yes
fpu_exception	: yes
cpuid level	: 13
wp		: yes
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer xsave avx lahf_lm arat epb xsaveopt pln pts dtherm tpr_shadow vnmi flexpriority ept vpid
bogomips	: 4186.27
clflush size	: 64
cache_alignment	: 64
address sizes	: 36 bits physical, 48 bits virtual
power management:
...

таких 4шт.

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

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

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