Простой π (x) в Haskell vs С++

Я изучаю Хаскелл. Я заинтересован в том, чтобы использовать его для экспериментов с персональным компьютером. Прямо сейчас, я пытаюсь понять, как быстро Haskell может получить. Многие утверждают, что они связаны с C (++), и если это правда, я был бы очень доволен (я должен отметить, что я буду использовать Haskell, быстро или быстро, но быстро все-таки хорошо).

Моя тестовая программа реализует π (x) с помощью очень простого алгоритма: числа Primes добавляют к результату 1. Правые числа не имеют целочисленных делителей между 1 и √x. Это не битва алгоритмов, это чисто для производительности компилятора.

Haskell, кажется, примерно на 6x медленнее на моем компьютере, что хорошо (все же на 100 раз быстрее, чем чистый Python), но это может быть только потому, что я новичок Haskell.

Теперь, мой вопрос: Как, не изменяя алгоритм, могу ли я оптимизировать реализацию Haskell? Действительно ли Haskell по соотношению производительности с C?

Вот мой код Haskell:

import System.Environment

-- a simple integer square root
isqrt :: Int -> Int
isqrt = floor . sqrt . fromIntegral

-- primality test        
prime :: Int -> Bool
prime x = null [x | q <- [3, 5..isqrt x], rem x q == 0]

main = do
  n <- fmap (read . head) getArgs
  print $ length $ filter prime (2:[3, 5..n])

Вот мой код C++:

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

bool isPrime(int);

int main(int argc, char* argv[]) {
    int primes = 10000, count = 0;
    if (argc > 1) {
        primes = atoi(argv[1]);
    }
    if (isPrime(2)) {
        count++;
    }
    for (int i = 3; i <= primes; i+=2) {
        if (isPrime(i)){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

bool isPrime(int x){
    for (int i = 2; i <= floor(sqrt(x)); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

Ответы

Ответ 1

Ваша версия Haskell создает ленивый список в prime только для проверки, является ли он нулевым. Кажется, это действительно бутылочная шее. Следующая версия работает так же быстро, как и версия С++ на моей машине:

prime :: Int -> Bool
prime x = go 3
  where
    go q | q <= isqrt x = if rem x q == 0 then False else go (q+2)
    go _  = True

3.31s при компиляции с -O2 против 3.18s для С++ с gcc 4.8 и -O3 для n = 5000000.

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

Компилирование и запуск с помощью

$ ghc --make primes.hs -O2 -prof -auto-all -fforce-recomp && ./primes 5000000 +RTS -p

дает

# primes.prof
  Thu Feb 20 00:49 2014 Time and Allocation Profiling Report  (Final)

     primes +RTS -p -RTS 5000000

  total time  =        5.71 secs   (5710 ticks @ 1000 us, 1 processor)
  total alloc = 259,580,976 bytes  (excludes profiling overheads)

COST CENTRE MODULE  %time %alloc

prime.go    Main     96.4    0.0
main        Main      2.0   84.6
isqrt       Main      0.9   15.4

                                                      individual     inherited
COST CENTRE MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN        MAIN                     45           0    0.0    0.0   100.0  100.0
 main       Main                     91           0    2.0   84.6   100.0  100.0
  prime     Main                     92     2500000    0.7    0.0    98.0   15.4
   prime.go Main                     93   326103491   96.4    0.0    97.3   15.4
    isqrt   Main                     95           0    0.9   15.4     0.9   15.4

--- >8 ---

который ясно показывает, что prime - это то, где вещи становятся горячими. Для получения дополнительной информации о профилировании я отсылаю вас к Real World Haskell, Chap 25.

Чтобы понять, что происходит, вы можете посмотреть (один из) промежуточных языков GHC Core, который покажет вам, как выглядит код после оптимизации. Некоторая хорошая информация в Haskell wiki. Я бы не рекомендовал делать это, если это необходимо, но хорошо знать, что существует такая возможность.

К вашим другим вопросам:

1) Как, не изменяя алгоритм, я могу оптимизировать реализацию Haskell?

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

2) Действительно ли Haskell по соотношению производительности с C?

Это зависит. GHC поражает и часто может оптимизировать вашу программу очень хорошо. Если вы знаете, что делаете, вы можете приблизиться к производительности оптимизированного C (100% - 200% от скорости C). Тем не менее, эти оптимизации не всегда легки или красивы для глаз, и высокий уровень Haskell может быть медленнее. Но не забывайте, что при использовании Haskell вы получаете потрясающую выразительность и абстракции высокого уровня. Обычно он будет достаточно быстрым для всех, кроме приложений с высокой критичностью производительности, и даже тогда вы часто можете приблизиться к C с некоторой оптимизацией и оптимизацией производительности.

Ответ 2

Я не думаю, что версия Haskell (оригинальная и улучшенная с помощью первого ответа) эквивалентна версии С++. Причина в том, что: Оба учитывают только каждый второй элемент (в главной функции), а версия С++ сканирует каждый элемент (только я ++ в функции isPrime().

Когда я исправлю это (измените я ++ на я + = 2 в isPrime() для С++), я добираюсь до почти 1/3 времени исполнения оптимизированной версии Haskell (2.1s С++ vs 6s Haskell).

Выход остается неизменным для обоих (конечно). Обратите внимание, что это не особая opimization версии С++, а просто адаптация трюка, уже примененного в версии Haskell.