This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[RFA] Algorithms vs operator* and operator==
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Thu, 04 Nov 2004 14:17:55 +0100
- Subject: [RFA] Algorithms vs operator* and operator==
Hi,
seems to me the natural development of the improvements to locale_facets
and stl_numeric but want to make sure I'm not missing something before
actually starting on it.
The fundamental observation is rather trivial: for a generic input_iterator
both operator* and operator== can be expensive and we should do our best
to minimize the number of calls throughout in the library.
This morning I changed tentatively std::replace_copy (see attached) and
benchmarked this type of test on my home machine:
typedef istreambuf_iterator<char> iterator_type;
istringstream iss("precipitevolissimevolmente");
iterator_type beg(iss);
iterator_type end;
char buffer[26];
for (unsigned i = 0; i < 10000000; ++i)
{
replace_copy(beg, end, buffer, 'i', 'z');
iss.seekg(0);
}
These are the numbers:
patched
=======
5.020u 0.010s 0:05.06 99.4% 0+0k 0+0io 203pf+0w
current
=======
6.130u 0.000s 0:06.16 99.5% 0+0k 0+0io 205pf+0w
Of course, I have also verified that there are no bad consequences when
beg and end are actually just random_access_iterators (the compiler
should be able to easily const propagate __value)
Can you spot anything wrong with this kind of change? If we agree that
it's good, there are quite a few places to tweak, both in stl_algo and
in stl_algobase (besides locale_facets ;)
Paolo.
/////////////
diff -urN libstdc++-v3-orig/include/bits/stl_algo.h libstdc++-v3/include/bits/stl_algo.h
--- libstdc++-v3-orig/include/bits/stl_algo.h 2004-10-29 23:44:55.000000000 +0200
+++ libstdc++-v3/include/bits/stl_algo.h 2004-11-04 13:17:38.000000000 +0100
@@ -909,6 +909,8 @@
_OutputIterator __result,
const _Tp& __old_value, const _Tp& __new_value)
{
+ typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
+
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
@@ -917,8 +919,11 @@
typename iterator_traits<_InputIterator>::value_type, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
- for ( ; __first != __last; ++__first, ++__result)
- *__result = *__first == __old_value ? __new_value : *__first;
+ for (; __first != __last; ++__first, ++__result)
+ {
+ const _ValueType __value = *__first;
+ *__result = __value == __old_value ? __new_value : __value;
+ }
return __result;
}