[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: speed up u8_strstr
From: |
Eric Blake |
Subject: |
Re: speed up u8_strstr |
Date: |
Thu, 20 Jan 2011 13:25:21 -0700 |
User-agent: |
Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.13) Gecko/20101209 Fedora/3.1.7-0.35.b3pre.fc14 Lightning/1.0b3pre Mnenhy/0.8.3 Thunderbird/3.1.7 |
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