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