Ответ 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 (1) сдвигает 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 не оказал существенного влияния на исходный код, он действительно сделал это на модифицированном (я хотел бы узнать, почему...).
Ну, в исходном коде используются списки , llvm не слишком хорошо знает, что с ними делать, он не может преобразовать этот код в циклы. Модифицированный код использует Integer иint, а пакет vector перезаписывает код в циклы, поэтому llvm знает, как его оптимизировать, и это показывает.
(1) Предполагая обычный двоичный компьютер. Эта оптимизация выполняется обычными компиляторами C даже без флага оптимизации, за исключением очень редких платформ, где инструкция div работает быстрее, чем сдвиг.