В контексте CLR в .NET как распределяется пространство стека - PullRequest
Новая
       23

В контексте CLR в .NET как распределяется пространство стека

2 голосов
/ 12 мая 2011

В контексте CLR в .NET как распределяется пространство стека и чем оно обычно ограничено?

Например:

Может ли какой-либо конкретный поток продолжать добавлять в стек, пока не закончится память?Если не;как CLR решает, сколько места выделить, и может ли он передумать?

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

1 Ответ

4 голосов
/ 12 мая 2011

CLR немедленно фиксирует полное пространство стека для каждого потока, как только он создан. Размер стека по умолчанию составляет 1 МБ. Если вы увеличиваете свой стек до этого размера, это переполнение стека и возникает ошибка.

CLR принимает политику, отличную от нативного кода, которая просто резервирует 1 МБ, но фиксирует ее по требованию.

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

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

static int fib(int n)
{
    int result = 0;
    int a = 1;
    for (int i=1; i<=n; i++)
    {
        int temp = result;
        result = a;
        a = temp + a;
    }
    return result;
}

Конечно, в действительности вы переполняли бы свою переменную результата задолго до того, как достигли переполнения стека. Но производительность рекурсивного алгоритма несостоятельна для значений n в области 30-40.

Еще один разумный подход - заполнить статический массив предварительно рассчитанными значениями. Опять же, поскольку значения растут так быстро, вам не нужен очень большой массив, чтобы он содержал все значения, которые вписываются в int или даже long.

...