Ranking from fast to slow .. interview question

Quote:

---

Originally Posted by Noddon

The inner for-loop:

Code:

---

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

---

has the exact same side effect as:

Code:

---

array1[i]=array2[15];

---

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

---

:eek::eek:

Quote:

---

Originally Posted by Noddon

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:

Code:

---

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:

Code:

---

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
...

Here are my comments about each piece of code:

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:

Code:

---

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.

Code:

---

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.

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!

Quote:

---

Originally Posted by SuperKoko

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?!

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

Quote:

---

Originally Posted by Noddon

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).

Quote:

---

Originally Posted by Noddon

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.

Quote:

---

Originally Posted by Graham

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)!

Main issue is between
1 :

Code:

---

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

---

and
3 :

Code:

---

  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.

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...

Quote:

---

Originally Posted by Sahir

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:

Code:

---

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.

Ok here are the real question from what i can remember

Code:

---


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 ?

Quote:

---

Originally Posted by GoDaddy

So how about it ?

---

See the 20 or so replies above.

Regards,

Paul McKenzie

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.

1. You cannot guarantee that sizeof(int) = 4
2. You don't know if the char arrays are aligned on a 4-byte [or sizeof(int) byte] boundary.
3. 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).
4. memmove() must make some additional checks for memory overlap -- checks that could be ignored and are ignored by (1) and (2).
5. You don't really know how memmove() is implemented.
6. There are a lot of other things too (are the arrays cached, exist in registers, etc...?)

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