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]

 



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

Dave

>
> --
> 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
>



-- 
"It is no measure of health to be well adjusted to a profoundly sick society."
   Krishnamurti

-- 
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