Re: speed up u8_strstr

[Eric Blake]

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.

> 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.

-- 
Eric Blake   address@hidden    +1-801-349-2682
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature