El enfoque "CPS" ha hecho un gran daño al rendimiento en SML / NJ; razonamiento deseado

11

En un comentario a Learning F #: ¿Qué libros que usan otros lenguajes de programación se pueden traducir a F # para aprender conceptos funcionales? Makarius declaró:

Tenga en cuenta que el enfoque "CPS" ha hecho un gran daño al rendimiento en SML / NJ. Su modelo de evaluación física viola demasiados supuestos integrados en el hardware. Si toma grandes aplicaciones simbólicas de SML como Isabelle / HOL, SML / NJ con CPS sale aprox. 100 veces más lento que Poly / ML con su pila convencional.

¿Alguien puede explicar las razones de esto? (Preferiblemente con algunos ejemplos) ¿Hay un desajuste de impedancia aquí?

compilers functional-programming proof-assistants continuations Guy Coder
fuente
1
Tengo entendido que el hardware asume una disciplina de pila, por lo que el enfoque de CPS se ve afectado por no cumplir con esta suposición. Pero esa es solo mi opinión desinformada.
Andrej Bauer

Respuestas:

9

En la primera aproximación, hay una diferencia en la "localidad" del acceso a la memoria, cuando un programa simplemente se ejecuta en el montón en estilo CPS, en lugar del tradicional crecimiento y reducción de la pila. También tenga en cuenta que CPS siempre necesitará GC para recuperar sus datos aparentemente locales colocados en el montón. Estas observaciones por sí solas habrían sido adecuadas hace 10 o 20 años, cuando el hardware era mucho más simple que hoy.

Yo no soy ni un gurú del hardware ni un compilador, así que, como segunda aproximación, aquí hay algunas razones concretas para el aprox. factor 100 visto en Isabelle / HOL:

  • Pérdida de rendimiento básica según la "primera aproximación" anterior.

  • SML / NJ Heap Management y GC tienen graves problemas para escalar más allá de varias decenas de MB; Isabelle ahora usa de 100 a 1000 MB de forma rutinaria, a veces varios GB.

  • La compilación SML / NJ es muy lenta; esto podría no estar relacionado (tenga en cuenta que Isabelle / HOL alterna la compilación de tiempo de ejecución y el código de ejecución).

  • SML / NJ carece de subprocesos múltiples nativos, no totalmente ajenos, ya que CPS se anunciaba como "enrolle sus propios hilos en el espacio del usuario sin pilas separadas".

Morriset / Tolmach PPOPP 1993 "Procs and Locks: A Portable Multiprocessing Platform for Standard ML of New Jersey" ( CiteSeerX ) Nota: PDF en CiteSeerX está al revés, páginas de 10- 1 en lugar de 1-10.

Makarius
fuente