[web-devel] WAI routing?

[Stephen Paul Weber]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Somebody claiming to be Michael Snoyman wrote:
>On Sun, Mar 18, 2012 at 2:21 PM, Gregory Collins
>>> 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
>
>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.

Hmm, this also looks interesting.  Though it's more of a backend algorithm 
for a router than a router itself (which is fine).  It might be interesting 
to patch support into Scotty (definitely possible).

I wonder what the overhead is (ie: approximately how many routes one needs 
before the fancy algorithm is faster).

- -- 
Stephen Paul Weber, @singpolyma
See <http://singpolyma.net> for how I prefer to be contacted
edition right joseph
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQIcBAEBCAAGBQJPZhd6AAoJENEcKRHOUZzefwQQAJyxhr9cz0HD8vjZTqPURFBL
mTZPITi/3MLlxTS+fFPLe0G3QAG3ZgjGkGsx3TQ80kx1X1os9D/BoGHWs2Vi1asv
G/7N5Q7GzafrguhgJOReTLkOwztJwVwoB9YBGWCnXd3Ml+ass8pZokvvjwGwt4Ta
DVDdP1VAisjSWKB/v5OO3Yxk5l0ekr9Ivml2JiqxnKwQ+E6wRWl7bpVZuHPXU/jD
xXwf3PUFtLbKNuL4BLQfr94qaeIVAWObYUnTL92jc+qHL3+QzbDG9vKLNvT1u7WY
Wf1WWyRZ3OcrfdhiQyRz8JuhBfjNPxTigc5jmZAhBJ8KhKzGmXChsb/ItD7Dn/BK
NHfG9K2Z7bBRkuOBDcnLp25+F6aACugn/sQvKIYd9+6wdyaRNme4xFTg42T/KvYk
vTIrUygqZVApjuzWvNEG1jvu1rLzRcfseIG1FVBR2btFWBiRth0HI3RTxZB6pY0l
sfDf5Y79cVSaAvcgvvVC1YKZI1Vpp2zVD/5Z0nVkNz7+q8ARfnLunmsDlvtRVdFo
vHCuNbYd5Clm66X8ZzCJhRFmpDNwmZo5JOxkxZ8OVxaZZlV/kS5xwlB7a0yiC1ef
LC90P0I+rq8sgDlOMnKesKdpY3lJLsGX+rGWUX6cDmQPp5M1HQvJ0LbzsC9t7UuN
x4uri5wvjvsHxC7vRQ3u
=ZGsM
-----END PGP SIGNATURE-----