Forest Tree Module

[ballsteve]

The new 'Forest' module is ready to be merged into the dev branch.

This is a replacement for the graph-based tree implementation. Forest uses an arena allocator (generational_arena).

Benchmarks show a 27 times speedup! This is based on a 10K sized source document. The performance difference increases with input document size (in other words, the graph implementation is displaying exponentially poor performance).

Introducing the Forest module makes the evaluator and xslt modules monomorphised. In other words, they will be using concrete types instead of dynamic trait objects. This is what is driving the speedup: resolving types at compile-time rather than run-time.

[mdubinko]

Brief follow-up from the sample code discussion. Y'all are probably much more aware of these kinds of things than rust-newbie-me, but in the context of making a baseline Forest module that allows pluggable extensions like XPath or XSLT or XQuery, I found this discussion and code sample inspiring for thinking about what such an API would look like.
"Type-Driven API Design in Rust" by Will Crichton

[ballsteve]

We're all rust-newbies here ;-)

That video has some really cool ideas. Definitely going to incorporate that into the API design.

[ballsteve]

The next release, 0.10.0, will have a 'trees' module. All tree implementations will be housed in that module.