хвост. префикс в ILAsm - любой пример использования?

Question

В ECMA-335, III.2.4 указан префикс tail., который может использоваться в рекурсивных функциях. Однако я не смог найти его использование ни в C#, ни в коде F #. Есть ли какой-нибудь пример использования?

Answer 1

Вы не найдете его ни в каком коде, создаваемом компилятором MS C#. Вы найдете его в коде, создаваемом компилятором F #, но не так сильно, как вы могли ожидать, по почти противоположным причинам.

Теперь, чтобы первый правильный одна ошибка в вашем заявлении:

ECMA-335, III.2.4 определяет хвост. префикс, который может использоваться в рекурсивных функциях.

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

Хвост вызова - это любой вызов функции (включая метод ООП), где последняя операция в этом кодовом пути заключается в том, чтобы выполнить этот вызов, а затем вернуть возвращаемое им значение или просто вернуться, если функция, t возвращает значение. Поэтому в:

int DoSomeCalls(int x) 
{ 
    if(A(x)) 
    return B(x); 
    if(DoSomeCalls(x * 2) > 3) 
    { 
    int ret = C(x); 
    return ret; 
    } 
    return D(DoSomeCalls(x-1)); 
} 

Здесь звонки на B и D являются хвостовые вызовы, потому что единственное, что было сделано после вызова, чтобы вернуть значение они возвратили. Вызов C не является хвостовым вызовом, но его можно легко преобразовать в один, удалив избыточное присвоение ret, просто вернувшись напрямую. Вызов A не является хвостовым вызовом, и ни один из них не является вызовом DoSomeCalls, хотя они являются рекурсивными.

Теперь механизм вызова обычных функций зависит от реализации, но обычно включает в себя сохранение полезных значений, которые могут потребоваться после вызова в стек, помещения параметров в стек и/или в регистры вместе с текущей инструкцией (для возврата), перемещение указателя инструкции, а затем считывание возвращаемого значения из регистра или стека, когда указатель инструкции будет возвращен обратно после завершения вызова. С помощью вызова хвоста можно пропустить много этого, потому что вызываемая функция может использовать текущий стек стека, а затем возвращаться прямо к более раннему вызывающему.

Префикс tail. требует, чтобы это было сделано с помощью вызова.

Хотя это не обязательно связано с рекурсией, вы были в курсе рекурсии, потому что преимущества устранения хвостовых вызовов в рекурсивных случаях больше, чем в противном случае; делая вызовы, которые являются O (n) в пространстве стека, когда фактическое использование механизма вызова функции становится O (1) в пространстве стека, а также уменьшает затраты времени на постоянное время для каждого элемента (так что все равно O (n) в этом но O (n) означает, что он принимает n × k секунд, и мы имеем меньший k). Во многих случаях это может быть разницей между вызовом, который работает, и вызовом, который выдает StackOverflowException.

Теперь, в ECMA-335, есть несколько случаев, о которых не может быть признано, как tail.. В частности, есть текст в разделе III.2.4, который гласит:

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

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

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

Из-за этого, на самом деле существует четыре способа сделать хвост-вызов устранение в ИЛ:

1. Используйте префикс tail. перед вызовом и получите его (не гарантируется).
2. Не используйте префикс tail. перед вызовом, но при этом дрожание решит применить его любым способом (даже менее гарантированным).
3. Используйте инструкцию jmp IL, которая является фактически специальным случаем устранения хвостового вызова (никогда не используется C#, потому что она производит непроверяемый код для нормально относительно небольшого коэффициента усиления, хотя это может быть самый простой подход, иногда когда ручное кодирование связано с его относительная простота).
4. Повторно написать весь метод для использования другого подхода; в частности, рекурсивный код, который наиболее выгоден для устранения хвостового вызова, может быть переписан для явного использования своего итеративного алгоритма, устранение хвостового вызова эффективно превращает рекурсию в. * (Иными словами, устранение хвостового вызова происходит до джим или даже компиляция).

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

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

Между тем на стороне C# вещей было принято решение не испускать tail. Существует общий подход с C#, который не сильно оптимизирует созданный код. Выполняются некоторые оптимизации (в частности, удаление мертвого кода), но по большей части, поскольку усилия по оптимизации могут просто дублировать сделанные дрожанием (или даже мешать им), недостатки оптимизации (больше осложнений означает более возможные ошибки , и IL будет более запутанным для многих разработчиков), относительно перевешивают верх. Использование tail. является классическим примером этого, потому что иногда настаивать на хвостовых вызовах фактически стоит больше, чем экономит с .NET, поэтому, если джиттер уже пытается разобраться, когда это хорошая идея, тогда есть больше шансов, что компилятор C# будет просто усугублять ситуацию во много раз, и не имеет значения, остальное.

Стоит также отметить, что со стилями кодирования наиболее общего с языком C-стиле, как C#:

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

Теперь, наступил F #.

С видом функционального и декларативного программирования F # поощряет, существует множество случаев, когда наиболее естественным образом делается то, что естественно делается на итеративном пути в C#, наиболее естественно делается с помощью рекурсивного подхода. Там, где люди, взламывающие языки C-стиля, учатся превращать рекурсивные случаи в итеративный код, люди, взломающие языки с языком F #, учатся превращать итеративные случаи в рекурсивный код и нерекурсивный код с обратным вызовом в рекурсивный код хвоста.

поэтому F # используется tail. много.

И он получил StackOverflowException много, потому что дрожь не почитала его.

Это одна из вещей, из-за которой люди дрожания увеличивали количество случаев, когда они устраняли хвостовые звонки, как в целом, так и даже в случае, если используется tail..

Между тем, люди F # не могли просто зависеть от tail., поэтому компилятор F # будет оптимизировать гораздо больше, чем C#; так же, как мы можем вручную переписать рекурсивные вызовы как итеративные, как в сноске, поэтому компилятор F # делает эквивалент при создании IL.

И по этой причине, много раз, когда вы пишете метод F #, где вы ожидаете увидеть какой-нибудь ИЛ, который использует tail., то, что вы на самом деле получили, - это ИЛ, который делает итеративную эквивалентную вещь.

Однако F # будет по-прежнему использовать tail., когда метод вызывает другой метод во взаимно-рекурсивном способе, как:

let rec even n = 
    if n = 0 then 
    true 
    else 
    odd (n-1) 
and odd n = 
    if n = 1 then 
    true 
    else 
    even (n-1) 

Что я полностью украл из this answer, потому что я играл только крошечная с F # так Я лучше полагаюсь на кого-то более знакомого, чем я.

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

---

* Пример превращения рекурсивного вызова в итеративном был бы начать с рекурсивным вызовом, как:

void ClearAllNodes(Node node) 
{ 
    if(node != null) 
    { 
    node.Value = null; 
    ClearAllNodes(node.Next) 
    } 
} 

Самым простым изменением является вручную добавить, что делает устранение хвоста вызова , сами настройки параметров, и прыгать обратно к началу метода:

void ClearAllNodes(Node node) 
{ 
start: 
    if(node != null) 
    { 
    node.Value = null; 
    node = node.Next; 
    goto start; 
    } 
} 

Поскольку есть веские причины, чтобы избежать goto если мы можем, мы бы Gener союзника изменить его на что-то, что делает то же самое с помощью более строго определенных LOOPING механизмов:

void ClearAllNodes(Node node) 
{ 
    while(node != null) 
    { 
    node.Value = null; 
    node = node.Next; 
    } 
}