Sorry, the runtime complexity in Calfpath would be generally O(n^2) because iterating routes and under every route iterating each character in the URI template in the worst case.
Shantanu On Monday, 7 January 2019 12:43:44 UTC+5:30, Shantanu Kumar wrote: > > > > On Monday, 7 January 2019 01:03:16 UTC+5:30, Paul deGrandis wrote: >> >> Hi Shantanu, >> >> Interesting project and congrats on the release! >> >> I think Alan was asking more about the runtime and space complexities. >> What is the core approach used in Calfpath? What is the runtime and space >> complexity? What are the ideal operational conditions and under what >> conditions does it suffer? What were the trade-offs made in the approach? >> >> I'm curious to know the answers myself. Thanks! >> > > > Hi Paul, > > Thanks for expanding Alan's question. I think, the short answer about > runtime and space complexity would be O(n) and O(n) in Calfpath. Please > read on for more details. The top performing implementations in Calfpath > cannot support a very large number of routes (subject to Java method size > limit.) > > At the grass root level, the URI matching code (hand coded in Java, not > using any regex) is common across all Calfpath routing. It pre-compiles a > URI pattern, e.g. "/foo/:id/bar" into a vector of tokens ["/foo" :id > "/bar"] and later the URI-matching function iterates over the tokens. > > There are three implementations of routing supported in Calfpath, each of > which returns `nil` as soon as it realises a match is not likely: > > 1. Macros: There are macros (in calfpath.core ns) for matching URI, method > etc. that expand in-line. The URI, method etc are literals that are > pre-compiled for efficient matching. Obviously, this approach leads to > in-lined code that runs the risk of exceeding the Java method size (in > bytecodes) limit for a large number of routes. However, given that the vast > majority of applications have < 50 routes in number, it is not a concern > for many. > > 2. Walking precompiled routes: This is an implementation (in > calfpath.route ns) of data driven, potentially nested, routes (vector of > maps). The routes are pre-compiled to a substrate form, still as vector of > maps, that a function iterates over recursively where nested. This is a > simple, iterative implementation that can also handle a large number of > routes. It is also the slowest among the three routing implementations. > > 3. Loop-unrolled expression tree: This is also an implementation (in > calfpath.route ns) of data driven, potentially nested, routes (vector of > maps). The routes are pre-compiled to a substrate form like in the second > implementation. Then, a function assembles an expression tree using all the > routes info, wraps it in a function form and calls `eval` to turn the > expression tree into a function. The result is an in-lined function that > performs close to the first macro-based implementation, and runs the same > risk of exceeding Java method size limit for a large number of routes. This > technique also makes optional (enabled by default) use of deep > expression-tree building, where pre-compiling URI matching and method > matching also emit expressions in addition to matcher functions. > > In general, the optimisations in Calfpath rely more on JIT's instruction > caching than data-cache coherence, and the fact that web-routing is such a > repeatedly executed code that it's OK to inline most of the routing code > together. Hope this explains Calfpath's approach. Please let me know if you > have any other questions. > > > Shantanu > > >> >> Cheers, >> Paul >> >> -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
