This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] Use std::search in string::find
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Fri, 11 Jun 2004 22:16:56 +0200
- Subject: [Patch] Use std::search in string::find
Hi,
the below is what I have implemented and tested on x86 and x86-64.
Interestingly for the new performance testcase the stripped code
size does *not* change. In mainline the total time changes as
follows on P4-2400 (always -O2):
current mainline x86
--------------------
22.370u 0.000s 0:22.46 99.5% 0+0k 0+0io 166pf+0w
patched mainline x86
--------------------
9.090u 0.000s 0:09.13 99.5% 0+0k 0+0io 168pf+0w
And as follows on x86-64-2GHz:
current mainline x86-64
-----------------------
5.216u 0.000s 0:05.21 100.0% 0+0k 0+0io 0pf+0w
patched mainline x86-64
-----------------------
4.743u 0.000s 0:04.74 100.0% 0+0k 0+0io 0pf+0w
In general, in these days often happens that on x86 current 3.4
gives better results than mainline. Indeed, this happens here
too for unpatched 3.4:
current 3.4 x86
---------------
14.920u 0.010s 0:15.03 99.3% 0+0k 0+0io 162pf+0w
patched 3.4 x86
---------------
9.450u 0.010s 0:09.51 99.4% 0+0k 0+0io 164pf+0w
All in all, the numbers speak in favor of this approach, and,
in case we really want to change the algorithm, we can just
improve the one provided generically in std::search.
I'll wait 'til tomorrow in case of comments.
Paolo.
/////////////////
2004-06-11 Paolo Carlini <pcarlini@suse.de>
* include/bits/basic_string.tcc (find(const _CharT*, size_type,
size_type)): Reimplement using std::search.
* src/string-inst.cc: Instantiate std::search for char/wchar_t.
2004-06-11 Dhruv Matani <dhruvbird@gmx.net>
* testsuite/performance/21_strings/string_find.cc: New.
diff -urN libstdc++-v3-orig/include/bits/basic_string.tcc libstdc++-v3/include/bits/basic_string.tcc
--- libstdc++-v3-orig/include/bits/basic_string.tcc 2004-04-25 17:45:13.000000000 +0200
+++ libstdc++-v3/include/bits/basic_string.tcc 2004-06-11 16:39:13.000000000 +0200
@@ -685,12 +685,17 @@
find(const _CharT* __s, size_type __pos, size_type __n) const
{
__glibcxx_requires_string_len(__s, __n);
+ size_type __ret = npos;
const size_type __size = this->size();
- const _CharT* __data = _M_data();
- for (; __pos + __n <= __size; ++__pos)
- if (traits_type::compare(__data + __pos, __s, __n) == 0)
- return __pos;
- return npos;
+ if (__pos + __n <= __size)
+ {
+ const _CharT* __data = _M_data();
+ const _CharT* __p = std::search(__data + __pos, __data + __size,
+ __s, __s + __n, traits_type::eq);
+ if (__p != __data + __size || __n == 0)
+ __ret = __p - __data;
+ }
+ return __ret;
}
template<typename _CharT, typename _Traits, typename _Alloc>
@@ -698,8 +703,8 @@
basic_string<_CharT, _Traits, _Alloc>::
find(_CharT __c, size_type __pos) const
{
- const size_type __size = this->size();
size_type __ret = npos;
+ const size_type __size = this->size();
if (__pos < __size)
{
const _CharT* __data = _M_data();
diff -urN libstdc++-v3-orig/src/string-inst.cc libstdc++-v3/src/string-inst.cc
--- libstdc++-v3-orig/src/string-inst.cc 2004-01-24 12:34:06.000000000 +0100
+++ libstdc++-v3/src/string-inst.cc 2004-06-11 19:07:25.000000000 +0200
@@ -76,6 +76,11 @@
C*
S::_S_construct(const C*, const C*, const allocator<C>&,
forward_iterator_tag);
+
+ // Used in str::find.
+ template
+ const C*
+ search(const C*, const C*, const C*, const C*, bool(*)(const C&, const C&));
} // namespace std
namespace __gnu_cxx
diff -urN libstdc++-v3-orig/testsuite/performance/21_strings/string_find.cc libstdc++-v3/testsuite/performance/21_strings/string_find.cc
--- libstdc++-v3-orig/testsuite/performance/21_strings/string_find.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/performance/21_strings/string_find.cc 2004-06-11 19:25:06.000000000 +0200
@@ -0,0 +1,105 @@
+ // Copyright (C) 2004 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction. Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License. This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <string>
+#include <testsuite_performance.h>
+
+void
+test_pair(const std::string& s, const std::string& f, int n)
+{
+ std::string::size_type sz = 0;
+
+ for (int i = 0; i < n; ++i)
+ sz = s.find(f);
+}
+
+int main()
+{
+ using namespace std;
+ using namespace __gnu_test;
+
+ time_counter time;
+ resource_counter resource;
+
+ const unsigned int iterations = 2000000;
+
+ string s, f;
+ s = "aabbaabbaaxd adbffdadgaxaabbbddhatyaaaabbbaabbaabbcsy";
+ f = "aabbaabbc";
+ start_counters(time, resource);
+ test_pair(s, f, iterations);
+ stop_counters(time, resource);
+ report_performance(__FILE__, "1", time, resource);
+ clear_counters(time, resource);
+
+ f = "aabbb";
+ start_counters(time, resource);
+ test_pair(s, f, iterations);
+ stop_counters(time, resource);
+ report_performance(__FILE__, "2", time, resource);
+ clear_counters(time, resource);
+
+ f = "xd";
+ start_counters(time, resource);
+ test_pair(s, f, iterations);
+ stop_counters(time, resource);
+ report_performance(__FILE__, "3", time, resource);
+ clear_counters(time, resource);
+
+ s = "dhruv is a very very good boy ;-)";
+ f = "very";
+ start_counters(time, resource);
+ test_pair(s, f, iterations);
+ stop_counters(time, resource);
+ report_performance(__FILE__, "4", time, resource);
+ clear_counters(time, resource);
+
+ f = "bad";
+ start_counters(time, resource);
+ test_pair(s, f, iterations);
+ stop_counters(time, resource);
+ report_performance(__FILE__, "5", time, resource);
+ clear_counters(time, resource);
+
+ f = "extra irritating";
+ start_counters(time, resource);
+ test_pair(s, f, iterations);
+ stop_counters(time, resource);
+ report_performance(__FILE__, "6", time, resource);
+ clear_counters(time, resource);
+
+ s = "this is a very this is a very this is a verty this is a very "
+ "this is a very long sentence";
+ f = "this is a very long sentence";
+ start_counters(time, resource);
+ test_pair(s, f, iterations);
+ stop_counters(time, resource);
+ report_performance(__FILE__, "7", time, resource);
+ clear_counters(time, resource);
+
+ return 0;
+}