swizard (swizard) wrote,
swizard
swizard

Category:
  • Location:
  • Music:

MapReduce und SBCL multithreading

Это поразительно, но какой-нибудь свободной имплементации MapReduce для CL я не нашел :) В гугле триллион статей, и все они начинаются словами, мол, map и reduce -- это из лиспа, но мы сейчас все заимплементим вот-на-таком-языке.

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

Сразу настроился сделать аккуратно и по-уму, чтобы получить возможность сразу использовать в бою. Посему пошел по следующему плану:

1. Пул тредов
2. По-возможности без мьютексов, где возможно заменить блокировки на compare-and-swap.
3. Не заморачиваться портабельностью, вместо этого вылизать под sbcl.
4. Интерфейс оставить такой же, как и у mapcar.
5. Поддержать рекурсивные вызовы, чтоб не воткнулось где-нибудь на вечной блокироке.

Внезапно провозился заметно больше чем ожидал, но справился:

CL-PMAP> (pmap #'+ '(1 2 3) '(4 5 6))
(5 7 9)


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

Собственно, вот так выглядит ожидаемый эффект:

CL-PMAP> (progn (defvar *long-list* (iter (for i from 0 below 4096) (collect (+ i 262144)))) nil)
NIL
CL-PMAP> (defun inf (n) 
           (locally 
               (declare (optimize (speed 3) (safety 0)))
             (iter (declare (iterate:declare-variables)) 
                   (for (the fixnum i) from 1 below (the fixnum (+ (the fixnum n) 2)))
                   (summing (the double-float (/ 1.0d0 i)) into (the double-float r))
                   (finally (return r)))))
STYLE-WARNING: redefining INF in DEFUN
INF
CL-PMAP> (set-max-workers *pmap-pool* 0)
0
CL-PMAP> (time (progn (pmap #'inf *long-list*) nil))
Evaluation took:
  14.009 seconds of real time
  13.997668 seconds of total run time (13.997668 user, 0.000000 system)
  99.92% CPU
  33,623,081,973 processor cycles
  332,272 bytes consed
  
NIL
CL-PMAP> (set-max-workers *pmap-pool* 1)
1
CL-PMAP> (time (progn (pmap #'inf *long-list*) nil))
Evaluation took:
  7.003 seconds of real time
  13.990248 seconds of total run time (13.990248 user, 0.000000 system)
  199.77% CPU
  16,807,298,787 processor cycles
  331,488 bytes consed
  
NIL
CL-PMAP> (set-max-workers *pmap-pool* 3)
3
CL-PMAP> (time (progn (pmap #'inf *long-list*) nil))
Evaluation took:
  3.800 seconds of real time
  13.996116 seconds of total run time (13.996116 user, 0.000000 system)
  368.32% CPU
  9,121,423,707 processor cycles
  323,336 bytes consed
  
NIL

Кратное пояснение бенчмарка следующее: делаем какую-нибудь числодробилку (inf --я взял вычисление суммы 1 + 1/2 + 1/3 + ... + 1/N), и запускаем эту функцию на длинном списке (у меня это *long-list*, содержащий числа от 262 144 до 266 240).

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

Неприятности вылезают, как только в дело вступает garbage collector :( Уберем генерацию эффективного кода из inf, чтобы это проверить:

CL-PMAP> (defun inf (n) 
           (iter (for i from 1 below (+ n 2))
                 (summing (/ 1.0d0 i) into r)
                 (finally (return r))))
STYLE-WARNING: redefining INF in DEFUN
INF
CL-PMAP> (time (inf 16384))
Evaluation took:
  0.001 seconds of real time
  0.001040 seconds of total run time (0.001040 user, 0.000000 system)
  100.00% CPU
  2,594,790 processor cycles
  786,424 bytes consed
  
10.28136774143965d0

Теперь inf начал генерить кучу мусора. Взглянем на разницу в производительности с одним и четырьмя рабочими тредами:

CL-PMAP> (set-max-workers *pmap-pool* 0)
0
CL-PMAP> (time (progn (pmap #'inf *long-list*) nil))
Evaluation took:
  85.992 seconds of real time
  86.657988 seconds of total run time (84.989211 user, 1.668777 system)
  [ Run times consist of 16.028 seconds GC time, and 70.630 seconds non-GC time. ]
  100.77% CPU
  206,388,069,282 processor cycles
  51,942,821,928 bytes consed
  
NIL
CL-PMAP> (set-max-workers *pmap-pool* 3)
3
CL-PMAP> (time (progn (pmap #'inf *long-list*) nil))
Evaluation took:
  96.941 seconds of real time
  153.749776 seconds of total run time (138.403300 user, 15.346476 system)
  [ Run times consist of 48.947 seconds GC time, and 104.803 seconds non-GC time. ]
  158.60% CPU
  232,665,886,368 processor cycles
  38,024,089,176 bytes consed
  
NIL

Стало не только страшно тормознее, но еще и распараллеленый map о четырех тредах внезапно огорчил. На самом деле выигрыш от pmap в таких случаях все равно часто бывает, но он порядка 15-50%, но никак не 400%, как на числодробилке.

Отсюда первый и основной вывод: не трогать без крайней нужды GC!.

В принципе, это неприятно, но не фатально. В числодробнях можно сурово оптимизировать ассемблер, в обходах структур данных память в принципе и не нужна, а для всяких там стеков / хэшей можно держать cons-pool и преаллоцировать что-то заранее.

Второй момент. Даже при нулевом потреблении памяти можно нарваться на нечто вроде GIANT-LOCK'a, ну или я даже не знаю как это назвать :) Проиллюстрирую:

CL-PMAP> (defun rnd-test (n) (iter (for i from 0 below n) (summing (random 10))))
RND-TEST

Казалось бы, обычная сумма N рандомных чисел от 0 до 9. Но о чудо:

CL-PMAP> (time (progn (pmap #'rnd-test (make-list 100 :initial-element 1000000)) nil))
Evaluation took:
  2.211 seconds of real time
  2.208648 seconds of total run time (2.208648 user, 0.000000 system)
  99.91% CPU
  5,305,283,019 processor cycles
  5,112 bytes consed
  
NIL
CL-PMAP> (set-max-workers *pmap-pool* 1)
1
CL-PMAP> (time (progn (pmap #'rnd-test (make-list 100 :initial-element 1000000)) nil))
Evaluation took:
  4.980 seconds of real time
  9.938369 seconds of total run time (9.938369 user, 0.000000 system)
  199.56% CPU
  11,951,572,914 processor cycles
  8,192 bytes consed
  
NIL
CL-PMAP> (set-max-workers *pmap-pool* 2)
2
CL-PMAP> (time (progn (pmap #'rnd-test (make-list 100 :initial-element 1000000)) nil))
Evaluation took:
  5.418 seconds of real time
  15.952849 seconds of total run time (15.952849 user, 0.000000 system)
  294.44% CPU
  13,003,251,318 processor cycles
  12,896 bytes consed
  
NIL
CL-PMAP> (set-max-workers *pmap-pool* 3)
3
CL-PMAP> (time (progn (pmap #'rnd-test (make-list 100 :initial-element 1000000)) nil))
Evaluation took:
  6.049 seconds of real time
  22.275797 seconds of total run time (22.275797 user, 0.000000 system)
  368.26% CPU
  14,517,357,174 processor cycles
  12,992 bytes consed
  
NIL

Это вообще черт знает что: с увеличением количества воркеров процесс равномерно замедляется, при этом процессоры треды жрут дай Бог каждому. Это даже не giant-lock, а какая-то ересь.

Поэтому вывод второй: даже если с виду все хорошо, иногда получается неведомая хуйня.

Ну и дальше кое-чего по-мелочи.

1. Вернемся к имплементации inf. Если типизацию double-float сменить на single-float, то он начинает жрать память, как ты его не насилуй. Вот черт знает что такое, в ассемблерный листинг я не воткнул.

2. pmap можно очень удобно использовать и со стороны заднего прохода:

CL-PMAP> (pmap #'funcall (list 
                          (lambda () (inf 16777216))
                          (lambda () (rnd-test 16777216))
                          (lambda () (+ 1 2))))
(17.212748087744874d0 75495102 3)

Это будет что-то типа OpenMP, только удобней: параллельное выполнение thunk'ов на заданном пуле тредов и получение результатов в виде аккуратного списка, на который можно с чистой совестью натравить reduce.

Ну вот собственно как-то так.
Tags: code, common lisp, garbage collector, gc, lisp, map, mapreduce, multithreading, reduce
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 14 comments