Edit Question - KnowledgeHub

Title Body

Note: I may have chosen the wrong word in the title; perhaps I'm really talking about polynomial growth here. See the benchmark result at the end of this question. Let's start with these three recursive generic interfaces † that represent immutable stacks: 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); } I've created straightforward implementations EmptyStack<T> , NonEmptyStack<T,TStackBeneath> . Update #1: See the code below. I've noticed the following things about their runtime performance: Pushing 1,000 items onto an EmptyStack<int> for the first time takes more than 7 seconds. Pushing 1,000 items onto an EmptyStack<int> takes virtually no time at all afterwards. Performance gets exponentially worse the more items I push onto the stack. Update #2: I've finally performed a more precise measurement. See the benchmark code and results below. I've only discovered during these tests that .NET 3.5 doesn't seem to allow generic types with a recursion depth ≥ 100. .NET 4 doesn't seem to have this restriction. The first two facts make me suspect that the slow performance is not

Tags (comma-separated) Cancel