Could SortedSet.InOrderTreeWalk use recursion instead of allocating?

[jamesqo]

SortedSet.InOrderTreeWalk currently uses a stack on which the nodes to walk are pushed/popped: https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/SortedSet.cs#L234

It looks like it would be possible to implement this recursively instead, i.e. InOrderTreeWalk(left); action(current); InOrderTreeWalk(right) and eliminate the Stack allocation.

[stephentoub]

Given that there's little risk of stack overflow due to the balancing of the tree, seems reasonable to explore and measure. At the same time it may also be useful to separate the reverse checks out so that there's only one check/branch for reverse to go down a different path that does right;current;left instead of left;current;right. One could also look at having the function take not only a delegate but also a T that would be passed into the delegate, allowing the call site to avoid the closure/delegate allocation that most of them have.

[ianhays]

I'd be interested to see how much space you save by removing the stack allocation in favor of recursion. My gut says it would be slower than the approach we're using because of the added overhead in method calls, but I agree it's worth investigation.

[jamesqo]

because of the added overhead in method calls,

@ianhays Neither Stack.Pop or Stack.Push inline currently.

[ianhays]

@jamesqo are you still interested in looking into this and getting some perf results to see if it's a good enhancement?

[jamesqo]

@ianhays, I haven't forgotten about this issue. I am thinking it would be good to cleanup the SortedSet code a bit more first (I have a PR for part 2 of the cleanup open at dotnet/corefx#16061) before making optimizations. I also think that maybe we could just remove InOrderTreeWalk entirely and do the recursion ourselves at every call site, avoiding the delegate invocations-- it shouldn't be too hard, especially after we get C# 7 local functions in corefx.

[eiriktsarpalis]

This was investigated by @johnthcall in #56561. While there are substantial perf improvements in a recursion-based approach, we decided not make that change out of abundance of caution.