[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: memmem issues
From: |
Eric Blake |
Subject: |
Re: memmem issues |
Date: |
Thu, 20 Dec 2007 06:36:21 -0700 |
User-agent: |
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.9) Gecko/20071031 Thunderbird/2.0.0.9 Mnenhy/0.7.5.666 |
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
According to Jim Meyering on 12/20/2007 12:33 AM:
> Eric Blake <address@hidden> wrote:
> ...
>> - The implementation was naively quadratic in the worst-case complexity. I
>> lifted Bruno's KMP ideas in mbsstr to make it linear+delayed allocation.
>> glibc
>> still uses the naive implementation - should we file a bug with them to fix
>> it?
>
> This is the part I was replying to when I said
> it's worth a try.
http://sourceware.org/bugzilla/show_bug.cgi?id=5514
I've committed my initial patch. I'm not sure how to best go about
writing a test that determines if memmem is worst-case quadratic (perhaps
write a runtime test that compares time for running the algorithm on 100,
1000, then 10000 bytes, and assume quadratic when cross-compiling), so we
can tackle that later.
- --
Don't work too hard, make some time for fun as well!
Eric Blake address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHam/V84KuGfSFAYARAtB2AJ4lN0eL7BO+g7B2Hal5rwthVMCxcACcDILB
ajVo1OS8ZCgEYPQ8AdfTa/A=
=qNje
-----END PGP SIGNATURE-----
- memmem issues, Eric Blake, 2007/12/19
- Re: memmem issues, Jim Meyering, 2007/12/20
- Re: memmem issues, Jim Meyering, 2007/12/20
- Re: memmem issues,
Eric Blake <=
- Re: memmem issues, Simon Josefsson, 2007/12/20
- Re: memmem issues, Paul Eggert, 2007/12/21
- Re: memmem issues, Paul Eggert, 2007/12/29
- Re: memmem issues, Bruno Haible, 2007/12/31