Nice, but is the templating engine really the bottleneck for your application? And if not, does it really matter that this implementation is 40 times faster?
For a lot of dynamic languages, at least, the templating engine is a surprisingly large portion of your page load times. I wish I could bring up the breakdown I saw a while back, but it's certainly non-trivial in many cases.
A (niche) use may be to compile for NativeClient, to provide better responsiveness if you're doing large templated live-previews (though admittedly this is more sensible with formatting like markdown rather than templating).
I have no experience with Ruby template engines, including Crustache and Mustache, but of course it matters about serving clients 40x times faster. 800ms to serve me what could be had in 20ms? Amazon, Google [1][2], and others have talked extensively on speed-to-conversion ratios.
In Python land, there have huge improvements in template engines [3]. And they are not done; Jinja(2) author, Armin Ronacher, is working on a Google Summer of Code (GSoC) project [4] to speed up Django and Jinja2 templates.
I had a little project a while ago that compiled Mustache templates into C. Never was completely done, but it mostly works: https://github.com/tyler/speed_stache
Yikes. I hate to be critical, but whenever I read, "a faster implementation of $ruby_thing in C", I get ready for an entertaining night of reading someone's first ever C project. Crustache did not disappoint. So far, I've only read array.c, but I had to stop when I realized that his "dynamic arrays" reallocate by 1 array element each time. This provides for O(n) appends, which means O(n^2) to build an entire array. Ouch.
You need to double the size of the array each time in order to get amortized O(1) appends. It's easy to convince yourself of this if you don't trust me: assign a "copy credit" to each array element you add to the array without calling realloc (which can copy the entire array in O(n) steps), and spend one "copy credit" each time you copy an element to a new array. If you've spent more than you've earned, you aren't amortized constant time anymore.
Let's walk though an example. Let's allocate two elements to start. We write the 0th element, and get a credit, then write the 1st element, and get a credit. When we write the 2nd element, we need to grow the array. We allocate a 4 byte array and copy the original array here, spending two credits in the process. This leaves us with zero credits, which means everything is OK.
Also interesting is that the author gets his binary search right (at first glance) and even protects against integer overflow correctly. The irony is that binary search is a standard library function, bsearch(3), so why reimplement it? And, why copy and paste that implementation no less than three times? And, oh... of none of the other additions in the file (on operations on the same array as the binary search, no less) are protected from overflow. Inconsistent.
I'm not sure how much I like the array insertion function that reallocs, copying the entire array, and then memmoves the half of the array after the inserted elements. That's a lot of copying; why not use a linked list or a more esoteric random-insert data structure? A finger tree can provide O(log n) inserts and O(1) lookups.
Finally, why "int" for the size and not size_t?
Anyway, be careful when you download some code from the internet written for speed. It's often not as fast as it could be, and it's certainly not as reliable as code written in a higher-level language.
I love the author's complete disregard for what science actually is, and instead using the word as a synonym for something unstable and dangerous:
"WHO KNOWS WHATS GONNA HAPPEN. DO IT FOR SCIENCE."
It reminds me of Looney Tunes cartoons' impressions of chemistry sets and scientists. Fun is often the best response to the natural question: "but what if I just do...that?"
24 comments
[ 5.4 ms ] story [ 104 ms ] threadhttp://tomayko.com/writings/ruby-markdown-libraries-real-che...
In Python land, there have huge improvements in template engines [3]. And they are not done; Jinja(2) author, Armin Ronacher, is working on a Google Summer of Code (GSoC) project [4] to speed up Django and Jinja2 templates.
[1] http://googleresearch.blogspot.com/2009/06/speed-matters.htm...
[2] http://glinden.blogspot.com/2006/11/marissa-mayer-at-web-20....
[3] http://stackoverflow.com/questions/1324238/what-is-the-faste...
[4] https://www.djangoproject.com/weblog/2011/apr/25/gsoc/
To their credit, this is the first time a templating engine makes me laugh.
You need to double the size of the array each time in order to get amortized O(1) appends. It's easy to convince yourself of this if you don't trust me: assign a "copy credit" to each array element you add to the array without calling realloc (which can copy the entire array in O(n) steps), and spend one "copy credit" each time you copy an element to a new array. If you've spent more than you've earned, you aren't amortized constant time anymore.
Let's walk though an example. Let's allocate two elements to start. We write the 0th element, and get a credit, then write the 1st element, and get a credit. When we write the 2nd element, we need to grow the array. We allocate a 4 byte array and copy the original array here, spending two credits in the process. This leaves us with zero credits, which means everything is OK.
Also interesting is that the author gets his binary search right (at first glance) and even protects against integer overflow correctly. The irony is that binary search is a standard library function, bsearch(3), so why reimplement it? And, why copy and paste that implementation no less than three times? And, oh... of none of the other additions in the file (on operations on the same array as the binary search, no less) are protected from overflow. Inconsistent.
I'm not sure how much I like the array insertion function that reallocs, copying the entire array, and then memmoves the half of the array after the inserted elements. That's a lot of copying; why not use a linked list or a more esoteric random-insert data structure? A finger tree can provide O(log n) inserts and O(1) lookups.
Finally, why "int" for the size and not size_t?
Anyway, be careful when you download some code from the internet written for speed. It's often not as fast as it could be, and it's certainly not as reliable as code written in a higher-level language.
<roy>Well no.</roy>