A abordagem "CPS" causou grandes danos ao desempenho em SML / NJ; raciocínio desejado

11

Em um comentário ao Learning F #: que livros usando outras linguagens de programação podem ser traduzidos para o F # para aprender conceitos funcionais? Makarius declarou:

Observe que a abordagem "CPS" causou grandes danos ao desempenho em SML / NJ. Seu modelo de avaliação física viola muitas suposições embutidas no hardware. Se você utiliza grandes aplicações simbólicas de SML como Isabelle / HOL, SML / NJ com CPS sai aprox. 100 vezes mais lento que o Poly / ML com sua pilha convencional.

Alguém pode explicar as razões para isso? (De preferência com alguns exemplos) Há uma incompatibilidade de impedância aqui?

compilers functional-programming proof-assistants continuations Guy Coder
fonte
1
Meu entendimento é que o hardware assume uma disciplina de pilha e, portanto, a abordagem do CPS leva um golpe de desempenho por não aderir a essa suposição. Mas essa é apenas a minha opinião desinformada.
Andrej Bauer 03/03

Respostas:

9

Na primeira aproximação, há uma diferença na "localidade" do acesso à memória, quando um programa apenas avança no heap no estilo CPS, em vez do crescimento e encolhimento tradicionais da pilha. Observe também que o CPS sempre precisará do GC para recuperar seus dados aparentemente locais colocados no heap. Somente essas observações seriam adequadas 10 ou 20 anos atrás, quando o hardware era muito mais simples do que hoje.

Eu mesmo não sou um guru de hardware nem de compilador; portanto, como segunda aproximação, aqui estão algumas razões concretas para o aprox. fator 100 observado em Isabelle / HOL:

  • Perda de desempenho básico de acordo com a "primeira aproximação" acima.

  • O gerenciamento de heap SML / NJ e o GC têm problemas sérios para escalar além de várias dezenas de MB; Isabelle agora usa 100-1000 MB rotineiramente, às vezes vários GB.

  • A compilação SML / NJ é muito lenta - isso pode não ter relação alguma (observe que Isabelle / HOL alterna a compilação de tempo de execução e o código de execução).

  • O SML / NJ não possui multithreading nativo - não totalmente independente, pois o CPS foi anunciado como "role seus próprios threads no espaço do usuário sem pilhas separadas".

A correlação de heap e threads também é discutida no artigo de Morriset / Tolmach PPOPP 1993 "Procs and Locks: A Portable Multiprocessing Platform for ML Standard of New Jersey" ( CiteSeerX ). Nota: O PDF no CiteSeerX está para trás, 1 em vez de 1-10.

Makarius
fonte