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