In my Computer Science II class, the professor considers ++,--,*=, etc. to be 2 operations. However, at the Assembly level this is not really two operations. Can someone explain or is this just for the sake of simplicity?
+6
A:
I'd actually consider it to be 3 operations: read, increment (or whatever), write. That's assuming it's reading from some sort of shared memory into some sort of local storage (e.g. register or stack), operating on the local storage, then writing back.
How many operations it is at assembly level will depend on what you're incrementing, the platform, the hardware etc.
Jon Skeet
2009-01-14 15:49:13
unless, perhaps, you're incrementing a cpu register? I'm not sure, but that might be one Machine language op... You can, if I remember, in some languages specify that a declared variable will be stored only in a register.
Charles Bretana
2009-01-14 15:54:55
Hence the assumption about shared memory, and also the statement that it depends on what you're incrementing, platform, hardware etc.
Jon Skeet
2009-01-14 15:56:03
(Downvotes are more useful if they come with comments, folks...)
Jon Skeet
2009-01-14 16:08:46
Nobody downvotes the Skeet +1 for truth justice and the Stackoverflow way!
Omar Kooheji
2009-01-14 16:15:27
Is is relevant how many assembly operations it outputs? I thought most complexity analysis tools measure how difficult the code would be to grok in general?
Allain Lalonde
2009-01-14 16:16:46
Mathematically, it's 2 operations. The addition and assignment. In assembly it's 3 micro-ops (may only be one opcode in some cases (CISC)) - load, increment, store. Stephen Wrighton's answer is more correct to the way the original question was written.
Brian Knoblauch
2009-01-14 16:20:35
@Brian: Out of interest, what kind of "mathematically" sense is this, and why isn't the load included?
Jon Skeet
2009-01-14 16:23:30
(That isn't meant to be an aggressive "prove it!" comment, btw - I'm genuinely interested.)
Jon Skeet
2009-01-14 17:27:29
@Brian: Even though, Stephen Wrighton's answer is correct, my question also asked about what was happening at the assembly level.
dr.manhattan
2009-01-14 18:11:00
+7
A:
Because ++ (ex: b++) is a simplification of
b = b + 1
There are two operations there, the addition (b + 1) and then the assignment of the value of the addition to the original variable.
Stephen Wrighton
2009-01-14 15:49:46
A:
The prof is probably just referring to having to take the value, add 1 to it and then assign it back to the variable.
jacobangel
2009-01-14 15:50:38
+1
A:
I am gonna throw a few guesses.
- Is your professor is referring to interpreted languages?
- ++i is different than i++ maybe he's referring to that?
Maybe his assembly lang of choice needs the intermediate storage variable?
add reg_temp, reg_i, 1 mov reg_i, reg_temp
J.J.
2009-01-14 15:55:24
A:
At the assembly level everything is done in registers so having a variable in A
ADD AX,1
However, in compiled languages everything has to be stored so i++ becomes (in pseudo assembly)
MOV AX,i
ADD AX, 1
MOV i, AX
Which is three operations...Unless I have forgotten my basic architecture completely...
Jamie Lewis
2009-01-14 15:56:20
+2
A:
Why bother when doing complexity analysis? It is just O(1) :-)
EDIT: Please let me know why when you vote it down. Since the question is tagged complexity, I assume big O notion is the most important, rather than the actual constants. Besides, as already mentioned in other answers, how many operations this is depends on a lot of factors: the way you count operations, platform, compiler, etc.
PolyThinker
2009-01-14 16:00:00
A:
You reminded me of a Kinda "Jury is not out" problem that I heard a long time ago.
"Preincrement is faster than postincrement"
I just did a quick google search.
- Lots of people still hold that as true.
- Others contend that Compilers are so optimized, the comparative high level code code can't be benchmarked.
- Yet other people contend that there is no difference.
J.J.
2009-01-14 16:09:05
If there's a difference between standalone pre- or post-increment on basic data types on your compiler, the best thing you can do for optimization is get a better compiler. Under other circumstances, it may well be important that you may need to create a temporary value to return.
David Thornley
2009-01-14 16:14:50
Unoptimized, preincrement is faster than postincrement. In many common cases, however, this can be optimized by a decent compiler. Even when unoptimized, the difference will likely not be significant on a fundamental numerical type (as opposed to a user-defined type with overloaded operator++)
Tyler McHenry
2009-01-14 16:26:22
@David: Getting a better compiler is rarely if ever a solution.@Tyle: Good point. So the blanket statement of pre vs post is wrong, due to the variance of factors affecting it?
J.J.
2009-01-14 19:05:26
A:
It should be more than 2 in my opinion since it has two meanings depending on context and I always have to remind myself of them when I see it.
a = b++ is the same as a = b; b = b + 1
and
a = ++b is the same as b = b + 1; a = b
This is enough of a confusion to send most first year students off the cliff.
Allain Lalonde
2009-01-14 16:14:45
but his question is just concerning the ++ type operations (so it would be just ++b or b++ not a=b++ pr a=++b). In that case, context has no meaning, as both b++ and ++b = (b=b+1)
Stephen Wrighton
2009-01-14 16:36:37