Quick update--I'll post numbers later. It appears that the REXML stream 
parser in Ruby 1.8.1 is worse than O(n) in the number of input lines (or 
tags). Ruby 1.8.0 appears to be pretty close to O(n) (as it should).

I hope soon I won't be the only person in this thread :-).

Steve