Разбор строк в F# — сгенерированный IL

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

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

Вот как выглядят функции парсинга:

let eatTag (input : string) index =
    let len = input.Length
    let nothing = 0, null, TagType.Open

    // more functions used in the same way
    // ...

    let rec findName i =
        if i >= len then nothing
        else
            let chr = input.[i]
            if isWhitespace chr then
                findName (i+1)
            elif chr = '/' then
                getName (i+1) (i+1) true
            else getName (i+1) i false

    let rec findStart i =
        if i >= len then nothing
        elif input.[i] = '<' then findName (i+1)
        else findStart (i+1)

    findStart index

Вот как выглядит сгенерированный IL-код для функции findStart:

 // loop start
    IL_0000: nop
    IL_0001: ldarg.2
    IL_0002: ldarg.1
    IL_0003: blt.s IL_000e

    IL_0005: ldc.i4.0
    IL_0006: ldnull
    IL_0007: ldc.i4.0
    IL_0008: newobj instance void class [mscorlib]System.Tuple`3<int32, string, valuetype TagType>::.ctor(!0, !1, !2)
    IL_000d: ret

    IL_000e: ldarg.0
    IL_000f: ldarg.2
    IL_0010: call instance char [mscorlib]System.String::get_Chars(int32)
    IL_0015: ldc.i4.s 60
    IL_0017: bne.un.s IL_0024

    IL_0019: ldarg.0
    IL_001a: ldarg.1
    IL_001b: ldarg.2
    IL_001c: ldc.i4.1
    IL_001d: add
    IL_001e: call class [mscorlib]System.Tuple`3<int32, string, valuetype TagType> findName@70(string, int32, int32)
    IL_0023: ret

    IL_0024: ldarg.0
    IL_0025: ldarg.1
    IL_0026: ldarg.2
    IL_0027: ldc.i4.1
    IL_0028: add
    IL_0029: starg.s i
    IL_002b: starg.s len
    IL_002d: starg.s input
    IL_002f: br.s IL_0000
// end loop

Представление C# (ILSpy) для этой функции показывает следующий код, и именно поэтому я думаю, что делаю что-то не так. Очевидно, что аргументы функции каким-то образом присваиваются самой себе...?!

internal static Tuple<int, string, TagType> findStart@80(string input, int len, int i)
{
        while (i < len)
        {
                if (input[i] == '<')
                {
                        return findName@70(input, len, i + 1);
                }
                string arg_2D_0 = input;
                int arg_2B_0 = len;
                i++;
                len = arg_2B_0;
                input = arg_2D_0;
        }
        return new Tuple<int, string, TagType>(0, null, TagType.Open);
}

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


.net parsing f# il
person kongo2002    schedule 23.05.2012    source источник
comment
Почему вы думаете, что с этим кодом что-то не так? Просто из-за фрагмента кода, который в основном ничего не делает и, скорее всего, будет оптимизирован JIT-компилятором?   -  person svick    schedule 23.05.2012
comment
@svick: «практически ничего» здесь действительно не важно :)   -  person leppie    schedule 23.05.2012
comment
@svick: Да, может быть, в этом причина :-) Я просто пытался проверить различные варианты решения этой довольно простой задачи и наткнулся на эти инструкции, которых я не ожидал. Это может быть подсказкой мне, как новичку в F#, что я делаю что-то не совсем правильно :)   -  person kongo2002    schedule 23.05.2012

Ответы (3)


arrow_upward
7
arrow_downward

Это устранение хвостового вызова.

Процесс удаления хвостового вызова и превращения хвостового вызова в «переход» к началу функции. (iow конструкция while(true) { }).

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

person leppie    schedule 23.05.2012
comment
Понятно - может быть, я просто ожидал, что компилятор F# удалит эти присваивания, поскольку значения вообще не меняются. - person kongo2002; 23.05.2012
comment
@kongo2002: Анализ, чтобы определить это, слишком дорог. И JIT должен с этим справиться достаточно хорошо :) - person leppie; 23.05.2012

arrow_upward
5
arrow_downward

Как уже было сказано, в этом случае компилятор превращает рекурсивную функцию в нерекурсивную. Это возможно только тогда, когда рекурсивный вызов появляется в позиции "хвост-вызов" и если функция вызывает сама себя. В общем, у компилятора есть следующие опции:

  • Скомпилировать функцию как цикл — когда функция вызывает сама себя, а вызов находится в позиции хвостового вызова. Это наиболее эффективная альтернатива, поскольку она исключает создание нового кадра стека и использует стандартные циклы.

  • Скомпилировать функцию с помощью инструкции .tail call IL — когда вызов находится в позиции завершающего вызова, но вы вызываете другую функцию (например, если у вас есть две взаимно рекурсивные функции, объявленные с использованием синтаксиса let rec foo () = ... and bar () = ...). Это позволяет избежать создания нового фрейма стека (вы не получите переполнения стека), но это менее эффективно, поскольку инструкция .tail call в .NET не была так сильно оптимизирована.

  • Компиляция с использованием обычной рекурсии. Когда функция рекурсивно вызывает сама себя и затем выполняет дополнительные вычисления, код компилируется с использованием стандартного рекурсивного вызова вместо вызова хвоста< /em> (и для каждого вызова необходимо выделять новый фрейм стека, поэтому вы можете получить переполнение стека)

Оптимизация, которая делается в первом случае (в вашем примере), выглядит так: В общем случае функция хвостовой рекурсии выглядит примерно так:

let rec foo x = 
  if condition then 
    let x' = calculateNewArgument x // Run some computation
    foo x'                          // (Tail-)recursively calls itself
  else 
    calculateResult x               // Final calculation in the branch that returns

Код транслируется в следующий цикл, в котором аргумент сохраняется в изменяемой переменной:

let foo x = 
  let mutable x = x
  while condition do                // Check condition using current argument value
    x <- calculateNewArgument x     // Instead of recursion, run next iteration
  calculateResult x                 // Final calculation in the branch that returns
person Tomas Petricek    schedule 23.05.2012
comment
Спасибо за подробное объяснение. Кроме того, мне любопытно, почему компилятор F# присваивает аргументы функции при каждой итерации цикла, хотя они являются типами значений, которые не изменят свое значение. - person kongo2002; 23.05.2012
comment
@ kongo2002 Устранение этого дополнительного присваивания имело бы смысл — это можно было бы сделать, если бы компилятор F# имел более сложный анализ для проверки того, какие переменные присваиваются, но он просто не реализован (в общем, может потребоваться переназначить все аргументы ). Я думаю, что есть шанс, что JIT-компилятор устранит такие назначения. - person Tomas Petricek; 23.05.2012
comment
Это возможно только... Строго говоря, возможно всегда. amazon.com/Compiling-Continuations-Andrew-W-Appel/ дп/052103311X - person J D; 28.06.2012

arrow_upward
2
arrow_downward

По сути, вместо создания цепочки вроде

findstart(findstart(findstart(findstart.....

компилятор преобразуется в цикл, который устраняет вызовы функций.

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

person John Palmer    schedule 23.05.2012
comment
Это называется устранением хвостового вызова. Хвостовой вызов был удален, а рекурсивный вызов теперь представляет собой просто переход к началу функции. Не существует формальной такой вещи, как оптимизация хвостового вызова, если только вы конкретно не говорите о пространственной сложности. - person leppie; 23.05.2012
comment
Кроме того, ваш chain пример очень не хвостовой рекурсии. Хвостовой вызов может появляться только рядом с return. Так что return foo( return foo ( ... невозможно. - person leppie; 23.05.2012
comment
а если let ref f a = if a=0 then a else a-1 - как цепочка f(f(f(f(4)))) - person John Palmer; 23.05.2012
comment
Но это даже не рекурсивная функция ;p И объединение в цепочку не делает ее рекурсивной, не говоря уже о хвостовой рекурсии :) - person leppie; 23.05.2012