git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: memmem.c improvement

From
TMTor Myklebust <tmyklebu@csclub.uwaterloo.ca>
Date
Dec 1, 2007, 03:07 UTC
Message-ID
<Pine.LNX.4.64.0711302151340.9426@caffeine.csclub.uwaterloo.ca>
In-Reply-To
<4750C74B.8060308@pipapo.org>
On Sat, 1 Dec 2007, Christian Thaeter wrote:
> I am fully aware that this is not the best possible search algorithm.
> It is considerably better than the actual one for 'common' data.

And not considerably worse in the worst case I could think of. (Which was my point, not that it was slow or sucked in some other way.)

> Having a string with few symbols or other corner cases needs an 
> algorithm better suited for that task.

Yes, if it's actually worth anyone's time making strstr() fast in the case where the haystack has length three and the needle length two.

Amusingly enough, I haven't ever seen strstr() used to do any nontrivial string matching in any free software I've bothered to grep.

> But well, this was just reaching a low hanging fruit.

Suitably hacked, your code looks clearly correct. But there are valid reasons not to mess with the strstr() in libc (fewer for memmem()); chief among them is that *if* there is an undetected bug in the code, *then* lots of stuff can break.

> For me it suffices and I won't put more efforts into improving or 
> lobbying it, its just not worth it.

Clearly, the tone of my email did not help convey my message. (Perhaps I should just stop trying to write words of encouragement altogether --- it never goes according to plan and always seems to end in disaster.) I do commend you for submitting improvements (and this is clearly an improvement); I was merely trying to point out that it will likely be an uphill battle, and that certain things are either wrong or can be done better than you have done. Do go on, please! (And I'm sorry if my previous email caused you particular dismay.)

Tor Myklebust
Previous: Christian Thaeter
Message 4 of 4 in “memmem.c improvement”
  1. Christian ThaeterDec 1, 2007
  2. Tor MyklebustDec 1, 2007
  3. Christian ThaeterDec 1, 2007
  4. Tor MyklebustDec 1, 2007

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.