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.<p>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.<p>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.<p>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.<p>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.<p>Finally, why "int" for the size and not size_t?<p>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.