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

Примечание: Возможно, я выбрал неправильное слово в названии; возможно, я действительно говорю о полиномиальном росте здесь. См. Результат теста в конце этого вопроса.

Давайте начнем с этих трех рекурсивных общих интерфейсов ^{& dagger;} которые представляют неизменяемые стеки:

interface IStack<T>
{
    INonEmptyStack<T, IStack<T>> Push(T x);
}

interface IEmptyStack<T> : IStack<T>
{
    new INonEmptyStack<T, IEmptyStack<T>> Push(T x);
}

interface INonEmptyStack<T, out TStackBeneath> : IStack<T>
    where TStackBeneath : IStack<T>
{
    T Top { get; }
    TStackBeneath Pop();
    new INonEmptyStack<T, INonEmptyStack<T, TStackBeneath>> Push(T x);
}

Я создал простые реализации EmptyStack<T>, NonEmptyStack<T,TStackBeneath>.

Обновление # 1: См. код ниже.

Я заметил следующие вещи об их производительности во время выполнения:

• Перенос 1000 элементов на EmptyStack<int> в первый раз занимает более 7 секунд.
• Нажатие 1000 элементов на EmptyStack<int> не требует никакого времени.
• Производительность становится экспоненциально хуже, чем больше элементов, которые я нажимаю на стек.

Обновление # 2:

• Я, наконец, выполнил более точные измерения. См. Тестовый код и результаты ниже.

• Я обнаружил только во время этих тестов, что .NET 3.5, похоже, не позволяет создавать общие типы с глубиной рекурсии & ge; 100.NET 4, похоже, не имеет этого ограничения.

Первые два факта заставляют меня подозревать, что медленная производительность не связана с моей реализацией, а скорее с системой типов:.NET должен создать 1000 различных закрытых родовых типов, т.е.:

• EmptyStack<int>
• NonEmptyStack<int, EmptyStack<int>>
• NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>
• NonEmptyStack<int, NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>>
• и др.

Вопросы:

• Правильно ли подтверждена моя оценка?
• Если да, то почему создание типичных типов, таких как T<U>, T<T<U>>, T<T<T<U>>> и т.д., экспоненциально медленнее, чем глубже они вложены?
• Существуют ли реализации CLR, отличные от .NET(Mono, Silverlight,.NET Compact и т.д.), которые имеют те же характеристики?

^{& dagger;)} Относящаяся к теме сноска: эти типы довольно интересны кстати. потому что они позволяют компилятору поймать определенные ошибки, такие как:

stack.Push(item).Pop().Pop();
//                    ^^^^^^
// causes compile-time error if 'stack' is not known to be non-empty.

Или вы можете выразить требования к определенным операциям стека:

TStackBeneath PopTwoItems<T, TStackBeneath>
              (INonEmptyStack<T, INonEmptyStack<T, TStackBeneath> stack)

Обновление # 1: реализация указанных выше интерфейсов

internal class EmptyStack<T> : IEmptyStack<T>
{
    public INonEmptyStack<T, IEmptyStack<T>> Push(T x)
    {
        return new NonEmptyStack<T, IEmptyStack<T>>(x, this);
    }

    INonEmptyStack<T, IStack<T>> IStack<T>.Push(T x)
    {
        return Push(x);
    }
}
// ^ this could be made into a singleton per type T

internal class NonEmptyStack<T, TStackBeneath> : INonEmptyStack<T, TStackBeneath>
    where TStackBeneath : IStack<T>
{
    private readonly T top;
    private readonly TStackBeneath stackBeneathTop;

    public NonEmptyStack(T top, TStackBeneath stackBeneathTop)
    {
        this.top = top;
        this.stackBeneathTop = stackBeneathTop;
    }

    public T Top { get { return top; } }

    public TStackBeneath Pop()
    {
        return stackBeneathTop;
    }

    public INonEmptyStack<T, INonEmptyStack<T, TStackBeneath>> Push(T x)
    {
        return new NonEmptyStack<T, INonEmptyStack<T, TStackBeneath>>(x, this);
    }

    INonEmptyStack<T, IStack<T>> IStack<T>.Push(T x)
    {
        return Push(x);
    }
}

Обновление №2: код и результаты тестов

Я использовал следующий код для измерения рекурсивного времени экземпляра типичного типа для .NET 4 на ноутбуке Windows 7 SP 1 x 64 (Intel U4100 @1,3 ГГц, 4 ГБ). Это другая, более быстрая машина, чем та, которую я изначально использовал, поэтому результаты не совпадают с приведенными выше утверждениями.

Console.WriteLine("N, t [ms]");
int outerN = 0;
while (true)
{
    outerN++;
    var appDomain = AppDomain.CreateDomain(outerN.ToString());
    appDomain.SetData("n", outerN);
    appDomain.DoCallBack(delegate {
        int n = (int)AppDomain.CurrentDomain.GetData("n");
        var stopwatch = new Stopwatch();
        stopwatch.Start();
        IStack<int> s = new EmptyStack<int>();
        for (int i = 0; i < n; ++i)
        {
            s = s.Push(i);  // <-- this "creates" a new type
        }
        stopwatch.Stop();
        long ms = stopwatch.ElapsedMilliseconds;
        Console.WriteLine("{0}, {1}", n, ms);
    });
    AppDomain.Unload(appDomain);
}

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

Здесь график X-Y выхода:

• Горизонтальная ось: N обозначает глубину рекурсии типа, то есть:

  • N = 1 указывает a NonEmptyStack<EmptyStack<T>>
  • N = 2 указывает a NonEmptyStack<NonEmptyStack<EmptyStack<T>>>
  • и др.

• Вертикальная ось: t - время (в миллисекундах), необходимое для перемещения N целых чисел в стек. (Время, необходимое для создания типов времени выполнения, если это действительно происходит, включено в это измерение.)

Ответы

public interface IImmutableStack<T>
{
    T Top { get; }
    IImmutableStack<T> Pop { get; }
    IImmutableStack<T> Push(T x);
}

public class ImmutableStack<T> : IImmutableStack<T>
{
    private ImmutableStack(T top, IImmutableStack<T> pop)
    {
        this.Top = top;
        this.Pop = pop;
    }

    public T Top { get; private set; }
    public IImmutableStack<T> Pop { get; private set; }

    public static IImmutableStack<T> Push(T x)
    {
        return new ImmutableStack<T>(x, null);
    }

    IImmutableStack<T> IImmutableStack<T>.Push(T x)
    {
        return new ImmutableStack<T>(x, this);
    }
}