Podejście „CPS” wyrządziło wielką szkodę wydajności w SML / NJ; uzasadnienie pożądane

W komentarzu do Nauka F #: Jakie książki w innych językach programowania można przetłumaczyć na F #, aby nauczyć się funkcjonalnych koncepcji? Makarius stwierdził:

Zauważ, że podejście „CPS” wyrządziło wielką szkodę wydajności w SML / NJ. Jego model oceny fizycznej narusza zbyt wiele założeń wbudowanych w sprzęt. Jeśli weźmiesz duże symboliczne aplikacje SML, takie jak Isabelle / HOL, SML / NJ z CPS wyjdzie ok. 100 razy wolniejszy niż Poly / ML dzięki konwencjonalnemu stosowi.

Czy ktoś może wyjaśnić przyczyny tego? (Najlepiej z kilkoma przykładami) Czy występuje tu niedopasowanie impedancji?

Przy pierwszym przybliżeniu występuje różnica w „lokalizacji” dostępu do pamięci, gdy program po prostu działa na stosie w stylu CPS, zamiast tradycyjnego powiększania i zmniejszania stosu. Pamiętaj również, że CPS zawsze będzie potrzebował GC do odzyskania pozornie lokalnych danych umieszczonych na stercie. Same te obserwacje byłyby wystarczające 10 lub 20 lat temu, kiedy sprzęt był znacznie prostszy niż dzisiaj.

Nie jestem ani guru sprzętowym, ani kompilatorem, więc dla drugiego przybliżenia oto kilka konkretnych powodów dla ok. współczynnik 100 widoczny w Isabelle / HOL:

• Podstawowa utrata wydajności zgodnie z „pierwszym przybliżeniem” powyżej.

• Zarządzanie stertami SML / NJ i GC ma poważne problemy ze skalowaniem przekraczającym kilkadziesiąt MB; Isabelle używa teraz rutynowo 100-1000 MB, czasem kilku GB.

• Kompilacja SML / NJ jest bardzo powolna - może to być całkowicie niezwiązane (zauważ, że Isabelle / HOL na przemian kompiluje środowisko uruchomieniowe i uruchamia kod).

• SML / NJ nie ma natywnej wielowątkowości - nie do końca niezwiązanej, ponieważ CPS reklamowano jako „taczaj własne wątki w przestrzeni użytkownika bez osobnych stosów”.

Korelacja kupy i wątków jest również omawiana w pracy Morriset / Tolmach PPOPP 1993 „Procs and Locks: Portable Multiprocessing Platform for Standard ML of New Jersey” ( CiteSeerX ) Uwaga: PDF w CiteSeerX jest odwrócony, strony od 10- 1 zamiast 1-10.