L'approche «CPS» a nui gravement aux performances en SML / NJ; raisonnement souhaité

11

Dans un commentaire à Learning F #: Quels livres utilisant d'autres langages de programmation peuvent être traduits en F # pour apprendre des concepts fonctionnels? Makarius a déclaré:

Notez que l'approche "CPS" a fait un grand tort aux performances en SML / NJ. Son modèle d'évaluation physique viole trop d'hypothèses intégrées au matériel. Si vous prenez de grandes applications symboliques de SML comme Isabelle / HOL, SML / NJ avec CPS sort environ. 100 fois plus lent que Poly / ML avec sa pile conventionnelle.

Quelqu'un peut-il expliquer les raisons de cela? (De préférence avec quelques exemples) Y a-t-il un décalage d'impédance ici?

compilers functional-programming proof-assistants continuations Guy Coder
la source
1
Ma compréhension est que le matériel assume une discipline de pile, et donc l'approche CPS prend un coup performace pour ne pas adhérer à cette hypothèse. Mais c'est juste mon opinion non informée.
Andrej Bauer

Réponses:

9

En première approximation, il existe une différence dans la «localité» d'accès à la mémoire, lorsqu'un programme s'exécute simplement sur le tas en style CPS, au lieu de la croissance et du rétrécissement traditionnels de la pile. Notez également que CPS aura toujours besoin de GC pour récupérer vos données apparemment locales placées sur le tas. Ces observations à elles seules auraient été suffisantes il y a 10 ou 20 ans, lorsque le matériel était beaucoup plus simple qu'aujourd'hui.

Je ne suis moi-même ni un gourou du matériel ni du compilateur, donc à titre de seconde approximation, voici quelques raisons concrètes pour le approx. facteur 100 vu dans Isabelle / HOL:

  • Perte de performances de base selon la "première approximation" ci-dessus.

  • La gestion des segments de mémoire SML / NJ et GC présente de graves problèmes à l'échelle au-delà de plusieurs dizaines de Mo; Isabelle utilise désormais 100 à 1000 Mo en routine, parfois plusieurs Go.

  • La compilation SML / NJ est très lente - cela pourrait être totalement indépendant (notez qu'Isabelle / HOL alterne compilation d'exécution et code d'exécution).

  • SML / NJ manque de multithreading natif - pas totalement sans rapport, car CPS a été annoncé comme "rouler vos propres threads dans l'espace utilisateur sans piles séparées".

La corrélation du tas et des threads est également discutée dans le document de Morriset / Tolmach PPOPP 1993 "Procs and Locks: A Portable Multiprocessing Platform for Standard ML of New Jersey" ( CiteSeerX ) Note: PDF at CiteSeerX is backward, pages from from 10- 1 au lieu de 1-10.

Makarius
la source