MapReduce und SBCL multithreading

Apr 22, 2009 11:27

Это поразительно, но какой-нибудь свободной имплементации 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.

Ну вот собственно как-то так.

gc, code, garbage collector, map, multithreading, common lisp, lisp, reduce, mapreduce

Previous post Next post
Up
[]