Comments 21
Столько много букв, инструкция CALL общая для всех "абстрактных" названий функций и методов в языках высокого уровня
Инструкция CALL соответствует первой из трёх рассмотренных семантических интерпретаций, и статья как раз о том, что она сама по себе далеко не является общей, а уж её реализация - вообще тонкое дело.
Собственно, вы в своём комментарии озвучили как раз именно то распространённое заблуждение, для борьбы с которым и предназначена статья.
Экзотическа, в чем приемущества сохранения обратного вызова в регистре?
Откройте любой сишный исходник на git ... openssh, gnome и другие, чтобы понять что делает конкретно одна функция, нужно не менее 3-5 локальных функциях "провалится", чтобы до браться до функционала... так и регистров не хватит
Пожалуйста, дайте себе труд прочесть статью, так как на ваши реплики в ней содержатся подробные ответы (которые вы назвали "много букв"). А регистр в данном случае нужен только один.
я прочитал, и не понял, где "заблуждение"... Хорошо, регистр один, а если вызов процедуры происходит внутри другой процедуры, а если таких вызовов еще несколько, получается вызов новой процедуры затирает старый, где мы должны сохранить старый?
А где вообще мы должны сохранять регистры при вызове другой процедуры? В области сохранения. Которая при отсутствии рекурсии и реентерабельности может быть статической.
Я правильно понимаю, у каждой функции есть область сохранения, где она хранит все регистры и в том числе регистр в котором был сохранен обратный адрес?!
Да.
Ну это дополнительные накладные расходы
Рекурсивный вызов можно добиться на том же х86, то есть первый вызов CALL, а последующие JMP, с небольшими танцами с бубном можно использовать теже самые локальные переменные в стеке...
На x86 нет команд группового сохранения и восстановления всех регистров в области сохранения, как STM/LM у мейнфрейма. Поэтому издержки будут больше. Но всё равно же регистры сохранять как-то надо. Даже если соглашение о связях этого не требует, то логика пользовательской программы всё равно никуда не девается.
Насчёт бесстекового способа вставлю свои пять копеек.
Исторически в OS/360 каждое динамическое выделение памяти производилось путём обращения к супервизору (грубо говоря, к ядру ОС): ассемблерная программа, желающая получить память, использовала макрокоманду GETMAIN ("main" -- от названия "основная память", main storage, использовавшейся и использующейся поныне для обозначения ОЗУ в IBMовских мэйнфреймах), ну а эта макрокоманда разворачивалась в загрузку параметров (в первом приближении -- требуемого объёма памяти) в регистры процессора и выдачу команды SVC, приводящей к прерыванию по вызову супервизора. Сейчас такой способ кажется диким: прерывание на современных процессорах -- очень долгий процесс по сравнению с простым выполнением команд, но тогда, в середине 1960-х и в 1970-х, особой разницы во времени выполнения не было.
Такая достаточно современная архитектура, как ARM, хотя и имеет стек, позволяет реализовать вызов подпрограмм без его использования: команда BL, вызывающая подпрограмму, сохраняет адрес возврата в регистре LR, а не записывает его в стек, как это делает, скажем, CALL на IA-32 (x86). Соответственно, потенциально можно реализовать ту же схему вызова, что и в IBMовских мэйнфреймах. Правда, в ARM адрес возврата заносится всегда в один и тот же регистр, а в мэйнфреймах можно использовать любой из 16 регистров общего назначения, но это уже технические детали.
Система инструкции ARM - это старая система (1983) и это пример, как её не нужно делать! В настоящих современных архитектурах производиться разделение пользовательского стека и стека для хранения обратных вызовов и состояний.
Это разделение ещё в 6502 было.
увы, не реализованов 6502
регистры 6502: A - аккумулятор, 8 бит; X, Y - индексные регистры, 8 бит; PC - счетчик команд, 16 бит; S - указатель стека, 8 бит; P - регистр состояния. Вызов процедуры и прерывания сохраняют счетчик команд в стек.
Не было. Там самый что ни на есть обычный стек, только объём всего 256 байт.
Ну да, поэтому для контекста пользовательской программы там не было места. Вот локальные переменные в нём и не содержали.
Плюс, там были короткие команды для доступа к нулевой странице памяти (0000-00FF), которые работали быстрей обычных, длинных. Плюс, типичное применение машинок на процах такого уровня -- выполнение всего одной задачи, а значит, вся память -- её, повторная входимость обычно не нужна и т.д. и т.п. Так что вызовы подпрограмм нередко выполнялись по "гибридной модели", так сказать: сам вызов технически использовал стек для адреса возврата (команды JSR и RTS), а параметры нередко лежали в предопределённых ячейках памяти.
Лично я предпочитаю иметь модель примерно как в ARM: где я сам могу либо традиционным "стековым" образом вызывать подпрограммы, либо сделать, как в Системе 360, либо некое промежуточное решение. В общем, когда есть гибкость. Правда, она востребована, только если пишешь на ассемблере -- а сейчас это редкость.
Система инструкции ARM - это старая система (1983)
Но она новее и мэйнфреймов (анонс в 1964 году, продажи -- с 1965), и 8086/88, из коего выросла IA-32 (1977-й, если память не изменяет).
В настоящих современных архитектурах производиться разделение пользовательского стека и стека для хранения обратных вызовов и состояний
Спорная вещь. Но, замечу, на ARMе отдельные стеки для адресов возврата и для, скажем, данных сделать элементарно как раз благодаря его системе команд.
Я пишу этот комментарий ещё не прочитав вторую часть, но уже сейчас я со многим не согласен. Память для кадра локальных переменных функции можно выделять на стеке или в куче, оба этих региона ограничены, не только стек. На нём сильно проще выделить память (константное время) и проще вернуть.
Но есть ещё один момент. В функциональных языках поддерживаются значения-функции, которые запомнили контекст, в котором были определены, включая локальные переменные этого контекста. Такое хранилище контекста функции называется "замыкание"/"closure", и, поскольку для него порядок создания не соответствует обратному порядку удаления, оно создаётся на куче. А раз уж там живут локальные переменные, то имеет смысл его использовать в качестве кадра локальных переменных функции.
А с чем именно Вы не согласны?
Конечно, правильно реализованные замыкания требуют размещения связанных переменных в куче. Но это относится не только к замыканиям, но и к многим другим динамическим структурам данных – без кучи вообще жить тяжело. Обсуждаемый вопрос же состоит не в том, можно ли вообще в программе обойтись без кучи, а в том, всегда ли нужен стек для вызова функций. На замыканиях же не сошёлся свет клином, даже в функциональных языках.
Что касается ограничений. Память для локальных переменных можно выделить тремя способами: в статическом объектном коде, на стеке и в куче. Все эти способы имеют свои плюсы и свои минусы. Однако, говоря об ограничениях, я имею в виду вот что. Без кучи вообще обойтись в большинстве случаев нельзя, поэтому память для неё так и так придётся резервировать. Обычно это вся доступная программе память компьютера, за вычетом сегмента кода, сегмента статических данных и стеков. И если с сегментами кода и статических данных всё ясно, то стеки (по числу параллельных процессов) вы должны резервировать по их максимально возможному размеру, и этот – только потенциальный – размер каждого из них будет отбираться у фактического размера кучи. Хорошо, когда у вас для этого есть виртуальная память и 64-разрядное адресное пространство, и плохо, когда этого нет. Хотя замечу, что даже в 64-разрядных архитектурах в силу традиции выделение программистом больших сегментов под стеки на практике является исключительной редкостью. Не так просто будет найти реальную программу, в которой при создании нитки ей отводится хотя бы пара гигабайтов стека.
А в качестве казуистического примера ещё можно вспомнить упоминавшийся здесь процессор 6502, в котором стек был ограничен 256 байтами и находился в фиксированных адресах памяти. Я слышал, что 6502 до сих пор работает в каких-то устройствах в качестве части микроконтроллера. Так что случаи разные бывают.
На самом деле многие (в том числе наиболее распространённые) реализации Common Lisp на x86 используют стек при вызове функций, и там проблема переполнения стека проявляется только в путь. Особенно учитывая, что SBCL умеет оптимизацию хвостовой рекурсии только по запросу, а GNU Common Lisp вообще не умеет. Это одна из причин, по которым я предпочитаю Scheme.
Вызовы функций, стек, куча и продолжения. Часть 1