Which form of threading should I use to improve efficiency with recursion?

Question

I have two recursive methods that follow one after the other, each generating data for each node to a tree of any size. (I cannot combine the two because the second is dependent on the first's results - also, the first iteration is from leaf to root and the second, root to leaf.) I need to generate the data for every node addition/position update. I need to draw the tree to a cached bitmap every tree status update.

I currently am using a BackgroundWorker for this, but when the user adds a numerous amount of nodes, things start to lag as if the task was working on the same thread as the UI. (This is the first time I've used a BackgroundWorker but not for handling threads in general)

I came across Matt's post once: BackgroundWorker vs background Thread Should I revert back to a System.Thread instead or may their be another option? I need to store the resulting tree and an integer value on the main thread when the process is finished.

[Threading]
private void Commence()
{
    if (worker.IsBusy)
    {
        try
        {
            // I was thinking of fixing this with a timer instead
            worker.CancelAsync();
            while (worker.IsBusy) Thread.Sleep(10);
        }
        catch { return; }
    }
    worker.RunWorkerAsync();
}
void worker_DoWork(object sender, DoWorkEventArgs e)
{
    // int radMax; TreeNodeEx rTNH;
    // Call the two recursive methods
    radMax = GenerateDataFromNodes(rTNH, radMax);
    UpdateRenderRegion(); // draw result to cached bitmap
}
void worker_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
{
    // draw bitmap to screen
    if (!e.Cancelled) Invalidate();
}

[Algorithm]
private int GenerateDataFromNodes(TreeNodeEx hierarchy, int max)
{
    // set hierarchy values
    max = GenerateScaleAndRadius(hierarchy, max);
    GenerateStartAndSweep(hierarchy);

    return max;
}
private int GenerateScaleAndRadius(TreeNodeEx hierarchy, int max, int radius = 2)
{
    for (int i = 0; i < hierarchy.Nodes.Count; i++)
    {
        max = GenerateScaleAndRadius((TreeNodeEx)hierarchy.Nodes[i], max, radius+1);
    }
    // generation a
    return max;
}
private void GenerateStartAndSweep(TreeNodeEx hierarchy)
{
    for (int i = 0; i < hierarchy.Nodes.Count; i++)
    {
        // generation b-1
    }
}
private void node_SweepAngleChagned(object sender, EventArgs e)
{
    for (int i = 0; i < ((TreeNode)sender).Nodes.Count; i++)
    {
        // generation b-2
    }
}

[Invalidation]
private void UpdateRenderRegion()
{
    if (rTNH != null)
    {
        renderArea = new Bitmap(radMax * rScale * 2, radMax * rScale * 2);
        Graphics gfx = Graphics.FromImage(renderArea);

        gfx.SmoothingMode = SmoothingMode.AntiAlias;
        // pens, graphicspaths, and pathgradients

        // draw parent first

        // draw generations next using the same structure as the parent
        DrawNodes(gfx, p, rTNH, rScale, w, h);

        gfx.Dispose();
    }
}

"I need to store the resulting tree and an integer value on the main thread when the process is finished." - this part doesn't make sense. Memory is shared across threads. — RQDQ, Nov 16 '12 at 18:17
You've shown the implementation of methods that don't do anything interesting and omitted the implementation of the important methods you've discussed...If they're too big to post consider condensing your problem to a smaller example that can still demonstrate the problem. Oh, and any recursive method can always be implemented as an iterative method that just uses a `Stack`, if that's somehow causing a problem. — Servy, Nov 16 '12 at 18:18
You should post you Paint event handler code and UpdateRenderRegion();, I'm not sure if GenerateDataFromNodes can affect the UI since it is executed in background. — Nikola Davidovic, Nov 16 '12 at 18:27
The code you posted is irrelevant for your problem, how often are you calling Commence method, because you are actually not canceling your BackgroundWorker, it is waiting for it to finish? — Nikola Davidovic, Nov 16 '12 at 18:29
I call commence every time the user adds, removes, moves, or promotes a node in the tree. — TekuConcept, Nov 16 '12 at 18:35
while (worker.IsBusy) Thread.Sleep(10); It looks like this is executing on the UI thread. Why are you doing this? — RQDQ, Nov 16 '12 at 18:38
Ya, I know, I only just realized that when I posted additional code samples... NikolaD fixed this. — TekuConcept, Nov 16 '12 at 18:50

Nikola Davidovic · Accepted Answer · 2012-11-16T18:44:00.837

I suppose that this is the problem for your code. If you have a large tree, as you suggest, and your recursion is long process, then when you call Commence() method again, it will wait and do Thread.Sleep(10); producing UI unresponsevness. Rewrite your code like this, if the BackgroundWorker is canceled, it should call Commence() method in RunWorkerCompleted event handler instead of waiting the worker to finish. Check the code:

private void Commence()
{
      if (worker.IsBusy)
      {
           worker.CancelAsync();
      }
      else
      {
           worker.RunWorkerAsync();
      }
}

void worker_DoWork(object sender, DoWorkEventArgs e)
{
      BackgroundWorker bgw = (BackgroundWorker)sender;
      if (bgw.CancellationPending)
      {
            e.Cancel = true;
            return;
      }
      else
      {
            radMax = GenerateDataFromNodes(rTNH, radMax);
            if (bgw.CancellationPending)
            {
                  e.Cancel = true;
                  return;
            }
            UpdateRenderRegion(); // draw result to cached bitmap
      }
}
void worker_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
{
      if (!e.Cancelled)
           Invalidate();
      else
           Commence();
}

And as a side note, be careful that you don't access the backBuffer (bitmap you are using) at the same time when Invalidate occurs (for whatever reason). I don't know if you already handle access to this bitmap from different threads, but have that in mind.

Which form of threading should I use to improve efficiency with recursion?

1 Answers1