LINUX.ORG.RU

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

 


3

4

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

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

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

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

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

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

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

разве задача подсчёта какой-то функции от набора элементов не жизненна?

через жопу это твой ход мысли.

ЧСХ не только мой, но и большинства программистов и производителей CPU. Никаких лямбд я что-то в процессорах не наблюдаю. Сабжей тоже...

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

постить картинки с тарелками и беспредметно обзывать оппонента мудаком - верх мастерства. Демагогии.

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

Нет, конечно же. В релизе. Например, во всей embedded разработке это обязательное требование.

пруф будет?

Я парсеры не пишу, я получаю дерево от готового XML-парсера. И это делают если не все, то подавляющее большинство. Других применений деревьям в современном программировании нет.

тебя туда попросту не пускают. И правильно.

Какая редкостная, незамутненная чушь! Кешу плевать, что фетчить - для него все регистры абсолютно равноправны.

ты не понимаешь разницы между кешированием гигабайтной кучей и мегабайтным кешем? ну почитай вику что-ли...

Их до хера, на самом деле, и аллокатор их прекрасно раздает.

регистров до хера, а вот имён регистров - с гулькин хрен.

Ты никогда не сможешь отличить скорость обращения к массиву от скорости обращения к стеку.

да, конечно...

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

Такие «проблемы» при оптимизации недопустимы. Компилятор не имеет права менять семантику при оптимизациях, и никакие другие оптимизации этого не делают.

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

Ну расскажи, салага, что такое «семантика», и почему у кода с exception и кода без exception вдруг оказывается одинаковая семантика?

я знаю, что такое денотационная семантика и операционная семантика. Что такое «семантика по анонимусу» и почему она меняется я не знаю

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

Их никогда к программированию нельзя подпускать.

Ну теперь мне все понятно)

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

пруф будет?

Пруф чего, придурок? Смотри хотя бы в исходники eCOS и подобных систем.

тебя туда попросту не пускают. И правильно.

Вякнуло ламо, которое даже парсеров не пишет.

ты не понимаешь разницы между кешированием гигабайтной кучей и мегабайтным кешем? ну почитай вику что-ли...

Дитятко, а сколько разных кэшей сделало за свою убогую жизненку ты? Что, нисколько? Не умеешь? FPGA только в кино видело, а до средств разработки ASIC тебя тем более не допустит никто? Ну вот и помалкивай, сопля, раз ни черта про кэши не знаешь.

регистров до хера, а вот имён регистров - с гулькин хрен.

И кого это колышет? Я жду, лошарик, показывай код, где доступ к массиву тормозит.

да, конечно...

Ну вперед, показывай код бенчмарка. Посмеши народ.

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

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

Идиот. Редкостный. Обычно для каждой оптимизации формально доказывают, что она не меняет семантики кода.

я знаю, что такое денотационная семантика и операционная семантика. Что такое «семантика по анонимусу» и почему она меняется я не знаю

Ну а если знаешь, что такое операционная семантика, то должен и понимать, чем отличается семантика кода, который завершается с исключением от кода, который завершается корректно. Только сначала сраку порвешь, пытаясь операционную семантику исключений сформулировать, ха-ха. Начинай отсюда: http://code.google.com/p/c-semantics/

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

Не нарывайся, вертихуев.

О! Да ты у нас крутой перец, да? :D

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

посты на ЛОРе, это не резюме

После твоих постов на ЛОРе твое резюме уже не нужно - всё и так ясно.

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

Я парсеры не пишу, я получаю дерево от готового XML-парсера. И это делают если не все, то подавляющее большинство. Других применений деревьям в современном программировании нет.

а если выпилить весь XML, то и деревья в программировании больше не нужны :D

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

ну и зачем писать так, что с виду кажется, что нужно хранить, а на самом деле - не нужно?

Чтобы так не писать - нужно не использовать функции. Как только ты начинаешь вызывать функции - появляются хвостовые вызовы, которые можно оптимизировать.

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

нет. Не понял ни того, ни другого.

Это два кода, которые осуществляют итерацию. Первый записан в ХР, второй - в виде цикла. Ты предлагаешь писать второе вместо первого. Но любому здоровму человку ясно, что первый код лучше.

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

И да, «короче» не аргумент

Там не только короче, но еще и понятнее. Во втором случае код по сути такой же как и в первом, только руками приходится дописать ряд шаблонных конструкций, которые в первом случае все равно будут сгенерированы компилятором. Зачем делать руками то, что компилятор может сделать автоматически? Человеческое время дороже машинного.

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

Вот тебе пример вычисления факториала:

Так проблема только в синтаксисе сишки. В ЯП с нормальным синтаксисом будет как-нибудь так:

fac acc 0 = acc
fac acc n = facc acc*n n-1
теперь сравни это со своим недофакториалом через for.

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

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

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

Пруф чего, придурок? Смотри хотя бы в исходники eCOS и подобных систем.

тебя никто за язык не тянул:

Нет, конечно же. В релизе. Например, во всей embedded разработке это обязательное требование.

Дитятко, а сколько разных кэшей сделало за свою убогую жизненку ты? Что, нисколько? Не умеешь?

у intel это получается лучше.

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

Идиот. Редкостный. Обычно для каждой оптимизации формально доказывают, что она не меняет семантики кода.

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

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

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

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

Только операционная семантика описывает редукцию в абстрактной машине с бесконечной памятью и бесконечным стеком. По-этому со стековерфлоу там никогда ничего не падает.

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

Чтобы так не писать - нужно не использовать функции. Как только ты начинаешь вызывать функции - появляются хвостовые вызовы, которые можно оптимизировать.

4.2

даже в примитивной задаче вычисления факториала, хвостовых вызовов НЕ появляется, их туда специально нужно вставлять. А в более сложных появляются? Продемонстрируй...

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

Это два кода, которые осуществляют итерацию. Первый записан в ХР, второй - в виде цикла. Ты предлагаешь писать второе вместо первого. Но любому здоровму человку ясно, что первый код лучше.

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

Во втором случае код по сути такой же как и в первом, только руками приходится дописать ряд шаблонных конструкций, которые в первом случае все равно будут сгенерированы компилятором. Зачем делать руками то, что компилятор может сделать автоматически? Человеческое время дороже машинного.

это не оправдание того, что нужно делать двойную работу - сначала заворачивать всё в функции, а потом радоваться, что компилятор что-то развернул. Если в твоём ЯП нет тех же циклов - это проблема только твоего ЯП, ибо в процессорах они есть. И код разворачивается для процессора. А не для тебя.

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

В ЯП с нормальным синтаксисом будет как-нибудь так:
fac acc 0 = acc
fac acc n = facc acc*n n-1

чем оно лучше:

fac n = product [1..n]

если говорить именно про решение задачи?

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

Во-первых, речь шла о сравнении хвостовой рекурсии с циклом. Во-вторых - можно и лучше написать: fac = factorial.

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

Так проблема только в синтаксисе сишки. В ЯП с нормальным синтаксисом будет как-нибудь так:

врёшь. В той же вике есть пример на этой вашей схеме:

(define (factorial n)
  (define (fac-times n acc)
    (if (= n 0)
        acc
        (fac-times (- n 1) (* acc n))))
  (fac-times n 1))
также там есть и контрпример, который тоже на схеме, и для меня он прост и понятен:
(define (factorial n)
  (if (= n 0)
      1
      (* n
         (factorial (- n 1)))))
т.ч. про ЯП ты врёшь и не краснеешь - сишечка тут не причём. другое дело, что записать в этой вашей схеме
for(y = 1; x; x--)
    y*=x;
попросту невозможно, только используя костыли, надеясь на то, что компилятор это всё развернёт. ИЧСХ в простейших случаях разворачивает, что будет в более сложных - я не знаю, попросту никто завернуть не может ничего, сложнее факториала. Вот и получается, что обсуждать мы можем только примеры по типу факториалов. Такие дела.

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

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

даже в примитивной задаче вычисления факториала, хвостовых вызовов НЕ появляется

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

f(args ...) { *blah-blah-blah*; return g(*blah-blah-blah*) };

Вот это типичный хвостовой вызов. В любом коде такого вида есть хвостовой вызов.

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

врёшь. В той же вике есть пример на этой вашей схеме:

Ну а я написал на хаскеле, а не на схеме. Problem oficier?

В той же вике есть пример на этой вашей схеме:

Только это не эквивалент для

for(y = 1; x; x--)
    y*=x;

эквивалент для фора будет такой (с поправкой на синтаксис арифметики и семантику булевых значений):

(let f ([x x] [y 1])
  (if x (f x-1 y*x) y))
Ну и записать то, что ты хочешь, конечно же можно, но зачем? То есть есть макрсоы типа того же do, которые почти повторяют семантику for из сишки, но их никто не использует, потому что ХР удобнее, чем for.

надеясь на то, что компилятор это всё развернёт. ИЧСХ в простейших случаях разворачивает, что будет в более сложных - я не знаю

Вообще-то стандарт требует, что все гарантированно развернется в любом случае, сколь угодно сложном. И эти случаи весьма часто используются - например, при моделировании конечных автоматов или message-passing логики или CPS. Видишь ли, циклы удобны лишь в том случае, если итерация происходит по одной переменной, независимой от «аккумуляторов» (и в той же схеме есть макросы для итераций по коллекциям и т.п.). Во всех остальных случаях хвостовые вызовы либо удобнее, проще и лаконичнее (см. мой пример выше с эквивалентным кодом в цикле и с ХР), либо на циклах вообще не реализуются.

попросту никто завернуть не может ничего, сложнее факториала.

Если ты чего-то не можешь - и не знаешь - это не значит, что этого чего-то нет. Оно есть, достаточно заглянуть в код.

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

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

враньё. контрпример:

int f(int x)
{
    return x<2 ? 1 : x*f(x-1);
}
ещё контрпример
int f(int x)
{
    int i = 0;
    char c = x%10 + '0';
    if(x/10)
        i+=f(x/10);
    i+=printf("%c", c);
    return i;
}
в упор не наблюдаю ТСО

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

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

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

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

Так вот именно! Я за то и ратую, чтобы не делать двойную работу. И писать итерации через ХР, экономя свое время.

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

враньё. контрпример:

Нет, конечно. Вот здесь:

return x<2 ? 1 : x*f(x-1);

у тебя хвостовой вызов "?", а вот тут:

i+=printf(«%c», c); return i;

у тебя хвостовой вызов «+=».

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

чем оно лучше:

fac n = product [1..n]

если говорить именно про решение задачи?

А чем это лучше

fac: */1+!:

если говорить именно про решение задачи? :)

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

Поддерживаю ответившего тебе. А проблемы такие в Scala вылазят наружу, например, при использовании while(true) внутри reset или другого выражения, переработанного плагином продолжений. По своей сути, while для продолжений реализован в Scala примерно так же как в приведенном мною выше коде для F#. Но из-за отсутствия полноценного TCO это не работает в Scala должным образом.

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

читабельнее

А так:

K         Haskell                       Python

+/*/...   (+)/(*)/...                   add/mul/...
!         enumFromTo 0 . flip (-) 1     range
1+        (1 +)                         lambda x: x + 1
          map (1 +)                     lambda xs: map(lambda x: x + 1, xs)
          map (map (+ 1))               lambda xs: map(lambda ys: map(lambda z: z + 1, ys), xs)
                     ... up to any rank ...
/         foldl                         reduce
*/        foldl1 (*) = product          lambda xs: reduce(mul, xs)

?

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

у тебя хвостовой вызов "?"

в Си нет такой операции "?", есть операция X ? Y : Z, однако её невозможно выполнить, _предварительно_ не вычислив X и (Y или Z). В нашем случае для вычисления Z нужно _сначала_ вычислить f(x-1), а _потом_ выполнить умножение. Ладно, умножение - это такой «хвостовой вызов», но f(x-1) уже НЕ хвостовой? Ты собрался оптимизировать функцию «умножение на целое число»? Ты заболел?

у тебя хвостовой вызов «+=».

да. Ну и что? это не просто +=, а int::operator+=(int), расскажешь, как его «оптимизировать»? Если ты не знал, то в x86 оно изначально выполняется _одной_ командой. Куда меньше-то? При этом printf(const char*, int) выполняется в 100500 команд, но ты почему-то её оптимизировать не желаешь. Почему?

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

разве задача подсчёта какой-то функции от набора элементов не жизненна?

в указанном виде она тривиальна и не жизненна.

ЧСХ не только мой, но и большинства программистов и производителей CPU. Никаких лямбд я что-то в процессорах не наблюдаю. Сабжей тоже...

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

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

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

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

в Си нет такой операции "?", есть операция X ? Y : Z

Ах, да, энергичный порядок же. Тогда там хвостовой вызов «*».

Если ты не знал, то в x86 оно изначально выполняется _одной_ командой.

То есть он заинлайнен. Уже оптимизирован, говоря иными словами.

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

в указанном виде она тривиальна и не жизненна.

укажи другой вид.

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

ты на других не пеняй, а за себя говори. Если ты не наблюдаешь указателей, int'ов и double в твоём CPU, то это твоя проблема, в моём есть и то, и другое, и третье. Вот доступ по указателю: http://en.wikipedia.org/wiki/Load_Effective_Address#Scaled Тип int - это «естественный» тип для данной архитектуры, т.е. ширина РОНа, в x86 оно сейчас 32 бита, т.к. на 64 перешли далеко не все, про тип double в моём CPU описан здесь: http://en.wikipedia.org/wiki/Double_precision_floating-point_format

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

а... вот откуда такая попаболь... Понимаю. Хорошо хоть ты не маздайщик (:

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

То есть он заинлайнен. Уже оптимизирован, говоря иными словами.

ага. именно об этом я и говорил - хвостовые вызовы есть, но оптимизировать их НЕ НУЖНО. Это не отменяет того, что оптимизировать надо _другие_ вызовы, а вот их-то оптимизировать не получается из-за этой вашей семантики ):

ЧСХ, здесь говорили про исключения и про потерю стекового фрейма - это тоже получается из-за того, что хвостовой вызов только с виду хвостовой, а на самом деле он обёрнут в исключение(сохранение фрейма), потому и получается такая ерунда. Это можно доказать, если навелосипедить список-стек ручками вокруг «хвостового» вызова - сразу станет очевидно, что _между_ хвостовым вызовом и выходом есть ещё операции с фреймом. Этот синтаксический сахар настолько низкоуровневый, что даже есть в x86 асме - ENTER/LEAVE. Но он таки есть...

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

укажи другой вид.

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

ок я вот смотрю на хексдамп и вижу:

ты на других не пеняй, а за себя говори. <..>

уговорил. Только объясни одну вещь:

3fd5 5555 5555 5555 6666 6666 7777 7777 3fd5

это что дабл, указатель, инт, лонг или какая то их смесь?

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

ага. именно об этом я и говорил - хвостовые вызовы есть, но оптимизировать их НЕ НУЖНО.

Нужно, конечно. Во всех случаях, когда этот вызов не заинлайнен.

ЧСХ, здесь говорили про исключения и про потерю стекового фрейма - это тоже получается из-за того, что хвостовой вызов только с виду хвостовой

Да нет, он всегда хвостовой.

_между_ хвостовым вызовом и выходом есть ещё операции с фреймом.

Нет, нету. Хвостовой вызов - это, в общем, обычный джамп.

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

Это можно доказать, если навелосипедить список-стек ручками вокруг «хвостового» вызова - сразу станет очевидно, что _между_ хвостовым вызовом и выходом есть ещё операции с фреймом.

Да, кстати, в нормальных языках стек оверфлоу вообще не бывает, т.к. стек лежит в хипе.

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

в упор не наблюдаю ТСО

TCO это оптимизация связанная с TC, а TC - просто любой вызов который может случиться последним по ходу control flow данной функции. Если его нельзя никак оптимизировать устранением в условный или безусловный переход (то есть он не рекурсивный и/или jmp вместо него может сломать control flow нашей функции) или нельзя использовать для других оптимизаций (например, он не начинает простую последовательность детерминированных операцией вроде if, ?: или арифметики прямо перед call-вызовом (рекурсивным или нет)), то это просто хвостовой вызов безо всякой оптимизации.

Вот в первом примере gcc и clang (начиная с -O2 и -O1 соответственно) устраняют хвостовой ?:, устраняют (уже) хвостовой x* и устраняют (уже) хвостовой (бывший линейный) рекурсивный вызов f в локальный условный переход. clang даже что-то комментирует на эту тему:

f:                                      # @f
	cmpl	$2, %edi
	movl	$1, %eax
	jl	.LBB0_2
.LBB0_1:                                # %tailrecurse
                                        # =>This Inner Loop Header: Depth=1
	imull	%edi, %eax
	decl	%edi
	cmpl	$1, %edi
	jne	.LBB0_1
.LBB0_2:                                # %tailrecurse._crit_edge
	ret

Или лучше взять такой код:

unsigned f_(/* range<0, 5> */ unsigned x)
{
    switch (x) {
        case 0: return 1;
        case 1: return 1;
        case 2: return 2;
        case 3: return 6;
        case 4: return 24;
        case 5: return 120;
    }

    return 0; // unreachable (kinda)
}

unsigned f(unsigned x)
{
    return x <= 5 ? f_(x) : x * f(x - 1);
}

Что можно сделать:

  • 1) Устранить хвостовую операцию ?:
  • 2.1) Устранить (уже) хвостовой нерекурсивный вызов f_
  • 2.2) Или заинлайнить f_
  • 3) Устранить (уже) хвостовую операцию x*
  • 4) Устранить (уже) хвостовой (бывший линейный) рекурсивный вызов f_
  • 5) Ну и switch сделать через массив в качестве бонуса (хотя это к теме не относится).

clang (> -O1) делает 1-2.1:

	jmp	f_                      # TAILCALL

и не делает 3-5. И даже не может, потому тчто выбрав 2.1 уже нельзя сделать 2.2-4, так как ret в f_ сломает работу f.

gcc (> -O2) делает 1 и 2.2-5, то есть его код вообще без call*:

f:
.LFB1:
	cmpl	$5, %edi
	movl	$1, %eax
	jbe	.L10
.L9:
	leal	-1(%rdi), %edx
	imull	%edi, %eax
	cmpl	$5, %edx
	movl	%edx, %edi
	jne	.L9
.L7:
	imull	CSWTCH.2(,%rdx,4), %eax
	ret
.L10:
	movl	%edi, %edx
	jmp	.L7

(c -O3 он ещё вдруг начинает на SSE считать).

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

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

т.е. без tl; никак?

это что дабл, указатель, инт, лонг или какая то их смесь?

я не знаю что это, но на машинный код оно явно не похоже.

Забыл, с чего я начал? Я напомню:

но и большинства программистов и производителей CPU. Никаких лямбд я что-то в процессорах не наблюдаю. Сабжей тоже...

где тут про дампы? Тут про код CPU. Вот в этом коде есть указатели, есть int'ы, и есть double. А вот хвостовой рекурсии и лямбд нет. Что не удивительно, так-как отсутствует сама сущность данных - функция. Функция - это какой-то код, её можно только выполнить. И всё. На этом операции с функциями заканчиваются. Есть ещё и адрес функции, но с ним тоже ничего нельзя сделать, ибо его тоже можно лишь выполнять (и то, это костыль, который во первых медленный, во вторых, на большинстве CPU выполнять можно не что угодно, а только сегмент кода, если попытаться выполнить стек или данные, CPU сразу прибьёт эту программу, и отдаст управления OS. Потому возможна только эмуляция передачи функции, а уж действия над функциями невозможны принципиально. Например невозможно сделать полноценную передачу даже тривиальной функции типа x+y, максимум чего мы добьёмся, это косвенный вызов функции, который на порядок дороже самой тривиальной функции)

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

Да, кстати, в нормальных языках стек оверфлоу вообще не бывает, т.к. стек лежит в хипе.

Хоть один такой язык существует?

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

3) Устранить (уже) хвостовую операцию x*

они не «уже» хвостовые, в энергичном ЯП хвостовые вызовы веток ифа считаются хвостовыми вызовами ифа и (если иф сам хвостовой) хвостовыми вызовами всей функци просто согласно семантике ЯП. Так что тут хвостовые f_, * (последний инлайнится, т.к. это оператор) и все.

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

вобщем-то всегда можно, если нельзя - то он нифига не хвостовой :)

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

Кстати, у циклов через рекурсию есть один значительный плюс - loop-unrolling это по факту обычный инлайнинг, а вынесение константы за цикл превращается в вынесение константы из лямбды. То есть эти оптимизации получаем «искаробки».

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

Тут про код CPU.

Код цпу - это бинарник, дебилушка. А теперь ответь мне, чем в бинарнике отличается «положить в регистр инт» от «положить в регистр флоат».

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

Нужно, конечно. Во всех случаях, когда этот вызов не заинлайнен.

а если это библиотечная функция и/или функция из другого модуля? Тоже не нужно, ибо невозможно.

Да нет, он всегда хвостовой.

Нет, нету. Хвостовой вызов - это, в общем, обычный джамп.

в том-то и дело, что кроме RET там есть и другой код, который ты тупо НЕ ВИДИШЬ, но он - есть. Видел, я в своём коде написал в начале функции int i=0 ? Это я выделил sizeof(int) char'ов из стека. А кто их возвращает в стек? Если ты не видишь этого кода, это не значит, что его там нет. Потому JMP ты не отделаешься, нужно ещё SP пофиксить. В C++ ситуация ещё печальнее, там не только SP надо фиксить, но и выполнить код всех деструкторов, перед выходом из функции. Если 10 раз вошёл в одну и туже функцию, тебе 10 раз придётся все деструкторы выполнять - тут уже задумаешься о том, а стоило-ли такой цикл разворачивать в цикл?

И ещё об оптимизации: твоя ТСО это конечно сильно, но это далеко не всё: сам цикл тоже можно развернуть, и тем достигнуть профита. Например можно выполнять две итерации сразу - со времён iPentium у нас два ALU, а следовательно CPU умеет сразу две операции за такт выполнять, потому и кормим его Array и _одновременно_ Array[i+1], отчего скорость подскакивает почти вдвое. Вот только с сабжем это вряд-ли пройдёт - gcc сабж разворачивает только в самых примитивных случаях, потому IRL это будет просто CALL, и хорошо если с абсолютным (а не косвенным) адресом.

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

Да, кстати, в нормальных языках стек оверфлоу вообще не бывает, т.к. стек лежит в хипе.

ты так говоришь, как будто-бы в этом есть что-то хорошее...

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

ты так говоришь, как будто-бы в этом есть что-то хорошее...

В том, что не может быть стековерфлоу? Конечно, есть. Это, как минимум, гарантия отсутствия целого класса ошибок и уязвимостей.

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