Алексей Махоткин

домашняя страница

Критика Standard ML — эффективность

Andrew W. Appel, «Критика Standard ML», оглавление

Элегантный язык найдет немного применений, если программы, написанные на нем, всегда выполняются медленно. Поэтому так важно, чтобы ML можно было компилировать для эффективного выполнения. Многое говорит в пользу того, что это полностью достижимо. ML проверяет типы на стадии компиляции: это означает, что метки типов не нужно хранить на стадии выполнения, а операторы не вынуждены проверять типы своих аргументов на стадии выполнения. В ML нет «динамического поиска методов», который требуется во многих объектно-ориентированных языках.

ML определяет ошибки доступа за границы массива: такая возможность отсутствует в C, и она замедляет работу, если не устраняется хорошим оптимизирующим компилятором. ML проверяет, не равен ли указатель nil, перед тем, как обратиться по этому указателю; однако то, как именно это реализовано: с помощью сопоставления шаблонов, встроенного в язык, означает, что такие проверки будут просто частью обычного потока управления, написанного программистом. (К сожалению, иногда программист знает, что список не может быть пустым (nil), но проверку все равно приходится делать, потому что компилятор ML просто не может быть таким умным.) ML проверяет переполнение арифметических операций, но на большинстве компьютеров это обрабатывается в железе, и дополнительных инструкций не требуется.

Можно ли сделать ML столь же эффективным, как C? В какой-то степени этот вопрос всё еще стоит на повестке дня исследователей (и чрезвычайно интересует меня лично). На этот вопрос сложно ответить, потому что для этого требуется написать «одинаковые» программы одновременно на C и на Standard ML. Как понять, что программа, написанная на идиоматическом C « и программа, написанная на идиоматическом ML, «одинаковы»?

Можно было бы попробовать провести количественные сравнения, переписав программу с C на идиоматический ML, и наоборот, затем скомпилировав результаты «хорошими» компиляторами на одном и том же оборудовании. Это достаточно бесплодное занятие, и с «реальными задачами» такие эксперименты практически не проводились.

С другой стороны, есть много хороших компиляторов Scheme. Scheme выполняется не столь эффективно, как C, по крайней мере, для большинства задач. Однако, Scheme и Common Lisp достаточно эффективны, чтобы можно было написать на них достаточное количество реальных задач. ML можно заставить выполняться так же эффективно, как и C, потому что эти языки очень похожи, но ML, в отличие от Scheme, не требует проверки типов во время выполнения.

В любом случае, существует по меньшей мере одна достаточно эффективная реализация ML. У этой, и у других реализаций множество пользователей, которые считают их достаточно эффективными; это было бы не так, если бы они были медленнее на порядок.

Доступно несколько реализаций Standard ML:
  • Standard ML of New Jersey, из Принстонского Универсистета и AT&T Bell Laboratories (контактный адрес appel+princeton.edu)
  • Poly/ML, от Abstract Hardware Ltd. (контактный адрес bob+ahl.co.uk)
  • Poplog ML, от University of Sussex (isl+integ.uucp, pop+cs.umass.edu)

Программы на ML (скомпилированные некоторыми компиляторами) используют гораздо больше памяти, чем сравнимые программы на C. Это серьезная проблема, но недавние исследования указывают на возможные пути решения. В настоящее время представляется, что ML достаточно эффективен для использования в широком диапазоне приложений. Программы на C часто работают быстрее не более, чем в два раза, а зачастую даже и не столь быстро. Для многих применений ML имеет преимущества в безопасности, элегантности, простоте управления памятью, и тому подобном. Эти преимущества вполне могут перевесить разницу в производительности. Более того, программы, которые требуют сложного и дорогого управления памятью на C, могут выполняться быстрее в реализации на ML с хорошим сборщиком мусора.

Comments