Ranking from fast to slow .. interview question

[GoDaddy]

I just had a technical interview ...

I had to rank from fastest to slowest ...

1)

for( int i =0;i<16;i++)
array1[i] = array2[i];


2)

for(int i=0;i<16;i++)
(int)array1[i] = (int)array2[i];


3)

memmove(dest,src,16);


4)

for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
array1[i]=array2[j];



My answer : 3,1,2,4

Was it right ?

[Paul McKenzie]

The correct answer is

5) None of the above.

It depends on the compiler's optimizer. That was a trick question.

Regards,

Paul McKenzie

[GoDaddy]

:O crap

[VladimirF]

Well, this doesn't sound like an interview question. Unless you are interviewed by someone from this thread (http://www.codeguru.com/forum/showthread.php?t=377207) ...
BTW, you got #4 right - it does 16 times more work than #1..3. Of course, it's just writing different values over and over to the same location. Can't imagine why the speed would be an issue there.

[GoDaddy]

its a preselection test. Got tons of technical questions i had to answer on paper

[KevinHall]

Another (and probably more important question) is "What is correct"?

The call to memmove() would only be correct if both arrays had elements one byte in size.

- Kevin

BTW, (2) might effectively be the same statement as (1) if the arrays were arrays of integers.

[cilu]

It depends on the compiler's optimizer. That was a trick question.
I have this feeling that the person that asked the question did not think at that. ;)

[Graham]

I think I'd deliberately fail that interview. A company that asks questions like that probably isn't worth working for.

[RoboTact]

I have this feeling that the person that asked the question did not think at that. ;)
I once participated in 'competition' put by sponsor (hardware trade company) during lunch break on programming contest... They wrote some mix of C++ and Java code (mostly resembling C++) and asked tricky question about behaviour of objects with multiple inheritance and type casting. I wrote 'compile error' as answer and they ranked it as (the only) correct answer. Only two people there knew that sponsor good enough to answer in such manner. :D

[GoDaddy]

I think I'd deliberately fail that interview. A company that asks questions like that probably isn't worth working for.

What do you mean ?

[RoboTact]

What do you mean ?If they asked that question with intention to actually get some 'right' order, that question is just incompetence made manifest, which doesn't speek good for the firm.

[googler]

In 2), the left hand side is not even an lvalue so it produces a compilation error.

[exterminator]

In 2), the left hand side is not even an lvalue so it produces a compilation error.
You stole that from me... :thumb: I was going to reply with that until I saw your mention of it. Best regards.

[Hobson]

In 2), the left hand side is not even an lvalue so it produces a compilation error.

I think that point in 2) is that operating on ints is faster than on non-int numbers due to fact that int size should be natural data size for given architecture. Anyway, this question is not good one, I think...

Regards

[Vedam Shashank]

I think that point in 2) is that operating on ints is faster than on non-int numbers due to fact that int size should be natural data size for given architecture
int size need not be the natural data size for given architecture

[treuss]

int size need not be the natural data size for given architectureIn fact it is not on modern 64 bit CPUs/compilers, where sizeof(int) = 4 and sizeof(long) = sizeof(void*) = 8

[Graham]

int size need not be the natural data size for given architecture
The standard explicitly states that int is intended to have the natural size for the architecture of the target machine.

3.9.1/2:
Plain ints have the natural size suggested by the architecture of the execution environment.

[Vedam Shashank]

The standard explicitly states that int is intended to have the natural size for the architecture of the target machine.
What do they mean by "natural size" here ????

I ask this with regard to... this (http://www.codeguru.com/forum/showpost.php?p=1166552&postcount=8)

[Brad Jones]

A company that asks questions like that probably isn't worth working for.

I disagree.

I think the amount of discussion generated in this thread indicates that this is an excellent interview question.

An internview question need not be answerable or correctly worded. After all, in an interview, it isn't the question that is being evaluated, but rather the answer (and the person giving that answer). How someone answers a question is often more important than getting the answer right -- if there even is a correct answer. :D

Brad!

[NMTop40]

I've had interview questions recently where the correct answer was "undefined behaviour" and they knew it was - they were testing.

[Noddon]

I disagree.

I think the amount of discussion generated in this thread indicates that this is an excellent interview question.

An internview question need not be answerable or correctly worded. After all, in an interview, it isn't the question that is being evaluated, but rather the answer (and the person giving that answer). How someone answers a question is often more important than getting the answer right -- if there even is a correct answer. :D

Brad!

Personally, I'm with Graham on this one, for technical questions at least.

I've been in interviews where answers to questions like this have become length discussions. In more than a few cases, this has come down to the interviewer setting a question they cannot correctly answer themselves. This question looks very much like one of those. Obviously, until you answer it and talk about it with the interviewer you don't really know for sure.

Interviews are two way processes: not only is it the employers chance to assess the would-be employee... but also for the employee to assess the would-be employer.

I've declined and accepted jobs based on whether the person giving a technical interview can knowledgably discuss their own questions. If they can't then it's not a good indicator of the quality of your would-be colleagues.

[exterminator]

It is really unlucky in those times when people ask you something.. you give the correct answer.. but they know the wrong answer themselves and hence rate your correct answer as wrong.

On one such ocassion - a guy said that the allocation using new in the initializer list (and exception later on generated before exiting from the constructor) is safe. Upon such exceptions the run-time rolls the allocation back. That is the use of initializer list... it is that safe.. I just struck my head and couldn't say a word.. that was an internal one...

Sorry for the off-topic post.

[SierraP]

I've been in interviews where answers to questions like this have become length discussions. In more than a few cases, this has come down to the interviewer setting a question they cannot correctly answer themselves.


I would think that would be a reason to keep the question in the interview. If it brings about discussion with the perspective employee. For the very reasons you submitted, if an employee can discuss something with you and you both feel each other is competent (and can communicate with each other) you are more apt to be able to work together. Many companies are looking for that golden mix: a competent programmer who is personable...I tend to take jobs based on what I perceive they can teach me and how I can grow as much as whether I can do what they immediately need me to fulfil.

[Paul McKenzie]

On one such ocassion - a guy said that the allocation using new in the initializer list (and exception later on generated before exiting from the constructor) is safe. Upon such exceptions the run-time rolls the allocation back. That is the use of initializer list... it is that safe.. :eek: :eek:

Regards,

Paul McKenzie

[Sef]

I disagree.

I think the amount of discussion generated in this thread indicates that this is an excellent interview question.

An internview question need not be answerable or correctly worded. After all, in an interview, it isn't the question that is being evaluated, but rather the answer (and the person giving that answer). How someone answers a question is often more important than getting the answer right -- if there even is a correct answer. :D

Brad!I hope you're right in this case but unfortunately, it's probably an idealistic and optimistic view of the world (with all due respect). The sad truth is that there's rampant incompetence in this field and the inteviewer himself, like most programmers, probably falls into that category (far more often than not anyway).

[Vedam Shashank]

Go daddy could u let us know where (i mean place not which company) did u take the interview, and how many questions were asked in that written round, and how many had to write it along with u????

[GoDaddy]

The correct answer is

5) None of the above.

It depends on the compiler's optimizer. That was a trick question.

Regards,

Paul McKenzie

Why would it depend on the compiler optimizer ?

4 .. is the slowest no ? ....

[Noddon]

Why would it depend on the compiler optimizer ?

4 .. is the slowest no ? ....

Compilers only have to produce a program that works "as if" it were the program you described in the code.

A "clever" (possibly even too clever!) compiler could optimise this:


for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
array1[i]=array2[j];


to something that looks (algorithmically) like this:


for (int i=0;i<16;i++) array1[i]=array2[15];


or it could unroll the loop, or dozens of other things. The important thing is that the outcome is "as if" the code being compiled had been run. This could very well wind up being faster than the other examples since there are fewer memory accesses... even though it doesn't do the same thing!

In practice, many compilers optimisers won't do this (unless it's a trivial case) because they're difficult to spot, and programmers tend not to add loops pointlessly!

[sreehari]

to something that looks (algorithmically) like this:

for (int i=0;i<16;i++) array1[i]=array2[15];



:confused: :confused:

[Noddon]

:confused: :confused:

The inner for-loop:


for (j=0;j<16;j++) array1[i]=array2[j];


has the exact same side effect as:


array1[i]=array2[15];


since the only assignment to array1[i] which matters is the last one, when j is 15.

[Vedam Shashank]

The inner for-loop:


for (j=0;j<16;j++) array1[i]=array2[j];


has the exact same side effect as:


array1[i]=array2[15];


since the only assignment to array1[i] which matters is the last one, when j is 15.
:eek::eek:

[SuperKoko]

Compilers only have to produce a program that works "as if" it were the program you described in the code.

A "clever" (possibly even too clever!) compiler could optimise this:


for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
array1[i]=array2[j];


to something that looks (algorithmically) like this:


for (int i=0;i<16;i++) array1[i]=array2[15];


or it could unroll the loop, or dozens of other things. The important thing is that the outcome is "as if" the code being compiled had been run. This could very well wind up being faster than the other examples since there are fewer memory accesses... even though it doesn't do the same thing!

In practice, many compilers optimisers won't do this (unless it's a trivial case) because they're difficult to spot, and programmers tend not to add loops pointlessly!
I think that there is a problem with aliasing assumption.
If array1 or array2 is a restrict pointer, the compiler may optimize (or if the compiler deduces via another mechanism, that arrays don't overlap).
But, suppose array1==array2+15
...

[SuperKoko]

Here are my comments about each piece of code:

for( int i =0;i<16;i++)
array1[i] = array2[i];

Very likely to be optimized by the compiler, if and only if he can assume that array1 or array2 are not overlapping.
For example if array1 and array2 are both declared as automatic array variables or static storage variables.
If array2 is a const array (automatic or static), then, even if array1 is a pointer or anything else, the compiler can assume that array2 cannot be modified, hence there is no effective aliasing. Here is one of the seldom cases where a compiler can produce better code when the const keyword is used.
If either array1 or array2 is a restricted pointer (for a C99 compiler) and the other pointer/array is not based on the former, the compiler can assume that variables are not aliases.
If array2 and array1 may be easily proved to be non-overlapping by the compiler itself, for example:

int *array2=array1+16;
/* here, the compiler knows that array2[0..16] and array1[0..16] don't overlap */

Finally, since this construct is very common, the compiler may handle it specially, because it sees that the for loops 16 times, hence he can put an conditional statement; it will not make a big overhead.
And, this conditional statement will compare pointers to see if they are overlapping.
If the are'nt, the compiler calls (or inline) a fast memory movement routine, specifically optimized for this size of block (maybe using SSE registers).
If they are, the compiler uses another routine.


for(int i=0;i<16;i++)
(int)array1[i] = (int)array2[i];

ill-formed code.
May compile on some non-compliant compilers, if array1 and array2 are arrays of integers.
In that case, almost surely, it will produce the same code than for the first piece of code.


memmove(dest,src,16);

It should be fast, but may be different from the first piece of code if arrays are overlapping, or if arrays are not arrays of byte!

[Noddon]

I think that there is a problem with aliasing assumption.
If array1 or array2 is a restrict pointer, the compiler may optimize (or if the compiler deduces via another mechanism, that arrays don't overlap).
But, suppose array1==array2+15
...

Well, yes....

I guess I shouldn't have assumed that identifiers with the names "array1" and "array2" actually are array identifiers!

Then again, what if they're not pointers to arrays? They might be objects with overloaded [] and = operators! Oh... where does it end?!

[Graham]

I think this discussion provides ample answer to the question of why I said what I did in #8...

[SuperKoko]

I guess I shouldn't have assumed that identifiers with the names "array1" and "array2" actually are array identifiers!

I seldomly (never?) uses plain arrays.
Pointers to arrays (in C; C++ has vectors & iterators) are more used then plain arrays.
So, when I see an identifier such as "array1", I assume it is a pointer (Perhaps I am wrong).

They might be objects with overloaded [] and = operators! Oh... where does it end?!

This seems to be C-style programmation (although it needs C99 to compile).
Also, the memmove operation made me think that array1 and array2 are not vectors (but, of course they can be objects overloading operator type*).
But, I admit that you are rigt in saying that operator[] may be overloaded.
This point, and all its implications, should be deemed.

I think this discussion provides ample answer to the question of why I said what I did in #8...

Sure.

Code is incomplete, thus obscure
The type of array1 and array2 are unknown, and worst, the type pointed/referenced/contained by array1 and array2 are unknown. int? char?

Question is stupid.
Speed... On which implementation, with which CPU? With optimization flags? I know that GCC without optimization flags is really very bad (but produces very predictible code)... but with optimizations flags it is totally different.
Heck! what's this ill-formed code (second piece of code)!

[Sahir]

Main issue is between
1 :

for( int i =0;i<16;i++)
array1[i] = array2[i];

and
3 :

memmove(dest,src,16);


Contrary to popular belief , 1 is faster than 3 { using VC++ 6 } .

This looks like a "programming trivia quiz" kind of question. Not knowing the answer should not be held against you, hence it is not appropriate for an interview.

[JMS]

10-20% of all interviews are conducted by morons who either want to torment the candidate with unfair questions or don't know enough to know what is a reasonable question to ask.

Dostoyevsky wrote about this syndrom in in "Notes from the Underground" about a beurocrat in Czarist Russia. Yes self loathing sadists who want to make themselves feel superior at the expense of others is not an American or even modern invention.

One definition of a senior developer is how quickly one can recognize they just experienced this phenomenen and recover from the self questioning and self doubt in hours/days instead of weeks..... Personally I've gotten it down to minutes for technical interviews...

Personal experiences with this ilk...

(1) World Bank interview 1988.... Dude sits down and randomly opens up Charles Petzolt's book... Says to me finish this sentence... starts to read...
This position was open for almost 4 years, It was a joke in the DC area. I must have known six guys who interviewed with this PHD over that time, all got the question, none got the job.

(2) NASDAC interview 1992... "Name all the reserved words in C++."

(3) Some forgotton company circa, 1998... "What do you think of multiple inheritance in C++"?

I don't think it's a good idea, it can lead to undefined compiler specific behavior, it's descouraged by many books I've read, and in the last decade or so programming on very large and complex systems; I've not yet seen a situation where it contributed to a system from a performance or a code maintanability standpoint. ( this was the only question they asked in the interview, Knew two other guys who went on the interview and didn't matter how you answered the question none of use were offered the position... )

Interviewing is an art both from the perspective of the candiate and from the potential employer. Unfortunately some employers who interview are idiots and are just not capable of decerning, or appreciating what separates one candidate from another. Can't beat yourself up over that, you just have to interview widely to insulate your career from this phenomina...

[SuperKoko]

Contrary to popular belief , 1 is faster than 3 { using VC++ 6 } .

Thus, VC++ 6, which is known to be quite efficient, does not optimize calls to intrinsics functions.
The ISO standard reserves all identifiers of the standard library in the global namespace and the std namespace, hence a compiler can optimize such function calls.

The point here is that you cannot assume that the compiler will do optimizations you expect.
Even a good compiler may not do all optimizations.

It appears that VC++ calls the memove function, which involves a function call, a ret instruction, and some overhead due to memory alignment before the ultimate "rep movsd" operation.
This overhead is small for big arrays, but for a 16 bytes array (just 4 DWORD), it is significant.
Furthermore:

for( int i =0;i<16;i++)
array1[i] = array2[i];

Can be efficiently replaced by a "rep movsb" operation (VC++ probably does not this optimization), without changing the behaviour if arrays overlap.

In fact, due to those two facts:

You cannot know whether the compiler produces good code for a memove operation, or just a stupid library code.
You cannot know whether the compiler is efficient for doing small predictible for loops.

It is impossible to say what code is more efficient than the other.
It is implementation-dependent, and even compilation-flag dependent.

For example, try to compile your code without optimizations (in that case I think that it does not use register variables and is really very bad). it may change the speed ratio.

[GoDaddy]

Ok here are the real question from what i can remember



char src[16]= {...};
char dest[16] = { ... };

1)
for(int i=0;i<16;i++)
dest[i] = src[i];

2)
for(int i=0;i<4;i++)
{
*(int*) dest= *(int*) src;
dest+=4;
src+=4;
}

3)
memmove(dest,src,16)

4)

don't remember




So how about it ?

[Paul McKenzie]

So how about it ?See the 20 or so replies above.

Regards,

Paul McKenzie

[KevinHall]

You still cannot tell -- even with very good optimizations. And it is still possible that on some systems, the example code does not do the same thing.


You cannot guarantee that sizeof(int) = 4
You don't know if the char arrays are aligned on a 4-byte [or sizeof(int) byte] boundary.
You don't know if the arrays lie on different memory pages or not. (in other words, you cannot tell if there will be page faults or not).
memmove() must make some additional checks for memory overlap -- checks that could be ignored and are ignored by (1) and (2).
You don't really know how memmove() is implemented.
There are a lot of other things too (are the arrays cached, exist in registers, etc...?)

[RoboTact]

The only correct question here is "how would you implement it?", previously defining the extent of "it".