bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: speed up u8_strstr


From: Pádraig Brady
Subject: Re: speed up u8_strstr
Date: Fri, 21 Jan 2011 09:44:05 +0000
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.8) Gecko/20100227 Thunderbird/3.0.3

On 20/01/11 20:25, Eric Blake wrote:
> On 01/20/2011 01:16 PM, Pádraig Brady wrote:
>> On 31/07/10 20:48, Bruno Haible wrote:
>>> Hi Pádraig,
>>>
>>>>> the u8_strstr function.
>>>>
>>>> I wonder could we speed that up for UTF-8
>>>> by just deferring to strstr() ?
>>>
>>> This is a good idea, because the naïve implementation of u8_strstr is
>>> quadratic (O(n²)), whereas for strstr we now have an O(n) algorithm.
> 
> Alas, glibc strstr() reverted to quadratic on SSE4.2 machines;
> http://sourceware.org/bugzilla/show_bug.cgi?id=12100
> 
> and I still haven't gotten around to writing a patch that chooses an
> algorithm according to needle length, as well as benchmarking strstr()
> enough to provide Uli with convincing proof that it makes sense to use
> hueristics to choose negligible O(n^2) SSE4.2 speedups for short needles
> but O(n) for long needles.

Yes this is an issue if you compile on non SSE4.2 and run on SSE4.2
I can't think of anything gnulib can do here if the logic
changes underneath.

>> I'm thinking of adding an alarm(5) to the test
>> to enforce the performance check.
> 
> tests-strstr does this (on all but mingw, which lacks alarm()); but be
> sure you also signal(SIGALRM,SIG_DFL) to avoid inheriting an ignored
> signal handler.

Cool. I've amended with...

diff --git a/modules/unistr/u16-strstr-tests b/modules/unistr/u16-strstr-tests
index e180308..5c3cfbf 100644
--- a/modules/unistr/u16-strstr-tests
+++ b/modules/unistr/u16-strstr-tests
@@ -6,6 +6,7 @@ tests/macros.h
 Depends-on:

 configure.ac:
+AC_CHECK_DECLS_ONCE([alarm])

 Makefile.am:
 TESTS += test-u16-strstr
diff --git a/modules/unistr/u32-strstr-tests b/modules/unistr/u32-strstr-tests
index 2e7c26e..8ec3124 100644
--- a/modules/unistr/u32-strstr-tests
+++ b/modules/unistr/u32-strstr-tests
@@ -6,6 +6,7 @@ tests/macros.h
 Depends-on:

 configure.ac:
+AC_CHECK_DECLS_ONCE([alarm])

 Makefile.am:
 TESTS += test-u32-strstr
diff --git a/modules/unistr/u8-strstr-tests b/modules/unistr/u8-strstr-tests
index 51020db..fdc7b76 100644
--- a/modules/unistr/u8-strstr-tests
+++ b/modules/unistr/u8-strstr-tests
@@ -6,6 +6,7 @@ tests/macros.h
 Depends-on:

 configure.ac:
+AC_CHECK_DECLS_ONCE([alarm])

 Makefile.am:
 TESTS += test-u8-strstr
diff --git a/tests/unistr/test-u16-strstr.c b/tests/unistr/test-u16-strstr.c
index 312542d..4aa26b1 100644
--- a/tests/unistr/test-u16-strstr.c
+++ b/tests/unistr/test-u16-strstr.c
@@ -18,6 +18,9 @@

 #include <config.h>

+#include <signal.h> /* For signal.  */
+#include <unistd.h> /* For alarm.  */
+
 #include "unistr.h"

 #include "macros.h"
@@ -29,6 +32,13 @@
 int
 main (void)
 {
+#if HAVE_DECL_ALARM
+  /* Declare failure if test takes too long, by using default abort
+     caused by SIGALRM.  */
+  signal (SIGALRM, SIG_DFL);
+  alarm (5);
+#endif
+
   test_u_strstr ();

   return 0;
diff --git a/tests/unistr/test-u32-strstr.c b/tests/unistr/test-u32-strstr.c
index 6d85339..4cbbe41 100644
--- a/tests/unistr/test-u32-strstr.c
+++ b/tests/unistr/test-u32-strstr.c
@@ -1,4 +1,4 @@
-/* Test of u16_strstr() function.
+/* Test of u32_strstr() function.
    Copyright (C) 2011 Free Software Foundation, Inc.

    This program is free software: you can redistribute it and/or modify
@@ -18,6 +18,9 @@

 #include <config.h>

+#include <signal.h> /* For signal.  */
+#include <unistd.h> /* For alarm.  */
+
 #include "unistr.h"

 #include "macros.h"
@@ -29,6 +32,13 @@
 int
 main (void)
 {
+#if HAVE_DECL_ALARM
+  /* Declare failure if test takes too long, by using default abort
+     caused by SIGALRM.  */
+  signal (SIGALRM, SIG_DFL);
+  alarm (5);
+#endif
+
   test_u_strstr ();

   return 0;
diff --git a/tests/unistr/test-u8-strstr.c b/tests/unistr/test-u8-strstr.c
index a3cba36..ef2b582 100644
--- a/tests/unistr/test-u8-strstr.c
+++ b/tests/unistr/test-u8-strstr.c
@@ -18,6 +18,9 @@

 #include <config.h>

+#include <signal.h> /* For signal.  */
+#include <unistd.h> /* For alarm.  */
+
 #include "unistr.h"

 #include "macros.h"
@@ -29,6 +32,16 @@
 int
 main (void)
 {
+#if HAVE_DECL_ALARM
+  /* Declare failure if test takes too long, by using default abort
+     caused by SIGALRM.  Note since we defer to strstr() in this
+     case, we're assuming that we're running this test on the
+     same system that we did the check to ensure it has linear
+     performance characteristics.  */
+  signal (SIGALRM, SIG_DFL);
+  alarm (5);
+#endif
+
   test_u_strstr ();

   return 0;



reply via email to

[Prev in Thread] Current Thread [Next in Thread]