[web-devel] WAI routing?
michael at snoyman.com
Sun Mar 18 13:42:52 CET 2012
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.
> 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.
> Gregory Collins <greg at gregorycollins.net>
> web-devel mailing list
> web-devel at haskell.org
The code at play for Yesod is in the Yesod.Routes.Dispatch module.
The source 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, 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
 It might be worth switching to a HashMap here, if someone can put
together a good benchmark I'd love to see the results.
More information about the web-devel