performance - keywords - meta tags google

Ejemplos en los que el código funcional optimizado para el compilador funciona mejor que el código imperativo (4)

Una de las promesas de la programación funcional referencialmente transparente , libre de efectos colaterales, es que dicho código se puede optimizar ampliamente. Para citar Wikipedia :

La inmutabilidad de los datos puede, en muchos casos, conducir a la eficiencia de la ejecución, al permitir que el compilador haga suposiciones que no sean seguras en un lenguaje imperativo, lo que aumenta las oportunidades de texto para la expansión en línea.

Me gustaría ver ejemplos donde un compilador de lenguaje funcional supere uno imperativo al producir un código mejor optimizado.

Editar: Intenté dar un escenario específico, pero aparentemente no fue una buena idea. Entonces trataré de explicarlo de otra manera.

Los programadores traducen ideas (algoritmos) en lenguajes que las máquinas pueden entender. Al mismo tiempo, uno de los aspectos más importantes de la traducción es que también los humanos podemos entender el código resultante. Desafortunadamente, en muchos casos hay una compensación: un código conciso y legible adolece de un rendimiento lento y debe optimizarse manualmente. Esto es propenso a errores, lleva mucho tiempo y hace que el código sea menos legible (hasta totalmente ilegible).

Los fundamentos de los lenguajes funcionales, como la inmutabilidad y la transparencia referencial, permiten a los compiladores realizar optimizaciones extensas, que podrían reemplazar la optimización manual del código y los programadores gratuitos de esta compensación. Estoy buscando ejemplos de ideas (algoritmos) y sus implementaciones, tales que:

la implementación (funcional) está cerca de la idea original y es fácil de entender,
está ampliamente optimizado por el compilador del lenguaje, y
es difícil (o imposible) escribir un código similarmente eficiente en un lenguaje imperativo sin optimizaciones manuales que reducen su concisión y legibilidad.

Me disculpo si es un poco vago, pero espero que la idea sea clara. No quiero dar restricciones innecesarias a las respuestas. Estoy abierto a sugerencias si alguien sabe cómo expresarlo mejor.

Mi interés no es solo teórico. Me gustaría usar tales ejemplos (entre otras cosas) para motivar a los estudiantes a interesarse en la programación funcional.

Al principio, no estaba satisfecho con algunos ejemplos sugeridos en los comentarios. Pensándolo bien, recojo mis objeciones, esos son buenos ejemplos. Por favor, siéntase libre de expandirlos a respuestas completas para que la gente pueda comentar y votar por ellos.

(Una clase de tales ejemplos probablemente sea un código paralelo, que puede aprovechar múltiples núcleos de CPU. A menudo, en los lenguajes funcionales esto se puede hacer fácilmente sin sacrificar la simplicidad del código (como en Haskell al agregar par o pseq en los lugares apropiados). ''estar interesado en tales ejemplos también, pero también en otros, no paralelos.)

Esto es solo una nota, no una respuesta: el gcc tiene un atributo pure sugiere que puede tener en cuenta la pureza; las razones obvias son comentadas en el manual here .

Creo que la ''asignación única estática'' impone una forma de pureza: vea los enlaces en http://lambda-the-ultimate.org/node/2860 o el artículo de wikipedia.

Hay casos en los que el mismo algoritmo se optimizará mejor en un contexto puro. Específicamente, la fusión de flujo permite un algoritmo que consiste en una secuencia de bucles que pueden ser de forma muy variable: mapas, filtros, pliegues, despliegues, para componerse en un solo bucle.

La optimización equivalente en un ajuste imperativo convencional, con datos mutables en bucles, tendría que lograr un análisis de efecto completo, que nadie hace.

Por lo tanto, al menos para la clase de algoritmos que se implementan como conductos de ana y catamorfismos en secuencias, puede garantizar resultados de optimización que no son posibles en un entorno imperativo.

Un artículo muy reciente, Haskell vence a C usando la fusión de flujo generalizada de Geoff Mainland, Simon Peyton Jones, Simon Marlow y Roman Leshchinskiy (presentado a ICFP 2013) describe este ejemplo. Resumen (con la parte interesante en negrita):

Stream fusion [6] es una poderosa técnica para transformar automáticamente funciones de procesamiento de secuencias de alto nivel en implementaciones eficientes. Se ha utilizado con gran éxito en las bibliotecas de Haskell para manipular matrices de bytes, texto Unicode y vectores no compartidos. Sin embargo, algunas operaciones, como la adición de vector, todavía no funcionan bien dentro del marco de fusión de flujo estándar. Otros, como el cálculo SIMD utilizando las instrucciones SSE y AVX disponibles en los modernos chips x86, no parecen encajar en absoluto en el marco.
En este artículo presentamos la fusión de flujo generalizada, que resuelve estos problemas. La idea clave es agrupar múltiples representaciones de flujo, cada una ajustada para una clase particular de consumidor de flujo. También describimos una representación de flujo adecuada para un cálculo eficiente con instrucciones de SSE. Nuestras ideas se implementan en versiones modificadas del compilador GHC y vector biblioteca de vector . Los puntos de referencia muestran que el código Haskell de alto nivel escrito usando nuestro compilador y bibliotecas puede producir código que es más rápido que el compilador y el vector vectorizado a mano.

make y varios sistemas de compilación funcionan mejor para proyectos grandes al asumir que varios pasos de compilación son referencialmente transparentes; como tal, solo necesitan volver a ejecutar los pasos que han cambiado sus entradas.

Para cambios pequeños a medianos, esto puede ser mucho más rápido que construir desde cero.