Using Dictionary results in StackOverflowError

[Papa.Coen]

After repeatedly calling/using a Dictionary I get a
StackOverflowError. What am I doing wrong?
The situation is as follows:

I have ruler class, this class contains some member variables,
encapsulated properties. SOme of those are calculated when get is
called. These kind of properties are actually Cell classes which have
a Calculation class attached. All Cell properties are stored in a
Dictionary <nameEnum, Cell>

When a Cell property is called, the correct Cell is extracted from the
dictionary and asked for its value. This value is calculated once,
every future call returns the previous calculated value.

Cell Property encapsulation:
public decimal PropertyOne
{
get { return this._myCells[Calc.MyName].Calculate(this,
this.helper); }
}

If I use the following code, I do _NOT_ get a stackoverflow error. I
can guess/understand what's going on here, but I'd really like to use
the dictionary:

Cell myCell = new Cell(new Calculator());

public decimal PropertyOne
{
get {return this.myCell.Calculate(this,this.helper);
}

It seems as if each cell is recreated upon retrieval from the
dictionary.......

Who can help me out?

 

[Jon Skeet [C# MVP]]

After repeatedly calling/using a Dictionary I get a
StackOverflowError. What am I doing wrong?
The situation is as follows:

<snip>

Well, you haven't shown the Calculate method, which could well be
relevant.

Could you post a short but complete program that demonstrates the
problem?
See http://pobox.com/~skeet/csharp/complete.html for what I mean by
that.

Jon

 

[Papa.Coen]

The following code does the trick. You might have to increase the
amount of rulers created.

using System;
using System.Collections.Generic;
using System.Text;
using System.Runtime.CompilerServices;

namespace Problem_Dict
{
internal enum Calc
{
PropertyOne
}

public class Program
{
static void Main(string[] args)
{
Program p = new Program();
}

public Program()
{
Ruler firstRuler = this.BuildRulers();

decimal myVal = firstRuler.PropertyOne;
}

private Ruler BuildRulers()
{
Ruler tmpRuler = null;
Ruler previous = null;

Ruler first = null;

for (int i = 1; i <= 5000; i++)
{
tmpRuler = new Ruler();
tmpRuler.Previous = previous;

if (previous == null)
{
first = tmpRuler;
}

if (previous != null)
{
previous.Next = tmpRuler;
}

previous = tmpRuler;
}

return first;
}
}

public class CalcDemo // : ICalculator
{

public decimal Calculate(Ruler ruler)
{
decimal myVal = 0.0M;

if (ruler.Next != null)
{
myVal += ruler.Next.PropertyOne;
}
else
{
myVal = 1;
}

return myVal;
}
}

public class Cell
{
private CalcDemo _iCalc = null;
private decimal _value = 0.0M;
private bool _isCalculated = false;

public Cell(CalcDemo iCalc)
{
this._iCalc = iCalc;
}

[MethodImpl(MethodImplOptions.Synchronized)]
public decimal Calculate(Ruler ruler)
{
if(!_isCalculated){
this._value = this._iCalc.Calculate(ruler);
this._isCalculated = true;
}

return _value;
}
}


public class Ruler
{
private Ruler _next = null;
private Ruler _previous = null;
private Dictionary<Calc, Cell> _cells = null;


public Ruler()
{
this.Build();
}

private void Build()
{
this._cells = new Dictionary<Calc, Cell>();
this._cells.Add(Calc.PropertyOne, new Cell(new CalcDemo()));
}

public Ruler Next
{
get { return this._next; }
set { this._next = value; }
}

public Ruler Previous
{
get { return this._previous; }
set { this._previous = value; }
}

public decimal PropertyOne
{
get { return this._cells[Calc.PropertyOne].Calculate(this); }
}
}
}

 

[Jon Skeet [C# MVP]]

The following code does the trick. You might have to increase the
amount of rulers created.

Okay, so the problem is that you've effectively got a linked list, and
when you ask the first element in the list to calculate its value,
that needs to ask the next element, which needs to ask the next, etc.

You may well run out of stack space earlier when using the dictionary
than without using it, but the problem is basically there either way -
you're recursing to a very deep level. Ideally, you want to avoid that
recursion (assuming this kind of depth is normal). The exact nature of
how you do that will depend on the real program (I'm assuming this is
just a cut down version) but you'll effectively need to simulate the
recursion with iteration instead.

Jon

 

[Papa.Coen]

Okay, so the problem is that you've effectively got a linked list, and
when you ask the first element in the list to calculate its value,
that needs to ask the next element, which needs to ask the next, etc.

You may well run out of stack space earlier when using the dictionary
than without using it, but the problem is basically there either way -
you're recursing to a very deep level. Ideally, you want to avoid that
recursion (assuming this kind of depth is normal). The exact nature of
how you do that will depend on the real program (I'm assuming this is
just a cut down version) but you'll effectively need to simulate the
recursion with iteration instead.

Jon

I do not recurse that deep, I get the error after approx. 344
subsequent calls. My calculation class has a bit (no, it's not a huge
class) more logic than the demo one and I have more calculations than
one. As far as I can see, replacing recursion with iteration poses a
bit of a problem: not every calculation refers to a Next, some refer
to a Previous or to no other cell. there's not a red line that can be
followed on which to base the iteration.

I specifically use the chain of command (like) pattern to simplify a
complex calculation. The mixed 'setup' of the Ruler class the result
of me thinking the calculations could be performed in a linear matter.

 

[Papa.Coen]

Additional info:

The calculations are performed more than once to find the value that
will result to a value of 0 (nil) of a certain property from a certain
ruler instance (the Control ruler). Which ruler is the control ruler
is derived from input parameters. It can be compared by searching a
tree starting somewhere in the middle.

 

[Jon Skeet [C# MVP]]

I do not recurse that deep, I get the error after approx. 344
subsequent calls.

Well, a stack of 344 calls (*3, at a guess - one for PropertyOne, one
for CalcDemo.Calculate and one for Cell.Calculate) is still pretty
huge.

My calculation class has a bit (no, it's not a huge
class) more logic than the demo one and I have more calculations than
one.

It only needs to be a bit bigger to significantly decrease the size
available. Just changing CalcDemo.Calculate to have one more decimal
in took the permissable iterations down on my box from about 5570 to
4750. Add a few more things in (which may not be terribly apparent
from your code, even - e.g. a call to a method with lots of
parameters) and you could easily have a large stack frame.

As far as I can see, replacing recursion with iteration poses a
bit of a problem: not every calculation refers to a Next, some refer
to a Previous or to no other cell. there's not a red line that can be
followed on which to base the iteration.

It's often a problem to replace something which is clean in design but
a pain in reality with one which works in reality. You may need to
just simulate recursion in this case by keeping track of results
you're still depending on, and what depends on them, growing a list
appropriately.

Jon

 

[Papa.Coen]

Well, I solved the problem by performing the 'forward' calculations
from end to start. A check is added if the (next) value is already
calculated or not. The rest of the calculations is left untouched but
can be adjusted accordingly if need be.

I really hate this solution because my previous one was good design,
regardless of any con-recursion arguments. Not being able to perform
all (cell based) calculations in a single uniform way prevents me from
implementing a truly (or at least more) generic solution.

As for my comparission to a tree, the app is more like Excel. How
would/does excel perform it's calculations if it's not capable of
recursing through each cell to calculate the value of a cell depending
on more than one other (and interdependant) cell(s)?

 

[Jon Skeet [C# MVP]]

Well, I solved the problem by performing the 'forward' calculations
from end to start. A check is added if the (next) value is already
calculated or not. The rest of the calculations is left untouched but
can be adjusted accordingly if need be.
Right.

I really hate this solution because my previous one was good design,
regardless of any con-recursion arguments. Not being able to perform
all (cell based) calculations in a single uniform way prevents me from
implementing a truly (or at least more) generic solution.

As for my comparission to a tree, the app is more like Excel. How
would/does excel perform it's calculations if it's not capable of
recursing through each cell to calculate the value of a cell depending
on more than one other (and interdependant) cell(s)?

I very much doubt that Excel will genuinely recurse arbitrarily - I
expect it simulates it using iteration, just as you've effectively had
to do.

It's the only way which doesn't have this potential problem. Recursing
an arbitrary number of times is always going to go "bang" at some
point, unless tail recursion is implemented/used appropriately (and
the .NET JIT doesn't do tail recursion AFAIK).

Jon