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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Thu, 2010-10-28 at 14:00 -0700, Dave Stevens wrote:
> Quoting Marko Vojinovic <vvmarko@xxxxxxxxx>:
> 
> > 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

-- 
users mailing list
users@xxxxxxxxxxxxxxxxxxxxxxx
To unsubscribe or change subscription options:
https://admin.fedoraproject.org/mailman/listinfo/users
Guidelines: http://fedoraproject.org/wiki/Mailing_list_guidelines

[Index of Archives]     [Older Fedora Users]     [Fedora Announce]     [Fedora Package Announce]     [EPEL Announce]     [EPEL Devel]     [Fedora Magazine]     [Fedora Summer Coding]     [Fedora Laptop]     [Fedora Cloud]     [Fedora Advisory Board]     [Fedora Education]     [Fedora Security]     [Fedora Scitech]     [Fedora Robotics]     [Fedora Infrastructure]     [Fedora Websites]     [Anaconda Devel]     [Fedora Devel Java]     [Fedora Desktop]     [Fedora Fonts]     [Fedora Marketing]     [Fedora Management Tools]     [Fedora Mentors]     [Fedora Package Review]     [Fedora R Devel]     [Fedora PHP Devel]     [Kickstart]     [Fedora Music]     [Fedora Packaging]     [Fedora SELinux]     [Fedora Legal]     [Fedora Kernel]     [Fedora OCaml]     [Coolkey]     [Virtualization Tools]     [ET Management Tools]     [Yum Users]     [Yosemite News]     [Gnome Users]     [KDE Users]     [Fedora Art]     [Fedora Docs]     [Fedora Sparc]     [Libvirt Users]     [Fedora ARM]

  Powered by Linux