While waiting for Fedora 14, a question for the engineering types re: searching and finding

[Patrick O'Callaghan]

On Thu, 2010-10-28 at 14:00 -0700, Dave Stevens wrote:
> Quoting Marko Vojinovic <vvmarko at gmail.com>:
> 
> > On Thursday, October 28, 2010 21:36:58 you wrote:
> >> On Thursday, October 28, 2010 19:27:16 William Case wrote:
> >> > How does the cpu search and find stuff?
> >> >
> >> > There is a huge amount of searching and finding of text in
> >> > memory, conditional statements requiring comparisons, and the use of
> >> > entry points but not exact addresses from within both kernel space and
> >> > user space.  It has occurred to me that a there is necessarily a lot of
> >> > physical or bit comparing going on.  Too much, I would think, to keep
> >> > dumping a search criteria into a cpu register and then replacing the
> >> > contents of a second register from a block of memory until one matches.
> >>
> >> Believe it or not, in a nutshell that's exactly what is happening.
> >
> > By the way, the sheer inefficiency of that searching algorithm (ie.  
> > what you are
> > complaining about) is _precisely_ one of the reasons why quantum  
> > computers are
> > so interesting (the other reason is the number factorization into  
> > primes). But
> > that's going a bit off-topic, I guess... ;-)
> >
> > Best, :-)
> > Marko
> 
> surely the kernel folks know about boyer-moore and other much better  
> algorithms
> 
> http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

There aren't that many places where string searching is done in the
kernel. In fact the only use for it that occurs to me is in directory
lookups, and given that most filenames (rather than pathnames) are not
very long it's open to doubt whether BM and pals would be very useful,
but I'm open to correction from anyone who actually knows :-)

poc