using System;
using System.Diagnostics;
namespace TestTailCall
{
class Program
{
static void Main(string[] args)
{
var sw = new Stopwatch();
sw.Start();
fun1(0);
sw.Stop();
Console.WriteLine(sw.Elapsed);
Console.ReadLine();
}
static int fun1(int count)
{
if (count < 10000)
{
count = count + 1;
return fun2(count);
}
else
return count;
}
static int fun2(int count)
{
if (count < 10000)
{
count = count + 1;
return fun1(count);
}
else
return count;
}
}
}
Версия на MSIL (писал в соответствии с описанием Tailcall в MSDN, исходя из того, что для корректной обработки хвостового вызова обязательно должна присутствовать цепочка tail. -> call -> ret):
Здравствуйте, hardcase, Вы писали:
H>Для взаимнорекурсивных функций вполне годится. А для случая с одной функцией br и замена параметров — наше все.
Да. Это, собственно, две разные оптимизации по сути — раскрутка хвостовой рекурсии в цикл и использование префикса tail. для хвостовых вызовов. Собственно, о чем я как раз и хотел сказать. А тот тут ваше "руководство" почему-то считает, что использование tail. вообще не имеет смысла.
Кстати, я время криво померил. У меня в итоговое время попадает так же и Джит. Так что фактически там разница даже поболее двух раз будет.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Да. Это, собственно, две разные оптимизации по сути — раскрутка хвостовой рекурсии в цикл и использование префикса tail. для хвостовых вызовов. Собственно, о чем я как раз и хотел сказать. А тот тут ваше "руководство" почему-то считает, что использование tail. вообще не имеет смысла.
Что-то мне подсказывает, что "руководство" имеет в виду использование .tail в рамках одной функции.
Здравствуйте, catbert, Вы писали:
C>Версия фреймворка? Машина?
4.0
i7 M 620
Да, и тест не очень корректный, я прокосячил малость — не учитывается время на Джит. Т.е. реальная ситуация должна быть еще более благоприятной для tailcall.
Здравствуйте, hardcase, Вы писали:
ВВ>>Да. Это, собственно, две разные оптимизации по сути — раскрутка хвостовой рекурсии в цикл и использование префикса tail. для хвостовых вызовов. Собственно, о чем я как раз и хотел сказать. А тот тут ваше "руководство" почему-то считает, что использование tail. вообще не имеет смысла. H>Что-то мне подсказывает, что "руководство" имеет в виду использование .tail в рамках одной функции.
Честно говоря, не хочется играть в испорченный телефон. Но почему-то мою мысль о том, что tail recursion и proper tail call — это две *разные* оптимизации, не восприняли.
Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, Воронков Василий, Вы писали: ВВ>>Выводы делайте сами. H>Дошел до дома. Проверил. Тормозит. Флаг компилятора -Ot, .net 4.0, x86. Не исключаю возможности, что тормоза есть лишь на x86.
Забавно, блин. На x86 действительно картина совершенно иная. Я немного поправил тест — так, чтобы он не учитывал Джит. В начале метода Main добавил:
ldc.i4.0
call int32 TestTailCall.Program::fun1(int32)
pop
Т.о. тест прогоняется два раза и время компиляции не учитывается.
Здравствуйте, hardcase, Вы писали:
ВВ>>Они практически меняются местами ВВ>>Что-то они намудрили H>На x64 другой JIT-компилятор и другая конвенция вызовов.
Я понимаю, что другой. Но "tail." сам по себе ничего не меняет. По большому счету он должен просто снимать со стека текущий фрейм. Здесь же речь идет о разнице в производительности в два порядка. Это при том, что далее идет самый обычный call, который в свою очередь на два порядка быстрее. Я находить это странным.
Здравствуйте, hardcase, Вы писали: H>Здравствуйте, Воронков Василий, Вы писали: ВВ>>Я находить это странным. H>Где-то об этом писалось. В x86 какая-то функция вызывается вместо джита её тела по месту.
Здравствуйте, VladD2, Вы писали:
VD>Ну, так теперь то ты понимашь, что это косяк? Могли бы везде сделать шустро. Переписывание в цикл всегда работает шустро.
Для х86 — косяк. Хотя однозначного ответа об использовании tail call эти тесты все же не дают. На х64 быстро, под моно, как вы говорите, тоже быстро. Ну и все-таки стек не слетает.
VD>Кстати попробуй его тоже в тесте реализовать. Чтобы было с чем сравнивать.
Да с циклом и так все понятно. Меня вообще proper tail call интересует в первую очередь не в связи с рекурсией, а в связи с CPS, для которого он есть первое и необходимое требование.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Для х86 — косяк. Хотя однозначного ответа об использовании tail call эти тесты все же не дают. На х64 быстро, под моно, как вы говорите, тоже быстро. Ну и все-таки стек не слетает.
Со стеком все ясно. Только на практике он и так не слетает. Ни одно жалобы за много лет.
Что до tail call, то опция компиляции такая есть. Кому оно надо, может включить.
VD>>Кстати попробуй его тоже в тесте реализовать. Чтобы было с чем сравнивать.
ВВ>Да с циклом и так все понятно. Меня вообще proper tail call интересует в первую очередь не в связи с рекурсией, а в связи с CPS, для которого он есть первое и необходимое требование.
Не, не. Понятно не все. Ты сделай и покажи результат. Потому как может оказаться, что по сравнению с ним tail call не конкурент.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
