Giraffe: Router & Route Performance

[gerardtoconnor]

@TheAngryByrd @dustinmoris @imetallica
This is a move of the topic over from Task CE issue. Just to summarise

1. Current Giraffe router uses a process of elimination on a list of path substrings/patterns, iteratively testing everyone till match met which is elegant, simple but not performant.
2. For performance, routes can be compiled into a tree structure that minimises the number of failed tested paths.
3. The best tree structures are Tries (character/edge nodes) or Binary/AVL Tree (chunk/token tested higher/lower)
4. I have initially tried trie as it only checks path char once while Bin/AVL checks same start path, multiple chars, multiple times, so if the trie node traversal can be sped up close to string checking, trie will be faster.
5. I have built first draft of Trie Router and it reads path, char by char checking for node path and firing off Http Handler functions at appropriate endpoints.
6. The initial draft (with exception of one route bug) has same perf for short routes, 20% faster on long, 50% on long parse routes, leading to blended 9% improvement on total.
7. Custom made crawl/stream parsers are an important part of performance boost over standard regex.
8. The initial draft uses ref obj nodes with dictionary edges, a crude and bulky way to initially test function, now that concept works, I will migrate nodes to structs with compressed sparse array edges in an effort to improve performance as the stack is faster than heap etc.
9. You can note from perf table below, there is only a slight degradation of performance on Trie over longer routes while old router understandably is noticeably slower.
10. I think the ultimate goal is that Giraffe router should be a lot faster than MVC such that Giraffe is the most compelling web platform when performance & composability are taken into account.

With all this said I will just re-iterate how Trie router Handler works vs standard route HttpHandler:
```f#
// (Node->Node) list -> HttpHandler
let routeTrie (routeFns:(Node->Node) list) = ...
// string HttpHandler -> (Node -> Node)
let routeT (path:string) (fn:HttpHandler) = fun (Node) -> Node
let (==>) (a: HttpHandler->Node->Node) (b:Httphandler) = a b

let trieApi : HttpHandler =
routeTrie [
routeT "/" ==> text "Hello world, from Giraffe!"
routeT "/test" ==> text "Giraffe test working"
routeT "/about" ==> text "Giraffe about page!"
routeTf "/data/%s/weather" (fun v -> sprintf "json (weatherForecasts (%s))" v |> text)
routeTf "/value/%s" text
subRouteT "/auth" ==> AuthHandler >=> routeTrie [
routeT "/inbox" ==> text "Auth Inbox"
routeTf "/parse%slong%istrings%sand%sIntegers" (fun (a,b,c,d) -> sprintf "%s | %i | %s | %s" a b c d |> text)
routeTf "token/%s" (fun v -> text "following token recieved:" + v)
subRouteT "/manager" ==> routeTrie [
routeT "/payroll" ==> text "Manager Payroll"
routeTf "/team%ssales%f" (fun (t,s) -> sprintf "team %s had sales of %f" t s |> text)
routeTf "/accesscode/%i" (fun i -> sprintf "manager access close is %i" i |> text)
subRouteT "/executive" ==> routeTrie [
routeT "/finance" ==> text "executive finance"
routeTf "/area/%s" (sprintf "executive area %s" >> text)
routeTf "/area/%s/district/%s/costcode%i" (fun (a,d,c) -> sprintf "executive area %s district %s costcode %s" a d c |> text)
]
]
]
]
```
routeTrie compiles the list of route mapping functions into its root node that then represents the pre-complied route Trie for requests/paths to traverse. The important part is to do as much work as possible in the compile stage such that compute time at runtime matching is minimised.

| URLS | GiraffeTask | GiraffeTaskTrie | Task/Trie |
|------------------------------------------------------------|-------------|-----------------|-----------|
| / | 2370840 | 2349487 | -1% |
| /about | 2391520 | 2324699 | -3% |
| /auth/dashboard | 2325389 | 2316402 | 0% |
| /auth/helpdesk | 2322608 | 2303590 | -1% |
| /auth/inbox | 2317181 | 2320119 | 0% |
| /auth/manager/accesscode/57646878 | 1792291 | 2271399 | 27% |
| /auth/manager/executive/area/globaloperationcentral | 1617520 | 2301895 | 42% |
| /auth/manager/executive/finance | 1930551 | 2311994 | 20% |
| /auth/manager/executive/mis | 1963573 | 2320318 | 18% |
| /auth/manager/executive/operations | 1954403 | 2337297 | 20% |
| /auth/manager/payroll | 2211415 | 2306816 | 4% |
| /auth/manager/teambravosales5345545.34544 | 1365431 | 2224991 | 63% |
| /auth/manager/teamview | 2188016 | 2342409 | 7% |
| /auth/manager/timesheets | 2199281 | 2316064 | 5% |
| /auth/parsefirstlong987654321stringssecondandthirdIntegers | 1503244 | 2264492 | 51% |
| /authtoken/as8d7f098adsf897asdf7a09dfasd7f9as7df987 | 2088203 | 2287279 | 10% |
| /data/sunnydrycold/weather | 2304337 | 2287102 | -1% |
| /delivery | 2322192 | 2343339 | 1% |
| /ourstory | 2342938 | 2370148 | 1% |
| /products | 2339945 | 2353792 | 1% |
| /test | 2377866 | 2374676 | 0% |
| /value/thisisavaluethatisbeingpassed | 2295704 | 2306295 | 0% |
| /wheretofindus | 2332918 | 2368049 | 2% |
| Grand Total | 48857366 | 53302652 | 9% |

Perf numbers represent total req per second over seperate 3 runs ( /3 for expected perf)

[dustinmoris]

Awesome work and I like those suggestions. Let me know how I can help you with progressing on this issue !

[TheAngryByrd]

I think routing can be optimize without involving IO, we should probably look into http://benchmarkdotnet.org/ or expecto's wrapper for it use https://github.com/haf/expecto#benchmarkdotnet-usage

[gerardtoconnor]

@TheAngryByrd I was only realising the same thing about an hour ago, you're absolutely right, a pattern matching algo can be run & tested outside the server with a dummy HttpHandler class, does not need to be tested inside server every time. I have 2/3 variants of algo/tree I want to test so makes way more sense to do it this way if I am micro-tweaking the performance. Thanks as always !! I'll try use the expecto wrapper (but I've never used before).

@dustinmoris Thanks, will do, it's just a case of testing a few variants of my algo/tree structure now to see which performs best. The problem with using structs for the nodes is that you usually have to recursively construct entire nodes on initialisation which calls for more complex construction algo ... or duplicating work by creating in Obj/Dictionary form first and then mapping. Will keep you posted.

If anyone has any ideas on most performant structures/algo please do share and we can implement & test.

[imetallica]

@gerardtoconnor great news!

[gerardtoconnor]

@TheAngryByrd Sorry meant to say, your last most recent run of trie router on Debian was actually significantly faster than osx, really pronounced on longer routes and ones with parsing (one route is +200% faster then vanilla Giraffe!?!)

This output nicely shows that we can get +26% performance boost on TaskCont ( 17% Task CE, 9% Continuation), and another +39% with basic trie router (+76% from vanilla giraffe). I have built another radix/token tree implementation that should be little faster again (will test when all 3 done) and am now developing a cpu-caching focused one that lays entire map onto a 1-dimensional struct array, minimizing hops and utilises prebuilt index key maps to eliminate lookups.

| Giraffe | TaskCont | TaskContTrie | Gir/Cont | Gir/Trie | Cont/Trie | Urls |
|---------|----------|--------------|----------|----------|-----------|------------------------------------------------------------|
| 88102 | 107562 | 110822 | +22% | +26% | +3% | / |
| 88501 | 107966 | 105799 | +22% | +20% | -2% | /about |
| 63268 | 81826 | 106559 | +29% | +68% | +30% | /auth/dashboard |
| 64892 | 73544 | 103903 | +13% | +60% | +41% | /auth/helpdesk |
| 63812 | 80834 | 108368 | +27% | +70% | +34% | /auth/inbox |
| 34609 | 46247 | 96658 | +34% | +179% | +109% | /auth/manager/accesscode/57646878 |
| 32088 | 40954 | 98299 | +28% | +206% | +140% | /auth/manager/executive/area/globaloperationcentral |
| 35423 | 51014 | 105696 | +44% | +198% | +107% | /auth/manager/executive/finance |
| 37659 | 50092 | 103655 | +33% | +175% | +107% | /auth/manager/executive/mis |
| 36439 | 48145 | 102607 | +32% | +182% | +113% | /auth/manager/executive/operations |
| 48084 | 64472 | 104357 | +34% | +117% | +62% | /auth/manager/payroll |
| 28899 | 33543 | 62715 | +16% | +117% | +87% | /auth/manager/teambravosales5345545.34544 |
| 46385 | 61851 | 101565 | +33% | +119% | +64% | /auth/manager/teamview |
| 46846 | 62551 | 104378 | +34% | +123% | +67% | /auth/manager/timesheets |
| 31418 | 37319 | 66035 | +19% | +110% | +77% | /auth/parsefirstlong987654321stringssecondandthirdIntegers |
| 42309 | 54735 | 101076 | +29% | +139% | +85% | /authtoken/as8d7f098adsf897asdf7a09dfasd7f9as7df987 |
| 60940 | 75203 | 98367 | +23% | +61% | +31% | /data/sunnydrycold/weather |
| 80472 | 107941 | 109810 | +34% | +36% | +2% | /delivery |
| 84192 | 102317 | 111883 | +22% | +33% | +9% | /ourstory |
| 84951 | 100414 | 103441 | +18% | +22% | +3% | /products |
| 87425 | 109061 | 115006 | +25% | +32% | +5% | /test |
| 56922 | 72761 | 101775 | +28% | +79% | +40% | /value/thisisavaluethatisbeingpassed |
| 86496 | 107979 | 112136 | +25% | +30% | +4% | /wheretofindus |
| 1330132 | 1678331 | 2334910 | +26% | +76% | +39% | Grand Total |

[dustinmoris]

I am going to close this issue as this one has been superseded by #53 and #69

[gerardtoconnor]

I think this is a separate issue/feature request but fine closing as I can integrate into continuation/task PR.

I finished my attempt at faster router but despite being 10x more complex was only 3% faster ... which is disappointing and pushes me to go for radix tree hybrid version that is almost as fast but far simplier to maintain.

[gerardtoconnor]

Can we re-open this until the new router PR is submitted? This is separate to both continuations & task CE as it implements a (radix-style) tree router with hand rolled parsers for max performance.

I would like to reopen as there are a few design questions I would like to ask & performance metrics to share etc?

[gerardtoconnor]

I have been bit delayed deploying this given I have been trying to re-design the parameter application structure to avoid boxing.

Given the high-frequency of parsing of URLs in web apps with a large slowdown in req/sec proportional to the amount of parsing, there is unneeded overhead in boxing parse values onto the heap, grouped together by a ref Tuple, more GC pressure.

By using partial application instead, (fun a b c ->), we should be able to push parsed value types right onto the stack without boxing, so the calling parse handler can just pop off values, not even touching the heap (string obj still on heap but without boxing & additional ref lookup).

So far method overloading having an issue matching initial curried function signature taken from (fmt:StringFormat<'T,HttpHandler> , fn: 'T ) so trying to figure out how to hack around this.

for routef "foo/%i/bar/%s" (fun i s -> ...), type 'T is int -> string -> HttpHandler matching our parse handler funtion fun i s next ctx -> ...

if I cannot figure a way around boxing after this weekend, will probably just release now with boxing, and put boxing issue on todo list.

[nojaf]

@gerardtoconnor did you ever find any time to work on this? Is there a way we can help you out?

[gerardtoconnor]

I have built 3 "working" routers

1. Trie (char tree nodes)
2. Token/Radix (substring token tree nodes)
3. Flat rolled tree (cpu caching optimized)

The Trie one is slow relative to other two, unfortunately the flat one was only 5% faster then token one to my surprise. I can tweak it to squeeze a little more but it's a lot less then I had hoped given the exponentially more complicated logic & execution.

I have spent/wasted last few weeks trying to fix boxing problem such that SRTP would be able to build partial application parser that pushed parsed values into function stack, avoiding boxing but it's just a bridge too far for now (I will come back to this).

For maintainability & simplicity I figured I'd release the token router first so I have created a branch token-router in my fork and all original routing now in BasicRouter module with token one in TokenRouter.
I then went and copied all HttpHandlerTests into a TokenRouterTests such that HttpHandlerTests uses BasicRouter namespace, and new tests test token router on same tests.

7 tests have failed to my surprise and despite my basic tests all working... so that's where I am now, just need to figure out bug in 7 tests and good to merge. most appear to relate to nested subroutes (how dev lays/dupes routes). I have labelled failing tests with comment //<<FAIL in repo.

I may need to change how trees mapped as with token implementation there is a tree built for each router(choose) whereas with the flat router I managed to suck entire app into one optimised tree.

Either way should be released this week.

NB: I am not including any case-insensitive matching in performance router as its a perf big slowdown and rarely causes a routing issue, users should turn caps lock off. BasicRouter will always be there for those who need it and performance isn't an issue.

[gerardtoconnor]

Actually, the token router is 580 lines vs Array routers 700 lines so not sure either fit into the "maintainability & simplicity" bucket. :flushed:

Feel free start reviewing process now as not too much will change with bug fixing... or just take my word for it and avoid burning your eyes on my spaghetti code :smirk: .

In case anyone is lost as to what the code is doing, its building & then navigating a hybrid radix tree where nodes can have functions attached that dictate how to process/continue the match/parse process.

Some weird optimisations are included which may look bizarre but help JIT.

[gerardtoconnor]

There is one test I cannot get to pass

Failed Giraffe.TokenRouterTests.GET "/foo/blah blah/bar" returns "blah blah"
Error Message:
Expected: blah%20blah
Actual: blah blah

I will submit PR and maybe @dustinmoris can perhaps throw a fresh set of eyes on it?

Basically, it expects the written response of parsed path to be url encoded, but given we are using NSubstitute and not the server, not seeing where the encoding is done in the prior version!?

[gerardtoconnor]

New token router live and merged #114 on develop branch so now closing issue

[dustinmoris]

Live now: https://github.com/dustinmoris/Giraffe/releases/tag/v0.1.0-beta-110