473,385 Members | 1,329 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,385 software developers and data experts.

Time Complexity

Hi,
when the processor meet this instruction

i >4;

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

Jul 11 '06 #1
9 1928
da***************@gmail.com 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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Jul 11 '06 #2

da***************@gmail.com wrote:
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.

Jul 11 '06 #3
In article <11**********************@75g2000cwc.googlegroups. com>,
<da***************@gmail.comwrote:
>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.

--
There are some ideas so wrong that only a very intelligent person
could believe in them. -- George Orwell
Jul 11 '06 #4
Richard Heathfield wrote:
da***************@gmail.com 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.
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
movl _i, %eax
--
Simon.
Jul 11 '06 #5
In article <44**********@news.peopletelecom.com.au>,
Simon Biber <ne**@ralmin.ccwrote:
>Richard Heathfield wrote:
>da***************@gmail.com said:
>>when the processor meet this instruction
i >4;
the operation, inside the processor, is computed constantly or linearly
>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.
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...)
--
If you lie to the compiler, it will get its revenge. -- Henry Spencer
Jul 11 '06 #6
da***************@gmail.com writes:
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.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jul 11 '06 #7
Walter Roberson wrote:
In article <44**********@news.peopletelecom.com.au>,
Simon Biber <ne**@ralmin.ccwrote:
>Richard Heathfield wrote:
>>da***************@gmail.com said:
>>>when the processor meet this instruction
i >4;
the operation, inside the processor, is computed constantly or linearly
>>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.

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.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Jul 11 '06 #8
On Tue, 11 Jul 2006 17:24:27 +0000 (UTC), ro******@ibd.nrc-cnrc.gc.ca
(Walter Roberson) wrote:
>In article <44**********@news.peopletelecom.com.au>,
Simon Biber <ne**@ralmin.ccwrote:
>>Richard Heathfield wrote:
>>da***************@gmail.com said:
>>>when the processor meet this instruction
i >4;
the operation, inside the processor, is computed constantly or linearly
>>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.

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.
>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...)
--
Al Balmer
Sun City, AZ
Jul 11 '06 #9
da***************@gmail.com wrote:
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.
Jul 11 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Edg Bamyasi | last post by:
This Is A Late Cross Post from comp.lang.python. It seems the mistery is deeper then i expected. What is the running time of conactination on character strings. i.e. >> joe="123" >>...
5
by: Scott Nonnenberg [MSFT] | last post by:
This is really exciting stuff. We'll see you there! It might be a good idea to do some background reading before you show up. :0) C# 3.0: http://msdn.microsoft.com/vcsharp/future/ The LINQ...
25
by: Neil Ginsberg | last post by:
A while back I posted a message re. using an ADP file with a SQL Server back end as opposed to MDB file with linked tables, thinking that the ADP file would be less problematic. The input I got was...
26
by: Lionel B | last post by:
Hi, Anyone know if the Standard has anything to say about the time complexity of size() for std::set? I need to access a set's size (/not/ to know if it is empty!) heavily during an algorithm...
33
by: desktop | last post by:
In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q is a pointer to an element can be done in amortized constant time. I guess that is not worst case since std::set is...
1
by: chits12345 | last post by:
Hi all Is there anybody who can solve this problem? This is not a easy problem. Problem: Assume that George(S,X) is a function that returns a Boolean value, where S is a stack, and that...
3
by: youtoo | last post by:
It has been extensively discussed the time complexity (quadratic) of string concatenation (due to string's immutability). But what is: == the time complexity of string indexing? Is it constant?...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: aa123db | last post by:
Variable and constants Use var or let for variables and const fror constants. Var foo ='bar'; Let foo ='bar';const baz ='bar'; Functions function $name$ ($parameters$) { } ...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.