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

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

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


c recursion 8-bit
person Kingsley    schedule 01.06.2020    source источник
comment
возможно, причина в том, что пространство стека слишком мало. рекурсивный вызов обычно выполняется гораздо чаще, чем повторный вызов функции   -  person mangusta    schedule 01.06.2020
comment
Читает мне, что C не очень хорошо адаптирован к некоторым навороченным 8-битным процессорам, у них есть все виды хитрых трюков, которые трудно раскрыть в C   -  person pm100    schedule 01.06.2020

Ответы (1)


arrow_upward
6
arrow_downward

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

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

person user1937198    schedule 01.06.2020
comment
В частности, это не свойственно 8-битному процессору. Скорее, дело в том, что существующий 8-битный процессор имеет совершенно ужасный дизайн ISA. - person R.. GitHub STOP HELPING ICE; 01.06.2020
comment
Я бы не назвал ISA ужасным, просто ограниченным. - person user1937198; 01.06.2020
comment
Просто чтобы добавить к этому ответу. На самом деле на 6502 для управления локальными переменными внутри рекурсивной функции можно использовать только режим косвенной адресации. Так, например. LDA (указатель), Y и STA (указатель), Y. Это ограничивает гибкость, потому что регистр Y необходимо будет постоянно перезагружать для доступа к различным локальным переменным вне кадра стека, и это также свяжет регистр Y для его использования в циклах. - person Guillermo Phillips; 02.06.2020