Анализируя медленную производительность программы на Haskell

Я пытался решить головоломку ITA Software "Word Nubmers" , используя метод грубой силы. Похоже, моя версия Haskell более чем в 10 раз медленнее, чем версия C # / C ++.

Ответ

Благодаря ответу Брайана О'Салливана я смог «исправить» свою программу к приемлемой производительности. Вы можете прочитать его код, который намного чище моего. Я собираюсь обрисовать здесь ключевые моменты:

• Int - это Int64 в Linux GHC x64. Если вы не unsafeCoerce , вам следует просто использовать Int . Это избавляет вас от необходимости использовать из Integral . Выполнение Int64 в 32-разрядной версии Windows GHC просто чертовски медленно, избегайте этого. (На самом деле это не вина GHC. Как упоминалось в моем сообщении в блоге ниже, 64-битные целые числа в 32-битных программах обычно работают медленно (по крайней мере, в Windows))
• -fllvm или -fvia -C для повышения производительности.
• Предпочитайте quotRem divMod , quotRem уже достаточно. Это дало мне ускорение на 20%.
• В общем, предпочитайте Data.Vector Data.Array в качестве «массива»
• Широко используйте шаблон обертка-рабочий.

Вышеупомянутых пунктов было достаточно, чтобы дать мне примерно 100% преимущество по сравнению с моей исходной версией.

В своем сообщении в блоге я подробно описал пошаговый иллюстрированный пример того, как я превратил исходную программу в соответствовать программе Брайана. Там же упоминаются и другие моменты.

Исходный вопрос

(Это может звучать как пост «не могли бы вы сделать для меня работу», но я утверждаю, что такой конкретный пример был бы очень поучительным, поскольку профилирование Haskell производительность часто рассматривается как миф)

(Как отмечено в комментариях, я думаю, что неправильно истолковал проблему. Но кого это волнует, мы можем сосредоточиться на производительности в другой проблеме)

Вот моя версия краткого обзора проблемы:

A wordNumber is defined as

wordNumber 1 = "one"
wordNumber 2 = "onetwo"
wordNumber 3 = "onethree"
wordNumber 15 = "onetwothreefourfivesixseveneightnineteneleventwelvethirteenfourteenfifteen"
...

Problem: Find the 51-billion-th letter of (wordNumber Infinity); assume that letter is found at 'wordNumber x', also find 'sum [1..x]'

С императивной точки зрения, наивный алгоритм будет иметь 2 счетчика, один для суммы чисел и один для суммы длин. Продолжайте считать длину каждого wordNumber и «break», чтобы вернуть результат.

Императивный подход грубой силы реализован в C # здесь: http://ideone.com/JjCb3 . На поиск ответа на моем компьютере уходит около 1,5 минут. Существует также реализация C ++ , которая выполняется на моем компьютере за 45 секунд.

Затем я реализовал версию Haskell методом перебора: http://ideone.com/ngfFq . На моей машине невозможно завершить расчет за 5 минут. (Ирония: в нем больше строк, чем в версии C #)

Вот профиль -p программы Haskell: http://hpaste.org/49934

Вопрос: Как чтобы заставить его работать по сравнению с версией C #? Есть ли очевидные ошибки, которые я делаю?

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

(Примечание 2: похоже, что утечки места нет. Программа работает с постоянной памятью (около 2 МБ) на моем компьютере)

(Примечание 3 : Я компилирую с помощью `ghc -O2 WordNumber.hs)

Чтобы сделать вопрос более удобным для читателя, я включаю" суть "двух версий.

// C#
long sumNum = 0;
long sumLen = 0;

long target = 51000000000;
long i = 1;

for (; i < 999999999; i++)
{
    // WordiLength(1)   = 3   "one"
    // WordiLength(101) = 13  "onehundredone"
    long newLength = sumLen + WordiLength(i);
    if (newLength >= target)
        break;

    sumNum += i;
    sumLen = newLength;
}
Console.WriteLine(Wordify(i)[Convert.ToInt32(target - sumLen - 1)]);

-

-- Haskell
-- This has become totally ugly during my squeeze for 
-- performance

-- Tail recursive
-- n-th number (51000000000 in our problem) -> accumulated result -> list of 'zipped' left to try
-- accumulated has the format (sum of numbers, current lengths of the whole chain, the current number)
solve :: Int64 -> (Int64, Int64, Int64) -> [(Int64, Int64)] -> (Int64, Int64, Int64)
solve !n !acc@(!sumNum, !sumLen, !curr) ((!num, !len):xs)
    | sumLen' >= n = (sumNum', sumLen, num)
    | otherwise = solve n (sumNum', sumLen', num) xs
    where
        sumNum' = sumNum + num
        sumLen' = sumLen + len

-- wordLength 1   = 3    "one"
-- wordLength 101 = 13   "onehundredone"
wordLength :: Int64 -> Int64
-- wordLength = ...

solution :: Int64 -> (Int64, Char)
solution !x =
    let (sumNum, sumLen, n) = solve x (0,0,1) (map (\n -> (n, wordLength n)) [1..])
    in (sumNum, (wordify n) !! (fromIntegral $ x - sumLen - 1))