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

[Paolo Carlini <pcarlini at suse dot de>]

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.

///////////////////
2004-11-xx  Paolo Carlini  <pcarlini@suse.de>

	* include/bits/streambuf_iterator.h: Consistently use _M_c to
	cache the current char, i.e., not only when operator++(int) is
	involved; change _M_c to mutable.
	(operator++(), operator++(int)): Always invalidate _M_c, i.e.
	reset it to eof.
	(_M_get()): Save the return value of _M_sbuf->sgetc() into
	_M_c.

	* testsuite/22_locale/time_get/get_monthname/char/1.cc: Fix
	(long standing) typo.
	* testsuite/22_locale/time_get/get_monthname/wchar_t/1.cc: Likewise.
	* testsuite/22_locale/time_get/get_weekday/char/1.cc: Likewise.
	* testsuite/22_locale/time_get/get_weekday/wchar_t/1.cc: Likewise.

diff -prN libstdc++-v3-1/include/bits/streambuf_iterator.h libstdc++-v3/include/bits/streambuf_iterator.h
*** libstdc++-v3-1/include/bits/streambuf_iterator.h	Sun Feb  8 05:46:42 2004
--- libstdc++-v3/include/bits/streambuf_iterator.h	Sun Nov  7 18:16:29 2004
*************** namespace std
*** 72,78 ****
        // NB: This implementation assumes the "end of stream" value
        // is EOF, or -1.
        mutable streambuf_type*	_M_sbuf;
!       int_type			_M_c;
  
      public:
        ///  Construct end of input stream iterator.
--- 72,78 ----
        // NB: This implementation assumes the "end of stream" value
        // is EOF, or -1.
        mutable streambuf_type*	_M_sbuf;
!       mutable int_type		_M_c;
  
      public:
        ///  Construct end of input stream iterator.
*************** namespace std
*** 113,120 ****
  	const int_type __eof = traits_type::eof();
  	if (_M_sbuf && traits_type::eq_int_type(_M_sbuf->sbumpc(), __eof))
  	  _M_sbuf = 0;
! 	else
! 	  _M_c = __eof;
  	return *this;
        }
  
--- 113,119 ----
  	const int_type __eof = traits_type::eof();
  	if (_M_sbuf && traits_type::eq_int_type(_M_sbuf->sbumpc(), __eof))
  	  _M_sbuf = 0;
! 	_M_c = __eof;
  	return *this;
        }
  
*************** namespace std
*** 132,139 ****
  	    && traits_type::eq_int_type((__old._M_c = _M_sbuf->sbumpc()),
  					__eof))
  	  _M_sbuf = 0;
! 	else
! 	  _M_c = __eof;
  	return __old;
        }
  
--- 131,137 ----
  	    && traits_type::eq_int_type((__old._M_c = _M_sbuf->sbumpc()),
  					__eof))
  	  _M_sbuf = 0;
! 	_M_c = __eof;
  	return __old;
        }
  
*************** namespace std
*** 154,169 ****
        _M_get() const
        {
  	const int_type __eof = traits_type::eof();
- 	int_type __ret = __eof;
  	if (_M_sbuf)
  	  {
! 	    if (!traits_type::eq_int_type(_M_c, __eof))
! 	      __ret = _M_c;
! 	    else if (traits_type::eq_int_type((__ret = _M_sbuf->sgetc()),
! 					      __eof))
  	      _M_sbuf = 0;
  	  }
! 	return __ret;
        }
  
        bool
--- 152,167 ----
        _M_get() const
        {
  	const int_type __eof = traits_type::eof();
  	if (_M_sbuf)
  	  {
! 	    if (!traits_type::eq_int_type(_M_c, __eof)
! 		|| !traits_type::eq_int_type((_M_c = _M_sbuf->sgetc()),
! 					     __eof))
! 	      return _M_c;
! 	    else
  	      _M_sbuf = 0;
  	  }
! 	return __eof;
        }
  
        bool
diff -prN libstdc++-v3-1/testsuite/22_locale/time_get/get_monthname/char/1.cc libstdc++-v3/testsuite/22_locale/time_get/get_monthname/char/1.cc
*** libstdc++-v3-1/testsuite/22_locale/time_get/get_monthname/char/1.cc	Thu Apr  8 01:13:39 2004
--- libstdc++-v3/testsuite/22_locale/time_get/get_monthname/char/1.cc	Sun Nov  7 18:05:03 2004
*************** void test01()
*** 102,108 ****
    tim_get.get_monthname(is_it06, end, iss, errorstate, &time06);
    VERIFY( time06.tm_mon == 4 );
    VERIFY( errorstate == ios_base::failbit );
!   VERIFY( *is_it05 == 'l');
  }
  
  int main()
--- 102,108 ----
    tim_get.get_monthname(is_it06, end, iss, errorstate, &time06);
    VERIFY( time06.tm_mon == 4 );
    VERIFY( errorstate == ios_base::failbit );
!   VERIFY( *is_it06 == 'l');
  }
  
  int main()
diff -prN libstdc++-v3-1/testsuite/22_locale/time_get/get_monthname/wchar_t/1.cc libstdc++-v3/testsuite/22_locale/time_get/get_monthname/wchar_t/1.cc
*** libstdc++-v3-1/testsuite/22_locale/time_get/get_monthname/wchar_t/1.cc	Thu Apr  8 01:13:41 2004
--- libstdc++-v3/testsuite/22_locale/time_get/get_monthname/wchar_t/1.cc	Sun Nov  7 18:05:20 2004
*************** void test01()
*** 102,108 ****
    tim_get.get_monthname(is_it06, end, iss, errorstate, &time06);
    VERIFY( time06.tm_mon == 4 );
    VERIFY( errorstate == ios_base::failbit );
!   VERIFY( *is_it05 == L'l' );
  }
  
  int main()
--- 102,108 ----
    tim_get.get_monthname(is_it06, end, iss, errorstate, &time06);
    VERIFY( time06.tm_mon == 4 );
    VERIFY( errorstate == ios_base::failbit );
!   VERIFY( *is_it06 == L'l' );
  }
  
  int main()
diff -prN libstdc++-v3-1/testsuite/22_locale/time_get/get_weekday/char/1.cc libstdc++-v3/testsuite/22_locale/time_get/get_weekday/char/1.cc
*** libstdc++-v3-1/testsuite/22_locale/time_get/get_weekday/char/1.cc	Thu Apr  8 01:13:48 2004
--- libstdc++-v3/testsuite/22_locale/time_get/get_weekday/char/1.cc	Sun Nov  7 18:06:06 2004
*************** void test01()
*** 106,112 ****
    tim_get.get_weekday(is_it06, end, iss, errorstate, &time06);
    VERIFY( time06.tm_wday == 4 );
    VERIFY( errorstate == ios_base::failbit );
!   VERIFY( *is_it05 == 'u');
  }
  
  int main()
--- 106,112 ----
    tim_get.get_weekday(is_it06, end, iss, errorstate, &time06);
    VERIFY( time06.tm_wday == 4 );
    VERIFY( errorstate == ios_base::failbit );
!   VERIFY( *is_it06 == 'u');
  }
  
  int main()
diff -prN libstdc++-v3-1/testsuite/22_locale/time_get/get_weekday/wchar_t/1.cc libstdc++-v3/testsuite/22_locale/time_get/get_weekday/wchar_t/1.cc
*** libstdc++-v3-1/testsuite/22_locale/time_get/get_weekday/wchar_t/1.cc	Thu Apr  8 01:13:51 2004
--- libstdc++-v3/testsuite/22_locale/time_get/get_weekday/wchar_t/1.cc	Sun Nov  7 18:06:17 2004
*************** void test01()
*** 106,112 ****
    tim_get.get_weekday(is_it06, end, iss, errorstate, &time06);
    VERIFY( time06.tm_wday == 4 );
    VERIFY( errorstate == ios_base::failbit );
!   VERIFY( *is_it05 == L'u' );
  }
  
  int main()
--- 106,112 ----
    tim_get.get_weekday(is_it06, end, iss, errorstate, &time06);
    VERIFY( time06.tm_wday == 4 );
    VERIFY( errorstate == ios_base::failbit );
!   VERIFY( *is_it06 == L'u' );
  }
  
  int main()