|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Andrey Tarasevich 2:5020/400 09 Jan 2002 03:32:09 To : Andrew Ezhguroff Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- Andrew Ezhguroff wrote: > > AT> Действительными накладным расходом тут может являеться только > AT> формирование кадра стека для доступа к переменным _всех_ охватывающих > AT> функций, в то время как фактически нужен доступ только к некоторым из > AT> них. Hо это сравнительно легко опитмизируемый момент. Качественный > AT> компилятор сведет этот накладной расход к нулю. > > ИМХО, все несколько сложнее. Ведь существует рекурсия (и прямая и > косвенная). Поэтому для каждой подпрограммы придется организовывать свой > стек кадров (скорее это будет единый стек, в котором для каждой подпрограммы > будет вестись свой список активаций). Да, компилятор это может > оптимизировать, но только частично. (Антиоффтопик: тут мы уже говорим об алгоритмах, т.е. это не оффтопик.) Что-то я не вижу в этом никаких сложностей. Точнее, я не вижу никакой разницы в организации кадров стека при наличии и отсутствии рекурсии. Зачем вести список активаций (а уж тем более заводить свой стек кадров для каждой функции)? Рекурсивная функция в Паскале имеет доступ только к текущему контексту, т.е. она имеет доступ только к самому позднему своему кадру стека и только к самому позднему кадру стека каждой охватывающей функции. Доступа к предыдущим своим (и чужим) кадрам стека она не имеет и ничего о них не знает. Если некоторая функция F вложена последовательно в функции A, B, C, D, E (A - самая внешняя, E - непосредственно охватывает F), то в тривиальной реализации кадр стека функции F содержит, помимо локальных переменных F, пять указателей на _последние_ кадры стека функции A...E. Получение адреса некоторой переменной охватвающей функции представляет собой выборку значения соответствуюшего указателя и прибавления к нему соответствующего смещения. Все. Сложность этой операции константна в том смысле, что не зависит ни от глубины вложенности, ни от глубины рекурсии. При вызове F, эта указательная часть ее кадра стека формируется вызывающим кодом по следующему алгоритму: Если F вызывается из E, то вызывающий код кладет в формируемый кадр указатели на кадры стека A...D из текущего кадра стека E (они там, разумеется есть) и затем добавляет туда указатель на текущий кадр стека функции E. Если F вызывается из F' (функция, прямо или опосредованно вложенная в E), то пять первых указателей из кадра стека F' просто копируются в формируемый кадр стека F. Причем допускается, что F' == F или F' вложено в F. Больше ниоткуда функция F вызвана быть не может. Вот и все. Менее тривиальная реализация будет анализировать код F и определять, указатели на кадры стека каких охватывающих функций действительно нужны в F. Подготовка только необходимых указателей может существенно сократить стоимость вызова, особенно при большой глубине вложенности. Все это делается на стадии компиляции. При этом надо учитывать и функции, вызываемые из F прямо или опосредованно. Т.е. анализ тут не совсем тривиальный. А если F содержит косвенные вызовы (через указатель), то от такой опимизации придется совсем отказаться (а есть в стандартном Паскале косвенные вызовы?). > > AT> "Чистокровные" глобальные переменные "рассыпью" в программировании на С > AT> _не_ _применяются_. Максимум, что можно увидеть в С программе > AT> глобального - это единичные глобальные указатели на _локальную_ > AT> структуру. > > Глобальные и статические переменные используются в Си очень активно. И, > кстати, в Паскале нет прямого аналога статическим переменным (опять > приходится эмулировать их через переменные охватывающей подпрограммы). В Борланде почти 100%-ным аналогом С-шных статических переменных, объявленных в локальном scope, являются типизированные "константы". Я не знаю, есть ли они в стандартном Паскале. > AT> Работающие > AT> программы на С с существенным хранением глобальных переменных прямо в > AT> блоке глобальных данных бывают только в программистских байках. > > Hе только глобальные, но и статические. И во многих случаях объявлять > массивы статическими удобнее (простейший пример - таблица перекодировки > символов). Большая проблема глобальных (и статических) переменных - нереентерабельность кода, использующего эти переменные. В первую очередь поэтому их и избегают на практике. Исключением являются константы. Твоя таблица перекодировки - как раз такая константа, т.е. пример непоказательный. Best regards, Андрей. --- ifmail v.2.15dev5 * Origin: good enough (2:5020/400) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/6682e75bff49.html, оценка из 5, голосов 10
|