perwendel/spark — pull request #149 by augustl (2014-05-28 20:48:25+00:00)
Title: ~30x routing speedup

Hello there :) I'll start with the juicy details.

```
BEFORE:
RoutePerformanceTest.doBenchmark: [measured 10 out of 15 rounds, threads: 1 (sequential)]
round: 2.77 [+- 0.24], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], \
GC.calls: 223, GC.time: 0.22, time.total: 40.99, time.warmup: 13.32, time.bench: 27.67
```

```
AFTER:
RoutePerformanceTest.doBenchmark: [measured 10 out of 15 rounds, threads: 1 (sequential)]
round: 0.10 [+- 0.03], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], \
GC.calls: 6, GC.time: 0.01, time.total: 1.90, time.warmup: 0.86, time.bench: 1.04
```

In other words, what used to take **27.67** seonds, now takes **1.04** seconds.

In short, the speed is obtained by using a trie-like data structure that has logarithmic performance, instead of a linear array check where at worst every route has to be checked against the incoming URL.

The built-in router has been replaced with https://github.com/augustl/path-travel-agent. **Note:** path-travel-agent is not published to maven central yet, as it's pretty new and absolutely not battle proven.

RouteEntry has been removed. Hopefully this wasn't considered a public API. I haven't investigated the possibility of keeping it around, but I have a hunch it's a lot of work, since it was pretty internal to the way the old router worked. SimpleRouteMatcher retains it's API despite the complete reworking of its internals.

I'm expecting this pull request to need some work before it's accepted, so I decided to include the benchmark code in it, even though it's probably not relevant for inclusion in spark code base.