c++ - ¿Por qué el polimorfismo es tan costoso en haskell(GHC)?

matrix monomorphism

Question

Estoy haciendo esta pregunta con referencia a this pregunta SO. Respuesta aceptada de Don Steewart: la primera línea dice "Su código es altamente polimórfico. Cambia todas las variables flotantes a Doble ..." y ofrece una mejora de rendimiento 4X.

Estoy interesado en hacer cálculos matriciales en Haskell, ¿debo convertirlo en un hábito de escribir código altamente monomórfico?

Pero algunos idiomas hacen buen uso del polimorfismo ad hoc para generar código rápido, ¿por qué GHC no quiere o no puede? (lea C ++ o D)

¿Por qué no podemos tener algo como blitz ++ o eigen para Haskell? No entiendo cómo funcionan las clases y el polimorfismo (ad-hoc) en GHC.

Answer 1

No entiendo cómo funcionan las clases de texto en GHC.

OK, considera esta función:

linear :: Num x => x -> x -> x -> x
linear a b x = a*x + b

Esto toma tres números como entrada y devuelve un número como salida. Esta función acepta cualquier tipo de número; Es polimorfo. ¿Cómo implementa eso GHC? Bueno, esencialmente el compilador crea un "diccionario de clase" que contiene todos los métodos de clase dentro de él (en este caso, + , - , * , etc.) Este diccionario se convierte en un argumento adicional y oculto para la función. Algo como esto:

data NumDict x =
  NumDict
  {
    method_add :: x -> x -> x,
    method_subtract :: x -> x -> x,
    method_multiply :: x -> x -> x,
    ...
  }

linear :: NumDict x -> x -> x -> x -> x
linear dict a b x = a `method_multiply dict` x `method_add dict` b

Cuando llama a la función, el compilador inserta automáticamente el diccionario correcto, a menos que la función de llamada también sea polimórfica, en cuyo caso habrá recibido un diccionario, así que simplemente transmítalo.

En realidad, las funciones que carecen de polimorfismo suelen ser más rápidas, no tanto debido a la falta de búsquedas de funciones, sino porque el conocimiento de los tipos permite realizar optimizaciones adicionales. Por ejemplo, nuestra función linear polimórfica funcionará en números, vectores, matrices, relaciones, números complejos, cualquier cosa . Ahora, si el compilador sabe que queremos usarlo en, digamos, Double , ahora todas las operaciones se convierten en instrucciones únicas de código de máquina, todos los operandos pueden pasarse en los registros del procesador, y así sucesivamente. Todo lo cual resulta en un código increíblemente eficiente. Incluso si se trata de números complejos con componentes Double , podemos hacerlo agradable y eficiente. Si no tenemos idea de qué tipo obtendremos, no podemos hacer ninguna de esas optimizaciones ... De ahí es donde proviene la mayoría de la diferencia de velocidad.

Para una función pequeña como lineal, es muy probable que esté en línea cada vez que se llame, lo que no genera una sobrecarga de polimorfismo y una pequeña cantidad de duplicación de código, más bien como una plantilla de C ++. Para una función polimórfica más grande y más compleja, puede haber algún costo. En general, el compilador decide esto, no tú, a menos que quieras comenzar a rociar pragmas alrededor del lugar. ;-) O, si en realidad no usas ningún polimorfismo, puedes simplemente darle firmas de tipo monomórfico ...

Answer 2

Con el código polimórfico, por lo general hay una compensación entre el tamaño del código y la velocidad del código. O produce una versión separada del mismo código para cada tipo en el que operará, lo que resulta en un código más grande, o produce una versión única que puede operar en múltiples tipos, que será más lenta.

Las implementaciones en C ++ de plantillas eligen a favor de aumentar la velocidad del código al costo de aumentar el tamaño del código. Por defecto, GHC toma la compensación opuesta. Sin embargo, es posible hacer que GHC produzca versiones separadas para diferentes tipos utilizando los pragmas SPECIALIZE e INLINABLE. Esto dará como resultado un código polimórfico que tiene una velocidad similar a la del código monomórfico.

Answer 3

Quiero complementar la respuesta de Dirk diciendo que INLINABLE generalmente se recomienda más que SPECIALIZE . Una anotación INLINABLE en una función garantiza que el módulo exporte el código fuente original de la función para que pueda especializarse en el punto de uso. Esto generalmente elimina la necesidad de proporcionar pragmas SPECIALIZE separados para cada caso de uso.

A diferencia de INLINE , INLINABLE no cambia las heurísticas de optimización de GHC. Simplemente dice "Por favor, exporte el código fuente".