Re[3]: Функции без оптимизации хвостовой рекурсии в библиоте - Nemerle

Заметил то что в библиотеке Немерле, используются некоторые функции без оптимизации хвостовой рекурсии, например:

FoldRight на списке из 50000 элементов убивает стэк, это дело можно переписать с помощью continuations, но это будет чуть медленее, думаю что скажет сообщество, может сделать отдельные варианты функций но с TCO, или переписать оригинальные.

Сравнительные показатели, FoldRight c continuations:

  public FoldRight[T, TOut] (this l : list [T], acc : TOut, f : T * TOut -> TOut) : TOut 
  {
    def loop(l, cont)
    {
      match (l)
      {
        | x :: xs => loop(xs, racc => cont(f(x, racc)))
        | []      => cont(acc)
      }
    }
    
    loop(l, x => x)
  }

в сравнении с FoldRight из библиотеки, не убивает стэк, TCO, но показатели следующие на 10000 элементов операция

def res = lst.FoldRight(0, (x, a) => x * 3 + a);

старая новая

61074 79434
61569 74705
61938 75744
62024 75350

С остальными наверное похожие показатели, что посоветует сообщество?

Здравствуйте, CodingUnit, Вы писали:

CU>Заметил то что в библиотеке Немерле, используются некоторые функции без оптимизации хвостовой рекурсии, например:

CU>FoldRight на списке из 50000 элементов убивает стэк, это дело можно переписать с помощью continuations, но это будет чуть медленее, думаю что скажет сообщество, может сделать отдельные варианты функций но с TCO, или переписать оригинальные.

Такие списки никому не нужны

Камрад Klapaucius вроде пробовал привести в чувство стандартну либо, да бросил.

Здравствуйте, CodingUnit, Вы писали:

CU>С остальными наверное похожие показатели, что посоветует сообщество?

На деле такие функции нужно разворачивать по месту использования (реализовывать т.н. macro-методы).

Здравствуйте, hardcase, Вы писали:

H>На деле такие функции нужно разворачивать по месту использования (реализовывать т.н. macro-методы).

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

Вопрос еще и в другом, даже тот метод с continuation не работает, и дает переполнение стэка, хотя в фшарпе работает с оптимизацией, можно ли такую вещь устранить -Ot компилятора или надо писать поддержку оптимизации хвостовой рекурсии в лямбдах?

Здравствуйте, hardcase, Вы писали:

H>Такие списки никому не нужны

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

H>Камрад Klapaucius вроде пробовал привести в чувство стандартну либо, да бросил.

Я бы часть функций дописал или переписал в хвостово-рекурсивной манере, но continuationы не работают как надо. Думаю как произвести такие оптимизации чтобы CPS был возможен без использования tail операнда

Здравствуйте, CodingUnit, Вы писали:

CU>Я бы часть функций дописал или переписал в хвостово-рекурсивной манере, но continuationы не работают как надо. Думаю как произвести такие оптимизации чтобы CPS был возможен без использования tail операнда

В нынешней реализации лямбд CPS тебе на каждой итераци будет создавать ДВА объекта: замыкание и собственно лямбду. В принципе возможно сделать в компиляторе оптимизацию (и я пробовал это провернуть), когда немутабельное замыкание преобразуется в структуру (value-тип). Но даже тогда создание объекта на каждую итерацию — как-то не здорово.

Здравствуйте, CodingUnit, Вы писали:

CU>Заметил то что в библиотеке Немерле, используются некоторые функции без оптимизации хвостовой рекурсии, например:

Нафиг CPS, если уж переписывать foldr, то нужно список сериализовывать в массив и по нему с хвоста итерироваться.

Здравствуйте, CodingUnit, Вы писали:

CU>Я бы часть функций дописал или переписал в хвостово-рекурсивной манере, но continuationы не работают как надо. Думаю как произвести такие оптимизации чтобы CPS был возможен без использования tail операнда

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

Как известно лямбда состоит из след. частей:


private sealed class _N__N_lambda__4061__4193<T, TRes> : Function<TRes, TRes>
{
    // Fields
    private MutualDefinition2._N_closure_4073<T, TRes> _N_FoldRight_closure_4199;
    private MutualDefinition2._N_closure_4090<T, TRes> _N_loop_closure_4197;

    // Methods
    public _N__N_lambda__4061__4193(MutualDefinition2._N_closure_4090<T, TRes> _N_loop_closure_4197, MutualDefinition2._N_closure_4073<T, TRes> _N_FoldRight_closure_4199);
    public sealed override TRes apply(TRes racc);
}

и замыкание:

private sealed class _N_closure_4090<T, TRes>
{
    // Fields
    internal Function<TRes, TRes> _N_cont_4097; // <--- вот эту функцию компилятор вызывает рекурсивно
    internal T _N_head_4095;

    // Methods
    internal _N_closure_4090()
    {
    }
}

цикл выглядит так:

public sealed override TRes apply(TRes racc)
{
    return this._N_loop_closure_4197._N_cont_4097.apply(this._N_FoldRight_closure_4199._N_fold_4078.apply(this._N_loop_closure_4197._N_head_4095, racc));
}

это то что в алгоритме FoldRight представленном выше выглядит так: cont(fold(head, racc))

Здесь он вызывает функцию вглубь и естественно расходуется стэк, но cont в этом случае имеет два значения, сначала это x => x при первом вызове, далее это всегда экземпляр _N__N_lambda__4061__4193
Можно вот что сделать, в замыкание для такого рода функции добавить поле rec_lambda : _N__N_lambda__4061__4193
и устанавливать его, если функция ссылалась на этот экземпляр лямбды, иначе null


private sealed override apply_rec(racc : TRes) : TRes
{
    this._N_FoldRight_closure_4199._N_fold_4078.apply(this._N_loop_closure_4197._N_head_4095, racc); // убираем рекурсию
}

private sealed override TRes apply_rec(cont : _N__N_lambda__4061__4193, racc : TRes) : TRes
{
    def res =  cont.apply(racc); // вызываем функцию получая результат отложенной лямбды без рекурсивного вызова континуации
    if (cont._N_loop_closure_4197.rec_lambda != null) // если следующая функция это таже лямбда
       apply_rec(cont._N_loop_closure_4197.rec_lambda, res)  // запускаем этотже метод рекурсивно с лямбдой и результатом, компилятор должен это развернуть в цикл
    else
       cont._N_loop_closure_4197._N_cont_4097.apply(res) // иначе просто вызываем обычно      
}

public sealed override TRes apply(racc : TRes)
{
    apply_rec(this, racc) 
}

Эту оптимизацию надо проводить только для лямбд которые вызывают себя же, тогда рекурсивный вызов может не переполнить стэк и это даст реализовать поддержку использования CPS в языке без пресловутого tail опкода. Какие мысли?

Здравствуйте, hardcase, Вы писали:

H>Здравствуйте, CodingUnit, Вы писали:

H>В нынешней реализации лямбд CPS тебе на каждой итераци будет создавать ДВА объекта: замыкание и собственно лямбду. В принципе возможно сделать в компиляторе оптимизацию (и я пробовал это провернуть), когда немутабельное замыкание преобразуется в структуру (value-тип). Но даже тогда создание объекта на каждую итерацию — как-то не здорово.

Ну без промежуточного объекта в CPS не обойтись, потому что лямбда должна накапливаться, только как это сделать, в принципе вся эта CPS штука может без рекурсии обрабатываться как результат и ссылка на следующую функцию, далее освобождается стэк, и вызывается следующая функция и результат и так далее. Где эта функция должна храниться, вопрос, можно в замыкании, или в самой лямбде, но объект создавать по любому нужно. В таких алгоритмах это промежуточная структура, обычно если в таких функциях используется аккумулятор в виде списка, там тоже создается новый список. Можно на это закрыть глаза, производительность не должна сильно влиять по сравнению с эффективностью использования CPS.

Здравствуйте, hardcase, Вы писали:

H>Такие списки никому не нужны

Нужны алгоритмы, которые будут работать в нормальном стеке, а не взрываться в мегабайтном стеке, как ncc.

Здравствуйте, CodingUnit, Вы писали:

CU>Заметил то что в библиотеке Немерле, используются некоторые функции без оптимизации хвостовой рекурсии, например:

CU>FoldRight на списке из 50000 элементов убивает стэк, это дело можно переписать с помощью continuations, но это будет чуть медленее, думаю что скажет сообщество, может сделать отдельные варианты функций но с TCO, или переписать оригинальные.

CU>Сравнительные показатели, FoldRight c continuations:
CU>

CU>  public FoldRight[T, TOut] (this l : list [T], acc : TOut, f : T * TOut -> TOut) : TOut 
CU>  {
CU>    def loop(l, cont)
CU>    {
CU>      match (l)
CU>      {
CU>        | x :: xs => loop(xs, racc => cont(f(x, racc)))
CU>        | []      => cont(acc)
CU>      }
CU>    }
    
CU>    loop(l, x => x)
CU>  }
CU>

Просьба потестировать:

public FoldRight[T, TOut] (this l : list [T], acc : TOut, f : T * TOut -> TOut) : TOut 
{
  def buffer = SCG.Stack();
  foreach(x in l) buffer.Push(x);
  mutable result = acc;
  foreach(x in buffer) result = f(x, result);
  result
}

Здравствуйте, hardcase, Вы писали:

H>Просьба потестировать:
H>

H>public FoldRight[T, TOut] (this l : list [T], acc : TOut, f : T * TOut -> TOut) : TOut 
H>{
H>  def buffer = SCG.Stack();
H>  foreach(x in l) buffer.Push(x);
H>  mutable result = acc;
H>  foreach(x in buffer) result = f(x, result);
H>  result
H>}
H>

Решение легко переписывается на использование массива вместо стека (не думаю что будет шустрее):

public FoldRight[T, TOut] (this l : list [T], acc : TOut, f : T * TOut -> TOut) : TOut 
{
  mutable buffer = array(16);
  mutable pos = 0;
  foreach(x in l)
  {
    buffer[pos] = x;
    ++pos;
    when(pos == buffer.Length)
      Array.Resize(ref buffer, buffer.Length * 2)
  }
  mutable result = acc;
  for(mutable i = pos - 1; i >= 0; --i)
    result = f(buffer[i], result);
  result
}

Здравствуйте, hardcase, Вы писали:

H>Просьба потестировать:
H>

H>public FoldRight[T, TOut] (this l : list [T], acc : TOut, f : T * TOut -> TOut) : TOut 
H>{
H>  def buffer = SCG.Stack();
H>  foreach(x in l) buffer.Push(x);
H>  mutable result = acc;
H>  foreach(x in buffer) result = f(x, result);
H>  result
H>}
H>

результаты хорошие:
stack cps lib
30827 95746 61530
30294 95213 59784
30791 94877 59147

и результат со стэком единственный кто не вышибает стэк, и он быстрее, поэтому думаю можно этот алгоритм использовать в библиотеке.

Здесь согласен, императивный вариант дает преимущества, как быть если я хочу организовать Fold по двоичному дереву, например вот как можно обходить в рекурсивной манере (на f# это tail recursive):


variant Tree[T]
{
    | Node { data : T; left : Tree[T]; right : Tree[T];}
    | Leaf 
}

def FoldTree(nodeF : T * TRes * TRes -> TRes, leafV : TRes, t : Tree[T])
{
    def loop(t, cont)
    {
        match (t)
        {
         | Node(x, left, right) => loop(left,  lacc => 
                                     loop(right, racc =>
                                        cont (nodeF(x, lacc, racc))))
         | Leaf -> cont(leafV)
        }

    }

    loop(t, x => x)
}

При этом создается новое дерево, обработанное через функцию, есть подобные функции для работы с деревьями выражений, как все это можно реализовать в tail recursive манере, без CPS?

	От:	CodingUnit
	Дата:	17.11.11 15:39
	Оценка:	1 (1) +1

От:	hardcase	http://nemerle.org
Дата:	17.11.11 15:53
Оценка:

От:	hardcase	http://nemerle.org
Дата:	17.11.11 15:55
Оценка:

	От:	CodingUnit
	Дата:	17.11.11 19:57
	Оценка:

	От:	CodingUnit
	Дата:	17.11.11 20:00
	Оценка:

	От:	catbert
	Дата:	18.11.11 10:40
	Оценка:	1 (1) +1