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]

 



Thank you Marko and Patrick:

On Thu, 2010-10-28 at 21:36 +0100, Marko Vojinovic 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. When a 
> processor needs to "search" for something in memory, it typically does a 
> conditional loop --- load the number from memory into the register (the MOV 
> assembly instruction), compare it to the wanted value in the second register 
> (CMP), if they are the same break the loop (LOOPNE), otherwise load the next 
> number and repeat.
> 
> Why do you think there is "too much" of that comparison going on?
> 

I didn't think there was too much from my point of view.  I thought
there might be too much from an engineer's perspective.  As I have dug
into the inner workings of computers over the last few years, I have
become enthralled with the ingenuity, if not down right genius, of how
computers have been designed and improved over the years -- starting
with basic circuits and instruction sets.  I thought I might have missed
something -- missed an aha! moment.  In my mind. there was a good chance
that some engineer somewhere had seen the repetition involved in a
search and comparison and developed something quite cunning to shorten
the process.  As I said, I always look for the eureka's.

> > Is there a special unit within the cpu or memory were rapid comparison,
> > or partial comparisons are made during a search, before a criteria is
> > noted as found and moved into the cpu registers?  In a generalized way,
> > at the hardware level, how are searched for criteria found?
> 
> There is no special unit, AFAIK. You load the two numbers (to be compared) 
> into the processor registers, and do a CMP instruction. The processor 
> basically subtracts the two numbers, and modifies the flag register according to 
> whether the result is positive, negative or zero. The next instruction (say, 
> LOOPNE) inspects the flag register and decides what will be the following 
> instruction, based on the contents of the flags. This "deciding" amounts to 
> changing the value of the IP (instruction pointer) register to one or the 
> other predefined value.
> 
> You might want to learn a bit of assembly language, if you wish to understand 
> basic low-level operations of the processor. And if you want to understand the 
> concepts of how processors actually work and what is a computer program in 
> principle, you can start from here
> 
> http://en.wikipedia.org/wiki/Turing_machine

I have looked at a Turing Machine and assembly language.  Enough to have
a comfortable overview without developing a strong desire or need to dig
deeper.  Even spent a couple of afternoons with IA-32 just to take away
the mystery.
> 
> but don't curse me later for pointing you to that page. You asked for it! ;-)
>  
> > I have googled for an answer and found nothing helpful.  That usually
> > means I have somehow mis-posed the question, am working from wrong
> > assumptions or lack the correct terminology.  Help chasing the
> > 'searching' mechanism would be appreciated.
> 
> Searching "mechanism" is a software algorithm that I described above --- pick 
> a value from memory, compare it to the one you search for. If they are the 
> same, you found it. If not, pick the next value from memory and repeat.
> 
> There is nothing about searching (per se) that is implemented in hardware. The 
> processor knows how to move numbers (to registers and memory), how to add 
> them, subtract, multiply, divide, compare and jump to the next instruction. 
> And that's about it. Everything else is built from that, through various 
> algorithms. 
> 
> Note that this instruction set I described above is not minimal --- for 
> example, you can perform multiplication by looping addition (3x2 = 2+2+2). 
> Depending how the processor is designed, it can have more or less of these 
> non-essential instructions implemented in hardware. You can read on CISC 
> versus RISC philosophy here:
> 
> http://en.wikipedia.org/wiki/RISC
> 
> But I've never heard of a processor that has a "search" instruction 
> implemented in hardware. :-)
> 
> HTH, :-)
> Marko
> 

-- 
Regards Bill
Fedora 13, Gnome 2.30.2
Evo.2.20.2, Emacs 23.2.1

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