Arrays, pointers and other quantum phenomena around us

I do not want to say that we all live in a matrix, but to imitate neighbors the same sound of a rolling ball is suspiciously used.

This post is fully consistent with its name. For a start, it will show that, contrary to the statement of the standard, as well as the classics of the Kernighan C language, the use of array indices is absolutely not equivalent to the use of corresponding pointers, and the choice of an epigraph will be clear at the very end. And yes - the middle of the post is also not empty.

It all started with the refutation of Fermat's theorem and finding a number with a cosine exceeding one from a highly thoughtful post about the indefinite behavior of the compiler (undefined behavior or UB). That is, there were several such posts, but in this ( translation to habrahabr ) the following simplest code was cited and the far from obvious result of his work:

int table[4]; bool exists_in_table(int v) { for (int i = 0; i <= 4; i++) { if (table[i] == v) return true; } return false; } 

There is an error in the loop condition: "<= 4" instead of "<4".
Now, if we fill the table with zeros, and even make sure that the illegal fifth element of this array is 0, and then look at the table for a good number of 42, that is, call exists_in_table (42) , then it will definitely be there - in the case of a well-optimized C compiler, this function will return true in full accordance with the language standard!
')
The explanation is simple: exists_in_table () must either return true on one of the first four iterations, or it will read the table [4] , which is UB, and in this case, exists_in_table () can do anything, according to the C standard. and return true . That is, the compiler can optimize the whole exists_in_table () code to return true;

And this is not an abstract theory, but a concrete practice. This is how code optimizes, i.e. exists_in_table (42) returns true when compiling, for example, gcc 6.3 (via MinGW) using the -O2 or -O3 options. All results below are specific to this configuration.

And now let's at least once in life once again read the standard C.
Yes, in the section on arrays, he honestly warns that access to elements outside the array is UB. But, as everyone who has ever studied C knows, access to array elements is possible through pointers, or, in the language of ISO / IEC 9899, ​​the definition of the index operator [] is as follows: E1 [E2] is equivalent to (* ((E1) + (E2))). ”(“ The definition of the subscript operator [] is that E1 [E2] is identical to (* ((E1) + (E2)) ”).

And here something interesting is revealed. “Identical” - that is, identically, interchangeably under any circumstances. And even with UB? Let's see what happens if in the example above, use pointers to access array elements.
But first, we will make the code really safe, for which we wrap the table array into a structure so that the space allocated by us is guaranteed next to it, and going beyond the border of the array did not interfere with anyone, but on the contrary, it helped - for example, at the same time checking the contents of the neighboring array in one cycle .

 struct taddummy{ int table[4]; int dummy[4]; } tadam; int exists_in_table(int v) { for (int i = 0; i < 8; i++) { if (tadam.table[i] == v) return true; } return false; } int main() { for (int i = 0; i < 8; i++) { tadam.table[i] =0; } printf("%d\n",exists_in_table(42)); } 

You can believe or check that this code also returns true - from the point of view of UB, nothing has changed in it.

And now, in accordance with the standard, replace tadam.table [i] with * (tadam.table + i) .

 int exists_in_table(int v) { for (int i = 0; i < 8; i++) { if (*(tadam.table+i) == v) return true; } return false; } int main() { for (int i = 0; i < 8; i++) { *(tadam.table+i)=0; } printf("%d\n",exists_in_table(42)); } 

Run the program and make sure that the exists_in_table now returns 0, that is, the number 42 in our arrays and the truth is not. In fact, everything is not as it actually is.

And this is simply explained - according to the C standard, the use and dereference of pointers also has its own UB cases - reference to reallocated memory, dereferencing of the null pointer, etc. and etc. ... but there is no such thing as an "out of array" and there can be no - pointers they know nothing about arrays, so they behave in quite the expected way.

That is, contrary to a common misconception, the array index and the corresponding pointer for the compiler are not the same thing, it is more like an electron, which sometimes displays the properties of a particle (within the array boundaries), and sometimes - waves (in the UB region). ).

Moreover, this analogy can be further developed: if we are surprised at the presence of 42 in the array, we ask the exists_in_table to indicate a specific element number with a value of 42, changing its code to

 if (table[i] == v) return i; 

or, leaving this line unchanged, simply insert the output of the corresponding table [i] element in front of it, then, with the array remaining outside the array, the UB effect completely disappears - the function returns false, which is absolutely equivalent to having an observer in the experiment with electrons - there are no waves in his presence, only hardcore, only particles.

Now, if we move to a higher energy level - to distract from arrays and pointers and even UB, and look at the behavior of the compiler as a whole, then this effect will continue.

For example, part of my work at Intel is to optimize the performance of critical components in third-party code. Since this code is a commercial secret, usually after the completion of the project I get killed, I get only a function from several dozens of lines from them, which is proposed to be accelerated. And, since usually the function itself works for such an insignificant length of time that no profiler will show it with sufficient accuracy, and it is simply a “bottleneck” in the code because of millions of its calls, to evaluate the optimization result I have to use something like

  i1 = __rdtsc(); for (i = 0; i < 100000;i++) { performance_test(); } i2 = __rdtsc(); 

But it is “something like”, and not this particular code. If we use an optimizing compiler for the code fragment above, then it will simply reduce the entire cycle to a single iteration, throwing out all the others, and the execution time will be far from what was expected. To honestly complete the whole cycle, we have to bring something out, or just refer to the volatile variable, which is also a form of interaction with the outside world:

 volatile res = performance_test();//  . 

That is, in the person of the optimizing compiler, we have a system that behaves according to strange, counterintuitive laws (but laws!), For which only external manifestations are important, and the internal state can be considered anything, even indefinite, and most importantly - for any attempt to observe internal state, the magic disappears and the system begins to behave dull and predictable, as in the textbook.



But this is the quantum mechanics from the word "absolutely" - from Schrödinger's cat (number 42), which we are looking for going beyond the array, and have not yet looked inwards, then we can assume that everything is there, to any tangled particles and quantum teleportation (for example, invoking a callback function ). And finally, the emergence of a quantum mechanical “observer,” that is, situations when code interacts with something (external), the behavior of which is unknown to the optimizer, decoherence occurs, and the system collapses into classical - deep optimization of this place, which means “ magic "becomes impossible.

It was this couple of previous paragraphs that he began to tell me at the meeting. dibr . Dima connects us with a stormy youth , so I immediately tried to interrupt him, saying that I knew - also completely independently and repeatedly thought about it. But stopping Dima is not so easy, and sometimes it's very cool.

So, continued dibr , - “this means that quantum mechanics in our universe was possible only because of our world” .... And then I came to the end of the phrase, which I repeated with him in chorus - “it was assembled with deep optimization. That is, we live in the final release, not in the debug version! ”

Which, on the one hand, of course, pleases - although the behavior of the debug version is completely predictable, but in it, in the process of work, usually there are an order of magnitude more bugs. But, on the other hand, it is puzzling: firstly, optimization is needed where iron resources are sufficiently abutting without a reserve, and our future, given the possible development of civilization, is very vague. And secondly, it turns out that according to the documentation of the development of the Universe it was assumed that only classical mechanics would be available to us - that is, nothing more than arithmometers, and the current rapid development of electronics in general and computers in particular is due to the fact that we discovered internal features Universe ”associated with deep optimization, were able to understand their system, and create, in fact, exploits that use them to our advantage.

In this concept, it becomes clear why quantum mechanics is so unobvious and "inhuman" - it should not be like that, because it is a "hack" of the insides of the universe not intended for our eyes, and the standard interface to the world is classical mechanics, in which everything is simple and is logical.

And, in conclusion, I will quote Dmitry again: “And now the Developer of the Universe, probably, is sitting at the terminal, in a stupor from what is happening (he was expecting a sluggishly developing civilization with classical physics, and not this explosive development and“ hacking of the universe ”) , but the process does not interrupt: first, a lot of counting resources have already been invested, it’s a pity to throw out, and secondly, the development branch is interesting, you can watch, you see, a nontrivial result for an article on universe science will turn out, again - when you compile the next universe it will be clear what to avoid."