Re: To Richard Heathfield: enough's enough

From: Edward G. Nilges (spinoza1111_at_yahoo.com)
Date: 12/25/03 

Date: 25 Dec 2003 09:23:27 -0800

Willem <willem@stack.nl> wrote in message news:<slrnbukf3b.1b1j.willem@toad.stack.nl>...
> Edward wrote:
> ) Richard was claiming that if strlen(s) is implemented by a single CISC
> ) instruction in firmware, it is O(n*n) in the same way
> )
> ) for ( intIndex1 = 0; strInstring[intIndex1] = '\0'; intIndex1++ ) { }
> )
> ) makes an O(n) for loop into an O(n*n) for loop when this for is the
> ) inner for.
>
> This claim is true.
> A single CISC instruction that searches for a NUL byte takes O(n) time.
> Executing such an instruction n times makes that O(n*n).
>
>
> SaSW, Willem

This is an inexcusably sloppy use of the expression O(x).

The expression mean "on the order of", and it means that the time
value increases proportionally to the value of x.

The problem is that you are deliberately ignoring the k factor which
is the constant cycle time that a probe for Nul takes, and therefore
concealing the difference between the following two cases.

Take the code in question, written of course for clarity in Hungarian
notation.

for ( intIndex1 = 0; intIndex1 < strlen(strInstring); intIndex1++ ) {
}

Suppose first that strlen is implemented inline as the following
macro. I have not used the preprocessor since 1993 when I abandoned
the C language because of its problems, therefore the reader is
invited to make any corrections, and thugs with modems are invited to
go *** themselves. I will use non-Hungarian notation in the macro
definition for brevity.

#define strlen(s) { (int i; for ( i = 0; s[i++] != '\0'; ); i) }

Note that the above makes some quick assumptions because I need not to
waste my time on this issue, and although Richard Heathfield is a thug
with a modem, because of his C experience, he is invited to comment on
the above. The intent of the code is clear and it is to show the true
O(n*n) case where the strlen is inlined as C code of the same time as
its caller. The value of the strlen is developed and returned.
Alternatively, strlen could be a subroutine call.

This code will generate, approximately, the following "assembly
language" in a typical machine with a typical stack. I won't waste
time explaining the language because I would like to rid the audience
of most thugs, and I expect Richard and Willem will understand the
language although they are thugs. I won't comment because if you
understand the language you don't need comments. The code is extempore
and may contain errors which the reader is invited to fix or ignore,
for my point below will make it clear that this is an example.

push 0
pop intIndex1
LBL0
push intIndex1
LBL1
push 0
pop i
LBL2
push i
push i
increment
pop i
addAddress s
pushIndirect s
push 0
ifNE LBL2
push i
ifGE LBL3
push intIndex1
increment
pop intIndex1
jump LBL0

The above, and only the above, is clearly O(n*n) when you realize that
you have to specify a K, which is the average cycle time of any one of
the above RISC instructions (RISC in the sense that they are all
obviously constant time). The execution time formula is not sloppily
"O(n*n)" it is in fact n*n*K where K is a knowable number.

But suppose the instruction findChar is implemented in faster hardware
such that while it is (in terms of the order-of-magnitude FASTER cycle
time of the faster hardware) O(n) where n is the length of the string,
it is sufficiently fast that O(n) is constant from the standpoint of
most realistic n lengths. The code looks like this

push 0
pop intIndex1
LBL0
push intIndex1
push s
push \0
findCharCISC
ifGE LBL1
push intIndex1
increment
pop intIndex1
jump LBL0
LBL1

In most cases, if the firmware people do their frigging job,
findCharCISC will have the same constant performance as any other
instruction K, and if it does not for large strings, the
implementation could be changed to simply throw an error after a
constant time. The optimizing compiler could catch this error and
proceed to use the original inline code.

The final result, if you have a CISC-type instruction, of the sort
which has been around since Translate and Translate and Test, is that
the execution is, in a practical sense, O(n).

Quantcast