[Top][All Lists]
[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;