Re: [web-devel] WAI routing?

On Sun, Mar 18, 2012 at 2:21 PM, Gregory Collins wrote:

On Sat, Mar 17, 2012 at 3:32 PM, Greg Weber 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

_______________________________________________ web-devel mailing list web-devel@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/Yeso... [2] http://hackage.haskell.org/packages/archive/yesod-routes/0.0.1/doc/html/src/... [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.