Почему разрешение рекурсии делает C медленнее / неэффективнее на 8-битных процессорах

Question

Ответы на этот вопрос об эффективности компилятора для 8-битных процессоров, похоже, подразумевают, что включение рекурсии делает язык C неэффективным на этих архитектурах. Я не понимаю, чем рекурсивный вызов функции (одной и той же функции) отличается от простого повторного вызова различных функций.

Я хотел бы понять, почему это так (или почему так думают, казалось бы, образованные люди). Я мог предположить, что, возможно, в этих архитектурах просто нет места для стека, или, возможно, push/pop неэффективны - но это всего лишь предположения.

Answer 1

Потому что для эффективной реализации стека C вам нужна возможность эффективно загружать и сохранять произвольные смещения в текущем кадре. Например, процессор 8086 обеспечивал режимы индексированного и основанного адреса, что позволяло загружать переменную стека в рамках одной инструкции. С 6502 вы можете сделать это только с регистрами X или Y, и, поскольку это единственные регистры общего назначения, резервирование одного для указателя стека данных чрезвычайно дорого. Z80 может делать это со своими регистрами IX или IY, но не с регистром указателя стека. Однако выполнение индексированных инструкций загрузки на Z80 занимает много времени, поэтому это по-прежнему дорого, наряду с тем фактом, что вы либо резервируете второй регистр для указателя стека, либо должны загружать указатель стека из регистра SP в любое время. хотите получить доступ к переменным.

Для сравнения: если рекурсивные вызовы не поддерживаются, то второй экземпляр функции не может запускаться внутри вызова, пока существующий все еще выполняется. Это означает, что единовременно требуется только один набор переменных, и вы можете просто выделить каждой функции свой собственный статический фрагмент памяти для использования для переменных. Поскольку память имеет фиксированное расположение, вы можете использовать загрузку с фиксированным адресом. Некоторые реализации fortran использовали этот подход.