While waiting for Fedora 14, a question for the engineering types re: searching and finding
William Case
billlinux at rogers.com
Thu Oct 28 21:35:04 UTC 2010
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
More information about the users
mailing list