Могу ли я ускорить этот алгоритм Haskell?

Ответ 1

Две части кода делают разные вещи.

import Data.Bits
main = do
    print $ length $ filter (\i -> i .&. (shift 1 (i `mod` 4)) /= 0) [0..123456789]

создает список из 123456790 Integer (лениво), берет остаток по модулю 4 из каждого (сначала нужно проверить, достаточно ли Integer, чтобы обернуть целое число необработанных машин, затем после деления знак-проверка, так как mod возвращает только неотрицательные результаты - хотя в ghc-7.6.1 для этого есть primop, поэтому не так много тормозов использовать mod, как это было before), сдвиг Integer 1 оставил соответствующее количество бит, что связано с преобразованием в "большой" Integer и вызовом GMP, занимает побитовое и с i - еще один вызов GMP - и проверяет имеет ли результат 0, что вызывает другой вызов GMP или преобразование в малые целые числа, не зная, что GHC делает здесь. Затем, если результат отличен от нуля, создается новая ячейка списка, в которую помещается Integer и потребляется length. Это лот выполненной работы, большая часть из которых излишне усложняется из-за дефолта неуказанных типов номеров на Integer.

Код C

#include <stdio.h>
int main(void) {
    int count = 0;
    const int max = 123456789;
    int i;
    for (i = 0; i < max; ++i)
        if ((i & (1 << i % 4)) != 0)
            ++count;
    printf("count: %d\n", count);
    return 0;
}

(я взял на себя ответственность за исправление возвращаемого типа main), делает гораздо меньше. Он принимает int, сравнивает его с другим, если он меньше, принимает побитовое и первое int с 3 ⁽¹⁾ сдвигает int 1 влево соответствующее количество бит, принимает поразрядное и то же, и первое int, а если отличное от нуля приращение другого int, то увеличивает его. Это все машинные операции, работающие на сырых машинных типах.

Если мы переведем этот код в Haskell,

module Main (main) where

import Data.Bits

maxNum :: Int
maxNum = 123456789

loop :: Int -> Int -> Int
loop acc i
    | i < maxNum = loop (if i .&. (1 `shiftL` (i .&. 3)) /= 0 then acc + 1 else acc) (i+1)
    | otherwise  = acc

main :: IO ()
main = print $ loop 0 0

получим гораздо более близкий результат:

C, gcc -O3:
count: 30864196

real    0m0.180s
user    0m0.178s
sys     0m0.001s

Haskell, ghc -O2:
30864196

real    0m0.247s
user    0m0.243s
sys     0m0.003s

Haskell, ghc -O2 -fllvm:
30864196

real    0m0.144s
user    0m0.140s
sys     0m0.003s

Генератор исходного кода GHC не является особенно хорошим оптимизатором цикла, поэтому использование llvm-бэкэнда здесь имеет большое значение, но даже генератор собственных кодов не делает слишком плохо.

Хорошо, я выполнил оптимизацию замены вычисления модуля модулем силы двух с поразрядным и вручную, генератор исходного кода GHC этого не делает (пока), поэтому с `` `rem 4`` instead of. &. 3; встроенный генератор кода генерирует код, который занимает (здесь) 1,42 секунды для запуска, но бэкэнд llvm делает эту оптимизацию и производит тот же код, что и при ручной оптимизации.

Теперь перейдем к вопросу gspr

В то время как LLVM не оказал существенного влияния на исходный код, он действительно сделал это на модифицированном (я хотел бы узнать, почему...).

Ну, в исходном коде используются списки Integer и, llvm не слишком хорошо знает, что с ними делать, он не может преобразовать этот код в циклы. Модифицированный код использует int, а пакет vector перезаписывает код в циклы, поэтому llvm знает, как его оптимизировать, и это показывает.

⁽¹⁾ Предполагая обычный двоичный компьютер. Эта оптимизация выполняется обычными компиляторами C даже без флага оптимизации, за исключением очень редких платформ, где инструкция div работает быстрее, чем сдвиг.

Ответ 2

Немногие вещи избили рукописный цикл со строгим аккумулятором:

{-# LANGUAGE BangPatterns #-}

import Data.Bits

f :: Int -> Int
f n = g 0 0
  where g !i !s | i <= n    = g (i+1) (if i .&. (unsafeShiftL 1 (i `rem` 4)) /= 0 then s+1 else s)
                | otherwise = s

main = print $ f 123456789

В дополнение к упомянутым выше трюкам это также заменяет shift на unsafeShiftL, который не проверяет его аргумент.

Скомпилированный с -O2 и -fllvm, это примерно на 13 раз быстрее, чем оригинал на моей машине.

_{Примечание. Тестирование, если бит i of x установлен, может быть написан более четко как x `testBit` i. Это создает ту же самую сборку, что и выше.}

Ответ 3

Вектор вместо списка, свернуть вместо фильтра и длины

Подставляя список для unboxed vector, а размер фильтра и длины для сгиба (т.е. увеличивая счетчик) значительно увеличивает время меня. Вот что я использовал:

import qualified Data.Vector.Unboxed as UV
import Data.Bits

foo :: Int
foo = UV.foldl (\s i -> if i .&. (shift 1 (i `rem` 4)) /= 0 then s+1 else s) 0 (UV.enumFromN 0 123456789)

main = print foo

Исходный код (с двумя изменениями: rem вместо mod, как это предлагается в комментариях, и добавление Int к сигнатуре, чтобы избежать Integer):

$ time ./orig 
30864196

real    0m2.159s
user    0m2.144s
sys     0m0.008s

Приведенный выше модифицированный код дал:

$ time ./new 
30864196

real    0m1.450s
user    0m1.440s
sys     0m0.004s

LLVM

В то время как LLVM не оказал существенного влияния на исходный код, он действительно сделал это на модифицированном (я хотел бы узнать, почему...).

Оригинал (LLVM):

$ time ./orig-llvm 
30864196

real    0m2.047s
user    0m2.036s
sys     0m0.008s

Изменено (LLVM):

$ time ./new-llvm 
30864196

real    0m0.233s
user    0m0.228s
sys     0m0.004s

Для сравнения, исходный код кода OP входит в пользователя 0m0.152s в моей системе.

Это все GHC 7.4.1, GCC 4.6.3 и вектор 0.9.1. LLVM - 2,9 или 3,0; У меня есть и то, и другое, но я не могу понять, какой именно GHC на самом деле использует.

Ответ 4

Попробуйте следующее:

import Data.Bits
main = do
    print $ length $ filter (\i -> i .&. (shift 1 (i `rem` 4)) /= 0) [0..123456789::Int]

Без ::Int тип по умолчанию имеет значение ::Integer. rem делает то же самое, что и mod по положительным значениям, и это то же самое, что и % в C. mod, с другой стороны, математически корректно по отрицательным значениям, но медленнее.

• int в C 32bit
• int в Haskell имеет ширину 32 или 64 бит, например long в C
• Integer - произвольное целое число, оно не имеет значений min/max, а размер его памяти зависит от его значения (похоже на строку).