Почему программы используют стеки вызовов, если вложенные вызовы функций могут быть встроены?

33

Почему бы не сделать так, чтобы компилятор взял такую ​​программу:

function a(b) { return b^2 };
function c(b) { return a(b) + 5 };

и преобразовать его в программу, подобную этой:

function c(b) { return b^2 + 5 };

устраняя тем самым необходимость компьютера помнить обратный адрес c (b)?

Я предполагаю, что увеличение пространства на жестком диске и оперативной памяти, необходимых для хранения программы и поддержки ее компиляции (соответственно), является причиной, по которой мы используем стеки вызовов. Это верно?

moonman239
источник
30
Посмотрите, что произойдет, если вы сделаете это в программе с любым значимым размером. В частности, функции вызываются из более чем одного места.
user253751 12.06.15
10
Кроме того, иногда компилятор не знает, какая функция вызывается! Глупый пример:window[prompt("Enter function name","")]()
user253751
26
Как вы реализуете function(a)b { if(b>0) return a(b-1); }без стека?
pjc50
8
Где отношение к функциональному программированию?
мастов
14
@ pjc50: он хвостовой рекурсивен, поэтому компилятор переводит его в цикл с изменяемым b. Но нужно учесть, что не все рекурсивные функции могут устранить рекурсию, и даже если функция в принципе может, компилятор может быть недостаточно умен для этого.
Стив Джессоп

Ответы:

75

Это называется «встраивание», и многие компиляторы делают это как стратегию оптимизации в тех случаях, когда это имеет смысл.

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

И, очевидно, это возможно только для «частных» функций. Функции, которые доступны для внешних абонентов, нельзя оптимизировать, по крайней мере, в языках с динамическим связыванием.

JacquesB
источник
7
@Blrfl: Современные компиляторы больше не нуждаются в определениях в заголовке; они могут быть встроены через единицы перевода. Однако для этого нужен достойный компоновщик. Определения в заголовочных файлах - это обходной путь для тупых компоновщиков.
MSalters
3
«Функции, которые доступны для внешних абонентов, нельзя оптимизировать» - функция должна существовать, но любой заданный сайт вызова к ней (либо в вашем собственном коде, либо, если у них есть источник, у внешних абонентов) может быть встроен.
Random832
14
Ух ты, 28 голосов за ответ, в котором даже не упоминается причина, по которой встраивание всего невозможно: рекурсия.
мастов
3
@R ..: LTO - это оптимизация времени LINK, а не оптимизация времени LOAD.
MSalters
2
@immibis: Но если этот явный стек введен компилятором, то этот стек является стеком вызовов.
user2357112 поддерживает Monica
51

Ваш вопрос состоит из двух частей: зачем вообще иметь несколько функций (вместо того, чтобы заменять вызовы функций их определением) и зачем реализовывать эти функции с помощью стеков вызовов вместо статического размещения их данных где-то еще?

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

Тогда возникает проблема для библиотек: вы не знаете, какие функции будут вызываться откуда и как часто, поэтому «библиотеку» никогда нельзя будет скомпилировать, она будет отправлена ​​всем клиентам в каком-то удобном высокоуровневом формате, который затем будет вписано в приложение. Помимо других проблем, вы теряете динамическое связывание со всеми его преимуществами.

Кроме того, есть много причин, чтобы не использовать встроенные функции, даже если вы могли:

  1. Это не обязательно быстрее. Установка кадра стека и его разбиение - это, может быть, дюжина инструкций с одним циклом, для многих больших или циклических функций это даже не 0,1% времени их выполнения.
  2. Это может быть медленнее. Дублирование кода требует затрат, например, оно будет оказывать большее давление на кэш команд.
  3. Некоторые функции очень велики и вызываются из разных мест, встраивание их повсеместно увеличивает двоичный код, намного превышающий разумный.
  4. Компиляторы часто испытывают трудности с очень большими функциями. При прочих равных функция размера 2 * N занимает более 2 * T времени, тогда как функция размера N занимает T времени.

источник
1
Я удивлен пунктом 4. В чем причина?
JacquesB
12
@JacquesB Многие алгоритмы оптимизации являются квадратичными, кубическими или даже технически NP-полными. Каноническим примером является распределение регистров, которое является NP-полным по аналогии с раскраской графа. (Обычно компиляторы не пытаются найти точное решение, но только несколько очень плохих эвристик выполняются за линейное время.) Многие простые однопроходные оптимизации сначала требуют суперлинейного анализа, такого как все, что зависит от доминирования в потоках управления (обычно n log n времени с n базовыми блоками).
2
«У тебя действительно есть два вопроса здесь». Нет, не знаю. Только один - почему бы не рассматривать вызов функции как просто заполнитель, который, скажем, компилятор может заменить кодом вызываемой функции?
moonman239
4
@ moonman239 Тогда твоя формулировка сбила меня с толку. Тем не менее, ваш вопрос может быть разложен, как я делаю в своем ответе, и я думаю, что это полезная перспектива.
16

Стеки позволяют нам элегантно обходить ограничения, налагаемые конечным числом регистров.

Представьте, что у вас есть ровно 26 глобальных «регистров az» (или даже только 7-байтовые регистры микросхемы 8080). И каждая функция, которую вы пишете в этом приложении, разделяет этот плоский список.

Наивным началом было бы выделение первых нескольких регистров для первой функции, и, зная, что это заняло всего 3, начните с «d» для второй функции ... Вы быстро заканчиваете.

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

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

(рекурсия великолепна, но если бы вам когда-либо приходилось манипулировать регистрами без стека, вы бы по- настоящему оценили стеки.)


Я предполагаю, что увеличение пространства на жестком диске и оперативной памяти, необходимых для хранения программы и поддержки ее компиляции (соответственно), является причиной, по которой мы используем стеки вызовов. Это верно?

Несмотря на то, что в наши дни мы можем встроить больше, («большая скорость» всегда хороша, «меньшее количество килобайт сборок» означает очень мало в мире видеопотоков) Основное ограничение заключается в способности компилятора сглаживать определенные типы шаблонов кода.

Например, полиморфные объекты - если вы не знаете один-единственный тип объекта, который вам передадут, вы не сможете сплющить; Вы должны посмотреть на vtable возможностей объекта и вызвать через этот указатель ... тривиально, чтобы сделать во время выполнения, невозможно встроить во время компиляции.

Современный набор инструментов может успешно встроить полиморфно определенную функцию, когда он сгладил достаточно вызывающего (-ых) вызова (-ов), чтобы точно знать , какой вариант obj:

class Base {
    public: void act() = 0;
};
class Child1: public Base {
    public: void act() {};
};
void ActOn(Base* something) {
    something->act();
}
void InlineMe() {
    Child1 thingamabob;
    ActOn(&thingamabob);
}

в приведенном выше примере компилятор может выбрать статическое встраивание, начиная с InlineMe и заканчивая тем, что находится внутри act (), а также не нужно трогать какие-либо виртуальные таблицы во время выполнения.

Но любая неопределенность в какой аромат объекта оставит его как призыв к дискретной функции, даже если некоторые другие вызовы той же функции являются встраиваемыми.

Ксандер
источник
11

Случаи, которые этот подход не может обработать:

function fib(a) { if(a>2) return fib(a-1)+fib(a-2); else return 1; }

function many(a) { for(i = 1 to a) { b(i); };}

Там являются языки и платформа с ограниченными или нет вызовов стеков. Микропроцессоры PIC имеют аппаратный стек, ограниченный от 2 до 32 записей . Это создает ограничения дизайна.

COBOL запрещает рекурсию: https://stackoverflow.com/questions/27806812/in-cobol-is-it-possible-to-recursively-call-a-paragraph

Введение запрета на рекурсию означает, что вы можете статически представлять весь callgraph программы как DAG. Затем ваш компилятор может выдать одну копию функции для каждого места, из которого она вызывается, с фиксированным переходом вместо возврата. Не требуется стек, просто больше программного пространства, что может быть довольно много для сложных систем. Но для небольших встроенных систем это означает, что вы можете гарантировать отсутствие переполнения стека во время работы, что будет плохой новостью для управления вашим ядерным реактором / реактивной турбиной / дросселем автомобиля и т. Д.

pjc50
источник
12
Ваш первый пример - базовая рекурсия, и вы правы там. Но ваш второй пример - цикл for, вызывающий другую функцию. Встраивание функции отличается от развертывания цикла; функция может быть встроена без разматывания петли. Или я пропустил некоторые тонкие детали?
jpmc26
1
Если ваш первый пример предназначен для определения ряда Фибоначчи, это неправильно. (Он пропускает fibзвонок.)
Paŭlo Ebermann
1
Хотя запрещение рекурсии действительно означает, что весь граф вызовов может быть представлен как группа обеспечения доступности баз данных, это не означает, что можно перечислить полный список вложенных последовательностей вызовов в разумном количестве места. В одном из моих проектов для микроконтроллера с 128 КБ пространства кода я допустил ошибку, запросив граф вызовов, который включал все функции, которые могли бы повлиять на максимальное требование к параметру-ОЗУ, и этот граф вызовов был больше, чем концерт. Полный граф вызовов был бы еще длиннее, и это было для программы, которая помещается в 128 КБ пространства кода.
Суперкат
8

Вы хотите встроенную функцию , и большинство ( оптимизирующих ) компиляторов делают это.

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

Заметьте также, что вставка, даже когда это легко возможно, не всегда эффективна: вы (на самом деле ваш компилятор) могли бы увеличить размер кода настолько, что кэши ЦП (или предиктор ветвления ) будут работать менее эффективно, и это заставит вашу программу работать помедленнее.

Я немного сосредоточен на функциональном стиле программирования , так как вы пометили свой вопрос как таковой.

Обратите внимание, что вам не нужно иметь какой-либо стек вызовов (по крайней мере, в машинном смысле выражения «стек вызовов»). Вы можете использовать только кучу.

Итак, взгляните на продолжения и прочитайте больше о стиле передачи продолжения (CPS) и преобразовании CPS (интуитивно, вы можете использовать замыкания продолжения в качестве ограниченных «фреймов вызова», размещенных в куче, и они в некотором роде имитируют стек вызовов; тогда вам нужен эффективный сборщик мусора ).

Эндрю Аппель написал книгу Compiling с продолжениями и старой бумаги сборки мусора может быть быстрее , чем распределение стека . См. Также статью А. Кеннеди (ICFP2007), продолжение с продолжением, продолжение

Я также рекомендую прочитать книгу Куиннека « Лисп в маленьких частях» , в которой есть несколько глав, связанных с продолжением и компиляцией.

Также обратите внимание, что некоторые языки (например, Brainfuck ) или абстрактные машины (например, OISC , RAM ) не имеют каких-либо средств вызова, но по-прежнему полны по Тьюрингу , поэтому вам (в теории) даже не нужен механизм вызова функций, даже если это чрезвычайно удобно. Кстати, некоторые старые архитектуры набора команд (например, IBM / 370 ) даже не имеют аппаратного стека вызовов или машинной инструкции принудительного вызова (у IBM / 370 были только машинные инструкции Branch and Link )

Наконец, если вся ваша программа (включая все необходимые библиотеки) не имеет рекурсии, вы можете хранить адрес возврата (и «локальные» переменные, которые фактически становятся статическими) каждой функции в статических местоположениях. Старые компиляторы Fortran77 делали это в начале 1980-х годов (поэтому скомпилированные программы в то время не использовали стек вызовов).

Василий Старынкевич
источник
2
Это очень спорно является КПС не имеет «стек вызовов». Это не в стеке , мистическая область обычной оперативной памяти, которая имеет небольшую аппаратную поддержку %espи т. Д., Но она по-прежнему сохраняет эквивалентную бухгалтерию в точно названном стеке спагетти в другой области оперативной памяти. Адрес возврата, в частности, по существу закодирован в продолжении. И, конечно, продолжения не быстрее (и, как мне кажется, это то, к чему стремился OP), чем вообще не совершать звонки через встраивание.
Старые документы Аппеля утверждали (и демонстрировали с помощью бенчмаркинга), что CPS может быть столь же быстрым, как и стек вызовов.
Василий Старынкевич
Я скептически отношусь к этому, но независимо от того, что я не утверждал.
1
На самом деле, это было в конце 1980-х годов на рабочей станции MIPS. Вероятно, иерархия кеша на современных компьютерах несколько снизит производительность. Было несколько работ, в которых анализировались заявления Аппеля (и действительно, на современных машинах распределение стеков могло бы быть немного быстрее - на несколько процентов - чем тщательно продуманной сборкой мусора)
Василий Старынкевич
1
@Gilles: Многие новые ядра ARM, такие как Cortex M0 и M3 (и, возможно, другие, такие как M4), поддерживают аппаратный стек для таких вещей, как обработка прерываний. Кроме того, набор команд Thumb включает в себя ограниченный поднабор команд STRM / STRM, который включает STRMDB R13 с любой комбинацией R0-R7 с / без LR и LDRMIA R13 любой комбинации R0-R7 с / без ПК, что эффективно обрабатывает R13 как указатель стека.
Суперкат
8

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

Однако большие функции, которые в свою очередь вызывают другие функции, могут привести к огромному взрыву в размере программы, если все будет встроено.

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

Для чего это стоит: вы можете иметь вызываемые функции без стека вызовов. Например: IBM System / 360. При программировании на таких языках, как FORTRAN на этом оборудовании, счетчик программ (обратный адрес) будет сохранен в небольшом разделе памяти, зарезервированном непосредственно перед точкой входа в функцию. Он допускает повторное использование функций, но не допускает рекурсивный или многопоточный код (попытка рекурсивного или реентерабельного вызова приведет к перезаписи ранее сохраненного адреса возврата).

Как объясняют другие ответы, стеки это хорошие вещи. Они облегчают рекурсию и многопоточные вызовы. Хотя любой алгоритм, закодированный для использования рекурсии, может быть закодирован без использования рекурсии, результат может быть более сложным, более сложным в обслуживании и менее эффективным. Я не уверен, что архитектура без стека вообще может поддерживать многопоточность.

Zenilogix
источник