Short-Circuit Evaluation Is Fast : Kinky Solutions : A Student's Perspective by Ben Nadel

Recent Entries Complete Entry List May 2008 April 2008 March 2008 February 2008 January 2008 December 2007 November 2007 October 2007 September 2007 August 2007 July 2007 June 2007 May 2007 April 2007 March 2007 February 2007 January 2007 December 2006 November 2006 October 2006 September 2006 August 2006 July 2006 June 2006 May 2006 April 2006 AJAX (13) Ask Ben (92) Books (12) ColdFusion (832) Exercise List (17) Flash (3) Health / Fitness (31) HTML / CSS (28) Javascript / DHTML (85) Life (62) Movies (20) Project HUGE (28) Relationships (6) Search Engine Optimization (14) Skin Spider (30) SQL (82) Work (101) XStandard WYSIWYG (21) RSS 2.0 Custom RSS 2.0

Posted June 2, 2006 at 8:23 AM

Tags: ColdFusion, Search Engine Optimization

As I wrote some time ago, taking Michael Dinowitz's advice, I turn off session management for Spiders and Bots in an effort to cut down on memory usage on the server. See, spiders do not accept client cookies and therefore (on my sites) cannot hold sessions. Consequently, they start a new session for each page request they make. Since sessions take some time to timeout, this ends of creating large numbers of session variables that go unused (in proportion to the number of pages spidered).

When I first did this I used a Regular Expression (RegEx) to check for commonly known spider user agents (CGI.http_user_agent). It looked something like:

 Launch code in new window » Download code as text file »

This works great; however, I started adding more spiders to the list (as they started hitting my site) and I starting to fear that it wasn't efficient. If you ever look at how a regular expression works by using a program such as The RegEx Coach you can actually step through the RegEx path and you will see that for every character it comes across in the target sting, it does a LOT of logic for the regular expression. And, the larger the expression the more the logic.

This got me thinking about short-circuit evaluation. I am not sure which version brought this on board, but ColdFusion MX 7 has this feature, this optimization. This optimization means that evaluation of a relational expression in an IF statement is terminated just as soon as it is possible to tell what the result will be. Meaning that if you have several parts of a single IF statement and the first can determine the fate of the IF, then the remaining parts are not evaluated.

For example, in the following example, only the first value is checked:

if (false AND true AND true AND true){ ... }

Since the "false" makes the statement false no matter what the rest of the arguments are, the remaining "true" statement are not even evaluated.

I have taken this idea and applied it to the problem of turning off session management for spiders. Instead of using a regular expression, I break out each comparison to its own sub-part of an IF statement:

 Launch code in new window » Download code as text file »

Now, regular expressions do short-circuit evaluation also, so the difference here is subtle. Let's say that we get a page request from a non-spider user agent. This is the "worst case" scenario since we will have to check every spider value against the string. With a regular expression, we would have to run through the matching processing for each of the (N) spider values for each of the (C) characters in the user agent. That's NxC iterations. However, in the compound IF statement, we would only have to run the matching process for each spider for each (U) instance of a user agent. That's just NxU and since U is always one, its just N number of iterations.

Now this is misleading because for string comparison, the substrings still have to match against many characters in the target string, but I am sure (but do not know for a fact) that literal matching must be faster than RegEx matching since there is not "logic" to literal matching.

If we do get a spider request that is a popular spider (higher in the IF statement, earlier in the regular expression), it's still faster to have the compound IF statement. See, the regular expression still needs to be checked in it's entirety for EACH character it comes across in the target string. But the IF statement only needs a sub-set of the IF sub-part run just once.

Of course, in practicality, they all run between 0-16ms per page hit. With large iterations (10,000+), the compound IF statement is levels of magnitude faster.

Furthermore, you can make it even faster by creating a temporary string of the LCase() of the user agent and then doing Find() rather than FindNoCase() for each sub-part (not shown above).

Download Code Snippet ZIP File

Comments (2)  |  Post Comment  |  Ask Ben  |  Permalink  |  Other Searches  |  Print Page

• Add To Del.icio.us
• Add To Digg
• Add to Spurl.net
• Add to Wists
• Add to Simpy
• Add to Newsvine
• Add to BlinkList
• Add to Furl
• Add to reddit
• Add to FARK
• Add to BlogMarks
• Add to Yahoo! My Web
• Add to smarking
• Add to Ma.gnolia
• Add to Segnalo

Reader Comments

Would a switch statement be even faster in this case Ben?

Posted by Andy Matthews on Oct 24, 2007 at 3:48 PM

@Andy,

A Switch statement would not quite work in a situation like this since we are not matching on the entire user agent, just parts of it.

Posted by Ben Nadel on Oct 24, 2007 at 7:36 PM

Post Comment  |  Ask Ben