Максимизация производительности петли Haskell с GHC

Чтобы сравнить производительность с медленными списками в этой ошибке GHC Я пытаюсь получить следующий цикл как можно быстрее:

{-# LANGUAGE BangPatterns #-}

module Main (main) where

import Control.Monad
import Data.Word


main :: IO ()
main = do
  loop (maxBound :: Word32) $ \i -> do
    when (i `rem` 100000000 == 0) $
      print (fromIntegral i / fromIntegral (maxBound :: Word32))


loop :: Word32 -> (Word32 -> IO ()) -> IO ()
loop n f = go 0
  where
    go !i | i == n = return ()
    go !i          = f i >> go (i + 1)

скомпилирован с ghc -O loop.hs.

Однако для этого требуется 50 секунд на моем компьютере - в 10 раз медленнее, чем эквивалентная программа на C:

#include "limits.h"
#include "stdint.h"
#include "stdio.h"

int main(int argc, char const *argv[])
{
  for (uint32_t i = 0; i < UINT_MAX; ++i)
  {
    if (i % 100000000 == 0) printf("%f\n", (float) i / (float) UINT_MAX );
  }
  return 0;
}

скомпилирован с gcc -O2 -std=c99 -o testc test.c.

Использование недавно выпущенного GHC 7.8 или с помощью -O2 не улучшило производительность.

Однако компиляция с флагом -fllvm (в любой версии ghc) привела к улучшению скорости 10x, приведя производительность на уровне с помощью C.

Вопросы:

  • Почему GGC native codegen настолько медленнее для моего loop?
  • Есть ли способ улучшить мой цикл так, чтобы он был быстрым и без -fllvm, или это уже самый быстрый цикл IO над Word32, который можно достичь?

Ответы

Ответ 1

Осмотрите сборку. Я немного изменил основную функцию, чтобы результат стал немного яснее (но производительность остается идентичной). Я использовал GHC 7.8.2 с -O2.

main :: IO ()
main = do
  loop (maxBound :: Word32) $ \i -> do
    when (i `rem` 100000000 == 0) $
      putStrLn "foo"

Существует много беспорядка, поэтому я стараюсь включать только интересные части:

Native Codegen

Main_zdwa_info:
.Lc3JD: /* check if there enough space for stack growth */
    leaq -16(%rbp),%rax
    cmpq %r15,%rax
    jb .Lc3JO /* this jumps to some GC code that grows the stack, then
                 reenters the main closure */
.Lc3JP:
    movl $4294967295,%eax /* issue: loading the bound on every iteration */
    cmpq %rax,%r14
    jne .Lc3JB
.Lc3JC:
   /* Return from main. Code omitted */
.Lc3JB: /* test the index for modulus */
    movl $100000000,%eax /* issue: unnecessary moves */
    movq %rax,%rbx      
    movq %r14,%rax
    xorq %rdx,%rdx
    divq %rbx /* issue: doing the division (llvm and gcc avoid this) */
    testq %rdx,%rdx
    jne .Lc3JU
.Lc3JV: 
   /* do the printing. Code omitted. */
.Lc3JN:
   /* increment index and (I guess) restore registers messed up by the printing */
    movq 8(%rbp),%rax
    incq %rax  
    movl %eax,%r14d
    addq $16,%rbp
    jmp Main_zdwa_info
.Lc3JU:
    leaq 1(%r14),%rax   /*issue: why not just increment r14? */
    movl %eax,%r14d     
    jmp Main_zdwa_info

LLVM

 Main_zdwa_info:
/* code omitted: the same stack-checking stuff as in native */
.LBB1_1:
    movl    $4294967295, %esi /* load the bound */
    movabsq $-6067343680855748867, %rdi /*load a magic number for the modulus */
    jmp .LBB1_2
.LBB1_4:              
    incl    %ecx
.LBB1_2:  
    cmpq    %rsi, %rcx
    je  .LBB1_6 /* check bound */

    /* do the modulus with two multiplications, a shift and a magic number */
    /* note : gcc does the same reduction */ 
    movq    %rcx, %rax
    mulq    %rdi
    shrq    $26, %rdx
    imulq   $100000000, %rdx, %rax  
    cmpq    %rax, %rcx
    jne .LBB1_4 
    /* Code omitted: print, then return to loop beginning */
.LBB1_6:                       
    /* Code omitted: return from main */

Наблюдения

  • Накладные расходы ввода-вывода отсутствуют в обеих сборках. Ток состояния с нулевым байтом RealWorld заметно отсутствует.

  • Нативный кодеген не сильно снижает силу, в отличие от LLVM, который легко преобразует модуль в умножение, сдвиг и магические числа.

  • Native codegen повторяет проверку пространства стека на каждой итерации, а LLVM - нет. Однако это не является значительным накладным расходами.

  • Нативный кодеген просто плох здесь при циклировании и распределении регистров. Он перемещается вокруг регистров и загружает привязку на каждой итерации. LLVM испускает код, сопоставимый с рукописным кодом в чистоте.

Что касается вашего вопроса:

Есть ли способ улучшить мой цикл, чтобы он был быстрым и без -fllvm, или это > уже самый быстрый цикл ввода-вывода по Word32, который можно достичь?

Лучшее, что вы можете сделать здесь, - это сокращение ручной силы, я думаю, хотя я лично считаю этот вариант неприемлемым. Однако после этого ваш код будет значительно медленнее. Я также запускал следующий тривиальный цикл и в два раза быстрее с LLVM, чем с native:

import Data.Word
main = go 0 where
    go :: Word32 -> IO ()
    go i | i == maxBound = return ()
    go i = go (i + 1)

Преступник снова не нужен перетасовке и перегрузке. На самом деле нет способа устранить такие проблемы низкого уровня, кроме перехода на LLVM.

Ответ 2

Легкой оптимизацией будет использование Float деления вместо стандартного Double. Просто напишите удобную функцию для замены fromIntegral

w2f :: Word32 -> Float
w2f = fromIntegral

Однако быстрее вычислить цикл следующим образом:

main :: IO () 
main = forM_ [0, 100000000 .. mb] $ \i ->
    print (fromIntegral i / fromIntegral mb :: Float))
    where mb = maxBound :: Word32