Нещо като OpenMP...на 27 реда код

Често (особено на чашка) съм се опитвал да обяснявам на хората, с които надигаме съответната течност, колко смислен e Lisp-а и колко безмислена -- Java-та. Този пост е още един пример в подкрепа на първото.

Става въпрос за високо-производителни изчисления (HPC). Знаем, че мулти-трединга, особено в контекста на съвременните многоядрени процесори, е един от механизмите за постигане на по-добра производителност. Когато говорим конкретно за математически изчисления (а и не само), едно от нещата, които се ползват от съответното комюнити е OpenMP. За тези, които не са наясно, с две думи: вместо да занимаваме нАучните работници да мислят в термините тредове, синхронизация, race conditions и др., им даваме достатъчно проста абстракция, с която да си раз-паралелят кода, като например следното (това съм го взел от Wikipedia, признавам си):

 1  int main(int argc, char *argv[])
 2  {
 3      const int N = 100000;
 4      int i, a[N];
 5  
 6      #pragma omp parallel for
 7      for (i = 0; i < N; i++) {
 8          a[i] = 2 * i;
 9      }
10
11      return 0;
12  }

Единственото странно нещо в този код е на 6-ти ред. Въпросната прагма указва на компилатора, че следващия стейтмънт (т.е. for-а с цялото си тяло) представлява всъщност паралелен for. Това е една от т.н. worksharing constructs, основна концепция в OpenMP, чиято семантика е следната: създават се няколко паралелни треда, които изпълняват тялото на цикъла; N-те итерации на цикъла се разпределят между тях; на края има имлицитна синхронизация, така че на ред 11 тредовете пристигат заедно (ако въобще пристигат до там няколко треда, защото би могло и да приключват на ред 9).

Разбира се в OpenMP има и куп други подобни благини, разни сложнотии и възможности за финно доизпипване на как точно искаме да ни се изпълни паралелния код, но в края на краищата, моя опит показва, че в 99% от програмите, които ползват OpenMP, 99% от конструкциите са parallel for.

Очевидно OpenMP е много смислено нещо. Използва се поголовно в световен мащаб. В него са наляти много време и пари, направен е консорциум, уеб-сайт, документация, пачнати са компилатори, направени са библиотеки и въобще бая труд е хвърлен за да се направи да работи. А то работи посредством специални издания на компилаторите, напр. за да проима идея за #pragma omp ..., даден компилатор трябва да е специално създаден за това. Още веднъж ще наблегна на това, защото е важно -- не е достатъчно само да свържете към кода си някоя библиотека, за да ползвате OpenMP -- трябва ви специален компилатор, който да разбира от съответните прагми. Има издания на повечето смислени компилатори за C/C++/FORTRAN, които кльопат директивите. gcc след версия 4.3.2 (ако не се лъжа) поддържа OpenMP по подразбиране.

Сигурно вече се питате "Aми за Java има ли го?". Само от уважение към колегите от EPCC към Университета в Единбург няма да нареча JOMP "абоминация", но сериозно си го мисля. Аз не смятам да обяснявам какво точно е JOMP, защото получавам позиви само като се сетя, но ако ви влече -- прочетете си го сами. Само ще кажа, че това е research проект, с няколко нАучни публикации, екип от нАучни работници и т.н. Искам да уточня -- не са виновни колегите, виновна е нефелната Java, на която дори да се издрайфаш не можеш като хората.

Та да си дойдем на думата. Викам си "след като това е толкова полезно и след като в 98% от случаите се използва конструкцията за parallel for, не мога ли да се опитам да си реализирам един такъв на Lisp?". И така -- седнах и за 1/2 час написах това:

 1  (defparameter *default-num-threads* (or (sb-posix::getenv "NUM_THREADS") 2))
 2 
 3  (defmacro dotimes* ((var count &optional (num-threads *default-num-threads*)
 4    (result nil)) &body body)
 5    (let ((thread-list (gensym "THREAD-LIST-"))
 6 (i (gensym "I-"))
 7 (q (gensym "Q-"))
 8 (r (gensym "R-"))
 9 (s (gensym "S-"))
10 (e (gensym "E-")))
11    `(let* ((,thread-list ())
12     (%num-threads ,num-threads))
13       (multiple-value-bind (,q ,r)
14    (ceiling ,count %num-threads)
15  (dotimes (,i %num-threads)
16    (let ((%thread-id ,i) ,s ,e)
17      (declare (ignorable %thread-id))
18      (if (< ,i (+ %num-threads ,r))
19   (setf ,s (* ,i ,q) ,e (+ ,s ,q))
20   (setf ,s (+ %num-threads ,r (* ,i (1- ,q))) ,e (+ ,s (1- ,q))))
21      (push (sb-thread:make-thread
22      #'(lambda ()
23   (do ((,var ,s (1+ ,var)))
24       ((>= ,var ,e) ,result)
25     ,@body)))
26     ,thread-list))))
27       (mapcar #'(lambda (th) (sb-thread:join-thread th)) ,thread-list))))

Забележете, че става въпрос за 27 реда, от които един празен, събрани на 80 колони (както всеки сорс код следва да бъде). Имайки горното, мога да напиша това:

(let* ((n 100000)
       (a (make-array n)))
  (dotimes* (i n)
    (setf (aref a i) (* 2 i))))

което отговаря на main функцията на C програмата, дадена малко по-горе. Единственото, което съм променил спрямо стандартен Lisp е, че вместо dotimes съм написал dotimes*. Получавам същия ефект като при parallel for конструкцията на OpenMP. Е, не е като да съм направил сайт, документация, нямам борд на директорите на консорциум, нито екип от 100-200 човека, които да направят пачове на всеки известен компилатор, но пък от друга страна...не ми и трябват. В интерес на истината моите 27 реда не могат да се сравняват със софистицизма на OpenMP, но реализират 98% от usage pattern-а му. Представете си какво би могло да се направи с 270 или 2700 реда на Lisp. А за JOMP не искам и да си спомням, защото ще сънувам кошмари (наистина, прочетете описанието, за да го сравните после с 27-те реда).

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