Оптимизация вызовов хвоста C

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

Кроме того, что послужило основанием для отказа от оптимизации вызова хвоста из стандарта?

источник

2010-08-18 dsimcha

Связано: http://stackoverflow.com/questions/2250727/regarding-stack-reuse-of-a-function-calling-itself –

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

источник

2010-08-18 16:27:51 AnT

Чтобы ответить на последний вопрос: стандарт должен определенно не делать никаких утверждений об оптимизации. Там могут быть среды, где ее более или менее сложно реализовать.

источник

2010-08-18 16:28:16 Frank

+11

Было бы неправильно, если бы стандарт требовал, чтобы в то время как циклы выполнялись в постоянной памяти? (за исключением распределений в цикле while) Было бы неправильно, если бы стандарт требовал, чтобы хвостовые рекурсивные функции выполнялись в постоянной памяти? – Jules

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

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

источник

2010-08-18 16:35:48 bta

Было бы очень просто просто потребовать, чтобы шаблоны вызовов, удовлетворяющие определенному требованию, использовали постоянное пространство памяти. Это часть того, как ведет себя язык, и эффекты, если вы можете называть миллионы и миллионы раз в программе, не возвращаясь (поскольку одна программа, которую я написал, опираясь на компилятор, TCO делает). –

Я думаю, что оптимизация хвостового звонка должна быть гарантирована только там, где ожидается рекурсии; то есть на языках, которые поощряют или применяют стиль функционального программирования. (С этими типами языков вы можете обнаружить, что петли for или while либо сильно обескуражены, либо воспринимаются как неэлегантные, либо, возможно, даже полностью отсутствуют на этом языке, поэтому вы прибегаете к рекурсии по всем этим причинам и, возможно, к более.)

Язык программирования C (IMHO) явно был не разработан с функциональным программированием в виду. Существуют все виды петлевых конструкций, которые обычно используются в пользу рекурсии: for, do .. while, while. На таком языке было бы нецелесообразно предписывать оптимизацию хвостового вызова в стандарте, потому что не требуется строго гарантировать рабочие программы.

Контрастность этого снова с функциональным языком программирования, который не имеет while: Это означает, что вы будете need recursion; что, в свою очередь, означает, что язык должен быть уверен, что при многих итерациях переполнение стека не станет проблемой; таким образом, официальный стандарт для такого языка может выбрать предписание оптимизации хвостового вызова.

P.S .: Примечание небольшой недостаток в моей аргументации для оптимизации хвостового вызова. К концу, я упоминаю переполнение стека. Но кто говорит, что вызовы функций всегда требуют наличия стека? На некоторых платформах вызовы функций могут быть реализованы совершенно по-другому, и переполнение стека никогда не будет проблемой. Это будет еще одним аргументом против предписывающей оптимизации хвостового вызова в стандарте. (Но не поймите меня неправильно, я вижу достоинства таких оптимизаций, даже без стека!)

источник

2010-08-18 16:46:56 stakx

Однако реализованный общий случай вызова функции всегда требует сохранения и восстановления некоторого состояния. Следовательно, всегда будут такие функции, что слишком много вызовов вложенных функций заполняют доступную память для хранения этого состояния. Обычная структура данных для этого представляет собой стек в фиксированном блоке памяти, но это можно сделать по-другому. Исключение вызова хвоста может избежать этого сохранения и восстановления для некоторых функций, но нетривиальная функция, которая вызывает себя дважды, должна будет сохранить состояние для второго вызова. – jilles

@jilles: Именно, оптимизация хвостовых вызовов должна помочь сохранить память независимо от того, как работают вызовы функций.Однако одна черта стека процессора заключается в том, что он обычно относительно ограничен по мощности; более того, чем, например, память кучи. Вот почему я упоминал переполнение стека, но не более общее условие отсутствия памяти; Я предположил, что вам понадобится почти невероятная часть рекурсии для истощения, например. 2 ГБ памяти. – stakx

Хотя современные компиляторы МОГУТ оптимизировать хвостовые вызовы, если вы включите оптимизацию, ваши отладочные сборки, вероятно, будут работать без него, чтобы вы могли получать трассировки стека и входить/выходить из кода и замечательные вещи вроде этого. В этой ситуации оптимизация хвостового вызова нежелательна.

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

источник

2014-05-01 17:34:55

Бывают ситуации, когда оптимизация хвостового вызова потенциально может нарушить ABI или, по крайней мере, будет очень сложной для реализации в семантическом сохранении. Например, подумайте о независимом от позиции коде в разделяемых библиотеках: некоторые платформы позволяют программам динамически связываться с библиотеками, чтобы сохранить основную память, когда разные приложения зависят от одной и той же функциональности. В таких случаях библиотека загружается один раз и отображается в каждую из виртуальной памяти программы, как если бы это было единственное приложение в системе. В UNIX, а также в некоторых других системах это достигается за счет использования независимого от положения кода для библиотек, поэтому адресация относится скорее к смещению, чем к абсолютному, к фиксированному адресному пространству. Однако на многих платформах независимый от положения код не должен быть оптимизирован для хвостового вызова. Проблема заключается в том, что смещения для навигации по программе должны храниться в реестрах; на Intel 32-бит, %ebx используется, который является зарегистрированным регистром; другие платформы следуют этому понятию. В отличие от функций, использующих обычные вызовы, те, кто развертывает хвостовые вызовы, должны восстанавливать регистры, сохраненные вызываемым абонентом, до того, как они отключаются к подпрограмме, а не когда они возвращаются. Обычно это не проблема, потому что на данный момент самая главная функция вызова не заботится о значении, хранящемся в %ebx, но независимый от позиции код зависит от этого значения от каждой команды перехода, вызова или ветвления.

Другие проблемы могут быть ожидающими очистки в объектно-ориентированных языках (C++), что означает, что последний вызов в функции на самом деле не является последним вызовом - очистками являются. Следовательно, компилятор обычно не оптимизирует, если это так.

Также setjmp и longjmp проблематичны, конечно, так как это эффективно означает, что функция может завершить выполнение более одного раза, прежде чем она на самом деле закончится. Трудно или невозможно оптимизировать во время компиляции!

Есть, вероятно, больше технических причин, о которых можно подумать. Это лишь некоторые соображения.

источник

2018-02-17 10:04:27 nondeterministic

ответ

Смежные вопросы