Congrats on the library! Read your code and It seems that writing the low-level code with Java pays off performance wise - the small routing tables in your perf tests are really, really fast. Reitit also has some Java-based optimizations for the JVM, but wildcard/trie routing is written in pure Clojure and on my laptop it seems to be few times slower on your test suite. The slower trie-based approach might catch up with larger routing tables, but still a good reason to investigate porting the trie to Java too. Also, citius looks nice.
Tommi maanantai 7. tammikuuta 2019 9.58.51 UTC+2 Shantanu Kumar kirjoitti: > > 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.
