Почему в Haskell нет неявного parallelism?

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

Рассмотрим этот тривиальный пример:

f = do
  a <- Just 1
  b <- Just $ Just 2
  -- ^ The above line does not utilize an `a` variable, so it can be safely
  -- executed in parallel with the preceding line
  c <- b
  -- ^ The above line references a `b` variable, so it can only be executed
  -- sequentially after it
  return (a, c)
  -- On the exit from a monad scope we wait for all computations to finish and 
  -- gather the results

Схематически план выполнения может быть описан как:

               do
                |
      +---------+---------+
      |                   |
  a <- Just 1      b <- Just $ Just 2
      |                   |
      |                 c <- b
      |                   |
      +---------+---------+
                |
           return (a, c)

Почему в компиляторе нет такой функциональности с флагом или прагмой? Каковы практические причины?

Ответ 1

Это долго изученная тема. Хотя вы можете неявно получить parallelism в коде Haskell, проблема в том, что для текущего оборудования слишком много parallelism, при слишком тонком зерне.

Итак, вы в конечном итоге тратите усилия на ведение бухгалтерского учета, не ускоряя работу.

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

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

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

Для фона см. http://research.microsoft.com/en-us/um/people/tharris/papers/2007-fdip.pdf, где они вводят автоматический подход к вставке par в произвольные программы Haskell.

Ответ 2

Хотя ваш кодовый блок может быть не лучшим примером из-за неявных данных зависимость между a и b, стоит отметить, что эти два привязки коммутируют в том, что

f = do
  a <- Just 1
  b <- Just $ Just 2
  ...

даст те же результаты

f = do
  b <- Just $ Just 2
  a <- Just 1
  ...

поэтому это все равно можно распараллеливать спекулятивно. Стоит отметить, что это не должно иметь ничего общего с монадами. Мы могли бы, например, оценить все независимые выражения в let -блоке параллельно или мы могли бы ввести версия let, которая сделает это. lparallel library для Common Lisp делает это.

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

Тогда не всегда быстрее бросать больше ядер в проблему. Даже когда явно распараллеливая проблему с множеством доступных библиотек Haskell, вы часто не увидите большого ускорения, просто оценивая выражения параллельно из-за интенсивного распределения памяти и использования, а также напряжения, которое это накладывает на мусор сборщиком и кешем процессора. В конечном итоге вам нужен хороший компактный макет памяти и чтобы интеллектуально обрабатывать ваши данные. Имея 16 потоков, пересекающих связанные списки, просто узкое место у вас на шине памяти и на самом деле может замедлить работу.

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

Ответ 3

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

Тем не менее, вы по-прежнему можете "внезапно использовать все эти ядра, не беспокоясь о потоках, тупиках и условиях гонки". Это не автоматическое; вам просто нужно дать компилятору некоторые подсказки о том, где это сделать!:-D

Ответ 4

Одна из причин заключается в том, что Haskell не является строгим, и по умолчанию он ничего не оценивает. В общем случае компилятор не знает, что вычисление a и b завершается, поэтому попытка вычислить это будет пустой тратой ресурсов:

x :: Maybe ([Int], [Int])
x = Just undefined
y :: Maybe ([Int], [Int])
y = Just (undefined, undefined)
z :: Maybe ([Int], [Int])
z = Just ([0], [1..])
a :: Maybe ([Int], [Int])
a = undefined
b :: Maybe ([Int], [Int])
b = Just ([0], map fib [0..])
    where fib 0 = 1
          fib 1 = 1
          fib n = fib (n - 1) + fib (n - 2)

Рассмотрим его для следующих функций

main1 x = case x of
              Just _ -> putStrLn "Just"
              Nothing -> putStrLn "Nothing"

(a, b) часть не нуждается в оценке. Как только вы получите x = Just _, вы можете перейти к ветки - следовательно, он будет работать для всех значений, но a

main2 x = case x of
              Just (_, _) -> putStrLn "Just"
              Nothing -> putStrLn "Nothing"

Эта функция обеспечивает оценку кортежа. Следовательно, x завершается с ошибкой, пока остальная работа будет работать.

main3 x = case x of
              Just (a, b) -> print a >> print b
              Nothing -> putStrLn "Nothing"

Эта функция сначала напечатает первый список, а затем второй. Он будет работать для z (что приведет к печати бесконечного потока чисел, но Haskell может справиться с ним). b в конечном итоге закончится.

Теперь, в общем, вы не знаете, заканчивается ли вычисление или нет, и сколько ресурсов он будет потреблять. Бесконечные списки отлично подходят для Haskell:

main = maybe (return ()) (print . take 5 . snd) b -- Prints first 5 Fibbonacci numbers

Следовательно, нереста потоков для оценки выражения в Haskell может попытаться оценить то, что не предназначено для полной оценки - скажем, список всех простых чисел, но программисты используют как часть структуры. Вышеприведенные примеры очень просты, и вы можете утверждать, что компилятор мог их заметить, однако это вообще невозможно из-за проблемы с Halting (вы не можете писать программу, которая принимает произвольную программу и ее вход и проверяет, завершается ли она), поэтому она не является безопасная оптимизация.

Кроме того, о чем говорили другие ответы, трудно предсказать, стоит ли накладные расходы на дополнительную нить. Несмотря на то, что GHC не порождает новые потоки для искр, используя зеленую нить (с фиксированным количеством потоков ядра - за исключением нескольких исключений), вам все равно нужно переместить данные из одного ядра в другое и синхронизировать между ними, что может быть довольно дорогостоящим.

Однако Haskell действительно управляет распараллеливанием, не нарушая чистоту языка par и аналогичные функции.

Ответ 5

На самом деле была такая попытка, но не на общем аппаратном обеспечении из-за низкого количества ядер. Проект называется Reduceron. Он запускает код Haskell с высоким уровнем parallelism. Если бы он был выпущен как 2-ГГц ASIC-ядро, у нас был бы серьезный прорыв в скорости выполнения Haskell.