Вопросы Теги

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

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

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

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 , NonEmptyStack .

Обновление №1: См. Код ниже.

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

  • Размещение 1000 элементов в EmptyStack в первый раз занимает более 7 секунд.
  • Размещение 1000 элементов в EmptyStack после этого практически не занимает времени .
  • Чем больше элементов я помещаю в стек, тем хуже становится производительность.

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

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

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

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

  • ] EmptyStack
  • NonEmptyStack >
  • NonEmptyStack >>
  • NonEmptyStack >>>
  • и т. д.

Вопросы:

  1. Верна ли моя оценка выше?
  2. Если да, то почему создание экземпляров универсальных типов, таких как T , T > , T >> и т.д. становятся экспоненциально тем медленнее, чем глубже они вложены?
  3. Известно ли, что реализации CLR, отличные от .NET (Mono, Silverlight, .NET Compact и т. Д.), Обладают такими же характеристиками?

† ) Сноска не по теме: эти типы весьма интересны, кстати . потому что они позволяют компилятору обнаруживать определенные ошибки, такие как: 

 stack.Push (item) .Pop (). Pop ();
 // ^^^^^^
 // вызывает ошибку времени компиляции, если известно, что «стек» непустой.

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

 TStackBeneath PopTwoItems 
  (Стек INonEmptyStack )

Обновление №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 x64 ( 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);
}

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

Вот график XY выходных данных:

Line chart showing a measurement for recursive generic type instantiation times

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

    • N = 1 указывает на NonEmptyStack >
    • N = 2 указывает на NonEmptyStack >>
    • и т. д.

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

36
задан stakx supports GoFundMonica 24 February 2012 в 08:35
поделиться