Time Complexity

[davide.sammartino]

Hi,
when the processor meet this instruction

i >> 4;

the operation, inside the processor, is computed constantly or linearly
in time?

 

[Richard Heathfield]

(e-mail address removed) said:

Hi,
when the processor meet this instruction

i >> 4;

the operation, inside the processor, is computed constantly or linearly
in time?

Probably in zero time, since the processor will probably never see it,
because it is probably equivalent to a NOP, so the optimiser will probably
throw it away. If the i identifier is a macro, however, all bets are off.

 

[forkazoo]

Hi,
when the processor meet this instruction

i >> 4;

the operation, inside the processor, is computed constantly or linearly
in time?

I don't think there is any guarantee. Some processors may do an
arbitrary shift in a single cycle, others may do it as a sequence of
steps depending on the shift. If this is a very time critical thing,
it may be best to benchmark it.

It is also possible that if the compiler knows the value of i, then it
will just treat this as a constant expression, and it may take no time
at runtime.

 

[Walter Roberson]

when the processor meet this instruction

i >> 4;

the operation, inside the processor, is computed constantly or linearly
in time?

"inside the processor" is a hardware issue, and the answer is
going to depend on the exact model and revision of the processor.

Some processors have a "barrel shifter" that does everything in one
go, and some processors do not and internally would do four single-bit
shifts. But even on those processors, does it make sense to talk
about constant or linear time of computation if the processor
guarantees that the result will be ready within the natural clock
cycle -- repeated shifts might take place at the microcode level and
even the maximum number of them might finish in plenty of time to
be ready to clock the outputs out for the next step. Not that
microcoding is guaranteed: you need to look at the processor
documentation.

There are a few other issues to consider:

a) is "i" signed or unsigned? The C result of i>>4 is well defined if
i is unsigned, or if i is signed and positive, but if i is signed
and negative then the result is implementation dependant and that
means there -could- be some kind of value clean-up code or trap-catching
code, the time complexity of which is not something we can predict here

b) i>>4 is defined in terms of value, not in terms of bit representation.
If the hardware implementation does not happen to be 2s complement,
then there may need to be value adjustment cycles [it would take
me some thinking to figure out the formulae.] C89 does not restrict
value representations, but C99 narrows down to three different
classes of value representations, of which 2s complement is but one

c) i>>4 is defined in terms of value, not in terms of bit representation.
If there are padding bits in the representation, the implementation
needs to do something about those; we can't predict what it might
use those padding bits for, so we can't say what it will need to do.

 

[Simon Biber]

(e-mail address removed) said:


Probably in zero time, since the processor will probably never see it,
because it is probably equivalent to a NOP, so the optimiser will probably
throw it away. If the i identifier is a macro, however, all bets are off.

Also, if i has a volatile-qualified type, the compiler ought to go
through the motions of loading its value. I'm not saying that all
compilers necessarily will do that. GCC does.

C:\docs\prog\c\sh>cat shift1.c
int i;

void foo(void)
{
i >> 4;
}

C:\docs\prog\c\sh>diff shift1.c shift2.c
1c1
< int i;
---

> volatile int i;

C:\docs\prog\c\sh>gcc -S shift1.c -o shift1.s

C:\docs\prog\c\sh>gcc -S shift2.c -o shift2.s

C:\docs\prog\c\sh>diff shift1.s shift2.s
7a8

 

[Walter Roberson]

Also, if i has a volatile-qualified type, the compiler ought to go
through the motions of loading its value.

On first reading, I'm not certain about that. C89 2.1.2.3 Program Execution
specifies that,

In the abstract machine, all expressions are evaluated as specified
by the semantics. An actual implementation need not evaluate part
of an expression if it can deduce that its value is not used
and that no needed side effects are produced (including any caused
by calling a function or accessing a volatile object.)


My (possibly naive) intepretation of that is:

- if there are multiple volatile variables, then accessing i just -might-
happen to change one of the other ones, so if any of the other
variables are used after that point, the access must be done

- if i is not used after that point and it is the only volatile
variable, then no "needed side effects are produced" and the
access could be discarded

The above is based upon the assumption that -reading- a volatile
variable does not produce an -output- in the environment; a quick
skim over the discussion of volatile seems to me to imply that
C does not worry about such possibilities. But plausibly the wording
of the standard is saying, "The overall implementation, drawing
upon detailed knowledge of the architecture, might be able to figure
out which reads of volatiles might trigger extra behaviour and which
ones will never do so; and for the ones that are certain never to do so,
the implementation could skip the read access."

(For example, if a volatile variable is block scope, or is file scope
and there are no volatile-qualified writes to it in other routines
in the file scope, and the address of the variable is not passed
around, then the only way to change the variable value would be through
a debugger... which wouldn't trigger any side effects anyhow.
On the other hand, if a variable has extern scope then even though
intra-procedure analysis might seem to indicate the variable has no
side effects, on some systems the address of extern variables can
be specified at link time, and the address might be that of a
memory-mapped I/O register... which an even more sophisticated system
might be able to detect...)

 

[Flash Gordon]

On first reading, I'm not certain about that. C89 2.1.2.3 Program Execution
specifies that,

In the abstract machine, all expressions are evaluated as specified
by the semantics. An actual implementation need not evaluate part
of an expression if it can deduce that its value is not used
and that no needed side effects are produced (including any caused
by calling a function or accessing a volatile object.)


My (possibly naive) intepretation of that is:

- if there are multiple volatile variables, then accessing i just -might-
happen to change one of the other ones, so if any of the other
variables are used after that point, the access must be done

- if i is not used after that point and it is the only volatile
variable, then no "needed side effects are produced" and the
access could be discarded

The above is based upon the assumption that -reading- a volatile
variable does not produce an -output- in the environment;

Your assumption is wrong on at least some hardware I've used.

> a quick
skim over the discussion of volatile seems to me to imply that
C does not worry about such possibilities. But plausibly the wording
of the standard is saying, "The overall implementation, drawing
upon detailed knowledge of the architecture, might be able to figure
out which reads of volatiles might trigger extra behaviour and which
ones will never do so; and for the ones that are certain never to do so,
the implementation could skip the read access."

So how can the implementation detect whether I'm going to attach a logic
analyser and watch for that variable being read?

(For example, if a volatile variable is block scope, or is file scope
and there are no volatile-qualified writes to it in other routines
in the file scope, and the address of the variable is not passed
around, then the only way to change the variable value would be through
a debugger... which wouldn't trigger any side effects anyhow.

Depends on your definition of a side effect.

On the other hand, if a variable has extern scope then even though
intra-procedure analysis might seem to indicate the variable has no
side effects, on some systems the address of extern variables can
be specified at link time, and the address might be that of a
memory-mapped I/O register... which an even more sophisticated system
might be able to detect...)

Since a memory-mapped I/O register can be, as far as the processor is
concerned, just another memory address to which someone has decided to
attach hardware (possibly after you write the software) that is mighty
tricky.

 

[Keith Thompson]

when the processor meet this instruction

i >> 4;

the operation, inside the processor, is computed constantly or linearly
in time?

Yes, probably. (The C standard is silent on this point.)

 

[Al Balmer]

On first reading, I'm not certain about that. C89 2.1.2.3 Program Execution
specifies that,

In the abstract machine, all expressions are evaluated as specified
by the semantics. An actual implementation need not evaluate part
of an expression if it can deduce that its value is not used
and that no needed side effects are produced (including any caused
by calling a function or accessing a volatile object.)


My (possibly naive) intepretation of that is:

- if there are multiple volatile variables, then accessing i just -might-
happen to change one of the other ones, so if any of the other
variables are used after that point, the access must be done

- if i is not used after that point and it is the only volatile
variable, then no "needed side effects are produced" and the
access could be discarded

The above is based upon the assumption that -reading- a volatile
variable does not produce an -output- in the environment;

I don't know why you restrict the analysis to "output", whatever that
might be. Reading the variable might well produce a change (needed
side effect) in the environment. As an example, reading a status
register or data register may clear it.

 

[Martin Ambuhl]

Hi,
when the processor meet this instruction

i >> 4;

the operation, inside the processor, is computed constantly or linearly
in time?

Since the effect of the statement is a NOP, it is possible that your
compiler treats it as one. It then becomes silly to ask in what way a
computation not done is done.