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)

Там же написана - нужна, но обходится слишком дорого.

tailgunner ★★★★★
()

Правильно написано. В сях и крестах она не нужна.

nanoolinux ★★★★
()

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

Вероятно, причина в том, что создатели современных процессоров потратили очень много времени и сил на оптимизацию именно конвенции вызовов из Си. Конвенция вызовов с автоматической поддержкой хвостовой оптимизации (см. PAIP) совсем несложная, но похоже, что под нее тоже надо подстраивать процессоры.

На мой взгляд полная поддержка хвостовых вызовов как и полная и настоящая поддержка хвостовой рекурсии нужны в языках не только с полноценными лямбдами, но и с таким преобразованием кода, которое известно или как «нотация do» (haskell), или как «вычислительные выражения» (f#), или как «плагин продолжений» (scala, но она тут пролетает из-за того, что в ней нет TCO). Именно там такая оптимизация становится важной (при раскрытии конструкции while, а иначе съедается стек).

Зачем TCO для Си и Си++? А нафига козе баян?

dave ★★★★★
()
Последнее исправление: dave (всего исправлений: 1)

странный вопрос какой-то. Пусть будет. В некоторых сложных случаях оно сильно упрощает код. На, а то, что 100% быдлокодеров вставляют goto и TC туда, куда это не нужно - проблема не языка, и не компилятора.

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

Вероятно, причина в том, что создатели современных процессоров потратили очень много времени и сил на оптимизацию именно конвенции вызовов из Си. Конвенция вызовов с автоматической поддержкой хвостовой оптимизации (см. PAIP) совсем несложная, но похоже, что под нее тоже надо подстраивать процессоры.

ППКС. Но я считаю, что это хорошо, хотя и делает твою любимую ФП ненужной и тормозной ☺

Зачем TCO для Си и Си++?

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

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

Вероятно, причина в том, что создатели современных процессоров потратили очень много времени и сил на оптимизацию именно конвенции вызовов из Си.

Т.е. call работает быстрее, чем [long] jamp?

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

А ты точно понимаешь, что такое TCO?

(грубо) замена «хвостовой пары» call+ret на jmp?

P.S. А ты уверен, что во всех ассемблерах именно jmp? ;)

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

(грубо) замена «хвостовой пары» call+ret на jmp?

Я и сам не понимаю деталей работы tail calls, но есть мнение, что «Making tail calls can sometimes (though not by any means always) require support from your platform's calling conventions, linker, and runtime library». Собственно, Грейдон об этом и говорит.

P.S. А ты уверен, что во всех ассемблерах именно jmp? ;)

Я уверен, что нет слова jamp %) А так, в ассемблерах бывают branch и даже goto.

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

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

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

(грубо) замена «хвостовой пары» call+ret на jmp?

Грубо да, но ещё остаётся вопрос, что делать с предыдущим фреймом. Надо ли ещё свернуть перед вызовом, а потом накатать новый фрейм, или можно просто поперезаписывать в стеке аргументы. В том же Си++ там ещё деструкторы повызывать надо, причём по семантике языка это надо делать после выхода из (якобы) хвостового вызова. Отдельный вопрос, что делать с внешним кодом, который об этом всём не в курсе.

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

Т.е. call работает быстрее, чем [long] jamp?

почти одинаково дёшево и то и другое. Причина дороговизны jmp/call сегодня не в том, что в стек надо лезть, не надо, L1 рядышком, и тут анон говорил, что там 2..4 такта всего надо. Причина в конвейере. Любой переход может сбить конвейер, и это будет намного дороже, чем запись в стек.

Что именно дороже - предсказать очень сложно, это зависит от многих причин, даже от производителя. Никакой кодер сегодня этого не знает, и знать не может. Такое под силу только компилятору, который и помнит, где надо, а где не надо менять jmp на call и наоборот.

Но будет-ли менять компилятор call на jmp? Если отключить эту оптимизацию - не будет. Профита от замены тоже не будет.

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

(грубо) замена «хвостовой пары» call+ret на jmp?

неправильный ответ. Точнее неполный. call+ret компиляторы уже давно умеют, дело не в этом. Дело в том, что рекурсивный алгоритм очень часто можно переписать в итеративный. Вот компилятор с TCO это умеет.

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

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

не обязательно. Все рекурсивные алгоритмы используют стек, хотя не для всех этот стек нужен. Вот тебе пример рекурсивного алгоритма

int factorial(int x, int result = 1)
{
	if(x == 1)
		return result;
	else
		return factorial(x - 1, result * x);
}

int main(int argc, const char *argv[])
{
	return factorial(argc);
}
А вот результат
00000000004004c0 <main>:
  4004c0:       83 ff 01                cmp    edi,0x1
  4004c3:       b8 01 00 00 00          mov    eax,0x1
  4004c8:       74 13                   je     4004dd <main+0x1d>
  4004ca:       66 0f 1f 44 00 00       nop    WORD PTR [rax+rax*1+0x0]
  4004d0:       0f af c7                imul   eax,edi
  4004d3:       83 ef 01                sub    edi,0x1
  4004d6:       83 ff 01                cmp    edi,0x1
  4004d9:       75 f5                   jne    4004d0 <main+0x10>
  4004db:       f3 c3                   repz ret 
  4004dd:       c3                      ret    

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

Грубо да, но ещё остаётся вопрос, что делать с предыдущим фреймом.

это и есть основной вопрос жизни и бытия.

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

В хаскеле, как раз, из-за ленивости хвостовая рекурсия не слишком полезна - стека-то все равно нет.

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

Т.е. call работает быстрее, чем [long] jamp?

Возможно. Там фишка в том, что при TCO адрес возврата мог быть положен в стек задолго до вызова текущей функции. Конвейер должен учитывать это, а значит, надо лезть в память, если вершина стека не хранится в самом процессоре. В общем, нужно подстраивать конвейер под TCO, и возможно даже архитектуру самого процессора. Но это все предположения.

Итого, мой посыл в том, что современные архитектуры процессоров сильно завязаны на язык Си и его распространенные реализации. Тут значимая обратная связь.

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

мой посыл в том, что современные архитектуры процессоров сильно завязаны на язык Си и его распространенные реализации

Пока что ты не привел ни одного довода в пользу этого.

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

Меня больше возврат из функции интересует.

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

В хаскеле, как раз, из-за ленивости хвостовая рекурсия не слишком полезна - стека-то все равно нет.

Это для Cont и его вариаций.

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

Я и сам не понимаю деталей работы tail calls, но есть мнение, что «Making tail calls can sometimes (though not by any means always) require support from your platform's calling conventions, linker, and runtime library».

Как минимум - могли бы начать с оптимизации «локальных» «хвостовых вызовов»

Я уверен, что нет слова jamp %)

Уупс :(

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

В том же Си++ там ещё деструкторы повызывать надо, причём по семантике языка это надо делать после выхода из (якобы) хвостового вызова.

Ну значит не надо ТСО для плюсов :)

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

Дело в том, что рекурсивный алгоритм очень часто можно переписать в итеративный. Вот компилятор с TCO это умеет.

компилятор и без ТСО может уметь оптимизировать «хвостовую рекурсию». С ТСО у него это получается «автоматом». А вот «call+ret компиляторы уже давно умеют» - получить бы список этих компиляторов?

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

может так: «Профита от замены может не быть.»?

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

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

компилятор и без ТСО может уметь оптимизировать «хвостовую рекурсию». С ТСО у него это получается «автоматом».

нет, с ТСО компилятор _обязан_ её делать.

А вот «call+ret компиляторы уже давно умеют» - получить бы список этих компиляторов?

вроде это все умеют. Проблема ведь именно в рекурсии, там нет никакого call+ret, там именно call на саму себя. А потом куча ret'ов.

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

Как минимум - могли бы начать с оптимизации «локальных» «хвостовых вызовов»

aka хвостовой рекурсии. И...

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

«But the WIP patch I have to use the machine return value may allow LLVM to optimize that function into a loop»

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

нет, с ТСО компилятор _обязан_ её делать.

Нет, с TCO оптимизация хвостовой рекурсии получается именно автоматом, как тут правильно заметили выше.

К слову о компиляторах, они не всесильны. Например, компилятор Scala в принципе не может оптимизировать косвенную хвостовую рекурсию, поскольку JVM не умеет TCO. Только прямая хвостовая рекурсия может быть преобразована в циклы на уровне байт-кода.

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

Тут надо только добавить, что компилятор F# при прочих равных все равно стремится преобразовать прямую хвостовую рекурсию к циклу, хотя и не обязан был этого делать. Видимо, из-за того, что TCO в .NET реализован не очень эффективно (минус несколько процентов к скорости), да и работает эта оптимизация не очень надежно (есть проблемы с unit/void). Ну, и от греха подальше компилятор F# сам пишет циклы в байт-коде .NET, когда может.

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

Над IL (.NET Intermediate Language)? Да, только вызов надо поменить специальным атрибутом. Кажется, он называется ".tail".

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

нет . необходим концевой вызов

и он может быть не один

и он может быть не прямым(самого себя) , а косвенный - т.е из А tco B из которой всегда tco A - в итеративном виде это достоточно нетривиальное вид имеет.

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

Нет, с TCO оптимизация хвостовой рекурсии получается именно автоматом, как тут правильно заметили выше.

«автоматом» получается замена call/ret на jmp, как не очень полезный частный случай. Сама по себе TCO это совсем другое, это поиск и устранение неизменного контекста, который лежит в стеке.

К слову о компиляторах, они не всесильны. Например, компилятор Scala в принципе не может оптимизировать косвенную хвостовую рекурсию, поскольку JVM не умеет TCO.

это проблемы JVM. не более того.

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

Сама по себе TCO это совсем другое, это поиск и устранение неизменного контекста, который лежит в стеке.

Что для «локальных функций» в сишном исполнении опять-же не представляет никакой магии.

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

anonymous from Так ли нужна оптимизация хвостовых вызовов? (комментарий)

только для случая вызова самой себя - которая легко заменяется на цикл условием выхода концевой ветки рекурсии.

вот такой случай перепиши(т.е сделай вручную ТСО) в итеративный вид :

int a(int x){
 if(P(x))return x>>1;
 //some side eff:
{
...
}
 if(Q(x))return b((x*x)^x);
 return a(x-1);
}
int b(int x){
  if(R(x))return 0;
  return a(x);
}
qulinxao ★★☆
()
Ответ на: комментарий от yyk

Что для «локальных функций» в сишном исполнении опять-же не представляет никакой магии.

да, магии там нет. Просто анализируем использование стекового фрейма, если он не меняется, выносим его из тела цикла. Например при расчёте факториала Так ли нужна оптимизация хвостовых вызовов? (комментарий) мы хоть и используем стек, но только ДО перехода. После перехода (ret) данные уже не используются, и потому сохранять их не нужно. Сам адрес перехода тоже один и тот же, и его(переход) можно заменить на jmp. В итоге, в каждой итерации данные нужны только внутри цикла, а значит их можно хранить не в стеке, а в регистрах/памяти. Если-бы я считал return x ? 1 : factorial(x - 1) * n; всё было-бы не так - мы последовательно считаем 9 * (8!) == 9 * (8 * (7!)) и т.д. Т.е. фактически сначала считаем 9 8 7 6 5 4 3 2 1, а потом их умножаем. Тут стек нужен. Но это и не ТСО.

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

только для случая вызова самой себя

не только. В твоём примере, адреса возврата в стек - тоже данные, и зависят от x. А если-бы они не зависели, то можно было-бы переписать в цикл. Например

int F1(int x)
{
 //нет возвратов и рекурсий
 return F2(x);
}

int F2(int x);
{
 return F1(x);
}

тут стек детерминирован, там А1 А2 А1 А2 А1 А2…, и значит его можно выкинуть, и сделать цикл.

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

Но это и не ТСО.

Совершенно верно, поэтому не стоит и рассматривать. Мне трудно представить, как в случае сишного TC может _меняться стековый фрейм_, поэтому все пары call+ret можно смело «оптимизировать».

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

Прикинь, в ARM вообще нет call, есть только jump-ы.

и что теперь. там push pc/jmp вместо call. В x86 тоже, только это одной командой, а не двумя(и то, только до ядра, в ядре тоже две. А может и больше)

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

Совершенно верно, поэтому не стоит и рассматривать. Мне трудно представить, как в случае сишного TC может _меняться стековый фрейм_, поэтому все пары call+ret можно смело «оптимизировать».

ты меня не понял. call+ret это TCO, но не только call+ret. В примере выше у меня не совсем call+ret.

В качестве примера: бинарное дерево. Мы спускаемся вниз к листьям, функцией типа

find(node *x)
{
 find(x->left);
 find(x->right);// (***1)
 // (***2)
}
эта функция обходит все узлы в обратном порядке. При этом стек нужен, ибо именно там запоминается наш путь, в виде адресов возврата: выход из левого узла возвращает нас к обходу правого узла (***1), а вот обход правого узла возвращает нас в (***2). Никакое это НЕ TCO, ибо стек хранит данные (текущий путь из корня). Это не разворачивается, только если сделать массив(список), и хранить там по 1 биту на поворот.

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

Никакое это НЕ TCO

конечно - нет связки call+ret. Я только не понимаю чего ты к этому приколупался. Или, по-твоему, ТСО должно и вот такие твои алгоритмы «разрекурсировать»?

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

конечно - нет связки call+ret.

есть. Смотри внимательнее.

Я только не понимаю чего ты к этому приколупался. Или, по-твоему, ТСО должно и вот такие твои алгоритмы «разрекурсировать»?

если понимать как «call+ret», то должно.

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

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

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