Здравствуйте, Воронков Василий, Вы писали:
ВВ>Я не понимаю, почему нужно противопоставлять хвостовую рекурсию и proper tail call — и к тому же сравнивать их по производительности. TailCall логично генерировать в том случае, если у нас нет банальной хвостовой рекурсии. Он всяко должен быть быстрее, чем обычный Call.
Все просто. Если исходить из того что нужно потрындеть в форумах, а получить бенефит от фичи, то становится очевидно, что использовать на практике TailCall не обеспечивающий достаточной скорости глупо.
ЗЫ
Ты прочитай всю ветку. Посмотри что за вопрос в ней был задан. А то твоя манера поменять смысл обсуждения несколько раздражает.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Собственно, чисто логически это так. Но с т.з. реализации не совсем. Хвостовая рекурсия вполне тривиально реализуется и без поддержки рантайма, собственно, тут и не нужно никакой поддержки.
Рекурсия бывает не прямая. Для прямой сделать оптимизацию действительно не сложно. А вот для непрямой — сложно. Тут рядом кто-то скзал, что для and-методов в F# применяют МС-ный опкод, а для прямой переписывание в цикл. В Немерле непрямая рекурсия вообще не оптимизируется, что как ты понимаешь не здорово.
ВВ>Хвостовой вызов же ты руками не сделаешь никак. Ну или по крайней мере это задачка на уровне full program optimization.
А зачем он нужен, если исключить реализацию рекурсии?
ВВ>Вы же зачем-то сравниваете заинлайненную вручную хвостовую рекурсию и стандартный TailCall, и мне непонятно — зачем? TailCall может рулить и в тех случаев, где вообще никакой рекурсии нет.
Он медленее даже обычного вызова. В МС поют о том, что дескать там мешает защита. В 4.0 они его ускорили, но все равно это тормоз.
В то же время в Моно TailCall работает очень быстро. Так что это явно недоработка ребят из МС.
ЗЫ
Предлагаю закрыть тему и не разводить флуд.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
Z>>>Кстати, ктонибудь тестил ее в .Net4? Они ее оптимизировали вроде. Кто на ты с IL, потестите плиз. VD>>Тестил. Нихера они не сделали. Разогнали немного. Теперь она тормоизт не в 10 раз больше, а в 5.
ВВ>А все потому что property tail call (оп код TailCall) и tail recursion — это не совсем одно и то же.
В МС объясняют это проблемами связанными с протаскиванием защиты. Вот только кому нужна защита для private-методов или (тем более) локальных фукнций?
Заявление что TailCall и хвостовая рекурсия это не одно и тоже просто бредовый флуд. TailCall единственный легальный способ выразить ховстовую рекурсию (как прямую, так и не прямую). Других нет. По сему обсуждать тут нечего. В Моно TailCall работает с той же скорость, что и переписывание кода в цикл (а то и быстрее).
Тебя же предупреждаю, что в этой теми это офтоп. Будешь развивать тему, снесу все твои сообщения, а тебя забаню за провокацию флуда.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
ВВ>>Я не понимаю, почему нужно противопоставлять хвостовую рекурсию и proper tail call — и к тому же сравнивать их по производительности. TailCall логично генерировать в том случае, если у нас нет банальной хвостовой рекурсии. Он всяко должен быть быстрее, чем обычный Call. WH>В реализации мелкософт он значительно медленней, чем обычный вызов.
А как это тестировалось? По сути TailCall — это обычный Call + некие дополнительные действия. Т.е. чистое время работы больше. Но TailCall позволяет не возвращаться в родительский метод. К примеру, возможный тест — взять функцию типа foldr и прогнать ее для большого списка с включенным TailCall и без него.
На моей виртуальной машине, к примеру, TailCall тоже формально медленнее Call, но в сценариях, аналогичных вышеописанному, он дает существенный прирост.
WH>А ты опять развел флуд даже не попытавшись понять, о чем разговор.
Разговор, я так понимаю, о том, что TailCall вы не генерируете.
ВВ>>Собственно, чисто логически это так. Но с т.з. реализации не совсем. Хвостовая рекурсия вполне тривиально реализуется и без поддержки рантайма, собственно, тут и не нужно никакой поддержки. VD>Рекурсия бывает не прямая. Для прямой сделать оптимизацию действительно не сложно. А вот для непрямой — сложно. Тут рядом кто-то скзал, что для and-методов в F# применяют МС-ный опкод, а для прямой переписывание в цикл. В Немерле непрямая рекурсия вообще не оптимизируется, что как ты понимаешь не здорово.
Я одно пытаюсь понять — вы утверждаете, что TailCall в MSIL настолько медленный, что совершенно не юзабелен? Т.е. если бы в F# для взаимно-рекурсивных функций не использовали TailCall, то код работал бы быстрее?
По крайней мере благодаря нему стек слетать не должен.
ВВ>>Хвостовой вызов же ты руками не сделаешь никак. Ну или по крайней мере это задачка на уровне full program optimization. VD>А зачем он нужен, если исключить реализацию рекурсии?
Для CPS, например.
Потом мы исключаем не рекурсию, а хвостовую рекурсию. Бывают более хитрые сценарии. К примеру, TailCall может быть полезен для функций типа foldr — где рекурсия выражена через хвостовой вызов предиката.
Короче — любая непрямая рекурсия с хвостовым вызовом. and — как частный случай.
ВВ>>Вы же зачем-то сравниваете заинлайненную вручную хвостовую рекурсию и стандартный TailCall, и мне непонятно — зачем? TailCall может рулить и в тех случаев, где вообще никакой рекурсии нет. VD>Он медленее даже обычного вызова. В МС поют о том, что дескать там мешает защита. В 4.0 они его ускорили, но все равно это тормоз. VD>В то же время в Моно TailCall работает очень быстро. Так что это явно недоработка ребят из МС. VD>ЗЫ VD>Предлагаю закрыть тему и не разводить флуд.
Если ты считаешь это обсуждение "флудом", можешь просто не отвечать.
Здравствуйте, VladD2, Вы писали:
VD>Никак. Просто вызов как в C#.
Но F# хотя бы tail call влепляет, а в Nemerle, получается, stack overflow будет, даже если рекурсия хвостовая, хотя и не прямая.
Или я не правильно понял?
Re[10]: 2Модератор. Отделите обсуждение по TailCall
Здравствуйте, Димчанский, Вы писали:
Д>Но F# хотя бы tail call влепляет, а в Nemerle, получается, stack overflow будет, даже если рекурсия хвостовая, хотя и не прямая.
Так и есть. Только на практике непрямая рекурсия переполняющая стек встречается редко. А вот скорость важна всегда.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: 2Модератор. Отделите обсуждение по TailCall
Здравствуйте, Димчанский, Вы писали:
Д>Здравствуйте, VladD2, Вы писали:
VD>>Никак. Просто вызов как в C#.
Д>Но F# хотя бы tail call влепляет, а в Nemerle, получается, stack overflow будет, даже если рекурсия хвостовая, хотя и не прямая. Д>Или я не правильно понял?
В проекте насущно необходим tail-call — сообщи об этом компилятору флагом -Ot.
Здравствуйте, Димчанский, Вы писали:
Д>Здравствуйте, VladD2, Вы писали:
VD>>Никак. Просто вызов как в C#.
Д> а в Nemerle, получается, stack overflow будет, даже если рекурсия хвостовая, хотя и не прямая.
А как по твоему работают while, foreach, for макросы, если они выражены через рекурсивную функцию?
Здравствуйте, hardcase, Вы писали:
H>А как по твоему работают while, foreach, for макросы, если они выражены через рекурсивную функцию?
Это ты меня спрашиваешь?
Я не создавал Nemerle но позволю предположить, что хоть они и выраженены через рекурсивную функцию, но рекурсия там, видимо, прямая и в итоге компилятор на уровне IL инструкций раскручивает все в обычный цикл.
А вот если попытаться написать макрос/метод с непрямой рекурсией, где используется несколько взаимно рекурсивных методов, то, как говорил Влад, такое развернется в обычные вызовы (IL-инструкция call, без tail), что чревато потенциальным срывом стека.
Здравствуйте, hardcase, Вы писали:
H>В проекте насущно необходим tail-call — сообщи об этом компилятору флагом -Ot.
Я бы не сказал, что tail-call насущно необходим везде и всюду.
Если что-то можно развернуть в цикл — не нужно никаких tail-cal. Если рекурсию не получается в циклы развернуть, т.к. используется много взаимно рекурсивных методов, но рекурсии тем не менее хвостовые, то нужно делать tail call. Если взаимные рекурсии НЕ хвостовые, то обычный call.
Такое поведение считаю единственно верным.
Здравствуйте, Димчанский, Вы писали:
Д>А вот если попытаться написать макрос/метод с непрямой рекурсией, где используется несколько взаимно рекурсивных методов, то, как говорил Влад, такое развернется в обычные вызовы (IL-инструкция call, без tail), что чревато потенциальным срывом стека.
Все так. Только пока что ни одной жалобы на такой срыв не было. Так что проблема сильно преувеличена.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Димчанский, Вы писали:
Д>Если что-то можно развернуть в цикл — не нужно никаких tail-cal. Если рекурсию не получается в циклы развернуть, т.к. используется много взаимно рекурсивных методов, но рекурсии тем не менее хвостовые, то нужно делать tail call. Если взаимные рекурсии НЕ хвостовые, то обычный call. Д>Такое поведение считаю единственно верным.
Оптимально было бы делать анализ наличия непрямой хвостовой рекурсии и именно в этих местах вставлять tail-call. А еще лучше переписывать взаимно-рекурсивные функции в одну функцию с циклами.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
TailCall может рулить и в тех случаев, где вообще никакой рекурсии нет.
