prediccion - FSharp ejecuta mi algoritmo más lento que Python

modelo logit en python

Question

Hace años, resolví un problema a través de la programación dinámica:

https://www.thanassis.space/fillupDVD.html

La solución fue codificada en Python.

Como parte de la expansión de mis horizontes, recientemente comencé a aprender OCaml / F #. Qué mejor manera de probar las aguas, que haciendo un puerto directo del código imperativo que escribí en Python a F # - y comenzar a partir de ahí, avanzando hacia una solución de programación funcional.

Los resultados de este primer puerto directo ... son desconcertantes:

En Python:

  bash$ time python fitToSize.py
  ....
  real    0m1.482s
  user    0m1.413s
  sys     0m0.067s

Bajo FSharp:

  bash$ time mono ./fitToSize.exe
  ....
  real    0m2.235s
  user    0m2.427s
  sys     0m0.063s

(en caso de que hayas notado el "mono" anterior: también lo he probado en Windows, con Visual Studio: la misma velocidad).

Estoy ... desconcertado, por decir lo menos. Python ejecuta el código más rápido que F #? Un binario compilado, utilizando el tiempo de ejecución de .NET, se ejecuta más lento que el código interpretado de Python?!?!

Sé sobre los costos iniciales de las VM (mono en este caso) y cómo los JIT mejoran las cosas para lenguajes como Python, pero aún así ... ¡esperaba una aceleración, no una desaceleración!

¿He hecho algo mal, tal vez?

He subido el código aquí:

https://www.thanassis.space/fsharp.slower.than.python.tar.gz

Tenga en cuenta que el código F # es más o menos una traducción directa, línea por línea, del código de Python.

PS: Por supuesto, hay otras ganancias, por ejemplo, la seguridad de tipo estático ofrecida por F #, pero si la velocidad resultante de un algoritmo imperativo es peor bajo F # ... estoy decepcionado, por decir lo menos.

EDITAR : acceso directo, como se solicita en los comentarios:

el código de Python: https://gist.github.com/950697

el código de FSharp: https://gist.github.com/950699

Answer 1

Como ha señalado Jon Harrop, la simple construcción de los diccionarios utilizando Dictionary(HashIdentity.Structural) ofrece una importante mejora en el rendimiento (un factor de 3 en mi computadora). Este es casi seguro el cambio mínimamente invasivo que necesita hacer para obtener un mejor rendimiento que Python, y mantiene su código idiomático (en lugar de reemplazar las tuplas con estructuras, etc.) y en paralelo a la implementación de Python.

Answer 2

El Dr. Jon Harrop, a quien contacté por correo electrónico, me explicó lo que está sucediendo:

El problema es simplemente que el programa ha sido optimizado para Python. Esto es común cuando el programador está más familiarizado con un idioma que el otro, por supuesto. Solo tienes que aprender un conjunto diferente de reglas que dictan cómo deberían optimizarse los programas F # ... Me saltaron varias cosas, como el uso de un ciclo "for i in 1..n do" en lugar de un "for i = 1 a n do "loop (que es más rápido en general pero no significativo aquí), repetidamente haciendo List.mapi en una lista para imitar un índice de matriz (que asignó listas intermedias innecesariamente) y su uso de F # TryGetValue para Dictionary que asigna innecesariamente (el .NET TryGetValue que acepta una referencia es más rápido en general pero no tanto aquí)

... pero el verdadero problema asesino resultó ser tu uso de una tabla hash para implementar una matriz 2D densa. Usar una tabla hash es ideal en Python porque su implementación de tablas hash ha sido extremadamente bien optimizada (como lo demuestra el hecho de que tu código Python se ejecuta tan rápido como F # compilado en código nativo!) Pero las matrices son una forma mucho mejor de representar densas matrices, particularmente cuando quieres un valor predeterminado de cero.

Lo gracioso es que cuando codifiqué por primera vez este algoritmo, Hice uso de una tabla: cambié la implementación a un diccionario por razones de claridad (evitando que las comprobaciones de límites de la matriz hicieran el código más simple) y mucho más fácil de razonar).

Jon transformó mi código (volver :-)) en su versión de matriz , y se ejecuta a velocidad 100x.

Moraleja de la historia:

• El diccionario F # necesita trabajo ... cuando se usan tuplas como claves, el compilado F # es más lento que las tablas hash de Python.
• Obvio, pero no hay daño en repetir: código más limpio a veces significa ... código mucho más lento.

Gracias, Jon, muy apreciado.

EDITAR : el hecho de que reemplazar Dictionary with Array hace que F # finalmente se ejecute a las velocidades que se espera que ejecute un lenguaje compilado, no niega la necesidad de una corrección en la velocidad del diccionario (espero que F # personas de MS lo lean). Otros algoritmos dependen de diccionarios / hashes, y no pueden cambiarse fácilmente a usar matrices; hacer que los programas sufran "velocidades de intérprete" cada vez que uno usa un Diccionario, es discutible, un error. Si, como algunos han dicho en los comentarios, el problema no es con F # sino con .NET Dictionary, entonces diría que esto ... ¡es un error en .NET!

EDIT2 : La solución más clara, que no requiere que el algoritmo cambie a arreglos (algunos algoritmos simplemente no serán susceptibles de eso) es cambiar esto:

let optimalResults = new Dictionary<_,_>()

dentro de esto:

let optimalResults = new Dictionary<_,_>(HashIdentity.Structural)

Este cambio hace que el código F # se ejecute 2.7 veces más rápido, y finalmente supere a Python (1.6 veces más rápido). Lo extraño es que las tuplas usan de forma predeterminada la comparación estructural, por lo que, en principio, las comparaciones hechas por el Diccionario sobre las claves son las mismas (con o sin Estructura). El Dr. Harrop teoriza que la diferencia de velocidad puede atribuirse al despacho virtual: "AFAIK, .NET hace poco para optimizar el despacho virtual y el costo del despacho virtual es extremadamente alto en el hardware moderno porque es un" goto computarizado "que salta el programa contrarrestar una ubicación impredecible y, en consecuencia, socava la lógica de predicción de bifurcación y casi con certeza hará que toda la tubería de la CPU se vacíe y se vuelva a cargar " .

En palabras sencillas, y como sugiere Don Syme ( mire las 3 respuestas inferiores ), "sea explícito sobre el uso del hash estructural al usar claves de referencia junto con las colecciones .NET". (El Dr. Harrop en los comentarios a continuación también dice que siempre debemos usar comparaciones estructurales al usar colecciones .NET).

Estimado equipo F # en MS, si hay una forma de solucionarlo automáticamente, por favor hazlo.

Answer 3

Editar: me equivoqué, no es una cuestión de tipo de valor frente a tipo de referencia. El problema de rendimiento estaba relacionado con la función hash, como se explica en otros comentarios. Guardo mi respuesta aquí porque hay una discusión interesante. Mi código solucionó parcialmente el problema de rendimiento, pero esta no es la solución limpia y recomendada.

-

En mi computadora, hice que tu muestra se ejecutara dos veces más rápido reemplazando la tupla con una estructura. Esto significa que el código F # equivalente debe ejecutarse más rápido que su código Python. No estoy de acuerdo con los comentarios que dicen que las tablas de .NET son lentas, creo que no hay una diferencia significativa con Python u otras implementaciones de idiomas. Además, no estoy de acuerdo con el "código de traducción 1 a 1 no se puede esperar que sea más rápido": el código F # generalmente será más rápido que Python para la mayoría de las tareas (la tipificación estática es muy útil para el compilador). En su muestra, la mayor parte del tiempo se dedica a realizar búsquedas de tablas hash, por lo que es justo imaginar que ambos lenguajes deberían ser casi tan rápidos.

Creo que el problema de rendimiento está relacionado con la recopilación de errores (pero no lo he comprobado con un generador de perfiles). La razón por la que el uso de tuplas puede ser más lento aquí que las estructuras se ha discutido en una pregunta de SO ( ¿Por qué el nuevo tipo Tuple en .NET 4.0 es un tipo de referencia (clase) y no un tipo de valor (struct) ) y una página de MSDN ( Edificio tuplas ):

Si son tipos de referencia, esto significa que puede haber mucha basura generada si está cambiando elementos en una tupla en un ciclo cerrado. [...] Las tuplas F # eran tipos de referencia, pero el equipo sintió que podían realizar una mejora en el rendimiento si dos, y quizás tres, tuplas de elementos eran tipos de valores en su lugar. Algunos equipos que habían creado tuplas internas habían usado el valor en lugar de los tipos de referencia, porque sus escenarios eran muy sensibles a la creación de muchos objetos administrados.

Por supuesto, como dijo Jon en otro comentario, la optimización obvia en su ejemplo es reemplazar hashtables con matrices. Las matrices son obviamente mucho más rápidas (índice entero, sin hash, sin manejo de colisiones, sin reasignación, más compacto), pero esto es muy específico para su problema, y ​​no explica la diferencia de rendimiento con Python (hasta donde yo sé, El código de Python usa tablas hash, no matrices).

Para reproducir mi aceleración del 50%, aquí está el código completo: http://pastebin.com/nbYrEi5d

En resumen, reemplacé la tupla con este tipo:

type Tup = {x: int; y: int}

Además, parece un detalle, pero debe mover el List.mapi (fun ix -> (i,x)) fileSizes fuera del bucle adjunto. Creo que la enumerate Python en realidad no asigna una lista (por lo que es justo asignar la lista solo una vez en F #, o usar el módulo Seq , o usar un contador mutable).