Подход «CPS» нанес большой вред производительности в SML / NJ; желательные рассуждения

11

В комментарии к Learning F #: Какие книги, использующие другие языки программирования, можно перевести на F # для изучения функциональных концепций? Макарий заявил:

Обратите внимание, что подход «CPS» нанес большой вред производительности в SML / NJ. Его модель физической оценки нарушает слишком много предположений, встроенных в аппаратное обеспечение. Если вы берете большие символические приложения SML, такие как Isabelle / HOL, SML / NJ с CPS выходит ок. В 100 раз медленнее, чем Poly / ML с его обычным стеком.

Может кто-нибудь объяснить причины этого? (Желательно с некоторыми примерами) Есть ли здесь несоответствие импеданса?

compilers functional-programming proof-assistants continuations Гай Кодер
источник
1
Насколько я понимаю, аппаратное обеспечение предполагает стековую дисциплину, и поэтому подход CPS требует снижения производительности за то, что он не придерживается этого предположения. Но это только мое неосведомленное мнение.
Андрей Бауэр

Ответы:

9

В первом приближении существует различие в «локальности» доступа к памяти, когда программа просто работает вперед в куче в стиле CPS вместо традиционного увеличения и уменьшения стека. Также обратите внимание, что CPS всегда будет нужен GC для восстановления ваших, казалось бы, локальных данных, помещенных в кучу. Одних этих наблюдений было бы достаточно для 10 или 20 лет назад, когда аппаратное обеспечение было намного проще, чем сегодня.

Я сам не являюсь ни гуру оборудования, ни компилятора, так что во втором приближении, вот некоторые конкретные причины для прибл. фактор 100, видимый в Изабель / HOL:

  • Основные потери производительности в соответствии с «первым приближением» выше.

  • Управление кучей SML / NJ и GC имеют серьезные проблемы, превышающие несколько десятков МБ; Теперь Изабель обычно использует 100-1000 МБ, иногда несколько ГБ.

  • Компиляция SML / NJ очень медленная - это может быть совершенно не связано (обратите внимание, что Isabelle / HOL чередует компиляцию во время выполнения и выполнение кода).

  • В SML / NJ отсутствует собственная многопоточность - не полностью не связанная, так как CPS рекламировался как «катите свои собственные потоки в пространстве пользователя без отдельных стеков».

Соотношение кучи и потоков также обсуждается в статье Morriset / Tolmach PPOPP 1993 года «Проки и блокировки: портативная мультипроцессорная платформа для стандартного ML Нью-Джерси» ( CiteSeerX ). Примечание: PDF в CiteSeerX обратный, страницы от 1 вместо 1-10.

Макарий
источник