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;