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

[Marko Vojinovic]

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?

> 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

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