performance - 함수 - 하스켈 Collatz 대 속도 비교



하스켈 함수 정의 (1)

나의 첫 번째 진짜 프로그래밍 경험은 Haskell과 함께였다. 임시적인 필요를 위해 나는 배우기 쉽고 코드 작성이 쉬우 며 유지 보수가 쉬운 도구가 필요했으며 제대로 작동했다고 말할 수 있습니다.

그러나 어느 시점에서 내 업무의 규모가 훨씬 커져서 C가 더 잘 적응할 수 있다고 생각했습니다. 어쩌면 나는 [모든] 프로그래밍의 관점에서 충분히 숙련되지 못했지만, 하스켈을 C만큼 빠른 속도로 만들 수는 없었습니다. 적절한 하스켈이 비슷한 성능을 낼 수 있다고 들었지만 말입니다.

최근에, 나는 하스켈을 다시 한 번 시도 할 것이고, 계산의 측면에서 볼 때 일반적인 단순한 작업에는 여전히 좋은 반면, C의 속도와 Collatz 추측과 같은 문제를 매치시킬 수는없는 것으로 보인다. 내가 읽고:

Project Euler와의 속도 비교 : C vs Python vs. Erlang vs Haskell

GHC 최적화 : Collatz 추측

haskell을 사용한 collatz-list 구현

하지만 내가 보는 것에서는 다음과 같은 간단한 최적화 방법을 사용할 수 있습니다.

  • Integer 대신 Int64와 같은 "더 단단한"유형 선택
  • GHC 최적화를
  • 불필요한 계산이나 간단한 함수를 피하는 것과 같은 간단한 최적화 기술 사용

하스켈 코드는 여전히 방법론의면에서 볼 때 거의 큰 숫자의 C 코드와 거의 비슷하지 않습니다. C의 성능을 대단위 문제와 비교할 수있는 유일한 방법은 코드를 길고 끔찍한 모나드 지옥으로 만드는 최적화 방법을 사용하는 것인데, 이것은 하스켈 (Haskell) (그리고 나)가 그토록 가치있게 여기는 원칙에 어긋납니다.

다음은 C 버전입니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int32_t col(int64_t n);

int main(int argc, char **argv)
{
    int64_t n = atoi(argv[1]), i;
    int32_t s, max;

    for(i = 2, max = 0; i <= n; ++i)
    {
        s = col(i);
        if(s > max) max = s;
    }
    printf("%d\n", max);

    return 0;
}

int32_t col(int64_t n)
{
    int32_t s;

    for(s = 0; ; ++s)
    {
        if(n == 1) break;
        n = n % 2 ? 3 * n + 1 : n / 2;
    }

    return s;
}

그리고 Haskell 버전 :

module Main where

import System.Environment (getArgs)
import Data.Int (Int32, Int64)

main :: IO ()
main = do
    arg <- getArgs
    print $ maxCol 0 (read (head arg) :: Int64)

col :: Int64 -> Int32
col x = col' x 0

col' :: Int64 -> Int32 -> Int32
col' 1 n            = n
col' x n
    | rem x 2 == 0  = col' (quot x 2) (n + 1)
    | otherwise     = col' (3 * x + 1) (n + 1)

maxCol :: Int32 -> Int64 -> Int32
maxCol maxS 2   = maxS
maxCol maxS n
    | s > maxS  = maxCol s (n - 1)
    | otherwise = maxCol maxS (n - 1)
    where s = col n

TL : Haskell 코드는 계산이 간단한 작업에 대해서만 작성하고 유지하기가 쉽고 성능이 중요 할 때 이러한 특성을 잃지 않습니까?


Haskell 코드의 가장 큰 문제점은 C 버전이 아닌 나누는 것입니다.

예, n % 2n / 2 를 썼습니다 만, 컴파일러는 이것을 시프트와 비트 단위로 바꿉니다. GHC는 불행히도 아직 그렇게하지 못했다.

직접 대치하면

module Main where

import System.Environment (getArgs)
import Data.Int (Int32, Int64)
import Data.Bits

main :: IO ()
main = do
    arg <- getArgs
    print $ maxCol 0 (read (head arg) :: Int64)

col :: Int64 -> Int32
col x = col' x 0

col' :: Int64 -> Int32 -> Int32
col' 1 n            = n
col' x n
    | x .&. 1 == 0  = col' (x `shiftR` 1) (n + 1)
    | otherwise     = col' (3 * x + 1) (n + 1)

maxCol :: Int32 -> Int64 -> Int32
maxCol maxS 2   = maxS
maxCol maxS n
    | s > maxS  = maxCol s (n - 1)
    | otherwise = maxCol maxS (n - 1)
    where s = col n

64 비트 GHC를 사용하면 비슷한 속도를 얻을 수 있습니다 (1000000 한계에 대해 상자에 0.32s의 0.35s). LLVM 백엔드를 사용하여 컴파일하는 경우 % 2/ 2 를 비트 연산으로 대체 할 필요조차 없습니다. LLVM이이를 처리합니다 (그러나 원래의 Haskell 소스에 대해서는 느린 코드 0.4s를 생성합니다. , LLVM은 루프 최적화에서 네이티브 코드 생성기보다 나쁘지 않습니다).

32 비트 GHC를 사용하면 64 비트 정수의 기본 연산이 C 호출을 통해 구현되기 때문에 비슷한 속도는 얻지 못할 것입니다. 32 비트 시스템에서 빠른 64 비트 연산에 대한 요구가 결코 충분하지 않습니다. 그들은 primops로 구현 될; GHC에서 일하는 소수의 사람들은 자신의 시간을 다른 중요한 일들에 보냈습니다.

TL : Haskell 코드는 계산이 간단한 작업에 대해서만 작성하고 유지하기가 쉽고 성능이 중요 할 때 이러한 특성을 잃지 않습니까?

조건에 따라서. 어떤 종류의 코드에서 GHC가 어떤 종류의 코드를 생성하는지에 대한 아이디어가 있어야하며 성능상의 함정을 피해야합니다. 약간의 연습을 통해 gcc -O3의 속도를 2 배로 높이는 것은 꽤 쉽습니다.





haskell