evolve75/RubyTree — pull request #37 by aidansteele (2014-12-18 01:39:56+00:00)
Title: Performance optimisations

Hi,

Firstly, thanks for the great library. It's been very handy for a project of mine. I was recently profiling my code and noticed a couple of hot spots in RubyTree that I fixed locally and you might want merged upstream.

The first is fairly simple and is part of the attached pull request. `TreeNode#is_root?` is fast when it is root, but slower when it has a parent node. A basic benchmark (with master and then my changes):

```ruby
require 'tree'
require 'benchmark'

n = Tree::TreeNode.new 'root'
n2 = Tree:TreeNode.new 'child'
n << n2

# master
Benchmark.measure { 10000000.times { n2.is_root? } }
# => #

# with change
Benchmark.measure { 10000000.times { n2.is_root? } }
# => #
```

The second change is with regards to `TreeNode#node_depth`. This is also a hot spot, probably because I am hitting the pathological case (but I imagine this happens fairly often), e.g.

```ruby
root_node.each do |node|
depth = node.node_depth
# do something else...
end
```

`TreeNode#each` is traversing the tree downwards, but each call to `TreeNode#node_depth` is then walking back up the entire tree to calculate its depth. The result is the depth method being called on the same objects repeatedly. What I have done locally is effectively this:

```ruby
def node_depth
@node_depth ||= is_root? ? 0 : (1 + parent.node_depth)
end
```

This requires the `@node_depth` ivar to be reset to nil when the parent changes. Should I attach this change to the pull request?

Finally, there is this line: https://github.com/evolve75/RubyTree/blob/master/lib/tree.rb#L363 It crops up in my profiling as the hottest line once the other two are resolved. (Embarrassingly) I don't actually understand what this line is meant to achieve. What is the point of it? It seems that the "if" and "unless" would cancel each other out?