Do you know arrays?

I think that few of those preparing for their first interview, when hiring for their first job as a (pre) junior programmer, will answer this question in the negative. Or at least doubt the positive answer. Of course, such a simple data structure with direct access by index - no tricks! No, in some languages ​​like JavaScript or PHP, arrays are, of course, implemented very interestingly and in fact are much more than just an array. But this is not about that, but about the "traditional" implementation of arrays in the form of a "continuous piece of memory." In this case, based on the indices and the size of one element, the address is simply calculated and the corresponding value is accessed. What's so complicated?
Let's figure it out. For example, in Java. We ask an unsuspecting applicant to create an array of integers nx n . A man confidently writes something in the spirit:

int g[][] = new int[n][n];

Excellent. Now we ask you to initialize the elements of the array with something. At least units, at least the sum of the indices. We get:

for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
          g[i][j] = i + j; 
      }
}

They even write more often

for(int i = 0; i < g.length; i++) {
      for(int j = 0; j < g[i].length; j++) {
          g[i][j] = i + j; 
      }
}

which is also a reason for conversation, but now we are talking about something else. We are trying to find out what a person knows and see how he thinks. Therefore, we draw his attention to the fact that the values ​​are located symmetrically and we ask you to save on iteration of cycles. Of course, why run through all the index values ​​when you can only go through the lower triangle? The subject usually agrees easily and wisely highlighting the main diagonal carefully writes something in the spirit:

for(int i = 0; i < n; i++) {
    g[i][i] = 2* i;
    for(int j = 0; j < i; j++) {
        g[j][i] = g[i][j] = i + j; 
    }
}

Instead

g[i][i] = 2* i;

often write

g[i][i] = i + i;

or

g[i][i] = i << 1;

and this is also an occasion to talk. But we go further and ask the key question: How much faster will the program work? . The usual reasoning is as follows: almost 2 times less than index calculations; almost 2 times less than the calculation of values ​​(summation); as many assignments. That means 30 percent faster. If a person has a good mathematical school, you can even see the exact number of operations saved and a more reasoned estimate of the effectiveness of optimization.
Now is the time for a major blow. We run both versions of the code on some rather large value of n (of the order of several thousand), for example, like this .

What do we see? The optimized version works 10-100 times slower! Now is the time to observe the reaction of the applicant for the post. What will be the reaction to an unusual (or rather, usual in the developer's practice) stressful situation. If the face of a client showed excitement and he began to press buttons temporarily forgetting about your existence, then this is a good sign. To a certain extent. You do not want to hire a researcher who does not care about the result of the project? Then do not ask him the question “Why?”. Ask to remake the second option so that it really works faster than the first.
Now you can safely go about your business for some time. In half an hour you will have enough material to evaluate the main personal and professional qualities of the applicant.
By the way, when I briefly described this problem on my working site, the most popular comment was "This is your Java curve like this." Especially for them, I post the code on the Great and Free. And the lucky owners of Free Pascal for Windows can take a peek

In the above Pascal code, I removed the “confusing” points and left only the essence of the problem. If it can be called a problem.
What kind of questions do we get for the client?
1. Why has it become slower? And in more detail ...
2. How to make initialization faster?

If there is a need to dig deeper into the Java implementation, we ask the applicant to observe the execution time for small values ​​of n . For example, on ideone.com for n = 117, the “optimized” option works twice as slow. But for the next value n = 118, it is already 100 (one hundred) times faster than not optimized! Suggest experimenting on a local machine. Let him play with the settings.
By the way, does everyone understand what is happening?


So far, the version is leading that the processor cache is “to blame”. Those. sequential access in the first embodiment works within a hash, which is updated when moving beyond a certain border. When accessing through columns, the hash is constantly updated and this takes a lot of time. Let's check this version in its purest form. Let's start an array and compare, which is faster - to process all the elements in a row or as many times to process the elements of an array with a random number? This program is ideone.com/tMaR2S . For 100,000 array elements, random access is usually noticeably faster. What does this mean?
Here I was rightly pointed out (Big_Lebowski) that permutation of cycles changes the results in favor of a sequential version. I had to put a cycle for warming up for the purity of the experiment. At the same time he made several repetitions in order to deduce the average operating time as advised by leventov. It turned out so ideone.com/yN1H4g . Those. random access to elements of a large array is ~ 10% slower than sequential. Perhaps the truth may be played by the cache. However, in the initial situation, performance sagged significantly. So there’s something else.

Gradually, a version about additional actions when moving from one line of the array to another comes out to the leaders. And it is right. It remains to figure out what exactly is happening there.