C so sánh Haskell Collatz phỏng đoán so sánh tốc độ

Question

Trải nghiệm lập trình thực đầu tiên của tôi là với Haskell. Đối với các nhu cầu đặc biệt của tôi, tôi yêu cầu một công cụ dễ học, nhanh chóng để viết mã và đơn giản để duy trì và tôi có thể nói nó đã làm công việc độc đáo.

Tuy nhiên, tại một thời điểm quy mô nhiệm vụ của tôi trở nên lớn hơn nhiều và tôi nghĩ rằng C có thể phù hợp với họ tốt hơn và nó đã làm. Có lẽ tôi không đủ kỹ năng về lập trình [bất kỳ] nào, nhưng tôi không thể làm cho Haskell có hiệu quả về tốc độ như C, mặc dù tôi nghe nói rằng Haskell thích hợp có khả năng hoạt động tương tự. Gần đây, tôi nghĩ rằng tôi sẽ thử một số Haskell một lần nữa, và trong khi nó vẫn tuyệt vời cho nhiệm vụ đơn giản (về tính toán), nó dường như không thể phù hợp với tốc độ của C với các vấn đề như phỏng đoán Collatz. Tôi đã đọc:

Speed comparison with Project Euler: C vs Python vs Erlang vs Haskell

GHC Optimization: Collatz conjecture

collatz-list implementation using haskell

Nhưng từ những gì tôi nhìn thấy, phương pháp tối ưu hóa đơn giản, bao gồm:

• chọn loại "chặt chẽ", như Int64 thay vì của Integer
• chuyển tối ưu hóa GHC s trên
• sử dụng các kỹ thuật tối ưu hóa đơn giản như tránh tính toán không cần thiết hoặc các chức năng đơn giản

vẫn không làm cho Haskell đang thậm chí gần gần như giống hệt nhau (về mặt phương pháp luận) mã C cho số thực sự lớn. Điều duy nhất dường như làm cho hiệu suất của nó so sánh với C [đối với các vấn đề quy mô lớn] là sử dụng các phương pháp tối ưu làm cho mã trở thành một địa ngục dài, khủng khiếp, đi ngược lại các nguyên tắc mà Haskell (và tôi) đánh giá rất nhiều.

Dưới đây là phiên bản 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; 
} 

và phiên bản 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; DR: Là mã Haskell nhanh chóng để viết và đơn giản để duy trì chỉ cho các nhiệm vụ tính toán đơn giản và mất này đặc trưng khi hiệu suất là rất quan trọng?

Answer 1

Vấn đề lớn với mã Haskell của bạn là bạn đang chia, mà bạn không có trong phiên bản C.

Có, bạn đã viết n % 2 và n/2, nhưng trình biên dịch thay thế bằng ca và bitwise và. GHC rất tiếc là chưa được dạy để làm điều đó.

Nếu bạn làm việc thay cho mình

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 

với 64-bit GHC bạn sẽ có được tốc độ tương đương (0.35s vs C 0.32s trên hộp của tôi cho một giới hạn của 1000000). Nếu bạn biên dịch bằng backend LLVM, bạn thậm chí không cần phải thay thế % 2 và / 2 với các hoạt động bitwise, LLVM thực hiện điều đó cho bạn (nhưng nó tạo mã chậm hơn, 0.4s, cho nguồn Haskell ban đầu của bạn, đáng ngạc nhiên - thông thường, LLVM không tệ hơn trình tạo mã gốc ở tối ưu hóa vòng lặp).

Với GHC 32 bit, bạn sẽ không nhận được tốc độ tương đương, vì các hoạt động nguyên thủy trên số nguyên 64 bit được thực hiện thông qua các cuộc gọi C - không bao giờ đủ nhu cầu cho các hoạt động 64 bit nhanh trên 32 -bit hệ thống cho họ được thực hiện như primops; vài người làm việc trên GHC dành thời gian làm những việc khác, quan trọng hơn.

TL; DR: Mã Haskell có thể ghi nhanh và đơn giản chỉ để duy trì các tác vụ đơn giản tính toán và mất đặc tính này khi hiệu suất là rất quan trọng?

Điều đó tùy thuộc. Bạn phải có một số ý tưởng về loại mã GHC sinh ra từ loại đầu vào nào, và bạn phải tránh một số bẫy hiệu suất. Với một chút thực hành, nó là khá dễ dàng để có được trong vòng nói 2 × tốc độ của gcc -O3 cho các nhiệm vụ như vậy.