Здравствуйте, Ziaw, Вы писали:
Z>Кстати, ктонибудь тестил ее в .Net4? Они ее оптимизировали вроде. Кто на ты с IL, потестите плиз.
Я тут попробовал изобразить на F# тест хвостовой рекурсии (можно скачать проект с откомпиленным exe: TailRecursionTest.zip):
open System
open System.Diagnostics
let rec loop_rec n =
if n > 0L
then help_tail_call (n-1L)
else ()
and help_tail_call n =
if n > 0L
then loop_rec (n-1L)
else ()
let loop_for n =
let mutable i = n
while i > 0L do
i <- i - 1L
()
let time s f =
printfn "Starting '%s'..." s
let sw = Stopwatch.StartNew()
f()
sw.Stop()
printfn "Done in %f ms..." sw.Elapsed.TotalMilliseconds
sw.Elapsed.TotalMilliseconds
let time_rec n = (fun () -> loop_rec n) |> time "rec"
let time_for n = (fun () -> loop_for n) |> time "for"
[<EntryPoint>]
let main (args : string[]) =
if args.Length <> 1
then failwith "Error: expected argument <loop count>"
let n = Int64.Parse(args.[0])
printfn "Ratio: %f" ((time_rec n) / (time_for n))
printfn "Ratio: %f" ((time_rec n) / (time_for n))
0
Рекурсию сделал через две рекурсивных функции, которые через tail call вызывают друг друга. Если делаешь в виде одной функции, то компилятор делает такой же цикл, как в loop_for.
Не знаю на сколько корректно. Но запустив программу (release build, any cpu) у себя на 64-битной системе получил:
> TailRecursionTest.exe 1000000000
Starting 'rec'...
Done in 1243.135100 ms...
Starting 'for'...
Done in 710.358100 ms...
Ratio: 1.750012
Starting 'rec'...
Done in 1242.459000 ms...
Starting 'for'...
Done in 711.537000 ms...
Ratio: 1.746162
Т.е. хвостовой вызов в 1.75 раза медленнее цикла. Для чистоты эксперимента нужно было бы наверное поправить IL код, чтобы loop_rec вызывала себя же.
Здравствуйте, Ziaw, Вы писали:
Z>Какая генерация имеется ввиду? Текстовая? Если текстовая — можно попробовать сделать преобразование AST в строку в виде C#. Не все можно преобразовать, но если ограничивать конструкции — вполне можно генерить. Но текст это плохое решение.
Да, имеется ввиду генереация текста на C# из AST Nemerle. Насколько это сложно (по времени)?
Z>Но nemerle умеет компилировать C#, при этом будут работать макросы уровня сборки и атрибутные. Эти макросы могут генерить что угодно на этапе компиляции.
Я просто подумал, что если вы можете в одну сторону C# -> Nemerle сконвертировать, то может быть можно и в обратную сторону?
Возможно я ошибаюсь, но мне кажется, что при наличии такой фичи людям было бы значительно проще общаться с работодателем, т.к. они бы могли уже сейчас начать спокойно играться с алгебраическими типами Nemerle, его макросами, например computation expressions, т.к. могли бы в любой момент свои наработки на Nemerle перевести в C# , что-то допилить и включить в C# проекты (понимаю, что кода там будет побольше и может быть не все будет выглядеть красиво). Т.е. у людей всегда был бы выбор или убедить своих, как все круто на Nemerle или, если упрутся, загенерить C# код и допиливать уже только его. Чисто стратегически это могло бы вывести часть теоретиков в разряд практиков, т.е. большее число людей могло бы спокойней играться с Nemerle и подтягивать других, т.к. мнение работодателя бы здесь играло значительно меньшую роль.
Здравствуйте, Димчанский, Вы писали:
Д>Скажите, насколько сложен такой финт ушами? Планируете ли?
Я планировал реализовать это в Н2. Ну, или в каком-то из промежуточных релизов.
Задача там не очень сложная, так что ее мог бы решить кто-то из комьюнити. На ней можно и язык подучить.
Кроме того эта же задача решается с другой стороны, со стороны декомпиляторов сборок. JetBrains dotPeek и ILSpy уже очень близки к тому чтобы полностью декомпилировать сборки немерла в C#. А это мало отличается от генерации кода по немерловым кишкам. Результат будет тот же — C#-код который можно скомпилировать компиляторами C#. Так что возможно, имеет смысл помочь разработчикам ILSpy-я и dotPeek-а. Первым можно просто присылать патчи исправляющие их ошибки. А вторым слать багрепорсты и просить их сделать поддержку немерла более качественной.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Так оп-код TailCall это же несколько более другая штука. Она нужна не для реализации хвостовой рекурсии, которая вполне банально переписывается в цикл, а для реализации хвостового вызова. По сути все, что она делает — это снимает со стека текущую функцию, и мы в нее больше не возвращаемся. В целом — довольно полезная оптимизация.
Ну и что ты тут опять левую философию на ровном месте разводишь?
Хвостовая рекурсия частный случай хвостового вызова.
И то и другое должно очень хорошо оптимизироваться рантаймом.
Но МС не осилил.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Я не понимаю, почему нужно противопоставлять хвостовую рекурсию и proper tail call — и к тому же сравнивать их по производительности. TailCall логично генерировать в том случае, если у нас нет банальной хвостовой рекурсии. Он всяко должен быть быстрее, чем обычный Call.
В реализации мелкософт он значительно медленней, чем обычный вызов.
А ты опять развел флуд даже не попытавшись понять, о чем разговор.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Воронков Василий, Вы писали:
Z>>>Кстати, ктонибудь тестил ее в .Net4? Они ее оптимизировали вроде. Кто на ты с IL, потестите плиз. VD>>Тестил. Нихера они не сделали. Разогнали немного. Теперь она тормоизт не в 10 раз больше, а в 5.
ВВ>А все потому что property tail call (оп код TailCall) и tail recursion — это не совсем одно и то же.
В МС объясняют это проблемами связанными с протаскиванием защиты. Вот только кому нужна защита для private-методов или (тем более) локальных фукнций?
Заявление что TailCall и хвостовая рекурсия это не одно и тоже просто бредовый флуд. TailCall единственный легальный способ выразить ховстовую рекурсию (как прямую, так и не прямую). Других нет. По сему обсуждать тут нечего. В Моно 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 будет, даже если рекурсия хвостовая, хотя и не прямая.
Или я не правильно понял?
Здравствуйте, hardcase, Вы писали:
H>В проекте насущно необходим tail-call — сообщи об этом компилятору флагом -Ot.
Я бы не сказал, что tail-call насущно необходим везде и всюду.
Если что-то можно развернуть в цикл — не нужно никаких tail-cal. Если рекурсию не получается в циклы развернуть, т.к. используется много взаимно рекурсивных методов, но рекурсии тем не менее хвостовые, то нужно делать tail call. Если взаимные рекурсии НЕ хвостовые, то обычный call.
Такое поведение считаю единственно верным.
Здравствуйте, Димчанский, Вы писали:
Д>А вот если попытаться написать макрос/метод с непрямой рекурсией, где используется несколько взаимно рекурсивных методов, то, как говорил Влад, такое развернется в обычные вызовы (IL-инструкция call, без tail), что чревато потенциальным срывом стека.
Все так. Только пока что ни одной жалобы на такой срыв не было. Так что проблема сильно преувеличена.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Димчанский, Вы писали:
Д>Скажите, насколько сложен такой финт ушами? Планируете ли?
Какая генерация имеется ввиду? Текстовая? Если текстовая — можно попробовать сделать преобразование AST в строку в виде C#. Не все можно преобразовать, но если ограничивать конструкции — вполне можно генерить. Но текст это плохое решение.
Но nemerle умеет компилировать C#, при этом будут работать макросы уровня сборки и атрибутные. Эти макросы могут генерить что угодно на этапе компиляции.
Здравствуйте, hardcase, Вы писали:
H>В общем случае это очень хреново реализуемо — ибо match. А вообще лучше плагин к ILSpy наваяать, который бы понимал немерловые лямбды и match.
А разве тот же match не разворачивается в итоге в дерево if/else в понимании C#?
Здравствуйте, Димчанский, Вы писали:
H>>В общем случае это очень хреново реализуемо — ибо match. А вообще лучше плагин к ILSpy наваяать, который бы понимал немерловые лямбды и match.
Д>А разве тот же match не разворачивается в итоге в дерево if/else в понимании C#?
Разворачивать-то придется тебе. Вполне можешь в if/else. Поскольку AST будешь строить тоже ты, особых проблем с разворачиванием я не вижу.
Здравствуйте, hardcase, Вы писали:
H>Не всегда. Он может и в switch развернуться. Но ты посмотри декомпилированные match-и Такой код человеки не пишут и уж тем более не поддерживают.
Ну я только вчера поставил Nemrle, накидал по-быстрому рекурсивную функцию фибоначи с аккумуляторами, посмотрел в ILSpy как выглядит — вполне нормальный while цикл получился.
Вот когда алгебраические типи матчить или что еще посложнее, то конечно там должно получаться что-то страшное. А с другой стороны, если бы на C# кто-то бы пытался те же самые алгебраические типы данных изобразить и работать с ними, неужели бы у него код получился бы сильно красивее?
Здравствуйте, Ziaw, Вы писали:
Z>Разворачивать-то придется тебе. Вполне можешь в if/else. Поскольку AST будешь строить тоже ты, особых проблем с разворачиванием я не вижу.
Ты выше писал: "Не все можно преобразовать, но если ограничивать конструкции — вполне можно генерить."
Я просто пытаюсь понять, что именно не получится преобразовать в код на C#?
Здравствуйте, Димчанский, Вы писали:
Д>Скажите, насколько сложен такой финт ушами? Планируете ли?
Мне кажется, это не слишком сложно, но из-за некоторых особенностей языка (матч и возможно хвостовая рекурсия) сгенерированный код будет не таким эффективным, как в Немерле.
Здравствуйте, catbert, Вы писали:
C>Мне кажется, это не слишком сложно, но из-за некоторых особенностей языка (матч и возможно хвостовая рекурсия) сгенерированный код будет не таким эффективным, как в Немерле.
По словам Влада, хвостовые рекурсии в Nemerle разворачиваются в циклы, т.е. не используется IL tail call иснтрукция, т.к. он медленнее. Поэтому с рекурсией видимо не должно быть больших проблем.
C>Влад говорил в видео
Здравствуйте, Димчанский, Вы писали:
Z>>Разворачивать-то придется тебе. Вполне можешь в if/else. Поскольку AST будешь строить тоже ты, особых проблем с разворачиванием я не вижу.
Д>Ты выше писал: "Не все можно преобразовать, но если ограничивать конструкции — вполне можно генерить." Д>Я просто пытаюсь понять, что именно не получится преобразовать в код на C#?
А чем тебе не нравится идея компайл-тайм генерации? Nemerle под нее прекрасно заточен, а вот текстовую придется пилить самостоятельно. Изобретать разные пребилд скрипты. Форматировать этот текст. При этом никакого анализа окружения. Хотя, можно распарсить, конечно.
Здравствуйте, Димчанский, Вы писали:
Д>По словам Влада, хвостовые рекурсии в Nemerle разворачиваются в циклы, т.е. не используется IL tail call иснтрукция, т.к. он медленнее. Поэтому с рекурсией видимо не должно быть больших проблем.
Кстати, ктонибудь тестил ее в .Net4? Они ее оптимизировали вроде. Кто на ты с IL, потестите плиз.
Спасиб за пример, на досуге посмотрю.
Z>А чем тебе не нравится идея компайл-тайм генерации? Nemerle под нее прекрасно заточен, а вот текстовую придется пилить самостоятельно. Изобретать разные пребилд скрипты. Форматировать этот текст. При этом никакого анализа окружения. Хотя, можно распарсить, конечно.
Видишь, я еще не совсем в теме, поэтому не очень понимаю, что значит компайл-тайм генерация. Как это выглядит? Может пример есть?
Здравствуйте, Димчанский, Вы писали:
Д>Здравствуйте, Ziaw, Вы писали:
Д>Спасиб за пример, на досуге посмотрю.
Z>>А чем тебе не нравится идея компайл-тайм генерации? Nemerle под нее прекрасно заточен, а вот текстовую придется пилить самостоятельно. Изобретать разные пребилд скрипты. Форматировать этот текст. При этом никакого анализа окружения. Хотя, можно распарсить, конечно.
Д>Видишь, я еще не совсем в теме, поэтому не очень понимаю, что значит компайл-тайм генерация. Как это выглядит? Может пример есть?
Например так
В файле проекта заменяем:
<Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
На
<Import Project="$(Nemerle)\Nemerle.MSBuild.targets" />
Пишем некий код:
[GenId]
class Test
{
public static void Main()
{
var id = new Test().Id;
Console.WriteLine("Compile time id = {0}", id);
}
}
Создаем макрос в отдельной сборке:
[Nemerle.MacroUsage(Nemerle.MacroPhase.BeforeTypedMembers, Nemerle.MacroTargets.Class)]
macro GenId(tb : TypeBuilder)
{
tb.Define(<[decl: public Id : Guid = Guid.NewGuid() ]>)
}
Здравствуйте, catbert, Вы писали:
C>Мне кажется, это не слишком сложно, но из-за некоторых особенностей языка (матч и возможно хвостовая рекурсия) сгенерированный код будет не таким эффективным, как в Немерле.
Эффективный код сгенерировать не проблема. Вот, легко читаемый сильно сложнее.
C>Влад говорил в видео
Здравствуйте, Димчанский, Вы писали:
Д>Да, имеется ввиду генереация текста на C# из AST Nemerle. Насколько это сложно (по времени)?
Зависит от качества генерируемого кода которое хочется получить.
В принципе, если не заморачиваться на качество, то по типизированному AST можно довольно просто сгенерировать C#-код. Вот только качество этого код будет крайне низким. Там будет куча goto, вместо лямбд будут объекты, вместо ПМ будут страшные if-ы и т.п.
Если такой результат устроит, то могу рассказать как это дело добавить в компилятор.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>В общем случае это очень хреново реализуемо — ибо match. А вообще лучше плагин к ILSpy наваяать, который бы понимал немерловые лямбды и match.
А зачем ILSpy-ю их понимать? Он их в C# и так переведет. ILSpy нужно немного подправить, чтобы он не падал на некотором коде и все.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Димчанский, Вы писали:
Д>Ну я только вчера поставил Nemrle, накидал по-быстрому рекурсивную функцию фибоначи с аккумуляторами, посмотрел в ILSpy как выглядит — вполне нормальный while цикл получился.
Это потому что случай простой. Ты декомпильни исходники компилятора и сам все увидишь. Особо прикольно выглядит функция Typer.DoType(). Там есть большой match по вариантам. Незабываемое зрелище .
Д>Вот когда алгебраические типи матчить или что еще посложнее, то конечно там должно получаться что-то страшное. А с другой стороны, если бы на C# кто-то бы пытался те же самые алгебраические типы данных изобразить и работать с ними, неужели бы у него код получился бы сильно красивее?
Вручную конечно же код будет красивее. Но главное, что на C# просто не стали бы так писать. Там стали бы использовать разные ООП-патетрны. Например, для обхода АСТ использовали бы паттерн "Посетитель". Вот переписать ПМ по вариантам в посетитель — это не реально.
Короче, сгенерить то C# можно. Но язык более высокого уровня по любому будет превращать язык более низкого уровня в аналог ассемблера. Так что такое кодогенераторы это очень формальное преодоление требований. К коду обычно предъявляется требование "читабельности". И этому требованию генерированный код не будет удовлетворять.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Мне кажется ты его не правильно понял. Он имеет в виду генерация C#-а по проектам немерла средствами компилятора немерла. Ну, чтобы компилятор вместо конечной сборки генерировал бы C#, а тот уже скармливать компилятору от МС или Моно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Ziaw, Вы писали:
Z>Кстати, ктонибудь тестил ее в .Net4? Они ее оптимизировали вроде. Кто на ты с IL, потестите плиз.
Тестил. Нихера они не сделали. Разогнали немного. Теперь она тормоизт не в 10 раз больше, а в 5. Но толку с того никакого, так как один хрен это в разы медленнее простого перехода и даже вызова через стек. Учитывая, что в 99% случаев хвостовая рекурсия используется в рамках одной функции, самопальная оптимизация рулит неимоверно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Это потому что случай простой. Ты декомпильни исходники компилятора и сам все увидишь. Особо прикольно выглядит функция Typer.DoType(). Там есть большой match по вариантам. Незабываемое зрелище .
Обязательно посмотрю.
VD>Короче, сгенерить то C# можно. Но язык более высокого уровня по любому будет превращать язык более низкого уровня в аналог ассемблера.
Спасибо за ответы, пример с посетителем пожалуй раскрыл мне глаза на проблему.
Похоже без какого-то суперкомпилятора здесь не обойтись.
Здравствуйте, VladD2, Вы писали:
VD>Мне кажется ты его не правильно понял. Он имеет в виду генерация C#-а по проектам немерла средствами компилятора немерла. Ну, чтобы компилятор вместо конечной сборки генерировал бы C#, а тот уже скармливать компилятору от МС или Моно.
Здравствуйте, VladD2, Вы писали:
VD>Мне кажется ты его не правильно понял. Он имеет в виду генерация C#-а по проектам немерла средствами компилятора немерла. Ну, чтобы компилятор вместо конечной сборки генерировал бы C#, а тот уже скармливать компилятору от МС или Моно.
Если так, то да. Осталось узнать смысл этого действа. С тем же успехом можно генерить код чем нибудь типа рефлектора.
Здравствуйте, Ziaw, Вы писали:
Z>Если так, то да. Осталось узнать смысл этого действа. С тем же успехом можно генерить код чем нибудь типа рефлектора.
Ну тут бабушка надвое сказала.. Когда AST конвертится в IL код — это одно, а когда его можно в текст на каком-то языке генерировать — это немного другое. По крайней мере мне интуитивно кажется, что из AST можно красивее сделать код на C#, нежели из конечного набора IL инструкций.
Здравствуйте, Димчанский, Вы писали:
Д>Ну тут бабушка надвое сказала.. Когда AST конвертится в IL код — это одно, а когда его можно в текст на каком-то языке генерировать — это немного другое. По крайней мере мне интуитивно кажется, что из AST можно красивее сделать код на C#, нежели из конечного набора IL инструкций.
Вот будут у нас сменные бэкэнды и сбацаешь бэкэнд "plain C#".
Здравствуйте, WolfHound, Вы писали:
Z>>Кстати, ктонибудь тестил ее в .Net4? Они ее оптимизировали вроде. Кто на ты с IL, потестите плиз. WH>Тестили. Тормозит.
Так оп-код TailCall это же несколько более другая штука. Она нужна не для реализации хвостовой рекурсии, которая вполне банально переписывается в цикл, а для реализации хвостового вызова. По сути все, что она делает — это снимает со стека текущую функцию, и мы в нее больше не возвращаемся. В целом — довольно полезная оптимизация.
Здравствуйте, VladD2, Вы писали:
Z>>Кстати, ктонибудь тестил ее в .Net4? Они ее оптимизировали вроде. Кто на ты с IL, потестите плиз. VD>Тестил. Нихера они не сделали. Разогнали немного. Теперь она тормоизт не в 10 раз больше, а в 5.
А все потому что property tail call (оп код TailCall) и tail recursion — это не совсем одно и то же.
Здравствуйте, WolfHound, Вы писали:
ВВ>>Так оп-код TailCall это же несколько более другая штука. Она нужна не для реализации хвостовой рекурсии, которая вполне банально переписывается в цикл, а для реализации хвостового вызова. По сути все, что она делает — это снимает со стека текущую функцию, и мы в нее больше не возвращаемся. В целом — довольно полезная оптимизация. WH>Ну и что ты тут опять левую философию на ровном месте разводишь? WH>Хвостовая рекурсия частный случай хвостового вызова. WH>И то и другое должно очень хорошо оптимизироваться рантаймом. WH>Но МС не осилил.
Я не понимаю, почему нужно противопоставлять хвостовую рекурсию и proper tail call — и к тому же сравнивать их по производительности. TailCall логично генерировать в том случае, если у нас нет банальной хвостовой рекурсии. Он всяко должен быть быстрее, чем обычный Call.
Здравствуйте, WolfHound, Вы писали:
WH>Хвостовая рекурсия частный случай хвостового вызова.
Собственно, чисто логически это так. Но с т.з. реализации не совсем. Хвостовая рекурсия вполне тривиально реализуется и без поддержки рантайма, собственно, тут и не нужно никакой поддержки. Хвостовой вызов же ты руками не сделаешь никак. Ну или по крайней мере это задачка на уровне full program optimization. Вы же зачем-то сравниваете заинлайненную вручную хвостовую рекурсию и стандартный TailCall, и мне непонятно — зачем? TailCall может рулить и в тех случаев, где вообще никакой рекурсии нет.
Здравствуйте, Димчанский, Вы писали:
Д>Ну тут бабушка надвое сказала.. Когда AST конвертится в IL код — это одно, а когда его можно в текст на каком-то языке генерировать — это немного другое. По крайней мере мне интуитивно кажется, что из AST можно красивее сделать код на C#, нежели из конечного набора IL инструкций.
Потенциально — да. Реально в декомпиляторы уже вложено много труда и они обеспечивают весьма высокое качество. Учитывая, что их использование инвестиций не требует или требует очень мало — это вполне себе вариант.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Я не понимаю, почему нужно противопоставлять хвостовую рекурсию и proper tail call — и к тому же сравнивать их по производительности. TailCall логично генерировать в том случае, если у нас нет банальной хвостовой рекурсии. Он всяко должен быть быстрее, чем обычный Call.
Все просто. Если исходить из того что нужно потрындеть в форумах, а получить бенефит от фичи, то становится очевидно, что использовать на практике TailCall не обеспечивающий достаточной скорости глупо.
ЗЫ
Ты прочитай всю ветку. Посмотри что за вопрос в ней был задан. А то твоя манера поменять смысл обсуждения несколько раздражает.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Собственно, чисто логически это так. Но с т.з. реализации не совсем. Хвостовая рекурсия вполне тривиально реализуется и без поддержки рантайма, собственно, тут и не нужно никакой поддержки.
Рекурсия бывает не прямая. Для прямой сделать оптимизацию действительно не сложно. А вот для непрямой — сложно. Тут рядом кто-то скзал, что для and-методов в F# применяют МС-ный опкод, а для прямой переписывание в цикл. В Немерле непрямая рекурсия вообще не оптимизируется, что как ты понимаешь не здорово.
ВВ>Хвостовой вызов же ты руками не сделаешь никак. Ну или по крайней мере это задачка на уровне full program optimization.
А зачем он нужен, если исключить реализацию рекурсии?
ВВ>Вы же зачем-то сравниваете заинлайненную вручную хвостовую рекурсию и стандартный TailCall, и мне непонятно — зачем? TailCall может рулить и в тех случаев, где вообще никакой рекурсии нет.
Он медленее даже обычного вызова. В МС поют о том, что дескать там мешает защита. В 4.0 они его ускорили, но все равно это тормоз.
В то же время в Моно TailCall работает очень быстро. Так что это явно недоработка ребят из МС.
ЗЫ
Предлагаю закрыть тему и не разводить флуд.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
ВВ>>Я не понимаю, почему нужно противопоставлять хвостовую рекурсию и proper tail call — и к тому же сравнивать их по производительности. TailCall логично генерировать в том случае, если у нас нет банальной хвостовой рекурсии. Он всяко должен быть быстрее, чем обычный Call. WH>В реализации мелкософт он значительно медленней, чем обычный вызов.
А как это тестировалось? По сути TailCall — это обычный Call + некие дополнительные действия. Т.е. чистое время работы больше. Но TailCall позволяет не возвращаться в родительский метод. К примеру, возможный тест — взять функцию типа foldr и прогнать ее для большого списка с включенным TailCall и без него.
На моей виртуальной машине, к примеру, TailCall тоже формально медленнее Call, но в сценариях, аналогичных вышеописанному, он дает существенный прирост.
WH>А ты опять развел флуд даже не попытавшись понять, о чем разговор.
Разговор, я так понимаю, о том, что 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), что чревато потенциальным срывом стека.
Здравствуйте, Димчанский, Вы писали:
Д>Если что-то можно развернуть в цикл — не нужно никаких tail-cal. Если рекурсию не получается в циклы развернуть, т.к. используется много взаимно рекурсивных методов, но рекурсии тем не менее хвостовые, то нужно делать tail call. Если взаимные рекурсии НЕ хвостовые, то обычный call. Д>Такое поведение считаю единственно верным.
Оптимально было бы делать анализ наличия непрямой хвостовой рекурсии и именно в этих местах вставлять tail-call. А еще лучше переписывать взаимно-рекурсивные функции в одну функцию с циклами.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Димчанский, Вы писали:
VD>> А еще лучше переписывать взаимно-рекурсивные функции в одну функцию с циклами. Д>Ну если вы такое сможете сделать, то это будет просто супер.
Это сложно, но можно. Если доказано, что существует только концевые вызовы, то код точно переписывается на циклах.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
TailCall может рулить и в тех случаев, где вообще никакой рекурсии нет.
Такой код человеки не пишут и уж тем более не поддерживают.
.
