public inbox for glibc-bugs@sourceware.org
help / color / mirror / Atom feed
From: "ebb9 at byu dot net" <sourceware-bugzilla@sourceware.org>
To: glibc-bugs@sources.redhat.com
Subject: [Bug libc/5514] memmem is O(n^2), but should be O(n)
Date: Tue, 08 Jan 2008 21:51:00 -0000	[thread overview]
Message-ID: <20080108215035.27954.qmail@sourceware.org> (raw)
In-Reply-To: <20071220133012.5514.ebb9@byu.net>


------- Additional Comments From ebb9 at byu dot net  2008-01-08 21:50 -------
Gnulib now has a reentrant linear-time constant-space solution for memmem, which
has the added benefit of sublinear speed for large enough needles:
http://git.sv.gnu.org/gitweb/?p=gnulib.git;a=blob;f=lib/memmem.c;h=622a034;hb=9d8d6cd

It also has a testsuite that exposes a couple of cases where the current glibc
takes orders of magnitude longer than the gnulib implementation to come up with
the same answer:
http://git.sv.gnu.org/gitweb/?p=gnulib.git;a=blob;f=tests/test-memmem.c

I'm still working on factoring the code to reuse the bulk of the algorithm in
strstr, strcasestr, strncasestr, and wcsstr (although sublinear speed there is
not an option, since the search for the NUL ending the haystack is an
unavoidable linear task), before posting the same code back here as a diff
against the glibc code base.


-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=5514

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.


  parent reply	other threads:[~2008-01-08 21:51 UTC|newest]

Thread overview: 22+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-12-20 13:30 [Bug libc/5514] New: " ebb9 at byu dot net
2007-12-20 19:53 ` [Bug libc/5514] " roland at gnu dot org
2007-12-21 13:38 ` bruno at clisp dot org
2007-12-21 13:50 ` bruno at clisp dot org
2007-12-21 14:00 ` jakub at redhat dot com
2007-12-26 16:18 ` bruno at clisp dot org
2007-12-26 16:19 ` bruno at clisp dot org
2007-12-26 16:20 ` bruno at clisp dot org
2008-01-04 23:05 ` ebb9 at byu dot net
2008-01-05  0:10 ` ebb9 at byu dot net
2008-01-08 21:51 ` ebb9 at byu dot net [this message]
2008-03-29 16:44 ` ebb9 at byu dot net
2008-03-29 16:45 ` ebb9 at byu dot net
2008-04-07 18:28 ` drepper at redhat dot com
2008-04-21 12:07 ` ebb9 at byu dot net
2008-05-15  4:43 ` drepper at redhat dot com
     [not found] <bug-5514-131@http.sourceware.org/bugzilla/>
2010-10-05 17:06 ` ppluzhnikov at google dot com
2010-10-05 17:12 ` eblake at redhat dot com
2010-10-05 17:14 ` ppluzhnikov at google dot com
2010-10-06 15:52 ` eblake at redhat dot com
2014-02-16 19:43 ` jackie.rosen at hushmail dot com
2014-05-28 19:45 ` schwab at sourceware dot org

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20080108215035.27954.qmail@sourceware.org \
    --to=sourceware-bugzilla@sourceware.org \
    --cc=glibc-bugs@sources.redhat.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).