Jeff’s Austin Blues

In the previous post I discussed how on the way to a planned re-implementation in C of some database access, achieved a nearly order of magnitude speed up by bypassing the Ruby on Rails ActiveRecord database access class and generated the SQL myself. Faster but still some performance problems. Benchmarking, profiling, and online research turned up hints that relational database joins are powerful, but slow. So I spent some time thinking about how to speed it up. There are several approaches, some I found in DSPAM, some I found online, and some that came to me in the middle of the night.

The associations are created (and destroyed) all at once. Rather than store them as many records in the database, how about one record, or even a field in the article record/row itself. DSPAM does this, and it is fast enough. Doing it in pure Ruby/Rails would involve marshaling an array or hash of string and integer pairs. Since Ruby allows the elements of an array (or hash) to not all be the same type, type information is required for each value. This could be slow. In this case all elements are the same, and the information is already in the item record, the article description itself. Can Rails/Ruby regenerate the information on the fly faster than it can read it from disk? The answer is yes. If I think outside the database and the usual way of doing things.

Associations/join table typically contain the record ID (the primary key by convention/default in Rails) of both sides of the association. But what if instead of using the ID as the lookup key, the word/token string itself is the lookup key. In MySQL, my benchmarking found that string lookup is approximately 10% slower than integer key lookup (both with indexes). With string lookup, the join table can be discarded completely.

When optimizing it must be kept in mind what is the expensive/scarce resource(s). For many projects, it is the programmer’s time (i.e, programmer salary and overhead, or time to market is the scarce resource). However, user’s time/patience must be kept in mind too. Moving away from DSPAM (in C) to a pure Rails and ActiveRecord solution put the latter on the critical path.

I have made the simplifying assumption that as few database calls as possible is a plausible way to go, keeping in mind that large joins are also expensive. With the string indexed lookup I eliminated the join table. By accumulating all changes and rolling all inserts into one SQL INSERT statement, all updates into one SQL UPDATE statement, I gained almost as much speedup as the first optimization. The combination is around 16 to 50 times, depending whether you measure elapsed time or CPU (times in seconds):

Better than I expected. Maybe it’s time to stop bit-twiddling and get back to adding features.

Pre-mature optimization is the root of all programming evil.

– Donald E. Knuth

The latest change to Amethyst, dropping DSPAM and using a simple frequency of use scoring, is working well. Except it is slow. I’ve tweaked the database access from Ruby on Rails about as much as is feasible (mostly combining multiple updates into a single SQL statement, e.g. UPDATE tokens SET occurrences = occurrences + 1 WHERE id IN (1,2, 3, 100, 1001, 1234)). By dropping down from ActiveRecord instances to SQL and pre-computing in the background where straightforward I’ve speeded up the Web/user interface to where the response is acceptable and the delays are where expected (i.e., searches but not click-throughs, up and down votes, etc.).

However the fetches of the RSS feeds and updates of the database take a long time. When my laptop has been off or off-line for several hours getting caught up is a problem. With DSPAM (written in C), it was possible to update in one big gulp. I’ve spread the update over four cron job invocations and it is still a problem. With all the code in Ruby, updates can take several minutes, frequently more than the five minute interval between cron jobs that do the updates. The result is multiple entries for the same blog story. I’ve add the use of a lockfile to prevent multiple instances of the cron job, but there are still occasional conflicts and unexplained errors.  And I like to not wait 20 minutes for the updates to complete.

Since I know from experience with DSPAM that dropping into C will speed it up enough and the current slowness is a problem, it seems to me that optimization is no longer pre-mature. And the place to start seems to be the DSPAM database access code without the scoring code.

Updates as details emerge. The DSPAM code is a bit of a slog, it has more options than you can shake a stick at.

The change from DSPAM to a home-grown solution for ranking the RSS feed articles in Amethyst has generally been a change for the better. In spite of several bugs that skewed the statistics, it generally behaves as desired. Except it is much more CPU intensive. DSPAM is written in C and eats a fair amout of CPU time. Amethyst is entirely in Ruby and Ruby on Rails. When the laptop has been off for several hours, it really eats up the CPU cycles when up and reconnected to the Internet. So much so that I’ve had to spread the catchup over 20 minutes instead of letting it do it all in one go. The reason is that the RSS feed refreshes run as a cronjob and don’t always complete in the 5 minutes between invocations. So there are multiple copies trying to update the database at once, leading to duplicates. Not good.

So I did a little searching around. There is a Ruby Gem, lockfile, for this and similar problems. It creates a a file, the lockfile, and runs a program if the lockfile doesn’t already exist. It deletes the lockfile when the program completes. If the lockfile already exists, it can retry for an period of time or a number of retries. It is NFS filesystem safe and has rudimentary stale lockfile detection (based on the age of the lockfile).

So far it has blocked just one invocation of the RSS feed refresh cronjob and I’m not seeing the duplicate key errors I had been. So far, so good.