This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] improve string find algorithm


On 07/12/16 11:46 -0600, Aditya Kumar wrote:
Here is an improved version of basic_string::find. The idea is to
split the string find in two parts:
1. search for the first match by using traits_type::find (this gets converted to memchr for x86)
2. see if there is a match (this gets converted to memcmp for x86)

Passes bootstrap on x86-64.

The patch results in good improvements on a synthetic test case I wrote using the google-benchmark.
following are the results.


Branch: master without patch
$ ./bin/string.libcxx.out
Run on (24 X 1899.12 MHz CPU s)
2016-12-06 16:41:55
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
Benchmark                           Time           CPU Iterations
-----------------------------------------------------------------
BM_StringFindNoMatch/10             8 ns          8 ns   81880927
BM_StringFindNoMatch/64            52 ns         52 ns   13235018
BM_StringFindNoMatch/512          355 ns        355 ns    1962488
BM_StringFindNoMatch/4k          2769 ns       2772 ns     249090
BM_StringFindNoMatch/32k        22598 ns      22619 ns      30984
BM_StringFindNoMatch/128k       89745 ns      89830 ns       7996
BM_StringFindAllMatch/1             7 ns          7 ns  102893835
BM_StringFindAllMatch/8             9 ns          9 ns   75403364
BM_StringFindAllMatch/64           12 ns         12 ns   60766893
BM_StringFindAllMatch/512          31 ns         31 ns   23163999
BM_StringFindAllMatch/4k          141 ns        141 ns    4980386
BM_StringFindAllMatch/32k        1402 ns       1403 ns     483581
BM_StringFindAllMatch/128k       5604 ns       5609 ns     126123
BM_StringFindMatch1/1           44430 ns      44473 ns      15804
BM_StringFindMatch1/8           44315 ns      44357 ns      15741
BM_StringFindMatch1/64          44689 ns      44731 ns      15712
BM_StringFindMatch1/512         44247 ns      44290 ns      15724
BM_StringFindMatch1/4k          45010 ns      45053 ns      15678
BM_StringFindMatch1/32k         45717 ns      45761 ns      15278
BM_StringFindMatch2/1           44307 ns      44349 ns      15730
BM_StringFindMatch2/8           44631 ns      44674 ns      15721
BM_StringFindMatch2/64          44300 ns      44342 ns      15750
BM_StringFindMatch2/512         44239 ns      44281 ns      15713
BM_StringFindMatch2/4k          44886 ns      44928 ns      15787

Branch: master with patch
$ ./bin/string.libcxx.out
Run on (24 X 2892.28 MHz CPU s)
2016-12-06 18:51:38
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
Benchmark                           Time           CPU Iterations
-----------------------------------------------------------------
BM_StringFindNoMatch/10            11 ns         11 ns   63049677
BM_StringFindNoMatch/64            12 ns         12 ns   57259381
BM_StringFindNoMatch/512           27 ns         27 ns   25495432
BM_StringFindNoMatch/4k           130 ns        130 ns    5301301
BM_StringFindNoMatch/32k          858 ns        859 ns     824048
BM_StringFindNoMatch/128k        4091 ns       4095 ns     171493
BM_StringFindAllMatch/1            14 ns         14 ns   53023977
BM_StringFindAllMatch/8            14 ns         14 ns   51516536
BM_StringFindAllMatch/64           17 ns         17 ns   40992668
BM_StringFindAllMatch/512          37 ns         37 ns   18503267
BM_StringFindAllMatch/4k          153 ns        153 ns    4494458
BM_StringFindAllMatch/32k        1460 ns       1461 ns     483380
BM_StringFindAllMatch/128k       5801 ns       5806 ns     120680
BM_StringFindMatch1/1            2062 ns       2064 ns     333144
BM_StringFindMatch1/8            2057 ns       2059 ns     335496
BM_StringFindMatch1/64           2083 ns       2085 ns     341469
BM_StringFindMatch1/512          2134 ns       2136 ns     336880
BM_StringFindMatch1/4k           2309 ns       2312 ns     308745
BM_StringFindMatch1/32k          3413 ns       3417 ns     208206
BM_StringFindMatch2/1            2053 ns       2055 ns     341523
BM_StringFindMatch2/8            2061 ns       2063 ns     343999
BM_StringFindMatch2/64           2075 ns       2077 ns     338479
BM_StringFindMatch2/512          2102 ns       2104 ns     332276
BM_StringFindMatch2/4k           2286 ns       2288 ns     300416
BM_StringFindMatch2/32k          3385 ns       3388 ns     204158


ChangeLog:

2016-12-07  Aditya Kumar <hiraditya@msn.com>
      * include/bits/basic_string.tcc(find(const _CharT* __s, size_type
      __pos, size_type __n) const)): Improve the algorithm


---
libstdc++-v3/include/bits/basic_string.tcc | 31 ++++++++++++++++++++++--------
1 file changed, 23 insertions(+), 8 deletions(-)

diff --git a/libstdc++-v3/include/bits/basic_string.tcc b/libstdc++-v3/include/bits/basic_string.tcc
index df1e8dd..7942ee6 100644
--- a/libstdc++-v3/include/bits/basic_string.tcc
+++ b/libstdc++-v3/include/bits/basic_string.tcc
@@ -1194,14 +1194,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
      if (__n == 0)
	return __pos <= __size ? __pos : npos;

-      if (__n <= __size)
-	{
-	  for (; __pos <= __size - __n; ++__pos)
-	    if (traits_type::eq(__data[__pos], __s[0])
-		&& traits_type::compare(__data + __pos + 1,
-					__s + 1, __n - 1) == 0)
-	      return __pos;
-	}
+      if (__n > __size)
+	return npos;
+
+      const _CharT __elem0 = __s[0];
+      const _CharT* __first1 = __data;
+      const _CharT* __first2 = __s;
+      const _CharT* __last1 = __data + __size;
+      ptrdiff_t __len2 = __n -  __pos;
+
+      while (true) {
+        ptrdiff_t __len1 = __last1 - __first1;
+	if (__len1 < __len2)
+	  return npos;
+
+	// Find the first match.
+	__first1 = traits_type::find(__first1, __len1 - __len2 + 1, __elem0);
+	if (__first1 == 0)
+	  return npos;
+	// Compare the full string when first match is found.
+        if (traits_type::compare(__first1, __first2, __len2) == 0)
+	  return __first1 - __data;

Don't you need to increment __first1 here? Otherwise we go into an
infinite loop when the first character is found but the rest of the
string doesn't match.

i.e. this never terminates:

#include <string>
int main() {
 std::string("aa").find("ab");
}

I'm surprised we don't have any tests for this case, but apparently we
don't, as your patch passes all our tests.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]