Simple π(x) en Haskell vs C++

performance

Question

Estoy aprendiendo Haskell. Mi interés es usarlo para la experimentación de computadora personal. En este momento, estoy tratando de ver qué tan rápido puede llegar Haskell. Muchos reclaman paridad con C (++), y si eso es cierto, me sentiría muy feliz (debo señalar que usaré Haskell tanto si es rápido como si no, pero rápido sigue siendo algo bueno).

Mi programa de prueba implementa π (x) con un algoritmo muy simple: los números de primes agregan 1 al resultado. Los números primos no tienen divisores enteros entre 1 y √x. Esto no es una batalla de algoritmos, es solo para el rendimiento del compilador.

Haskell parece ser aproximadamente 6 veces más lento en mi computadora, lo cual está bien (aún 100 veces más rápido que Python puro), pero podría ser solo porque soy un novato de Haskell.

Ahora, mi pregunta: ¿Cómo, sin cambiar el algoritmo, puedo optimizar la implementación de Haskell? ¿Haskell está realmente en paridad de rendimiento con C?

Aquí está mi código de Haskell :

import System.Environment

-- a simple integer square root
isqrt :: Int -> Int
isqrt = floor . sqrt . fromIntegral

-- primality test        
prime :: Int -> Bool
prime x = null [x | q <- [3, 5..isqrt x], rem x q == 0]

main = do
  n <- fmap (read . head) getArgs
  print $ length $ filter prime (2:[3, 5..n])

Aquí está mi código de C++ :

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

bool isPrime(int);

int main(int argc, char* argv[]) {
    int primes = 10000, count = 0;
    if (argc > 1) {
        primes = atoi(argv[1]);
    }
    if (isPrime(2)) {
        count++;
    }
    for (int i = 3; i <= primes; i+=2) {
        if (isPrime(i)){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

bool isPrime(int x){
    for (int i = 2; i <= floor(sqrt(x)); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

Answer 1

No creo que la versión de Haskell (original y mejorada por la primera respuesta) sea equivalente a la versión de C ++. El motivo es el siguiente: ambos solo consideran cada segundo elemento (en la función principal), mientras que la versión C ++ analiza cada elemento (solo i ++ en la función isPrime ()).

Cuando soluciono esto (cambio i ++ por i + = 2 en la función isPrime () para C ++) llego a casi 1/3 del tiempo de ejecución de la versión optimizada de Haskell (2.1s C ++ vs 6s Haskell).

La salida sigue siendo la misma para ambos (por supuesto). Tenga en cuenta que esto no es una opimización específica de la versión C ++, solo una adaptación del truco ya aplicado en la versión Haskell.

Answer 2

Su versión de Haskell está construyendo una lista perezosa en prime solo para probar si es nula. Esto parece ser un cuello de botella. La siguiente versión se ejecuta tan rápido como la versión C ++ en mi máquina:

prime :: Int -> Bool
prime x = go 3
  where
    go q | q <= isqrt x = if rem x q == 0 then False else go (q+2)
    go _  = True

3.31s cuando se compila con -O2 vs. 3.18s para C ++ con gcc 4.8 y -O3 para n = 5000000.

Por supuesto, "adivinar" donde el programa es lento para optimizarlo no es un muy buen enfoque. Afortunadamente, Haskell tiene buenas herramientas de perfilado a bordo.

Compilando y corriendo con

$ ghc --make primes.hs -O2 -prof -auto-all -fforce-recomp && ./primes 5000000 +RTS -p

da

# primes.prof
  Thu Feb 20 00:49 2014 Time and Allocation Profiling Report  (Final)

     primes +RTS -p -RTS 5000000

  total time  =        5.71 secs   (5710 ticks @ 1000 us, 1 processor)
  total alloc = 259,580,976 bytes  (excludes profiling overheads)

COST CENTRE MODULE  %time %alloc

prime.go    Main     96.4    0.0
main        Main      2.0   84.6
isqrt       Main      0.9   15.4

                                                      individual     inherited
COST CENTRE MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN        MAIN                     45           0    0.0    0.0   100.0  100.0
 main       Main                     91           0    2.0   84.6   100.0  100.0
  prime     Main                     92     2500000    0.7    0.0    98.0   15.4
   prime.go Main                     93   326103491   96.4    0.0    97.3   15.4
    isqrt   Main                     95           0    0.9   15.4     0.9   15.4

--- >8 ---

lo que muestra claramente que el prime es donde las cosas se ponen calientes. Para obtener más información sobre la creación de perfiles, lo remitiré a Real World Haskell, Capítulo 25 .

Para entender realmente lo que está pasando, puede ver (uno de) el Core de lenguajes intermedios de GHC, que le mostrará cómo se ve el código después de la optimización. Alguna buena información está en el wiki de Haskell . No recomendaría hacerlo a menos que sea necesario, pero es bueno saber que existe la posibilidad.

A tus otras preguntas:

1) ¿Cómo, sin cambiar el algoritmo, puedo optimizar la implementación de Haskell?

Haga un perfil e intente escribir bucles internos para que no hagan ninguna asignación de memoria y el compilador pueda hacerlos estrictos. Hacerlo puede requerir algo de práctica y experiencia.

2) ¿Haskell está realmente en paridad de rendimiento con C?

Eso depende. GHC es increíble y a menudo puede optimizar su programa muy bien. Si sabe lo que está haciendo, por lo general puede acercarse al rendimiento de C optimizado (100% - 200% de la velocidad de C). Dicho esto, estas optimizaciones no siempre son fáciles o bonitas a la vista y el nivel alto de Haskell puede ser más lento. Pero no olvide que está ganando una expresividad increíble y abstracciones de alto nivel al usar Haskell. Por lo general, será lo suficientemente rápido para todas las aplicaciones, excepto para las aplicaciones más críticas, y aún así, a menudo puede acercarse bastante a C con algunas optimizaciones de perfilado y rendimiento.