performance - compilador - compilacion y ejecucion de un algoritmo

¿La programación funcional permite mejores optimizaciones del compilador en tiempo de ejecución? (10)

NOTA: Ya hice esto un Wiki. No me importa cómo se marque esta pregunta, siempre que haya una buena discusión.

He escuchado que, dado que en los programas puramente funcionales, no hay efectos secundarios y los valores no muta, hace que sea más fácil para el compilador realizar más optimizaciones en tiempo de ejecución. ¿En qué medida es esto cierto?

Si esto es cierto, mi siguiente preocupación es ¿cuál es la pérdida de libertad por la que estamos intercambiando esto? Quiero decir, en lenguajes como C ++ / C, el desarrollador tiene un control total y puede modificar muchas cosas. Si entregamos este trabajo al compilador, perderemos esa oportunidad. El lado positivo de esto es que incluso un programador no experto puede escribir un buen código. Además, en estos días con tantas capas de caché en la arquitectura de la máquina, puede que incluso un experto realmente no pueda hacer nada que valga la pena. Entonces, delegar este trabajo al compilador que sabe más sobre la arquitectura subyacente que el programador, es una buena idea.

¿Cuáles son tus sugerencias?

no hay efectos secundarios y los valores no se modifican, lo que facilita que el compilador realice más optimizaciones en tiempo de ejecución

En cierto sentido, sí, hasta que te das cuenta de que los efectos secundarios y los valores mutables son optimizaciones en sí mismos.

¿Has visto esta entrada de blog de "matemáticas buenas, matemáticas malas" ?

Programo en C, ensamblaje y OCaml. A veces miro el ensamblaje generado por el compilador de C. Es terriblemente ineficiente. A menudo, me doy cuenta de que una variable global se vuelve a cargar una y otra vez, cuando está claro (para alguien consciente de la lógica del programa) que no cambia durante la ejecución de la función, sino que debido a que la función manipula los punteros, El compilador no puede asumir que la variable no se toca. Una forma sencilla de solucionar esto cuando se da cuenta de que es copiar el contenido del global en un local al comienzo de la función, de esta manera mantendrá la portabilidad de C pero obtendrá un rendimiento de conjunto ...

Pero no debería tener que hacer esto, y de hecho, con un lenguaje de nivel superior, no tiene también, porque hay menos punteros, conversiones y otras construcciones de bajo nivel que le permiten acercarse al hardware cuando Quiero, pero en realidad se interponga en el camino de la optimización automática.

Aquí hay un ejemplo en Clojure: iterar sobre una lista de cosas usando alguna función.

(map some-fn big-list)

Lo bueno es que puedes paralelizarlo (múltiples núcleos, no múltiples máquinas) con un solo personaje:

(pmap some-fn big-list)

La maquinaria de lenguaje / compilador que hace funcionar a pmap no sería posible sin funciones puras y estructuras de datos inmutables.

Esta es todavía una característica experimental. Pero la programación funcional y sin efectos secundarios hace que la ejecución de múltiples núcleos sea mucho más fácil.

Como regla general, la optimización del compilador hace una diferencia en el código que:

En realidad se compila. Si la mayoría de las veces la parte inferior de la pila de llamadas está dentro del código que el compilador nunca ve, puede optimizar todo lo que quiera, pero no tendrá ningún efecto.
Eso consume una fracción significativa (como el 10% o más) del tiempo de ejecución cuando el usuario u otros realmente están esperando el programa. Si nadie espera, la optimización nunca se notará.
Que no contiene llamadas a funciones. Si el código que se está compilando contiene llamadas a funciones, el contador del programa está casi siempre en otro lugar.

Por lo tanto, nunca lo notará, a menos que escriba algoritmos de procesamiento pesado que trabajen en gran cantidad de datos sin consultar el código que no compila. Al igual que en el momento en que coloca la comparación de cadenas en un algoritmo de clasificación, la optimización es académica.

Creo que deberías estar hablando de modelos de lenguaje en lugar de optimizaciones del compilador. Los imperativos de procedimiento / funcional tienen su propia área donde brillan. Te daré dos ejemplos:

Imperativo - procesal

Erlang (un lenguaje funcional). Adoptó el enfoque de estado compartido con su base de datos Mnesia integrada: es inherentemente no funcional, ya que una transacción de actualización bloquea un recurso de base de datos que obtiene un valor, lo cambia y lo vuelve a escribir. Hicieron esto para mejorar el rendimiento porque reconocen que la velocidad es importante en esta área y si no lo hicieran, Erlang sería inútil para los problemas que intentaban resolver (¿te imaginas escribir un archivo de base de datos completo cada vez que creas un archivo? ¿cambio?) = D.

Puro funcional

Funcional frente a no funcional en términos de rendimiento permitido por el modelo es un área temática divertida. Tomando el punto de vista funcional; Erlang puede saturar los núcleos que la máquina está ejecutando cuando los problemas están inherentemente orientados a la concurrencia. Algunas pruebas mostraron que el servidor web YAWS manejaba conexiones de 100k donde Apache se cayó a 4k : D Ejabberd también puede manejar MUCHO más carga que los interruptores de mensajes tradicionales. Lo que estoy tratando de decir es que el lenguaje funcional puro puede tener un motor de tiempo de ejecución que puede paralelizar masivamente la aplicación en grandes cantidades de núcleos. No se puede hacer esto fácilmente con un código de procedimiento imperativo.

Diferentes modelos son adecuados para diferentes problemas. Personalmente, creo que puede optimizar el código de procedimiento mucho mejor que el código funcional, el código funcional todavía se ejecuta como código de procedimiento, y se interpreta: PI ha estudiado la teoría del compilador y, honestamente, no puedo pensar en las asombrosas transformaciones de código que aplicaría. Al código funcional antes de ejecutarlo. Tiene recursión de cola y evaluación perezosa, pero seguramente esas son características del modelo de programación.

Echa un vistazo a la comparación de Haskell vs C aquí:

http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell

Notarás que la versión de Haskell es mucho más corta. Sin embargo, la página continúa diciendo que si bien la versión c es posiblemente más compleja, también se clasifica en su lugar, mientras que la versión Haskell debe asignar mucha más memoria para que funcione.

Por lo tanto, por definición, si desea la capacidad de obtener un ajuste extremo del rendimiento, el algoritmo c es el mejor enfoque.

En teoría, a medida que los compiladores se vuelven más inteligentes, usted desea programar en lenguajes de alto nivel, ya que no solo permitirían que el compilador haga más optimización, sino que la arquitectura de la CPU / memoria evolucione. Tal vez, algún día tengamos "CPU en evolución", que se reorganicen para ejecutar mejor una determinada aplicación. Los programas de C suponen que la computadora tiene una arquitectura determinada llamada arquitectura de Von Neumann, mientras que los programas funcionales / declarativos son más independientes de la arquitectura, ya que usted está indicando qué se debe calcular en lugar de cómo hacerlo.

Esto es sólo una contribución anecdótica:

Aprendí yo mismo (a algunos) Clojure usando los problemas de matemáticas del Proyecto Euler . Resolví algunos problemas usando secuencias perezosas.

Descubrí que, cuando apliqué sugerencias de tipo, el rendimiento de los cálculos largos (donde el inicio no importa) era generalmente comparable al de Java a mano.

Esto es casi lo que se espera: Clojure se compila con anticipación en el bytecode JVM, y se ejecuta con el mismo tiempo de ejecución de optimización que el código Java.

Lo que me sorprendió durante un tiempo fue que algunos cálculos ocupaban múltiples núcleos, aunque no lo había programado (a sabiendas) en ninguna paralelización. Parece que el tiempo de ejecución es capaz de aprovechar la oportunidad de paralelizar la generación de secuencias perezosas y el consumo.

Mi conclusión: la programación funcional limpia no tiene que ser más lenta que la programación imperativa y, a veces, puede encontrar vías inesperadas de optimización o paralelización.

¡Como alguien que odia pensar en la concurrencia porque hace que me duela el cerebro, considero que la "paralelización automática" es un beneficio inestimable!

Para ser claro, solo porque un compilador para un lenguaje funcional pueda optimizar mejor no significa que realmente lo haga . Cualquier optimización loca, por definición, conduce a un comportamiento inesperado en el tiempo de ejecución que casi con seguridad conduce a errores. Entonces, para descartar un gran error: en teoría, el compilador puede paralelizar los programas de Haskell, pero en realidad no lo son ni deberían serlo.

Creo que los días en que las optimizaciones del compilador fueron el rey se han acabado. Cuando clockspeed era el principal cuello de botella para las optimizaciones de rendimiento, como el desenrollado de bucle era esencial. Sin embargo, para la gran mayoría de las aplicaciones, el problema no es la velocidad bruta de la CPU, sino otros factores, como el ancho de banda de la red, la E / S del disco y / o la velocidad del algoritmo que está utilizando.

Que yo sepa, no hay optimización de compilación para volver a implementar su código para usar un patrón de diseño paralelo, por ejemplo. En otras palabras, si está utilizando Bubble Sort con cada optimización del compilador que pueda imaginar y estoy usando Quick Sort. El dinero inteligente está en la implementación de Ordenación rápida en la mayoría de las situaciones.

La programación funcional tiene mucho valor, pero "porque se ejecutan más rápido" no debería ser una consideración.

cuando se trata de C o C ++, hay una gran cantidad de optimización del compilador involucrada, y el compilador podría decidir eliminar cualquier pequeña y agradable idea, ya que puede determinar mucho mejor qué optimización usar en un lugar específico (como en líneas ) y toma en cuenta cosas como tuberías de instrucciones, etc. La arquitectura del hardware se ha vuelto demasiado compleja para que las personas puedan programar el hardware directamente. Hoy en día, incluso los compiladores simples emplean cantidades significativas de optimización. el uso de trucos funky es menos legible y más difícil de optimizar para el compilador, porque la optimización manual reduce la semántica. así que incluso si escribes C o C ++, tu elección es dispararte en el pie o dejar que el compilador haga la optimización para ello. De eso se trata la mayoría de las 9,513,227 líneas de código en el GCC.

Creo que es muy importante que el software sea verificable, robusto, mantenible, flexible y reutilizable / extensible. Cuanto más expresivo y conciso sea un lenguaje, más fácil será para los desarrolladores cumplir con estos criterios.

Hay un último criterio importante para el software: la eficiencia. La pregunta importante es cómo medir la eficiencia. Lo mediría en pura velocidad y escalabilidad. estos dos no se excluyen mutuamente, sin embargo, utilizan un lenguaje, que está estrechamente relacionado con los conceptos de computación paralela / distribuida y presenta el diseño de construcciones de lenguaje para esa materia, es mucho más fácil desarrollar tales algoritmos. por supuesto, la cosa se ejecutaría más rápido, si usted hiciera todo el envío usted mismo, pero eso es propenso a errores y consume mucho tiempo.

También debe tener en cuenta que la optimización del compilador tiene efectos lineales. Si sus algoritmos o el diseño de su sistema no se escalan bien, no resolverá el problema por usted. Si se escala bien, puede resolver los problemas de rendimiento al agregar más hardware, que siempre es más barato que el tiempo de desarrollo.

al final, la elección que hace es reinventar la rueda para tener la rueda óptima para ir por el camino que desea tomar, o tomar una rueda existente, y preocuparse más por elegir el camino correcto, en lugar de la velocidad, en que vas

Si escribe software, la única decisión importante que debe tomar por adelantado es el diseño ... luego, lo implementa y, una vez que se implementa, podrá determinar los cuellos de botella reales y luego optimizarlos ... generalmente más del 90% de su código se ejecuta menos el 10% del tiempo ... la optimización solo es importante para el 10% restante ... para determinarlos, necesita un software funcional que pueda perfilar ... y lo necesita rápidamente , para que puedas reconsiderar tu diseño, antes de escribir algo que esté súper optimizado, pero de lo contrario ...