LINUX.ORG.RU

Так ли нужна оптимизация хвостовых вызовов?

 , , ,


0

4

Вон в rust считают, что не нужна:

- Tail calls «play badly» with deterministic destruction. Including deterministic drop of ~ boxes. Not to say that they're not composable, but the options for composing them are UI-awkward, performance-penalizing, semantics-complicating or all of the above.

- Tail calls also «play badly» with assumptions in C tools, including platform ABIs and dynamic linking.

- Tail calls require a calling convention that is a performance hit relative to the C convention.

- We find most cases of tail _recursion_ convert reasonably well to loops, and most cases of non-recursive tail calls encode state machines that convert reasonably well to loops wrapped around enums. Neither of these are _quite_ as pretty as the tail-call-using variants, but they do work and are «as fast»*, as well as idiomatic for C and C++ programmers (who are our primary audience).

https://mail.mozilla.org/pipermail/rust-dev/2013-April/003557.html

★★★★★

Последнее исправление: cetjs2 (всего исправлений: 1)
Ответ на: комментарий от anonymous

Зачем? Прошлый правый уже полностью обработан, в прошлом правом только ret остался, который можно спокойно убрать с ТСО и вернуться сразу «домой».

нет. У прошлого правого(*) просмотрен только левый, в котором ничего нет. И вернуться надо опять на правый(*), и посмотреть его правый.

Такого быть не может. Нарисуй и разбери на бумажке, если так не получается.

что я должен рисовать-то? Где код с jmp? Сам пиши код и рисуй, что у тебя не получится. Я и так знаю, в чём тут дело.

drBatty ★★
()
Ответ на: комментарий от qulinxao

речь про случай «линейного» последнесторонего дерева

слушай, я про _любое_ дерево, в котором может быть что угодно, и как угодно. Алгоритм с рекурсией на нём работает. А после ТСО ломается. И я не знаю, как это чинить. предлагаешь чинить дерево, а не алгоритм?

короче концевой вызов допускает реализацию с замедлением(в идеале нулевой рост) роста стэка вот и всё.

да, только это надо дерево как-то лечить.

drBatty ★★
()
Ответ на: комментарий от qulinxao

именно с этой точки зрения оказывается понятной почему имена аргументов в первой версии С были в заголовке - а их типы в секции между заголовком функции и её телом.

ну это ещё в K&R написано.

drBatty ★★
()
Ответ на: комментарий от drBatty

нет. У прошлого правого(*) просмотрен только левый, в котором ничего нет.

Такого быть не может. Если у прошлого правого просмотрен левый, значит мы _уже_ находимся в правом прошлого правого. И если мы дошли до рет'а, значит его просмотрели. Вообще непонятно о чем спор, я тебе привел пример твоего кода с деревом, в котором стек не растет.

что я должен рисовать-то? Где код с jmp?

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

Сам пиши код и рисуй, что у тебя не получится.

:cry:

Уже получилось. Код я предоставил.

Я и так знаю, в чём тут дело.

Неправильно знаешь, выходит, раз твои знания противоречат экспериментальным фактам.

anonymous
()
Ответ на: комментарий от anonymous

Ты читать не умеешь? Написано же - расти не будет в том случае, если длина левых поддеревьев ограничена. Вот пример:

блжад. Оно всегда ограничено. Высотой дерева. Это у тебя какие-то особые деревья, там да, стек растёт пропорционально левой высоте.

В принципе, да, запоминать это всё нужно только для входа в левое дерево, только мне что-то не сообразить, как это в коде x86 будет выглядеть?

drBatty ★★
()
Ответ на: комментарий от yyk

тогда почему там нет TCO, если в конце стоит вызов другой функции?

ТСО формально везде есть. Имеется ввиду, что вызов p не ТСО. А взыов print - ТСО, понятное дело.

anonymous
()
Ответ на: комментарий от drBatty

А после ТСО ломается.

Почему у меня ничего не ломается?

anonymous
()
Ответ на: комментарий от yyk

Важно. Ибо если она что-то делает там, где у тебя // (***2), то это не ТСО. А если ничего не делает, то после отработки правого обхода x тебе уже нафиг не нужен, ибо тебе осталось только что вернуться на пред. уровень. А если и там это правый обход, то тебе тоже ничего не надо, кроме как вернуться на пред. уровень и т.д.

в принципе - да. Не нужно ничего, кроме как вернуться. Ладно, x->right это перейти, а возвращаться как? Повесить ещё по указателю на каждый узел? Не жирно-ли будет?

drBatty ★★
()
Ответ на: комментарий от drBatty

Это у тебя какие-то особые деревья, там да, стек растёт пропорционально левой высоте.

Да нет, это вполне обычное дерево. Просто из-за ТСО правые вызовы оптимизируются. В результате с правой высотой стек не растет, а с левой - растет. Если я сделаю, чтобы хвостовой вызов обходил левое поддерево, а не правое, то будет стек расти с правой высотой, а с левой не будет. Хотя дерево останется тем же самым.

anonymous
()
Ответ на: комментарий от dave

Можно не мучаться, да и просто взять F# async - там уже все придумано за нас. Будет тебе обход дерева без съедания стека просто за красивые глаза, если я правильно уловил суть вашей беседы - особо не вчитывался.

ЕМНИП там кучу будет есть, а не стек. Так я и в C++ могу.

drBatty ★★
()
Ответ на: комментарий от anonymous

ТСО формально везде есть. Имеется ввиду, что вызов p не ТСО. А взыов print - ТСО, понятное дело.

не везде, ибо не везде перед ret есть только call. Вызов p из p - тот самый tail recursion. Любой другой вызов - TCO. В том коде - putchar. Почему там нет ТСО?

yyk ★★★★★
()
Ответ на: комментарий от drBatty

Ладно, x->right это перейти, а возвращаться как?

А никак. Зачем? В этой ветке исполнения уже все сделали, не надо к ней возвращаться. В этом смысл ТСО - не возвращаться туда, куда возвращаться не нужно.

anonymous
()
Ответ на: комментарий от yyk

не везде, ибо не везде перед ret есть только call.

Я не рассматриваю операторы, так что - везде.

Почему там нет ТСО?

Так как оно есть везде вообще, то вопрос о его наличии смысла не несет.

anonymous
()
Ответ на: комментарий от drBatty

как это в коде x86 будет выглядеть?

это for(ptr = ..., ptr != null, ptr = ptr->next_ptr);

anonymous
()
Ответ на: комментарий от anonymous

ТСО формально везде есть. Имеется ввиду, что вызов p не ТСО. А взыов print - ТСО, понятное дело.

Тогда почему ты утверждал, что там ТСО нет? :)

yyk ★★★★★
()
Ответ на: комментарий от anonymous

При входе в p надо сохранить старое значение s и адрес возврата, чтобы потом выполнить putchar('Z');

зачем это всё надо для putchar('Z')?

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

зачем переставлять то, что ни на что не влияет? К тому-же это плохая перестановка, ибо если печатать static int, то до перестановки будет 3 2 1, а после 1 2 3. Меняется относительный порядок функции.

drBatty ★★
()
Ответ на: комментарий от drBatty

зачем это всё надо для putchar('Z')?

А это уже к ТСО не относится.

зачем переставлять то, что ни на что не влияет?

Переставить затем, чтобы вызов р стал хвостовым и стек не отвалился. А _можно_ переставить именно потому, что оно ни на что не влияет.

anonymous
()
Ответ на: комментарий от yyk

ТСО тут практическая, ибо по выходу из putchar совершенно всё равно, портил он там что или нет. И куда возвращаться из putchar - в p, чтобы сразу вернуться в место её вызова, или сразу в это место - безразлично.

вот только после функции порядок вызовов будет противоположный порядку вызовов до функции. Если просто печатать Z, да, без разницы. Впрочем, порядок будет противоположен функции p, а раз функции независимы, то и не важно, в каком порядке они выполняются (или не?).

Но если печатать *s, то TCO ломается - строка печатается наоборот. Символы загоняются в стек, а печатаются перед возвратом, начиная с последнего.

Код давай

дык поменяй 'Z' на *s.

drBatty ★★
()
Ответ на: комментарий от anonymous

Толку мне от умножения TCO, если это тривиальная функция?

Нету толку. Но это хвостовой вызов, в языках с proper TCO он будет оптимизирован.

там нечего оптимизировать.

drBatty ★★
()
Ответ на: комментарий от drBatty

К тому-же это плохая перестановка, ибо если печатать static int, то до перестановки будет 3 2 1, а после 1 2 3.

Ну тогда переставлять нельзя, а если переставлять нельзя - то p хвостовым никогда не будет и стек будет съеден без вариантов.

anonymous
()
Ответ на: комментарий от drBatty

там нечего оптимизировать.

Почему же, есть (один фрейм вызова и замена call+ret на джамп), и, как я уже сказал, языки с ТСО соптимизируют.

anonymous
()
Ответ на: комментарий от drBatty

дык поменяй 'Z' на *s.

Соптимизирован будет _хвостовой_ вызов, а это вызов print, а не вызов p.

anonymous
()
Ответ на: комментарий от anonymous

Да нет, это вполне обычное дерево. Просто из-за ТСО правые вызовы оптимизируются. В результате с правой высотой стек не растет, а с левой - растет.

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

drBatty ★★
()
Ответ на: комментарий от drBatty

там непонятно что происходит

Ну так учи стандарт схемы, станет понятно.

и есть-ли TCO.

ТСО там есть по 2 причинам:

1. стандарт схемы требует, чтобы оно было

2. потребление памяти не растет.

Давай C код.

с код ничего не даст, т.к. в сишке нету proper TCO. Можешь предложить другой вариант кроме схемы? Я просто что-то не могу вспомнить альтернатив.

anonymous
()
Ответ на: комментарий от drBatty

у меня обычно более-менее сбалансированные деревья

Ну так а ты проверь на несбалансированном.

anonymous
()
Ответ на: комментарий от drBatty

ЕМНИП там кучу будет есть, а не стек. Так я и в C++ могу.

А больше двоичное дерево ты никак и не обойдешь. Вариантов нет. Либо кушаешь стек по рабоче-крестьянски через прямую рекурсию, либо кушаешь кучу, но хитровывернуто как истый антилигент через TCO и продолжения.

dave ★★★★★
()
Ответ на: комментарий от drBatty

Ладно, x->right это перейти, а возвращаться как? Повесить ещё по указателю на каждый узел? Не жирно-ли будет?

Ничего вывешивать не надо. call и ret - это те-же goto (jmp) c сохранением/извлечением адреса возврата из стека - не? Мне влом писать ассемблерный код, ибо сначала придётся вспоминать внутренности этой кухни.

yyk ★★★★★
()
Ответ на: комментарий от drBatty

если нацелен на непонимание то только самостоятельное написание ТСО поможет.

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

qulinxao ★★☆
()
Ответ на: комментарий от drBatty

Нет уж, ты за базар отвечай - когда конкретно call быстрее jmp при прочих равных условиях? Код с TCO не будет «заметно больше», там будет максимум код для сдвига аргументов вызова в начало фрейма.

anonymous
()
Ответ на: комментарий от anonymous

Ну так а ты проверь на несбалансированном.

смысл? ладно, убедили, правый узел рекурсивно обходить не нужно. Что это даёт? Да ничего, только экономию стека в случае, если дерево кренит ВСЕГДА вправо (а где IRL такое бывает?). Причём очевидно, что хоть размер стека и определяется левой высотой, но вот время всё равно будет определяться максимальной. Т.е. профита от такого дерева тоже не будет. Не нужно.

drBatty ★★
()
Ответ на: комментарий от dave

А больше двоичное дерево ты никак и не обойдешь. Вариантов нет. Либо кушаешь стек по рабоче-крестьянски через прямую рекурсию, либо кушаешь кучу, но хитровывернуто как истый антилигент через TCO и продолжения.

нет. сбалансированное дерево обойду. Например стека на 64 эл-та мне хватит для обхода красночёрного дерева с 4294967296 узлами, а если дерево сбалансировано получше, то и с 9223372036854775808 узлами. Что мешает мне сделать стек скажем на 256 эл-тов, и обойти ВСЕ АТОМЫ этой вселенной?

drBatty ★★
()
Ответ на: комментарий от drBatty

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

dave ★★★★★
()
Ответ на: комментарий от dave

Про вселенную ты загнул

хорошо, пусть будет «видимая вселенная». Размер стека растёт как log₂ от числа узлов, и это можно строго доказать. Потому стек на 256 эл-тов хватит для ЛЮБОГО числа узлов, если они хранятся в памяти (в любой памяти, если конечно там не плотнее 1 бит/атом, и если атомов не более, чем в видимой вселенной).

А вот если дерево несбалансировано, то стек может и линейно расти. Тут да, проблема.

Мой посыл был о другом.

о чём же?

drBatty ★★
()
Ответ на: комментарий от drBatty

Извини, не хочу я сейчас балаболить :)

dave ★★★★★
()
Ответ на: комментарий от drBatty

Что это даёт?

А почему это должно что-то давать?

anonymous
()
Ответ на: комментарий от ilammy

О том, что математике до лампочки, сколько там в какой-то вселенной атомов.

а мне до лампочки, что там с твоей математикой. Я просто доказал, что при _любом_ числе узлов стек не переполнится. Этого достаточно.

drBatty ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.