Hacker News Reader

Comment by SEJeff | Hacker News Reader

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

View on HN

Looks like it uses regexp... There isn't any benchmark code as one would expect when making a claim that it's "fast".

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.

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.

> 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/

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]

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

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 ...

Regexes are the problem, because they're simply the wrong tool for the job.

> 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".

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.

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.

> 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.

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 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.

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.

> 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" ?

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 :)

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?

If you use a broken hammer to attempt to insert a screw, you're crazy for using the hammer, not because it's broken.

> 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.

I sincerely did not intend to insult you. I'm also not associated with the go community.

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?

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!

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)

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

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.

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...

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.

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.

Why is a trie obviously better then a hash map?

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.

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.

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.

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.

Isn't the same thing true for a 3 level deep hashmap of hashmaps?

See a much better answer than mine: https://news.ycombinator.com/item?id=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.

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.

Reply on news.ycombinator.com