LINUX.ORG.RU

О хвостовой рекурсии

 


3

4

Или с чем ее едят и как ее готовят? Набрел на статью в Википедии, ознакомился, сделал сравнительный замер времени выполнения для приведенного там примера. Результаты впечатлили, особенно если учесть, что тестировал я это для Scala с включенной оптимизацией.пиляторы

Собственно вопросов два.

1. Хотелось бы получше разобраться в устройстве хвосто-рекурсивных функций и их вызовов, дабы объяснить человеку, далекому от этой темы - в чем там магия?

2. Какие еще популярные ЯП и компиляторы поддерживают оптимизацию данного вида рекурсии?

Всем спасибо.

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

То есть если для CPU есть разница, значит он отличить определенно _может_.

для тебя есть разница, говно или конфетка? да/нет?

Как ты отличишь одно от другого? Правильно - посмотрев/понюхав/попробовав. Так и CPU. Конечно конфетки с видом/запахом/вкусом говна будут ошибочно приняты за говно. Как и числа. Потому конфетки с говном складируют в разных и известных местах. С числами тоже самое. Компилятор позволяет это автоматизировать, не более того.

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

Дебил. Не надо косвенного вызова. Сюда смотри, дебил:

теперь расскажи, СКОЛЬКО тактов ты на этом сэкономил?

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

И еще убирается ret. Ну если ф-и мелкие, то call+ret существенно замедлят выполнение по сравнению с обычным джампом. А вообще профит в том, что в этом случае не растет стек.

если это нерекурсивная и нетривиальная функция, то профит == 0. От тривиальной нерекурсивной функции профит тоже равен 0, ибо ещё лучше её заинлайтить. В итоге функция должна быть и тривиальная, и не инлайтовая. Т.е. тривиальная косвенная. Но от тривиальной косвенной профита тоже 0, ибо call eax/ret/ret вряд-ли намного дешевле jmp eax/ret (я так думаю, что стоимость косвенного перехода полюбому намного дороже обычного ret). А вот если функция рекурсивная, то мы избавляемся и от jmp и от ret, т.е. просто возвращаемся к началу.

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

Так что никто не мешает обрабатывать данные одного типа командой для данных другого.

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

или попробуй проверить два знаковых, и перейти командой для беззнаковых.

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

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

меня веселит, что дерево может быть вовсе не сбалансированным

может быть. Но это особый вырожденный случай. Если делимое может быть равно нулю, это совсем не значит, что деление бесполезно.

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

В процессоре циклов нет

есть. В x86 даже 2 вида - loop & jne.

в процессоре функции тоже кагбе не очень есть.

есть. call/ret называются. Есть и косвенные.

Да, код понятный человеку разворачивается в код понятный машине, и?

а кто тебе сказал, что ФП более _понятно_? Давай возьмём Over9000 ламеров, и будем их учить LISP & PHP, чему они научаться? Сам догадаешься или тебя в интернеты послать?

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

я тебя правильно понял, проблема синтаксиса лиспа в том, что код, убого выглядящий в других языках, выглядит в лиспе элегантно?

примерно так. Только не забудь, что «другие ЯП», это в т.ч. и ассемблер, а убогий код на ассемблере будет убого выполняться. Если-бы современные CPU были-бы ФП-ориентированы, вопросов-бы не возникло. Но это не так.

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

Если-бы современные CPU были-бы ФП-ориентированы...

А что в современных CPU для _декомпозиции кода_ есть кроме call/ret? :)

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

для тебя есть разница, говно или конфетка? да/нет?

Да, для меня есть.

Как ты отличишь одно от другого? Правильно - посмотрев/понюхав/попробовав. Так и CPU.

Ну так каким образом CPU должен «понюхать» память, чтобы узнать, чем является указанная последовательность машинных слов? Как реализован этот процесс?

Конечно конфетки с видом/запахом/вкусом говна будут ошибочно приняты за говно.

Если конфетка имеет вкус, вид, запах и атомарное строение как у куска говна - то это и есть кусок говна, а никакая не конфетка. И если ты кому-нибудь попытаешься такой кусок говна продать вместо конфеток, то получишь по ебалу.

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

От тривиальной нерекурсивной функции профит тоже равен 0, ибо ещё лучше её заинлайтить.

Там может быть неявная рекурсия через сотню вызовов (message-passing).

А вот если функция рекурсивная, то мы избавляемся и от jmp и от ret, т.е. просто возвращаемся к началу.

От jmp мы не избавляемся, мы избавляемся от пары call/ret. джамп быстрее колла и рета по отдельности и уж точно быстрее их вместе.

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

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

И что будет? У них представление одинаковое, процессор никак не отличит первое от второго.

В любом случае, с неверным типом ты получишь неверный результат.

Ну да, неверный. но процессор-то об этом не знает. Потому что он вообще о типах не знает. Он знает «сделай вот эту хуйню для того куска памяти» - и все. Никаких типов.

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

есть. call/ret называются. Есть и косвенные.

Это процедуры и функции, дебилушка.

а кто тебе сказал, что ФП более _понятно_?

Очень просто:

x + 2 = 10, чему равно х?

5 - x = 8, чему равно х?

x = 10, x = 5, чему равно х?

Декларативность и отсутствие состояния для человека более естественны.

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

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

Тут есть одна проблемка - на ассемблере любой код убогий.

Это, кстати, не говоря уже о том, что компилторы генерят более эффективный код, чем человек, хотя выглядит этот код тоже более убого.

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

А что в современных CPU для _декомпозиции кода_ есть кроме call/ret? :)

ничего нет... вот только loop&jne это почти аналог while, jc аналог if, а call/ret аналог сишной функции.

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

Я на этом целый stack frame и лишний return сэкономил, ничтожество ты безграмотное.

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

Ну так каким образом CPU должен «понюхать» память, чтобы узнать, чем является указанная последовательность машинных слов? Как реализован этот процесс?

никаким. Написано imul - это умножение знаковых. Если подставить беззнаковые - получим неправильный результат.

Если конфетка имеет вкус, вид, запах и атомарное строение как у куска говна - то это и есть кусок говна

ну в таком случае, чем является число 0?

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

вот только loop&jne это почти аналог while, jc аналог if, а call/ret аналог сишной функции.

в ФП нет ветвлений/условий? И ты как-бы телегу впереди лошади поставил: это в си while/if - аналоги процессорных переходов, а функции - аналоги процессорных call/ret. Что не запрещает и теми и другими инструкциями CPU пользоваться и в ФП - не?

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

От jmp мы не избавляемся, мы избавляемся от пары call/ret. джамп быстрее колла и рета по отдельности и уж точно быстрее их вместе.

быстрее, но ненамного. Выигрыш будет лишь в случае тривиальной функции вроде x+y. Но этот выигрыш в этом случае будет ещё больше, если использовать inline. Именно потому я и говорю, что смысл есть только если мы не знаем, какая именно функция (тривиальная) будет в рантайме. Т.е. косвенный вызов в неинлайновой тривиальной функции. Вот только _косвенный_ вызов настолько дорогой, что разницы между jmp и call/ret не будет.

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

есть. В x86 даже 2 вида - loop & jne.

jne и loop - это скорее такие goto, а не циклы.

есть. call/ret называются. Есть и косвенные.

это тоже не совсем функции. Или даже совсем не функции

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

примерно так. Только не забудь, что «другие ЯП», это в т.ч. и ассемблер, а убогий код на ассемблере будет убого выполняться. Если-бы современные CPU были-бы ФП-ориентированы, вопросов-бы не возникло. Но это не так.

Ну... современные cpu они лишь C-ориентированные. Или, скорее, наоборот: C - cpu-ориентированный язык. И что?

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

эх... Сложно что-ли понять простую вещь - важен только результат. Компилятор автоматически подставляет нужные операции в зависимости от типа, а ассемблер - не подставляет. Вот и вся разница. На самом деле, компилятор тоже не знает, ЧТО ты там в x хранишь, знает, что ты сказал, что дескать int, вот он и множет imul'ом. ВНЕЗАПНО там ASCIIZ лежит. И что ты получишь? Правильно, ерунду.

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

Но этот выигрыш в этом случае будет ещё больше, если использовать inline.

Только если именно для «х+у» - т.е. для _очень небольшого_ количества функций.

Если «тривиальных функций» много, их вызовов - больше на порядок, и вложенность вызовов >>1, а размер кода их - со страницу памяти, не поплохеет от инлайнинга?

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

jne и loop - это скорее такие goto, а не циклы.

это

do {} while(условие);
while(){} напрямую в x86 не компиллится, потому может считаться синтаксическим сахаром как и for(;;){}

это тоже не совсем функции. Или даже совсем не функции

это как раз и есть функции в смысле C, но совсем не функции в смысле ФП.

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

Только если именно для «х+у» - т.е. для _очень небольшого_ количества функций.

да.

Если «тривиальных функций» много, их вызовов - больше на порядок, и вложенность вызовов >>1, а размер кода их - со страницу памяти, не поплохеет от инлайнинга?

а от замены call/ret на jmp что, похорошеет? ну вот gcc меняет... Толку-то?

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

никаким. Написано imul - это умножение знаковых.

То есть для процессора нету деления на знаковое/беззнаковое, инты и флоаты и т.п, так?

ну в таком случае, чем является число 0?

Процессор не знает ничего о числах. У него есть область памяти, заполненная нулями, например. Чисел нет. Ни целых, ни с плавающей точкой, ни беззнаковых.

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

Выигрыш будет лишь в случае тривиальной функции вроде x+y.

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

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

это как раз и есть функции в смысле C, но совсем не функции в смысле ФП.

Это не функции, это процедуры.

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

Ты понимаешь что ты поехавший уже? Все. Не я, блядь, поехавший. Не он, блядь. А - ты! Меня твои истории уже просто доебали, я не могу их слушать. Одна история охуительней другой, просто. Про говно. Про какую-то хуйню, CPU. Чё ты несешь вообще? Ты можешь заткнуться? «Потому конфетки с говном складируют в разных и известных местах». Чего, блядь? Про что несешь? Вообще охуеть.

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

никаким. Написано imul - это умножение знаковых.

То есть для процессора нету деления на знаковое/беззнаковое, инты и флоаты и т.п, так?

не так. imul умножение знаковых целых. В сишечке ты когда объявляешь переменную, пишешь - знаковое целое, а в асме каждый раз пишешь, на _каждом_ использовании, где это играет какую-то роль. В сишечке тоже _не_ пишешь тип, если тебе пофиг до него (надо переслать N char'ов, или установить N char'ов в 0, или выделить N char'ов).

Процессор не знает ничего о числах. У него есть область памяти, заполненная нулями, например. Чисел нет. Ни целых, ни с плавающей точкой, ни беззнаковых.

компилятор тоже ничего не знает о числах. Он знает о переменных и о указателях (за исключением void*).

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

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

ну и где по твоему лежат эти переменные? в ацтрале что-ли? И почему TCO у мну сломалось, как только я в стек полез?

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

это как раз и есть функции в смысле C, но совсем не функции в смысле ФП.

Это не функции, это процедуры.

согласен. «полноценных функций» в сишечке нет. В моём CPU тоже.

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

Программа не вылетает со стек-оверфлоу, экономится память.

это если только удастся распихать всё по регистрам. А регистров ОЧЕНЬ мало.

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

Во первых, ничтожество, inline для кэша вреден. Во вторых, ничтожество, существует раздельная компиляция.

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

Gcc говно. Нормальный компилятор явно сдвинет stack frame при tco.

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

не так. imul умножение знаковых целых.

Но процессор не может определить, какое целое - знаковое, а какое - беззнаковое, так?

Другими словами и умножение знаковых целых и умножение без знаковых - это просто некоторые процедуры над машинными слвоами, которые в некотором смысле имеют чтото общее с соответствующими умножениями чисел. И потому _мы называем_ их знаковым/беззнаковым умножением. но для процессора разницы никакой нет - это просто две процедуры над машинными словами. Давай для определенности переименуем их в процедуры Х1 и Х2, причем поменяем представление знаковых/беззнаковых целых, чтобы оно не смущало. Теперь понятно, что эти процедуры ничего общего с типами не имеют.

компилятор тоже ничего не знает о числах. Он знает о переменных и о указателях (за исключением void*).

Нет, есть не переменные, а термы. И у термов есть типы (если язык статически типизированный). А у процессора любые команды принимают машинные слова и работают с машинными слвоами. Соответственно и тип один - машинное слово.

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

ну и где по твоему лежат эти переменные? в ацтрале что-ли?

на стеке (мы обсуждаем тсо, то есть считаем что регистров нет вовсе, для упрощения).

И почему TCO у мну сломалось, как только я в стек полез?

потому что там хвостовой вызов плюса, который все равно инлайнится и ТСО делать не на что. там ничего не ломалось - просто ТСО там и НЕ БЫЛО.

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

это если только удастся распихать всё по регистрам. А регистров ОЧЕНЬ мало.

Блять, ты чего такой тупой то? Тебе же говорят - ТСО никак не связана с регистрами. ТСО использует текущий фрейм стека при хвостовом вызове вместо того, чтобы выделять следующий. Благодаря тому, что на каждом вызове используется все тот же текущий фрейм стека потребление памяти не растет и стековерфлоу не происходит.

Тебе привести пример с функцией из 1000 аргументов, в которой нету ни стековерфлоу ни роста потребления памяти, или что?

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

согласен. «полноценных функций» в сишечке нет.

В сишке как раз есть.

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

ну если у тебя 100500 мест с былокодом - то да... Придётся так делать. Конечно давить 100500 раз F8 или что там у тебя next step - оно проще, надёжнее и безопаснее.

Тем временем в gdb сделали reverse debug, можно жать F9 и наоборот отходить назад от того места, где упало.

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

Во первых, ничтожество, inline для кэша вреден.

да. конечно хранить пару байт команды add куда как вреднее, чем хранить процедуру, причём выровненную, причём в рантайме ещё и стек жрать...

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

пофапай ещё, о великий. Кстати, на женщин фапать интереснее.

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

Но процессор не может определить, какое целое - знаковое, а какое - беззнаковое, так?

компилятор тоже НЕ может ничего определить. Ему сказали - «это целое», он считает это целым. Как и процессор.

Другими словами и умножение знаковых целых и умножение без знаковых - это просто некоторые процедуры над машинными слвоами, которые в некотором смысле имеют чтото общее с соответствующими умножениями чисел. И потому _мы называем_ их знаковым/беззнаковым умножением. но для процессора разницы никакой нет - это просто две процедуры над машинными словами. Давай для определенности переименуем их в процедуры Х1 и Х2, причем поменяем представление знаковых/беззнаковых целых, чтобы оно не смущало. Теперь понятно, что эти процедуры ничего общего с типами не имеют.

непонятно. Это не просто «некоторые процедуры», а специальные процедуры, предназначенные например для умножения. Называть их можешь как хочешь, но твоя X1 даст правильный целый знаковый результат только для целых знаковых операндов. Что оно даст для чего-то другого - никого не волнует. Кроме тебя.

Пойми простую вещь: типы не определяют, их назначают. Сказал ты «это целое», и НИКТО не станет проверять, целое оно или дробное. Ни процессор, ни компилятор.

Нет, есть не переменные, а термы. И у термов есть типы (если язык статически типизированный)

А у процессора любые команды принимают машинные слова и работают с машинными слвоами. Соответственно и тип один - машинное слово.

ну может у твоего процессора и так. А вот мой знает довольно много типов чисел. Да, я знаю, _можно_ подсунуть процессору не тот тип (и получить НЁХ), но это ничего не меняет, ибо компилятору тоже можно(с тем же результатом).

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

ну и где по твоему лежат эти переменные? в ацтрале что-ли?

на стеке (мы обсуждаем тсо, то есть считаем что регистров нет вовсе, для упрощения).

т.е. единственная ценность тсо в том, что оно иногда меняет call на jmp? И всё?

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

Тем временем в gdb сделали reverse debug

да вроде уже много лет как. или нет?

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

Тебе привести пример с функцией из 1000 аргументов, в которой нету ни стековерфлоу ни роста потребления памяти, или что?

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

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

Наркоман?

Если есть различные операции для различных типов, значит есть и типы.

Наличие типов определяется не тем, проверяет ли их «компутер», а, ВНЕЗАПНО, тем, предусмотрены ли соответствующие интерпретации или нет.

Тип в вычислительных системах - это не множество, а интерпретация байтиков. Или ты теоретик? Даже в этом случае отправляю тебя читать Д.Кнута...

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

единственная ценность тсо в том, что оно иногда меняет call на jmp? И всё?

Меняет call на jmp, удаляет лишний ret (а это несколько обращений к стеку, а каждое обращение к памяти это очень тяжело и долго), удаляет ненужный stack frame (то есть, экономит и без того убогую память выделенную под стек). Мало, что ли?

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

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

ЕМНИП в сишечке и ++ так не получится.

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

Твоя память похожа на говно. Это зависит только от ABI. Например, на ARM ABI вообще скорее всего большая часть параметров при вызове будет в регистрах.

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

ручками может и не получится, а компилятор почему не сможет? И да, я совсем забыл про передачу параметров через регистры :( (надо на sbcl-е проверить) - может (особенно для 64-разрядного) передача параметров через стек будет только в очень крайних случаях?

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