Optimising where it matters

Like Donald Knuth said, "Premature optimisation is the root of all evil", but when done right, and with careful analysis, it can make a world of difference.We found that Monkey was sequentially searching the MIME types list (today with around 131 entries) when trying to service a request, producing up to a 6 additional comparisons for a JPG image. That may not sound like much, but when you're dealing with 5000 requests, comparing 30000 strings is considered to be a bottleneck. At startup, the webserver reads the conf/monkey.mime file and stores it into a list, without any order, so naturally, if we add the most commonly used types, like HTML, JPG, PNG, CSS, XML, etc. at the beginning of the file, when searching, we will find them quicker.

This is only useful for the commonly used MIME types, because we can afford sequentially searching for up to 10 strings, but O(n) cannot be used for the rest of the of them. We implemented a simple, yet effective solution to keep two arrays in memory, one with the commonly used types, and another for the rest, both being populated when starting Monkey. So when searching for a type, if it's not found sequentially in the most used array, it will do a binary search for the rest, which costs only O(log n).

We got impressive results for the same JPG file: 50% less calls when comparing. In the case of a not so used type, we tried a manpage, actually the newly added monkey.1 file, resulting in:

85195 calls instead of 665000 to the string comparison function is a stunning improvement. Knuth also stated once:

In established engineering disciplines a 12 % improvement, easily obtained, is never considered marginal and I believe the same viewpoint should prevail in software engineering

This is a major achievement, specially considering the simplicity of the solution.