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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P.S. нет команды jamp.

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

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

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

(грубо) замена «хвостовой пары» 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.

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

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

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

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

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

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

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

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

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

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

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

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    

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

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

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

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

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

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

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

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

Зачем приводить довод на очевидное?

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

А... я упустил, что это очевидно.

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

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

Так нужна. А C++ не нужен

Я и сам не понимаю деталей работы 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 %)

Уупс :(

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

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

Профита от замены тоже не будет.

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

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

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

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

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

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

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

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

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

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

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»

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

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

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

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

TCO в .NET

это оптимизация в .NET производится над IR?

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

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

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

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

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

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

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

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

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

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

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);
}

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

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

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

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

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

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

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

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

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

http://dl.dropbox.com/u/5846668/850a6461fbe93548e48f7b0985a7ff826b907dd8.ps.bz2

статья про ТСО в сях.

Ну замени все return [a|b](x); на гипотетическую пару push_in_stack_head(x); goto [a|b]; и получишь искомое

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

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

Интересный документ.

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

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

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

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

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

find(node *x)
{
 find(x->left);
 find(x->right);// (***1)
 // (***2)
}

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

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

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

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

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

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

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