It pre-compiles routes to a prefix trie [0], which allows it to match any route in one run by walking down the tree rather than trying each route from scratch. Nginx uses the same strategy for static routes.
R3 does look fast, but there's a cost to crossing the JS -> C barrier. It's almost certainly possible to beat it using the same algorithm written in pure JS.
Finding a match in a tree structure is asymptotically O(log n), finding a match in a list is O(n). This router is also written in C.
There is a benchmark in the README comparing R3 to the Rails router and also to a replacement Rails router that I wrote for non-performance related reasons.
It should be noted that usually only a tiny proportion of the time taken to respond to a request is spent in route recognition. YMMV.