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.
