Haskell에 암시 적 병렬성이없는 이유는 무엇입니까?

Haskell에 암시 적 병렬성이없는 이유는 무엇입니까?

---

Haskell은 기능적이고 순수하기 때문에 기본적으로 컴파일러가 암시 적 병렬 처리 를 처리하는 데 필요한 모든 속성을 가지고 있습니다 .

이 사소한 예를 고려하십시오.

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)

플래그 또는 pragma를 사용하여 컴파일러에 구현 된 이러한 기능이없는 이유는 무엇입니까? 실제적인 이유는 무엇입니까?

---

이것은 오랫동안 연구 된 주제입니다. Haskell 코드에서 암시 적으로 병렬 처리를 유도 할 수 있지만 문제는 현재 하드웨어에 대해 너무 세밀하게 병렬 처리가 너무 많다는 것입니다.

그래서 당신은 일을 더 빨리 운영하는 것이 아니라 회계에 노력을 기울이게됩니다.

무한한 병렬 하드웨어가 없기 때문에 올바른 세분화를 선택하는 것이 전부입니다. 너무 거칠고 유휴 프로세서가 있고 너무 많고 오버 헤드가 허용되지 않을 것입니다.

우리가 가지고있는 것은 수천 또는 수백만 개의 병렬 작업을 생성하는 데 적합한 (스파크)보다 거친 병렬 처리 (스파크)이며, 이는 오늘날 일반적으로 사용 가능한 몇 개의 코어에 매핑됩니다.

일부 하위 집합 (예 : 어레이 처리)의 경우 비용이 적게 드는 모델이 포함 된 완전 자동 병렬화 라이브러리가 있습니다.

이에 대한 배경 지식은 http://research.microsoft.com/en-us/um/people/tharris/papers/2007-fdip.pdf를 참조하십시오. 여기 par에서 임의의 Haskell 프로그램에 자동으로 삽입하는 방법을 소개 합니다.

---

코드 블록이 a와 사이의 암시 적 데이터 종속성으로 인해 최상의 예가 아닐 수 있지만 b이 두 바인딩이

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

같은 결과를 줄 것입니다

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

그래서 이것은 여전히 ​​추측적인 방식으로 병렬화 될 수 있습니다. 이것은 모나드와 관련이있을 필요가 없다는 점에 주목할 가치가 있습니다. 예를 들어 let-블록의 모든 독립 표현식 을 병렬로 평가하거나 그렇게 할 수있는 버전을 도입 let할 수 있습니다. lparallel 라이브러리 커먼 리스프에 대해이 작업을 수행합니다.

Now, I am by no means an expert on the subject, but this is my understanding of the problem. A major stumbling block is determining when it is advantageous to parallelize the evaluation of multiple expressions. There is overhead associated with starting the separate threads for evaluation, and, as your example shows, it may result in wasted work. Some expressions may be too small to make parallel evaluation worth the overhead. As I understand it, coming up will a fully accurate metric of the cost of an expression would amount to solving the halting problem, so you are relegated to using an heuristic approach to determining what to evaluate in parallel.

Then it is not always faster to throw more cores at a problem. Even when explicitly parallelizing a problem with the many Haskell libraries available, you will often not see much speedup just by evaluating expressions in parallel due to heavy memory allocation and usage and the strain this puts on the garbage collector and CPU cache. You end up needing a nice compact memory layout and to traverse your data intelligently. Having 16 threads traverse linked lists will just bottleneck you at your memory bus and could actually make things slower.

At the very least, what expressions can be effectively parallelized is something that is not obvious to many programmers (at least it isn't to this one), so getting a compiler to do it effectively is non-trivial.

---

Short answer: Sometimes running stuff in parallel turns out to be slower, not faster. And figuring out when it is and when it isn't a good idea is an unsolved research problem.

However, you still can be "suddenly utilizing all those cores without ever bothering with threads, deadlocks and race conditions". It's not automatic; you just need to give the compiler some hints about where to do it! :-D

---

One of the reason is because Haskell is non-strict and it does not evaluate anything by default. In general the compiler does not know that computation of a and b terminates hence trying to compute it would be waste of resources:

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)

Consider it for the following functions

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

(a, b) part does not need to be evaluated. As soon as you get that x = Just _ you can proceed to branch - hence it will work for all values but a

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

This function enforces evaluation of tuple. Hence x will terminate with error while rest will work.

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

This function will first print first list and then second. It will work for z (resulting in printing infinite stream of numbers but Haskell can deal with it). b will eventually run out of memory.

Now in general you don't know if computation terminates or not and how many resources it will consume. Infinite lists are perfectly fine in Haskell:

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

Hence spawning threads to evaluate expression in Haskell might try to evaluate something which is not meant to be evaluated fully - say list of all primes - yet programmers use as part of structure. The above examples are very simple and you may argue that compiler could notice them - however it is not possible in general due to Halting problem (you cannot write program which takes arbitrary program and its input and check if it terminates) - therefore it is not safe optimization.

In addition - which was mentioned by other answers - it is hard to predict whether the overhead of additional thread are worth engaging. Even though GHC doesn't spawn new threads for sparks using green threading (with fixed number of kernel threads - setting aside a few exceptions) you still need to move data from one core to another and synchronize between them which can be quite costly.

However Haskell do have guided parallelization without breaking the purity of language by par and similar functions.

---

Actually there was such attempt but not on common hardware due to the low available quantity of cores. The project is called Reduceron. It runs Haskell code with a high level of parallelism. In case it was ever released as a proper 2 GHz ASIC core, we'd have a serious breakthrough in Haskell execution speed.

ReferenceURL : https://stackoverflow.com/questions/15005670/why-is-there-no-implicit-parallelism-in-haskell