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 ebl...@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
