write tag optimized moz img images how for example description alternative optimization compiler-construction haskell ghc heap-memory

optimization - optimized - seo image alt tag example



¿Buen texto introductorio sobre la implementación de GHC? (2)

Esto probablemente no es lo que tenía en mente en términos de un texto introductorio, pero Edward Yang tiene una serie continua de publicaciones de blog que hablan sobre el montón de Haskell, cómo se implementan las transferencias, etc.

Es entretenido, tanto con las ilustraciones como también en virtud de explicar cosas sin profundizar en demasiados detalles para alguien nuevo en Haskell. La serie cubre muchas de sus preguntas:

En un nivel más técnico, hay una serie de documentos que cubren (en concierto con otras cosas), partes de lo que quieres saber .:

  • Un documento de SPJ, Simon Marlow y otros en GC en Haskell : no lo he leído, pero dado que GC a menudo representa un buen portón del trabajo que hace Haskell, debería dar una idea.
  • El informe Haskell 2010 : estoy seguro de que habrás oído hablar de esto, pero es demasiado bueno para no vincularlo. Puede hacer que la lectura sea seca en algunos lugares, pero una de las mejores formas de entender lo que hace que Haskell sea como es, al menos las porciones que he leído.
  • Una historia de Haskell es más técnica de lo que su nombre sugiere, y ofrece algunas vistas muy interesantes sobre el diseño de Haskell y las decisiones detrás del diseño. No puede evitar comprender mejor la implementación de Haskell después de leerla.

Cuando programo en Haskell (y especialmente cuando resuelvo problemas de Project Euler, donde las soluciones subóptimas tienden a estresar las necesidades de la CPU o la memoria), a menudo me sorprende por qué el programa se comporta de la manera que es. Observé los perfiles, traté de introducir un poco de rigor, elegí otra estructura de datos, ... pero sobre todo está a tientas en la oscuridad, porque carezco de una buena intuición.

Además, aunque sé cómo se implementan Lisp, Prolog y los lenguajes imperativos, no tengo idea de implementar un lenguaje lento. También estoy un poco curioso.

Por lo tanto, me gustaría saber más sobre toda la cadena desde el origen del programa hasta el modelo de ejecución.

Cosas que me preguntan:

  • ¿Qué optimizaciones típicas se aplican?

  • ¿Cuál es el orden de ejecución cuando hay múltiples candidatos para la evaluación (aunque sé que se basa en los resultados necesarios, aún puede haber grandes diferencias de rendimiento entre la primera evaluación de A y B, o la evaluación de B primero para detectar que no es necesario A en absoluto)

  • ¿Cómo se representan los thunks?

  • ¿Cómo se usan la pila y el montón?

  • ¿Qué es un CAF? (El perfil indica a veces que el punto de acceso está ahí, pero no tengo ni idea)

La mayoría de la información técnica sobre la arquitectura y el enfoque del sistema GHC está en su wiki. Voy a vincular a las piezas clave, y algunos documentos relacionados que las personas pueden no saber.

¿Qué optimizaciones típicas se aplican?

El documento clave sobre esto es: Un optimizador basado en la transformación para Haskell , SL Peyton Jones y A Santos, 1998, que describe el modelo que utiliza GHC de la aplicación de transformaciones conservadoras de tipo (refactorizaciones) de un lenguaje central tipo Haskell para mejorar el tiempo y uso de memoria. Este proceso se llama "simplificación".

Las cosas típicas que se hacen en un compilador Haskell incluyen:

  • Inlineación;
  • Reducción de beta;
  • Eliminación del código muerto;
  • Transformación de las condiciones: caso-de-caso, eliminación de casos.
  • Unboxing;
  • Devolución del producto construido;
  • Completa transformación de la pereza;
  • Especialización;
  • Expansión de Eta;
  • Lambda levantando;
  • Análisis de Estrictas

Y aveces:

  • La transformación de argumento estático;
  • Build / foldr o fusión de flujo;
  • Eliminación de sub-expresión común;
  • Especialización de constructor.

El documento mencionado anteriormente es el lugar clave para comenzar a entender la mayoría de estas optimizaciones. Algunos de los más simples se dan en el libro anterior, Implementing Functional Languages , Simon Peyton Jones y David Lester.

¿Cuál es el orden de ejecución cuando hay múltiples candidatos para evaluación

Suponiendo que está en un procesador único, la respuesta es "algún orden que el compilador elija estáticamente en función de la heurística y el patrón de demanda del programa". Si está utilizando la evaluación especulativa a través de chispas, entonces "algún patrón de ejecución no determinista y fuera de orden".

En general, para ver cuál es el orden de ejecución, mire el núcleo, con, por ejemplo, la herramienta ghc-core . Una introducción a Core está en el capítulo de RWH sobre optimizaciones.

¿Cómo se representan los thunks?

Los subprocesos se representan como datos asignados en el montón con un puntero de código.

Vea el diseño de los objetos de montón . Específicamente, vea cómo se representan los thunks .

¿Cómo se usan la pila y el montón?

Según lo determinado por el diseño de Spineless Tagless G-machine , específicamente, con muchas modificaciones desde que se lanzó el documento. En general, el modelo de ejecución:

  • (en caja) los objetos se asignan en el montón global;
  • cada objeto de hilo tiene una pila , que consiste en marcos con el mismo diseño que los objetos de montón;
  • cuando haces una llamada a función, presionas valores en la pila y saltas a la función;
  • si el código necesita asignar, por ejemplo, un constructor, esos datos se colocan en el montón.

Para comprender profundamente el modelo de uso de la pila, ver "Empujar / Entrar frente a Evaluar / Aplicar" .

¿Qué es un CAF?

Un "Formulario de aplicación constante". Por ejemplo, una constante de nivel superior en su programa asignada durante la vida de la ejecución de su programa. Como están asignados estáticamente, deben ser tratados especialmente por el recolector de basura .

Referencias y lecturas adicionales :