Насколько атомными являются ГПК?

Ответ 1

Из сообщение в блоге связанный @Lambdageek, Комментарий GHC и Руководство пользователя GHC Я собираю следующее:

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

Метод, который он использует для избежания работы, заключается в замене thunks черной дырой, специальным маркером, который сообщает другим потокам (или иногда самому потоку, как это происходит при обнаружении <<loop>>), которое оценивается thunk.

Учитывая это, существует как минимум три варианта:

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

• С помощью -feager-blackholing-flag вместо этого создаются черные дыры, как только начнется оценка thunk, и в Руководстве пользователя рекомендуется это, если вы делаете много parallelism. Однако, поскольку блокировка на каждом thunk будет слишком дорогой, эти черные дыры являются более дешевыми "нетерпеливыми", которые не синхронизируются с другими потоками (хотя другие потоки все еще могут видеть их, если нет состояния гонки). Только когда потоки приостанавливаются, они превращаются в "истинные" черные дыры.

• Третий случай, о котором особенно беспокоился блог, используется для специальных функций, таких как unsafePerformIO, для которых вредно оценивать thunk более одного раза. В этом случае поток использует "истинную" черную дыру с реальной блокировкой, но создает ее немедленно, вставляя искусственную нить в паузу перед реальной оценкой.

Ответ 2

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

• Гарантированная чистота означает, что никогда не имеет значения, оценивается ли thunk дважды в терминах семантики программы. unsafePerformIO - это случай, когда это может быть проблемой, но оказывается, что unsafePerformIO следует избегать повторного запуска одного и того же действия ввода-вывода.

• Поскольку все значения - это thunks, большинство thunks оказываются довольно маленькими, поэтому иногда дублирование работы, чтобы заставить ее, не имеет большого значения с точки зрения скорости программы. Вы можете себе представить, что это дорого, чтобы дублировать, например, last [1,2..10000000], потому что все вычисление дорого. Но, разумеется, действительно самый дальний шторм просто решает другой тон, что-то вроде:

  case [1,2..10000000] of 
    [x] -> x
    (_:xs) -> last xs
    [] -> error "empty list"
  

  и если два потока дублируют работу, чтобы перевести вызов на last в использование case, это довольно дешево в великой схеме вещей.

Ответ 3

Да, иногда один и тот же thunk может быть оценен несколькими потоками. Время выполнения GHC старается минимизировать вероятность дублирования работы, поэтому на практике это редко. Пожалуйста, см. "Haskell на совместно используемом многопроцессоре" для получения информации о низком уровне, в основном в разделе "Блокировка свободного доступа". (Я бы рекомендовал документ для каждого профессионального разработчика haskell btw.)