Making a Lua program run more than 10 times faster
Archive - Originally posted on "The Horse's Mouth" - 2010-04-16 19:06:55 - Graham EllisI made an extraordinary claim on Thursday. One of my delegates had written a program that analyzed a huge data file in a Lua script, and it was taking over half an hour to run. "Give me five minutes, and I could have that running in less that five minutes" I claimed.
It was all to do with pattern matching in Lua ... and I was pretty sure of myself, but my delegates were less sure of the claim. But it didn't really matter - it would have been a diversion from the main course if we had sidetracked to test my assertion.
But when I make a claim, and that claim is doubted, I worry. Was my claim reasonable, or wash it brash and overoptimistic? Well - how better to find out than to try it.
Try it, I did ... the original takes 3283 c.p.u. seconds to run - that's analyzing a 43 Mbyte log file looking for search engine arrivals, and extracting the search terms that were used.
In the original, the lookup was simple on each line:
string.find(line,'(%S+).*"http.*%.google%..*[&?]q=(.-)[&"]')in other words, grab the first value on the line, then look for the referer, check if it's google, and if it is grab the query string.
It works - well - but s-l-o-w-l-y.
Let's try to speed that up. Rather than analyse every line starting with wild cared groups of indefinite size (which are a VERY fuzzy, so slow) match, let's start off by looking specifically for the google reference:
string.find(line,'%.google%.')if that works, lets grab the first field off the line:
string.find(line,'(%S+)')and also the query string:
string.find(line,'"http.-[&?]q=(.-)[&"]')Now your natural reaction may be to say "that code is longer and more complicated" - and indeed it is - "so it will take longer", but it turns out THAT conclusion is utterly incorrect.
The original took 3283 seconds. The modified code took (bang the symbol, roll the drums) ... 3.25 seconds. That's right - my claim that I could reduce the time from 30 minutes to 5 minutes was dreadfully conservative - I actually got it down to less that 5 seconds, or put another way it now runs 1000 times faster.
Although this example is written with Lua's pattern matching as the examples, exactly the same principles apply to regular expressions in Perl, PHP, Python, Ruby, Tcl ... etc.
• Start matches with anchors and literals if possible
• Try to avoid too many long woolly matches such as .+
• Eliminate lines / cases quickly if you can
• Don't try to do it all in one long pattern - several shorter ones are often much faster.
Source code of slow version - [here]
Source code of fast version - [here]