News for hackers. Stuff that matters.
Re:Mux – A lightweight, fast HTTP request router for Go by SEJeff on Monday December 05, 2016 @10:59AM (#13106250)
Does it use a trie? If not, it probably should. Here's a wonderful talk on using that datastructure (with go) for the gov uk url router:

https://gdstechnology.blog.gov.uk/2013/12/05/building-a-new-...

The Vulcan proxy from Mailgun does the same thing:

http://vulcand.github.io/proxy.html#route

It looks like it doesn't, so existing open source golang url routers will perform much better, contrary to this post. The one in vuland is interesting in that it supports both regex AND tries, so you get the best of both.

Additionally, httprouter (golang) uses a trie and is fast as hell:

https://github.com/julienschmidt/httprouter

Edit: Adding another one (thanks buro9!) that is used in production by CloudFlare:

https://github.com/pressly/chi

Re:Mux – A lightweight, fast HTTP request router for Go by alex_dev on Monday December 05, 2016 @11:59AM (#13106869)
Looks like it uses regexp... There isn't any benchmark code as one would expect when making a claim that it's "fast".
Re:Mux – A lightweight, fast HTTP request router for Go by laumars on Monday December 05, 2016 @12:32PM (#13107238)
Regexp definitely isn't something you'd want to be using if you're primary goal is speed. When running tight loops in string parsing I've found using string splitting and then cycling through the range of indices in a slice was several times faster than Regexp matching. Obviously performance difference will vary depending on the expression and application but that was enough to convince me to think twice about future usage of Regex - as to whether the problem needed Regex or if I was just using them lazily. The latter being a practice I'd slipped into after years of Perl hacking.
Re:Mux – A lightweight, fast HTTP request router for Go by jules on Monday December 05, 2016 @02:31PM (#13108467)
That depends entirely on the regex implementation. If the implementation uses a DFA to match multiple regexes simultaneously then the performance will be as good as a trie because a DFA is more or less a trie.
Re:Mux – A lightweight, fast HTTP request router for Go by vanderZwan on Monday December 05, 2016 @04:06PM (#13109574)
> That depends entirely on the regex implementation

True, and anyone who knows that Russ Cox is a core member of the Go team will have a hard time suppressing a smirk when reading this :)

https://swtch.com/~rsc/regexp/

Re:Mux – A lightweight, fast HTTP request router for Go by laumars on Monday December 05, 2016 @04:28PM (#13109816)
True. I was talking specifically about the same Regexp package as the one used in the topic project though.

I assumed that would have been obvious given the context however I apologise for not stating that in my comment and shall amend it appropriately. [edit: i can't add an amendment to my previous post now]

Re:Mux – A lightweight, fast HTTP request router for Go by mypalmike on Monday December 05, 2016 @05:01PM (#13110124)
True. But nowadays most regex implementations are quite good (apparently go's is not - I haven't used it).

That said, most regex performance problems are PEBKAC. Writing a fast regex is hard and requires a pretty thorough understanding of parser theory. And many who use regexes don't understand that it's critical to precompile them for performance. You don't get a fast parser when you rebuild the DFA each time you use it.

*edit: a word

Re:Mux – A lightweight, fast HTTP request router for Go by aikah on Monday December 05, 2016 @12:51PM (#13107458)
Go regexps are slow (https://goo.gl/r0K2xw ), the problem is not regexps but Go's implementation of regexps. So let's not blame regexps when regexps aren't the problem. Because by that logic, people shouldn't use the sort package as well ...
Re:Mux – A lightweight, fast HTTP request router for Go by laumars on Monday December 05, 2016 @04:44PM (#13109975)
You're making a distinction where one doesn't need to be made. It doesn't matter if regexp is generally slow or if it's Go implementation specifically - if you're using Go and wanting something where performance is your primary goal then you're generally best to avoid using regexp.
Re:Mux – A lightweight, fast HTTP request router for Go by aikah on Monday December 05, 2016 @04:59PM (#13110105)
> You're making a distinction where one doesn't need to be made. It doesn't matter if regexp is generally slow or if it's Go implementation specifically - if you're using Go and wanting something where performance is your primary goal then you're generally best to avoid using regexp.

Avoiding regexp doesn't fix Go's implementation of regexp. Making them faster does. Your argument is preposterous. If the Go team really cared about performances it would fix its regexp implementation.

Re:Mux – A lightweight, fast HTTP request router for Go by SEJeff on Monday December 05, 2016 @05:19PM (#13110286)
I think you're missing the point of the discussion entirely. When you're more or less doing string splitting, using regex (regardless of performance) really is the wrong tool for the job. In this use case (url routing) a tree based data structure aka a trie or radix tree, are better suited.
Re:Mux – A lightweight, fast HTTP request router for Go by aikah on Monday December 05, 2016 @05:40PM (#13110480)
> I think you're missing the point of the discussion entirely. When you're more or less doing string splitting, using regex (regardless of performance) really is the wrong tool for the job. In this use case (url routing) a tree based data structure aka a trie or radix tree, are better suited.

I'm not missing the point of the discussion. Using regex is not the wrong tool for the job. You deemed it the wrong tool for the job. And deeming it the wrong tool for the job doesn't fix Go regex being slower than in other languages. The 2 issues are not separate .People like you talk about performances as a goal while dismissing obviously performance issues in the standard library as "wrong tool for the job".

You're not going to convince anybody with this kind of argument, aside from gophers who already think like you do. I'm not one of them.

Re:Mux – A lightweight, fast HTTP request router for Go by SEJeff on Monday December 05, 2016 @09:27PM (#13111780)
FWIW If the router was in C or Rust or .net (which has a Jit for their regex engine) I would still tell you Regex is the wrong tool for splitting a URL on '/'. How many people have to tell you facts for you to believe them? Forget your pointless anti-go bias. A regex, while perfectly good for certain types of pattern matching makes no sense here.

I often have taught the same lesson to my junior colleagues who use regex in Python or C++ code where splitting the string would be simpler, more maintainable, and faster.

Re:Mux – A lightweight, fast HTTP request router for Go by aikah on Tuesday December 06, 2016 @12:23AM (#13112447)
> How many people have to tell you facts for you to believe them? Forget your pointless anti-go bias

Because a few people on HN is the consensus ? give me a break. You have your opinion, I've got mine, whatever you think you are you're in no way an authority on the matter. There are many ways to implement an http router, there are also many ways to implement regular expressions. A bad implementation isn't saved by deeming the use of regexp "wrong tool for the job".

> A regex, while perfectly good for certain types of pattern matching makes no sense here.

What make no sense is your petty comment.

> Forget your pointless anti-go bias

Pointing out facts is "anti-go bias". OK , how about you stopping drinking the "pro-go koolaid" ?

Re:Mux – A lightweight, fast HTTP request router for Go by SEJeff on Tuesday December 06, 2016 @10:31AM (#13115251)
I think you're a bit delusional, I don't even write go (hence there literally being no koolaid for me to drink), but you're free to continue disagreeing, and continuing to be wrong :)
Re:Mux – A lightweight, fast HTTP request router for Go by literallycancer on Monday December 05, 2016 @09:31PM (#13111800)
A person looking to use a HTTP router most likely isn't going to rewrite/fix the regexp package just so they can use this router when there are already other routers that are faster as is. Do you dispute that?
Re:Mux – A lightweight, fast HTTP request router for Go by duaneb on Monday December 05, 2016 @11:52PM (#13112348)
If you use a broken hammer to attempt to insert a screw, you're crazy for using the hammer, not because it's broken.
Re:Mux – A lightweight, fast HTTP request router for Go by aikah on Tuesday December 06, 2016 @12:19AM (#13112438)
> If you use a broken hammer to attempt to insert a screw, you're crazy for using the hammer, not because it's broken.

Are you resorting to insults now ? or is the typical hate and mean spirit of the Go community ? a router isn't a hammer. And I could care less about your opinion.

Re:Mux – A lightweight, fast HTTP request router for Go by duaneb on Tuesday December 06, 2016 @12:17PM (#13116312)
I sincerely did not intend to insult you. I'm also not associated with the go community.
Re:Mux – A lightweight, fast HTTP request router for Go by cyphar on Tuesday December 06, 2016 @01:03AM (#13112581)
The comment linked is about CSV parsing being slow (the linked GitHub issue in the comment shows that the `regexp` doesn't show up in the benchmarks at all). So I don't understand why you linked a 6-year-old thread that's been revived by unrelated topics?
Re:Mux – A lightweight, fast HTTP request router for Go by creshal on Monday December 05, 2016 @02:18PM (#13108367)
Regexes are the problem, because they're simply the wrong tool for the job.
Re:Mux – A lightweight, fast HTTP request router for Go by aikah on Monday December 05, 2016 @02:59PM (#13108840)
> Regexes are the problem, because they're simply the wrong tool for the job.

for what job? Extracting route variables from paths ?they are the right tool for the job, only in the Go community they are deemed "wrong tool for the job". Your statement embodies everything that is wrong with the Go community. Instead of finding a solution to a problem you guys spend your time shifting the blame on "bad practices".

Re:Mux – A lightweight, fast HTTP request router for Go by rudolf0 on Monday December 05, 2016 @03:43PM (#13109330)
Wouldn't it make more sense to use something faster and simpler for most routing, and then an optional argument for regular expressions? Lots of web frameworks use that approach.
Re:Mux – A lightweight, fast HTTP request router for Go by dvdhnt on Monday December 05, 2016 @11:10AM (#13106358)
These links are pretty cool. Are there any tutorials or walkthroughs you would recommend? Like, Go has always interested me but I have no idea where to start to get an experience like say ExpressJS or even where to find templating or rendering.

Any suggestions are appreciated!

Re:Mux – A lightweight, fast HTTP request router for Go by navd on Monday December 05, 2016 @11:39AM (#13106642)
With go there is really less emphasis on taking advantage of a web framework like expressjs (look at go alternatives like gin) and building server functionality from the std library (since everything you need is there). I wrote a small helper library to help with template rendering if you're interested in looking at the source to see how you can take advantage of the std library for templating: https://github.com/dannav/migo
Re:Mux – A lightweight, fast HTTP request router for Go by cloverich on Monday December 05, 2016 @11:36AM (#13106617)
When I was learning Go, Negroni was where I left off and felt like what you may be looking for as a next step: https://github.com/urfave/negroni (I"m sure someone more experienced can provide more context or other / better links -- thought this would be a better answer than none until then)
Re:Mux – A lightweight, fast HTTP request router for Go by thewhitetulip on Monday December 05, 2016 @10:31PM (#13112028)
https://github.com/thewhitetulip/web-dev-golang-anti-textboo...

I have written a very basic introduction to writing webapps in Go without using a framework, as others have rightly pointed out, we really do not need to use a framework in Go for writing webapps, and Go is a great language.

If you don't like mine, https://github.com/astaxie/build-web-application-with-golang... is a nice start for new comers.

Re:Mux – A lightweight, fast HTTP request router for Go by alistproducer2 on Monday December 05, 2016 @12:55PM (#13107500)
Interestingly enough, I used a trie (without knowing that's what it was called) when building the router for my Frontend framework.

https://github.com/ShamariFeaster/Templar/blob/master/core/R...

Re:Mux – A lightweight, fast HTTP request router for Go by zbobet2012 on Monday December 05, 2016 @01:29PM (#13107860)
Trie's are my favorite data structure. The implementation in the Linux kernel is a lock free RCU structure (http://lxr.free-electrons.com/source/lib/radix-tree.c). It is used for the page cache among other things.
Re:Mux – A lightweight, fast HTTP request router for Go by creshal on Monday December 05, 2016 @11:13AM (#13106394)
httprouter is really awesome. I switched to it when Go's built-in router would cause panics during msan stress testing (back in Go 1.6), and really performs well.
Re:Mux – A lightweight, fast HTTP request router for Go by sorokod on Monday December 05, 2016 @01:51PM (#13108105)
Why is a trie obviously better then a hash map?
Re:Mux – A lightweight, fast HTTP request router for Go by jeremiep on Monday December 05, 2016 @01:55PM (#13108160)
They allow you to match the URL in a series of steps. Where each step can be static (ie "/foo") or dynamic (ie /images/).

You can then easily add features to this structure, like route middlewares at every level in the tree; just apply them while doing the routing.

This also allows you to match route variants easily, ie "foo" and "foo/" are the same, so are "/" and "/index.html". In the same way you can extract query parameters for middleware/handler use.

Re:Mux – A lightweight, fast HTTP request router for Go by mstade on Monday December 05, 2016 @03:37PM (#13109247)
Also, tries means it's trivial to do detect routing ambiguities, so your routing table doesn't necessarily have to be built up front, or in any particular order. This is particularly powerful when you're developing an application with a team distributed both over space and time.
Re:Mux – A lightweight, fast HTTP request router for Go by zbobet2012 on Monday December 05, 2016 @02:54PM (#13108781)
A trie is O(k), where k is the length of the key on inserts and deletes. Generally, any hashing algorithm is also O(k) with the additional overhead of the lookup in the table. This also ignores that most hashes have only amortized O(1) inserts. A trie usually also exhibits better memory locality and caching behavior. Also, a trie (like most tree data structures) can be implemented in a lock-free format fairly easily.
Re:Mux – A lightweight, fast HTTP request router for Go by teraflop on Monday December 05, 2016 @01:54PM (#13108142)
A hash map doesn't solve the same problem. Given a collection of routes, you need to find the longest one which is a prefix of the given URL.
Re:Mux – A lightweight, fast HTTP request router for Go by buckhx on Monday December 05, 2016 @05:59PM (#13110654)
A trie can efficiently match all routes that start with a prefix. With a hashmap you wouldn't be off any better than a list efficiency wise.
Re:Mux – A lightweight, fast HTTP request router for Go by SEJeff on Monday December 05, 2016 @02:03PM (#13108235)
Fixed lookup time. A trie (aka radix tree) 3 levels deep with 1 million entries has the same lookup time as a 3 level deep trie with 5 entries.
Re:Mux – A lightweight, fast HTTP request router for Go by papaf on Monday December 05, 2016 @02:07PM (#13108266)
Isn't the same thing true for a 3 level deep hashmap of hashmaps?
Re:Mux – A lightweight, fast HTTP request router for Go by SEJeff on Monday December 05, 2016 @04:18PM (#13109706)
See a much better answer than mine: https://news.ycombinator.com/item?id=13108781