I’ve repeated all the tests with Ruby 1.8.0 and it sure looks like
String#strip is the problem.
To summarize, I have a bare REXML stream parser that reads its input
file and does nothing. I’m handing it an input file that looks like this
<?xml version="1.0" ?>
I’m varying the number of elements in the file from 100 to
50000 and calling that n. In Ruby 1.8.0, the runtime is roughly
proportional to n, as it should be. In 1.8.1, the total runtime is
greater (which is bad but not pathological) and worse than linear in n
(which is pathological).
Here’s the profile data for strip over all values of n:
time/call % total runtime
min max min max
Ruby 1.8.0 .01 .02 .82 2.48
Ruby 1.8.1 .10 1.21 5.08 29.04
In both cases, the number of calls is proportional to n, although strip
is called 2.5 times more often in 1.8.0 than 1.8.1. In 1.8.1 (only),
there is a strong increasing trend in the time per call as n increases.
I don’t suspect the problem is in strip itself. I suspect the problem is
that REXML creates a string that grows as more input is read and hands
it repeatedly to strip. I looked briefly at the REXML code and didn’t
see anything obvious. (Other than the fact that calling strip on a
buffer just to see whether it has any tokens in it is inefficient. That
just makes it slow, however, not nonlinear–unless the buffer is growing.)
I hope this is enough for someone to diagnose and fix the problem. I’ll
send the data to anyone who wants it.