peta - ¿Puedo acelerar este algoritmo de Haskell?

peta haskell en español

Question

Tengo este archivo ghc -O2 , compilado con ghc -O2 (ghc 7.4.1), y toma 1.65 segundos en mi máquina

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

El mismo algoritmo en C, compilado con gcc -O2 (gcc 4.6.3), se ejecuta en 0.18 seg.

#include <stdio.h>
void main() {
    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);
}

Actualización , pensé que podría ser la cosa de Data.Bits va lenta, pero sorprendentemente si quito los cambios y simplemente hago una mod directa, ¡en realidad corre más lento a 5,6 segundos!

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

mientras que el C equivalente corre un poco más rápido a 0.16 segundos:

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

Answer 1

Vector en lugar de lista, doble en lugar de filtro y longitud

Sustituir la lista por un vector sin caja y el filtro y la longitud por un pliegue (es decir, incrementar un contador) mejora el tiempo significativamente para mí. Esto es lo que usé:

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

El código original (con dos cambios sin embargo: rem lugar de mod como se sugiere en los comentarios, y agregar un Int a la firma para evitar el Integer ) dio:

$ time ./orig 
30864196

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

El código modificado anterior dio:

$ time ./new 
30864196

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

LLVM

Si bien LLVM no tuvo un efecto masivo en el código original, sí lo hizo en el modificado (me encantaría saber por qué ...).

Original (LLVM):

$ time ./orig-llvm 
30864196

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

Modificado (LLVM):

$ time ./new-llvm 
30864196

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

A modo de comparación, el código C original de OP aparece en 0m0.152s usuario en mi sistema.

Esto es todo GHC 7.4.1, GCC 4.6.3 y vector 0.9.1. LLVM es 2.9 o 3.0; Tengo ambos, pero parece que no puedo saber cuál de ellos está usando realmente GHC.

Answer 2

Las dos piezas de código hacen cosas muy diferentes.

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

crea una lista de 123456790 Integer (perezosamente), toma el resto del módulo 4 de cada uno (involucra primero una verificación de si el Integer es lo suficientemente pequeño como para envolver un entero de máquina en bruto, luego, después de la división, un signo de comprobación, ya que la mod devuelve no negativa solo resultados - aunque en ghc-7.6.1, hay un primop para eso, por lo que no es tanto un freno usar mod como lo era antes), cambia el Integer 1 dejando el número apropiado de bits, lo que implica una conversión a "grandes" Integer y una llamada a GMP, toma el bit a bit y con i - otra llamada a GMP - y verifica si el resultado es 0, lo que provoca otra llamada a GMP o una conversión a un entero pequeño, no estoy seguro de qué GHC hace aquí Luego, si el resultado es distinto de cero, se crea una nueva celda de lista donde se coloca ese Integer y se consume por length . Eso es mucho trabajo realizado, la mayoría de los cuales es innecesariamente complicado debido a la configuración predeterminada de tipos de números no especificados en Integer .

El código 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;
}

(Me tomé la libertad de arreglar el tipo de retorno de main ), hace mucho menos. Toma un int , lo compara con otro, si es más pequeño, toma el bit a bit y del primer int con 3 ⁽¹⁾ , desplaza el int 1 a la izquierda el número apropiado de bits, toma el bit a bit y de ese y el primer int y, si no es cero, aumenta otro int , entonces incrementa el primero. Esas son todas las operaciones de máquinas, que trabajan en tipos de máquinas en bruto.

Si traducimos ese código a 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

Obtenemos un resultado mucho más cercano:

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

El generador de código nativo de GHC no es un optimizador de bucle particularmente bueno, por lo que usar el backend llvm hace una gran diferencia aquí, pero incluso el generador de código nativo no lo hace tan mal.

Bien, he hecho la optimización de reemplazar un cálculo de módulo con un módulo de potencia de dos con un bit y a mano, el generador de código nativo de GHC no hace eso (todavía), así que con `` `rem 4`` instead of . &. 3`, el generador de código nativo produce código que tarda (aquí) 1.42 segundos en ejecutarse, pero el backend de llvm realiza esa optimización y produce el mismo código que con la optimización hecha a mano.

Ahora, volvamos a la pregunta de gspr

Aunque LLVM no tuvo un efecto masivo en el código original, sí lo hizo en el modificado (me encantaría saber por qué ...).

Bueno, el código original utilizado. Integer y listas, llvm no sabe muy bien qué hacer con ellas, no puede transformar ese código en bucles. El código modificado utiliza Int s y el paquete vector reescribe el código en bucles, de modo que llvm sabe cómo optimizar ese pozo, y eso se ve.

⁽¹⁾ Asumiendo una computadora binaria normal. Esa optimización la realizan compiladores C normales, incluso sin ningún indicador de optimización, excepto en las plataformas muy raras donde una instrucción div es más rápida que un cambio.

Answer 3

Pocas cosas superan a un bucle escrito a mano con un acumulador estricto:

{-# 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

Además de los trucos mencionados hasta ahora, esto también reemplaza shift con unsafeShiftL , que no comprueba su argumento.

Compilado con -O2 y -fllvm , esto es aproximadamente 13 veces más rápido que el original en mi máquina.

_{Nota: Probar si el bit i de x está establecido puede escribirse más claramente como x `testBit` i . Esto produce el mismo conjunto que el anterior.}

Answer 4

Prueba esto:

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

Sin el ::Int , el tipo por defecto es ::Integer . rem hace lo mismo que mod en valores positivos, y es igual que % en C. mod por otro lado, es matemáticamente correcto en valores negativos, pero es más lento.

• int en C es de 32 bits
• Int en Haskell tiene 32 o 64 bits de ancho, como long en C
• Integer es un entero de bits arbitrario, no tiene valores mínimos / máximos y su tamaño de memoria depende de su valor (similar a una cadena).