Re: Question about critical_factorization() in the Two-Way algorithm

2010-12-20 Thread Eric Blake
On 12/18/2010 06:58 AM, Bruno Haible wrote: > Hello Pádraig, > >> I've rebased the attached memmem reorg patch >> which splits correctness checks from performance checks. > > How about a couple of stylistic changes: use GNU style whitespace placement, > 'const char *' not 'char *' for string lite

Re: Question about critical_factorization() in the Two-Way algorithm

2010-12-18 Thread Bruno Haible
Hello Pádraig, > I've rebased the attached memmem reorg patch > which splits correctness checks from performance checks. How about a couple of stylistic changes: use GNU style whitespace placement, 'const char *' not 'char *' for string literals, and NULL not 0 for the null pointer, preprocessor

Re: Question about critical_factorization() in the Two-Way algorithm

2010-12-15 Thread Eric Blake
On 12/15/2010 04:48 PM, Eric Blake wrote: > On 12/15/2010 03:23 PM, Pádraig Brady wrote: I spoke too soon. We would also need to patch m4/memmem.m4 to actually perform the empty needle verification in the memmem-simple case. >>> >>> I also noticed the empty needle verification didn't >>>

Re: Question about critical_factorization() in the Two-Way algorithm

2010-12-15 Thread Eric Blake
On 12/15/2010 03:23 PM, Pádraig Brady wrote: >>> I spoke too soon. We would also need to patch m4/memmem.m4 to actually >>> perform the empty needle verification in the memmem-simple case. >> >> I also noticed the empty needle verification didn't >> check that the correct pointer was returned, >>

Re: Question about critical_factorization() in the Two-Way algorithm

2010-12-15 Thread Pádraig Brady
On 23/06/10 01:39, Pádraig Brady wrote: > On 22/06/10 15:42, Eric Blake wrote: >> On 06/22/2010 08:41 AM, Eric Blake wrote: >>> On 06/22/2010 08:34 AM, Pádraig Brady wrote: Cool, that's what I expected from the names. So do we just need to move a docs around a little like: >>> >>> Ye

Re: Question about critical_factorization() in the Two-Way algorithm

2010-06-22 Thread Pádraig Brady
On 22/06/10 15:42, Eric Blake wrote: > On 06/22/2010 08:41 AM, Eric Blake wrote: >> On 06/22/2010 08:34 AM, Pádraig Brady wrote: >>> Cool, that's what I expected from the names. >>> So do we just need to move a docs around a little like: >>> >> >> Yes, that looks like an appropriate patch. Please

Re: Question about critical_factorization() in the Two-Way algorithm

2010-06-22 Thread Eric Blake
On 06/22/2010 08:34 AM, Pádraig Brady wrote: > Cool, that's what I expected from the names. > So do we just need to move a docs around a little like: > > diff --git a/doc/glibc-functions/memmem.texi b/doc/glibc-functions/memmem.texi > index c7e3d73..7d34817 100644 > --- a/doc/glibc-functions/memme

Re: Question about critical_factorization() in the Two-Way algorithm

2010-06-22 Thread Eric Blake
On 06/22/2010 08:41 AM, Eric Blake wrote: > On 06/22/2010 08:34 AM, Pádraig Brady wrote: >> Cool, that's what I expected from the names. >> So do we just need to move a docs around a little like: >> > > Yes, that looks like an appropriate patch. Please apply. I spoke too soon. We would also nee

Re: Question about critical_factorization() in the Two-Way algorithm

2010-06-22 Thread Pádraig Brady
On 22/06/10 15:09, Eric Blake wrote: > On 06/22/2010 03:18 AM, Pádraig Brady wrote: >> >> Note the docs for "memmem" say it fixes >> >> "This function returns incorrect values in some cases, such as when >>given an empty needle: glibc <= 2.0, Cygwin 1.5.x." >> >> Could that functionality be r

Re: Question about critical_factorization() in the Two-Way algorithm

2010-06-22 Thread Eric Blake
On 06/22/2010 03:18 AM, Pádraig Brady wrote: >> http://sourceware.org/bugzilla/show_bug.cgi?id=11607 > > Coincidentally, I was about to mail you about this :) > Thanks for pointing out that bug which I was unaware of. > > I'm currently working on multibyte enhancements to coreutils > and was usin

Re: Question about critical_factorization() in the Two-Way algorithm

2010-06-22 Thread Pádraig Brady
On 22/06/10 00:30, Eric Blake wrote: > Meanwhile, glibc bug 11607 already complains that the time spent on > factorization is extremely noticeable for short strings. I have not > benchmarked things myself (partly because I don't know how cache-line > effects would play into a benchmark), but do w

Re: Question about critical_factorization() in the Two-Way algorithm

2010-06-21 Thread Eric Blake
On 06/21/2010 05:30 PM, Eric Blake wrote: > starting with a comparison of x[0] and x[1]), we can instead start with > only reduced-length suffixes (that is, start with a comparison of x[1] > and x[2]), for one less comparison, and a slightly faster factorization > time. Followup - the number of co

Re: Question about critical_factorization() in the Two-Way algorithm

2010-06-21 Thread Eric Blake
[adding bug-gnulib] On 06/20/2010 10:00 PM, Carlos wrote: > Howdy -- I'm writing an article for Code Quarterly on pattern > matching, featuring the Two-Way algorithm, which you added > to libc and gnulib a couple of years back. > > There is one result of the critical factorization phase I haven't