[web-devel] WAI routing?

[Michael Snoyman]

On Sun, Mar 18, 2012 at 2:21 PM, Gregory Collins
<greg at gregorycollins.net> wrote:
> On Sat, Mar 17, 2012 at 3:32 PM, Greg Weber <greg at gregweber.info> wrote:
>>
>> you might be interested in looking at the routing code in scotty,
>> which has some extra features.
>>
>> https://github.com/xich/scotty
>
>
> Routing there is also O(n) in the number of handlers, if I'm reading the
> code right. If you can't match a URL to a Handler in less than O(log n) in
> the number of handlers, you're doing it wrong. Programs that are growing in
> size usually do so because they are actually being used, so as your need for
> the framework to scale grows, you have to waste time re-engineering
> efficient routing into your existing program, and usually in a panic or
> crisis situation. Both Snap and Yesod do this right.
>
> G
> --
> Gregory Collins <greg at gregorycollins.net>
>
> _______________________________________________
> web-devel mailing list
> web-devel at haskell.org
> http://www.haskell.org/mailman/listinfo/web-devel
>

The code at play for Yesod is in the Yesod.Routes.Dispatch[1] module.
The source[2] is highly commented Literate Haskell, which goes into
details of our algorithm, which takes advantage of vectors for an
initial O(1) whittling down of possible routes, followed by a series
of Map lookups[3], and finally a linear traversal of the remaining
routes to address parsing of dynamic pieces. If you avoid overlapping
routes (highly recommended), then the last stage will always have
either 0 or 1 matches.

I purposely put this code into a separate module without any TH or
Yesod dependencies so that it could be used by others for route
dispatch. I don't believe there's anything really Yesod-specific about
it, so it might be a good fit for scotty.

I've never dug through the routing code for Snap; what's the dispatch
algorithm used?

Michael

[1] http://hackage.haskell.org/packages/archive/yesod-routes/0.0.1/doc/html/Yesod-Routes-Dispatch.html
[2] http://hackage.haskell.org/packages/archive/yesod-routes/0.0.1/doc/html/src/Yesod-Routes-Dispatch.html
[3] It might be worth switching to a HashMap here, if someone can put
together a good benchmark I'd love to see the results.