c# - Poor performance in tree pruning -

i made i'm calling treepruner. purpose: given hierarchy starting @ list of root level nodes, return new hierarchy new root nodes highest level nodes meet condition. here class.

public class breadthfirstpruner<tresource> {     private ienumerable<tresource> originallist;     private ienumerable<tresource> prunedlist;     private func<tresource, icollection<tresource>> getchildren;      public breadthfirstpruner(ienumerable<tresource> list, func<tresource, icollection<tresource>> getchildren)     {         this.originallist = list;         this.getchildren = getchildren;     }      public ienumerable<tresource> getprunedtree(func<tresource,bool> condition)     {         this.prunedlist = new list<tresource>();         this.prune(this.originallist, condition);         return this.prunedlist;     }      private void prune(ienumerable<tresource> list, func<tresource,bool> condition)     {         if (list.count() == 0)         {             return;         }          var included = list.where(condition);         this.prunedlist = this.prunedlist.union(included);         var excluded = list.except(included);         this.prune(excluded.selectmany(this.getchildren), condition);     } } 

the class it's supposed to, slowly, , can't figure out why. i've used on small hierarchies complete hierarchy in memory (so there should no linq-to-sql surprises). regardless of how eager or lazy try make things, first line of code evaluate results of linq expression winds taking 3-4 seconds execute.

here code that's consuming pruner:

func<businessunitlabel, icollection<businessunitlabel>> getchildren = l => l.children; var hierarchy = scope.tolist(); var pruner = new breadthfirstpruner<businessunitlabel>(hierarchy, getchildren); func<businessunitlabel, bool> hasbusinessunitsforuser = l =>     l.businessunits.selectmany(bu => bu.users.select(u => u.idguid)).contains(userid); var labels = pruner.getprunedtree(hasbusinessunitsforuser).tolist(); 

as stated previously, dataset i'm working when executes quite small. it's few levels deep 1 node on levels. it's written, slowness occur on first recursive call prune when call list.count(), because that's when second level of hierarchy (excluded.selectmany(this.getchildren)) being evaluated.

if, however, add .tolist call so:

var included = list.where(condition).tolist() 

then slowness occur @ point.

what need make thing go fast?

update

after prompted me reevaluate condition more carefully, realized associations in hasbusinessunitsforuser not being eager loaded. there problem.

these calls lazily executed , results not cached/materialized:

    var included = list.where(condition);     this.prunedlist = this.prunedlist.union(included);     var excluded = list.except(included); 

even in snippet included runs twice. since recursive algorithm there might many more invocations.

add tolist call sequence might executed more once.