This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] To string::find
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Mon, 04 Sep 2006 23:30:22 +0200
- Subject: [Patch] To string::find
Hi,
the below is the complete patch I tested on x86 and x86_64. The
performance number I'm getting are consistently better than the current
ones and, after all, we are talking about the same algorithm of glibc'
memmem, and also the same of the old string::find + a "trivial" but
effective optimization, something trustworthy. For example, on a dual
core Athlon 64 2200+, for our string::find performance testcase:
Current
3.996u 0.000s 0:03.99 100.0% 0+0k 0+0io 0pf+0w
Patched
2.728u 0.000s 0:02.72 100.0% 0+0k 0+0io 0pf+0w
Tomorrow I'd like to go ahead...
Paolo.
///////////////
2006-09-05 Paolo Carlini <pcarlini@suse.de>
* include/bits/basic_string.tcc (find(const _CharT*, size_type,
size_type)): Reimplement in terms of traits::eq and traits::compare.
* include/ext/vstring.tcc (find(const _CharT*, size_type,
size_type)): Likewise.
* src/string-inst.cc: Remove unneded std::search instantiation.
Index: include/ext/vstring.tcc
===================================================================
--- include/ext/vstring.tcc (revision 116682)
+++ include/ext/vstring.tcc (working copy)
@@ -1,6 +1,6 @@
// Versatile string -*- C++ -*-
-// Copyright (C) 2005 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006 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
@@ -271,17 +271,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();
- if (__pos + __n <= __size)
- {
- const _CharT* __data = this->_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;
+ const _CharT* __data = this->_M_data();
+
+ if (__n == 0)
+ return __pos <= __size ? __pos : npos;
+
+ for (; __pos + __n <= __size; ++__pos)
+ if (traits_type::eq(__data[__pos], __s[0])
+ && traits_type::compare(__data + __pos + 1, __s + 1, __n - 1) == 0)
+ return __pos;
+ return npos;
}
template<typename _CharT, typename _Traits, typename _Alloc,
Index: include/bits/basic_string.tcc
===================================================================
--- include/bits/basic_string.tcc (revision 116682)
+++ include/bits/basic_string.tcc (working copy)
@@ -1,6 +1,6 @@
// Components for manipulating sequences of characters -*- C++ -*-
-// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
+// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
@@ -710,17 +710,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();
- 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;
+ const _CharT* __data = _M_data();
+
+ if (__n == 0)
+ return __pos <= __size ? __pos : npos;
+
+ for (; __pos + __n <= __size; ++__pos)
+ if (traits_type::eq(__data[__pos], __s[0])
+ && traits_type::compare(__data + __pos + 1, __s + 1, __n - 1) == 0)
+ return __pos;
+ return npos;
}
template<typename _CharT, typename _Traits, typename _Alloc>
Index: src/string-inst.cc
===================================================================
--- src/string-inst.cc (revision 116682)
+++ src/string-inst.cc (working copy)
@@ -1,6 +1,6 @@
// Components for manipulating sequences of characters -*- C++ -*-
-// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
+// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
@@ -77,10 +77,6 @@
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&));
_GLIBCXX_END_NAMESPACE
_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)