[Patch/RFC] Speed-up istreambuf_iterator and... sorry Jon!

[Paolo Carlini]

Hi,

the below is the result of a few days of deep struggle, caused,
for good, by Jonathan.

In private email, Jon told me that he had always believed that a
quality implementation of istreambuf_iterator caches the current
char, not only when operator++(int) is involved, as mandated by
the standard. I replied, more or less, reiterating what I wrote
some days ago on the list: that basic_streambuf::underflow could
return different values if called two times, that, after all,
sgetc() is pretty fast, and so on. Plus, I said that caching
requires invasive changes.

Well, I should say that Langer & Kreft also present an implementation
that does not cache (but they do *not* rule out the other possibility,
just say that uses more memory and "handwaving" ;)

However, the fact is, our istreambuf_iterator was /slow/ , deadly
slow... and I was aware of implementations around actually caching
the current char. Result: I haven't been able to sleep well for a
few days, seriously.

Today, during some interesting, "orthogonal" exchanges with Chris,
the following came to my mind: "if we cannot generally assume that
two consecutive operator*() call, without operator++ in the middle,
return the same value, then, we cannot really describe algorithms
working with input_iterator!".

Then, I examined again what the standard says about underflow, and
appreciated, for the first time, 27.5.2.4.3/8:

    "Returns: traits::to_int_type(c), where c is the first
    character of the pending sequence, /without moving the
    input sequence past it/ " (emphasis mine)

therefore, there /is/ the general assumption, that, also in the
unbuffered case, when gptr() in NULL, the input sequence /cannot/
move.

Also, even if we avoid calling too many times operator*() everywhere
in locale and algorithms, we end up calling _M_sbuf->sgetc() anyway
for the same position in the input sequence for omputating operator==:
we /cannot/ completely avoid that! To me, this is also a decisive
observation.

In short, everything considered, Jonathan was right: an implementation
caching the current char is legal, and welcome, from the performance
point of view: the first time we call operator==, or operator*() the
char is cached until the next operator++() or operator++(int).

The patch below only required changing _M_c to mutable, otherwise is
really straightforward and its effects are quite impressive. For
instance, for the replace_copy example of the other day:

current
=======
6.130u 0.000s 0:06.16 99.5%     0+0k 0+0io 205pf+0w

algo patched
============
5.020u 0.010s 0:05.06 99.4%     0+0k 0+0io 203pf+0w

iter patched (only)
===================
4.670u 0.000s 0:04.68 99.7%     0+0k 0+0io 202pf+0w

You see: without changing the algorithm (that, would cause orthogonal
benefits), we have an improvement exceeding 20%! Of course, the same
effect, even larger in some cases, can be seen everywhere, for instance
with money_get::do_get, that still uses rather complex parsing loops,
evaluating operator== and operator*() many times in between operator++()
calls.

So... The below passes regtesting and seems rather safe and clean to
me: anyone objects to it? Otherwise, I want to test it better and then
commit. Fiuuu...

Thanks for the (long) attention,
Paolo.

P.S. During testing, I stumbled in a couple of very long standing typos
in the testsuite: we were using in a test the iterator object of the
previous test! We couldn't notice because the istreambuf_iterator, not
caching, had "no memory" and was calling every time sgetc() anyway.

///////////////////
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: CL_stream_iter
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20041107/f18126eb/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: patch_stream_iter
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20041107/f18126eb/attachment-0001.ksh>