leah blogs

Playing a bit with Nukumi2, I discovered a very interesting thing: If I disable BlueCloth, my pages suddenly render a lot slower. “This ain’t possible”, I stumbled. BlueCloth is fairly fast, but still the slowest component of the rendering stage. “What the hell is going on?”

I timed the rendering of a few entries by themselves, they were all faster than with BlueCloth. Well, all except one. Yesterday’s. I trimmed it a bit, and finally found out that if I removed that part, it would run at full speed again:

class Class
  def attr_inject(attribute)
    (@__attributes_to_inject ||= []) << attribute
  end
end

I ran a profiler (ruby -r profile), and it turned out String#scan was taking quite long… Where is it used? In RubyPants, look at the code:

def tokenize
  tag_soup = /([^<]*)(<[^>]*>)/

  tokens = []

  prev_end = 0
  scan(tag_soup) {
    tokens << [:text, $1]  if $1 != ""
    tokens << [:tag, $2]

    prev_end = $~.end(0)
  }

  if prev_end < size
    tokens << [:text, self[prev_end..-1]]
  end

  tokens
end

Ok, it’s a part of the HTML tokenizer… The only reason scan can be slow is the regular expression, let’s have a closer look:

tag_soup = /([^<]*)(<[^>]*>)/

Well, it looks alright: First match any preceding text and then a tag. After toying around for fifteen minutes with that regexp, trying various tweaks (e.g. making it non-greedy), I built a proper test case. That string took very long, ~6 seconds to parse it 100 times:

<hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...

Even more h to come. I remembered a scary issue about regular expressions: Under certain circumstances, backtracking can make Regexps run in exponential time (various string sizes showed that) because they try every possible match.

It really looked like that was the case… But where the hell does it backtrack? There are no alternations, and the match should run linearly. Well, it should. But it didn’t. It turned out that it really tries every possible match, because the match isn’t anchored.

D’oh! Of course, there is no anchor. Luckily, I remembered \G from back when I used Perl. man perlre says:

       \G  Match only at pos() (e.g. at the end-of-match position
           of prior m//g)

Hey, cool. That should be exactly what we need. Make that line simply

  tag_soup = /\G([^<]*)(<[^>]*>)/

and off it goes! Blazingly fast. :-)

Who would have thought two characters can make such a big difference?

(Of course, I’d have never discovered that “bug” if I only ran it on correct input (as >> is not valid HTML), so test your code with “invalid” data too!)

NP: Sum 41—We’re All To Blame