Date: Fri, 5 Oct 2001 15:43:16 +0100 (BST) From: Joshua Goodall <joshua@roughtrade.net> To: Farooq Mela <fmela0@sm.socccd.cc.ca.us> Cc: "Andrew L. Neporada" <andrew@nas.dgap.mipt.ru>, Bakul Shah <bakul@bitblocks.com>, <freebsd-hackers@freebsd.org> Subject: Re: current strstr(3) implementation is slow Message-ID: <Pine.LNX.4.33.0110051506300.31480-100000@elm.phenome.org> In-Reply-To: <3BBC8937.44A77CF9@sm.socccd.cc.ca.us>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, 4 Oct 2001, Farooq Mela wrote: > "Andrew L. Neporada" wrote: > > to Algorithms" book (AKA CLR) by MIT Press, more precisely "Knuth, Morris > > and Pratt algorithm". > > Hmm, sounds good, much better than naive string matching algorithm. Unless strstr gains an efficient (and elegant) way to remember preprocessed strings, most calls to strstr would probably end up spending more actual CPU preprocessing than any saving from fewer comparisons. A brief glimpse through the FreeBSD source shows few places that might possibly benefit from a KMP matcher, and many that I would expect to run slower than the naive in real cases. This correlates with my general experience with string matching in systems programming. There is no use of strstr in the kernel, by the looks. Code that intrinsically calls for a good algorithm generally includes its own (e.g. perl, grep, awk). Personally I find better results in such cases from fgetln with a Horspool than I do from fgrep. The folks that implement libc's are, I would hope, already aware of the many alternatives and have reached similar conclusions to my own. The possibility of extending libc to include alternative algorithms under new names, I leave to others to debate. Joshua To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.LNX.4.33.0110051506300.31480-100000>