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>>Я же еще в своем сообщении указал: флаг компиляции -Ot.
ВВ>А что делает этот флажок? Включает генерацию tail для случаев типа взаиморекурсивных функций или использует tail даже там, где сейчас рекурсия вручную раскручивается в цикл?
Включает генерацию .tail для хвостовых вызовов и это происходит на этапе T4 (после него происходит генерация IL). Локальные функции сворачивающиеся в цикл выявляются до этого.
Здравствуйте, hardcase, Вы писали:
H>Для взаимнорекурсивных функций вполне годится. А для случая с одной функцией br и замена параметров — наше все.
Да. Это, собственно, две разные оптимизации по сути — раскрутка хвостовой рекурсии в цикл и использование префикса tail. для хвостовых вызовов. Собственно, о чем я как раз и хотел сказать. А тот тут ваше "руководство" почему-то считает, что использование tail. вообще не имеет смысла.
Кстати, я время криво померил. У меня в итоговое время попадает так же и Джит. Так что фактически там разница даже поболее двух раз будет.
Здравствуйте, hardcase, Вы писали:
ВВ>>Они практически меняются местами ВВ>>Что-то они намудрили H>На x64 другой JIT-компилятор и другая конвенция вызовов.
Я понимаю, что другой. Но "tail." сам по себе ничего не меняет. По большому счету он должен просто снимать со стека текущий фрейм. Здесь же речь идет о разнице в производительности в два порядка. Это при том, что далее идет самый обычный call, который в свою очередь на два порядка быстрее. Я находить это странным.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Воронков Василий, Вы писали:
ВВ>>Для х86 — косяк. Хотя однозначного ответа об использовании tail call эти тесты все же не дают. На х64 быстро, под моно, как вы говорите, тоже быстро. Ну и все-таки стек не слетает.
VD>Со стеком все ясно. Только на практике он и так не слетает. Ни одно жалобы за много лет.
Тут ты лукавишь. На x64 самому компилятору нужен значительно больший стек.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Да. Это, собственно, две разные оптимизации по сути — раскрутка хвостовой рекурсии в цикл и использование префикса 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>Здравствуйте, Воронков Василий, Вы писали: ВВ>>Я находить это странным. 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 не конкурент.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
ВВ>>Для х86 — косяк. Хотя однозначного ответа об использовании tail call эти тесты все же не дают. На х64 быстро, под моно, как вы говорите, тоже быстро. Ну и все-таки стек не слетает. VD>Со стеком все ясно. Только на практике он и так не слетает. Ни одно жалобы за много лет. VD>Что до tail call, то опция компиляции такая есть. Кому оно надо, может включить.
В смысле Немерле уже умеет ее генерить?
VD>>>Кстати попробуй его тоже в тесте реализовать. Чтобы было с чем сравнивать. ВВ>>Да с циклом и так все понятно. Меня вообще proper tail call интересует в первую очередь не в связи с рекурсией, а в связи с CPS, для которого он есть первое и необходимое требование. VD>Не, не. Понятно не все. Ты сделай и покажи результат. Потому как может оказаться, что по сравнению с ним tail call не конкурент.
Блин, конечно, не конкурент. tail. call — это не замена ручной оптимизации хвостовой рекурсии, а дополнение к ней в тех случаях, когда раскрутить в цикл не получается. Попробуй раскрутить в цикл foldr. А tail. call даже тут дает некоторое преимущество.
Здравствуйте, Воронков Василий, Вы писали:
VD>>Что до tail call, то опция компиляции такая есть. Кому оно надо, может включить.
ВВ>В смысле Немерле уже умеет ее генерить?
Я что-то не ясно написал? Набери в консоли ncc -h
ВВ>Блин, конечно, не конкурент. tail. call — это не замена ручной оптимизации хвостовой рекурсии, а дополнение к ней в тех случаях, когда раскрутить в цикл не получается. Попробуй раскрутить в цикл foldr. А tail. call даже тут дает некоторое преимущество.
А в тех случаях когда получается? Пойми, не гоже такие оптимизации делать вручную. Для хвостовой рекурсии эта команда обязана порождать тупо переход в начало функции. Ничего снимать со стека не надо. Почему в МС это не делают никто не знает.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, VladD2, Вы писали:
ВВ>>>Для х86 — косяк. Хотя однозначного ответа об использовании tail call эти тесты все же не дают. На х64 быстро, под моно, как вы говорите, тоже быстро. Ну и все-таки стек не слетает. VD>>Со стеком все ясно. Только на практике он и так не слетает. Ни одно жалобы за много лет. VD>>Что до tail call, то опция компиляции такая есть. Кому оно надо, может включить.
ВВ>В смысле Немерле уже умеет ее генерить?
Я же еще в своем сообщении указал: флаг компиляции -Ot.
Здравствуйте, hardcase, Вы писали:
H>Я же еще в своем сообщении указал: флаг компиляции -Ot.
А что делает этот флажок? Включает генерацию tail для случаев типа взаиморекурсивных функций или использует tail даже там, где сейчас рекурсия вручную раскручивается в цикл?
Здравствуйте, VladD2, Вы писали:
VD>>>Что до tail call, то опция компиляции такая есть. Кому оно надо, может включить. ВВ>>В смысле Немерле уже умеет ее генерить? VD>Я что-то не ясно написал? Набери в консоли ncc -h
В другой ветке ты говорил, что в случае взаимной рекурсии Немерле использует обычный call — по крайней мере, я именно так это понял. Раз Немерле tail. call и так генерит, то, собственно, весь этот спор никакого смысла не имеет, все и так хорошо.
VD>А в тех случаях когда получается? Пойми, не гоже такие оптимизации делать вручную. Для хвостовой рекурсии эта команда обязана порождать тупо переход в начало функции. Ничего снимать со стека не надо. Почему в МС это не делают никто не знает.
Я уже понял, что на сей раз "точкой непонимания" у нас было то, что ты считаешь, что рантайм должен сам уметь разворачивать tail. call в цикл, когда это возможно. Я же просто читаю описание этого оп кода и вижу, что там никаких циклов не обещается, а говорится только то, что данный опкод снимает текущий фрейм со стека.
Опять же, согласись, проблема не в том, что он не умеет разворачиваться в цикл, вы и сами с этим прекрасно справляетесь, а в том, что под x86 там присутствуют какие-то дикие ничем не объяснимые тормоза, которые весьма сильно снижают пользу от tail. call.
Хотя, честно, для Немерле 2 я бы все же выбрал модель, когда tail. call генерируется по умолчанию, но его можно отключать через специальную опцию. Дополнительный кост вызова все же лучше, чем срыв стека. Особенно под x64, где, как правильно заметил хардкейс, стек имеет свойство заканчиваться куда быстрее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>В другой ветке ты говорил, что в случае взаимной рекурсии Немерле использует обычный call — по крайней мере, я именно так это понял. Раз Немерле tail. call и так генерит, то, собственно, весь этот спор никакого смысла не имеет, все и так хорошо.
Он ее не генерит, так как по умолчанию эта возможность выключена. И тебе тут раз 10 объяснили почему.
ВВ>Я уже понял, что на сей раз "точкой непонимания" у нас было то, что ты считаешь, что рантайм должен сам уметь разворачивать tail. call в цикл, когда это возможно. Я же просто читаю описание этого оп кода и вижу, что там никаких циклов не обещается, а говорится только то, что данный опкод снимает текущий фрейм со стека.
Сколько раз повторять, что этот опкод работает медленнее вызова (как нимимум на х86)?
ВВ>Хотя, честно, для Немерле 2 я бы все же выбрал модель, когда tail. call генерируется по умолчанию, но его можно отключать через специальную опцию. Дополнительный кост вызова все же лучше, чем срыв стека. Особенно под x64, где, как правильно заметил хардкейс, стек имеет свойство заканчиваться куда быстрее.
Зачем людям по умолчанию тормоза?
Единственное что разумно было бы сделать — это генерить этот опкод только для хвостовых вызовов и только для групп функций (тех что через and связаны). А для прямой хвостовой рекурсии всегда применять зацикливание. А то сейчас зацикливание отключается если генерируется этот опкод.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Сколько раз повторять, что этот опкод работает медленнее вызова (как нимимум на х86)?
Вроде бы с этим мы разобрались, зачем повторять?
ВВ>>Хотя, честно, для Немерле 2 я бы все же выбрал модель, когда tail. call генерируется по умолчанию, но его можно отключать через специальную опцию. Дополнительный кост вызова все же лучше, чем срыв стека. Особенно под x64, где, как правильно заметил хардкейс, стек имеет свойство заканчиваться куда быстрее. VD>Зачем людям по умолчанию тормоза?
Вопрос, насколько критичны эти тормоза. Стоимость вызова функции обычно меньше, чем стоимость выполнения функции. А без этого оп-кода очень легко сорвать стек. *Особенно* под x64. Где вроде как tail. call шустрый.
VD>Единственное что разумно было бы сделать — это генерить этот опкод только для хвостовых вызовов и только для групп функций (тех что через and связаны). А для прямой хвостовой рекурсии всегда применять зацикливание. А то сейчас зацикливание отключается если генерируется этот опкод
Хардкейс мне тут написал, что это не так и "зацикливание" не отключается. Кому верить?
Собственно, такой вариант и кажется оптимальным. Там, где можно — ручное раскрытие рекурсии в цикл. В остальных случаях — tail. call. Ну и tail. call может включаться или отключаться через опцию компилятора (тут уж по вкусу).
Здравствуйте, hardcase, Вы писали:
H>Включает генерацию .tail для хвостовых вызовов и это происходит на этапе T4 (после него происходит генерация IL). Локальные функции сворачивающиеся в цикл выявляются до этого.
Уверен? Мы с Вольфхаундом пробовали включать tail-call для проекта парсера. Это давало существенное замедление. Мне показалось, что это как раз из-за замены циклов на вызовы.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Вопрос, насколько критичны эти тормоза.
Если отталкиваться не от теоретико-болобольских интересов, а от практических, то все становится очень просто. Берешь проект, врубаешь в нем -Ot и прогоняешь бенчмарки. Именно это мы и делали. Получали замедление. Далее делался очевидный вывод — "на фига козе баян?".
ВВ>Хардкейс мне тут написал, что это не так и "зацикливание" не отключается. Кому верить?
Дык даже если не отколючается. Если нет непрямой рекурсии, то смысла в применении данного опкода нет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Если отталкиваться не от теоретико-болобольских интересов, а от практических, то все становится очень просто. Берешь проект, врубаешь в нем -Ot и прогоняешь бенчмарки. Именно это мы и делали. Получали замедление. Далее делался очевидный вывод — "на фига козе баян?".
Ага, а тестировали вы только под CLR x86. Когда есть CLR x64 и Mono, под которыми быстрее.
ВВ>>Хардкейс мне тут написал, что это не так и "зацикливание" не отключается. Кому верить? VD>Дык даже если не отколючается.
Ну хотелось бы все-таки понять, так это или нет.
VD>Если нет непрямой рекурсии, то смысла в применении данного опкода нет.
Мне непонятно, что ты хочешь этим сказать. Во-первых, смысл есть. Для CPS, о чем я вроде уже говорил. Во-вторых, я никогда никому не предлагал использовать этот опкод в качестве замены "зацикливанию".
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Ага, а тестировали вы только под CLR x86. Когда есть CLR x64 и Mono, под которыми быстрее.
Про то что в Mono быстрее мы и так знали. Это известно еще со времен реализации данной фичи в компиляторе. Если почитать описание к ключам компиляции, то можно заметить, что об этом в них сказано.
x64 же никого не трогает, так как мы тестировали парсер, а его производительность важна именно на х86, так как в основном он будет использоваться из VS.
ВВ>Мне непонятно, что ты хочешь этим сказать. Во-первых, смысл есть. Для CPS, о чем я вроде уже говорил. Во-вторых, я никогда никому не предлагал использовать этот опкод в качестве замены "зацикливанию".
Ты уже преизрядно достал. На вопрос тебе ответили, но ты хочешь добиться чего-то еще.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.