Мне вот эта статья нравится по теме. Написана старшим инженером по программным решения Intel.
https://habr.com/ru/company/intel/blog/351406/Массивы, указатели и другие квантовые явления вокруг нас
Не хочу говорить, что мы все живем в матрице, но для имитации соседей подозрительно используется один и тот же звук катающегося шара.
Этот пост полностью соответсвует своему названию. Для начала в нем будет показано, что вопреки утверждению стандарта, а также классиков языка Си Кернигана и Ритчи, использование индексов массивов соверешенно не равнозначно использованию соответствующих указателей, а выбор эпиграфа будет понятен в самом конце. И да – середина поста тоже не пустая.
Все началось с опровержения теоремы Ферма и нахождения числа с косинусом, превышающим единицу с сильно задумывающего поста про неопределенное поведение компилятора (undefined behavior или UB). То есть, таких постов было несколько, но в этом (перевод на habrahabr) приводился следующий простейший код и далеко не очевидный результат его работы:
int table[4];
bool exists_in_table(int v) {
for (int i = 0; i <= 4; i++) {
if (table[i] == v) return true;
} return false;
}
В условии цикла есть ошибка: "<= 4" вместо "< 4".
Теперь если заполнить table нулями, и даже позаботиться о том, чтобы нелегальный пятый элемент этого массива был 0, а потом хорошенько поискать в таблице число 42, т.е. вызвать exists_in_table(42), то оно там обязательно найдется — в случае хорошо оптимизирующего компилятора С эта функция в полном соответствии со стандартом языка вернет true!
Объясняется это просто: exists_in_table() либо должна вернуть true на одной из первых четырёх итераций, либо она прочтёт table[4], что является UB, и в этом случае exists_in_table() по стандарту языка С может сделать всё что угодно — в том числе, и вернуть true. То есть, компилятор может соптимизировать весь код exists_in_table() до return true;
И это не абстрактная теория, а конкретная практика. Именно так оптимизирует код, т.е. exists_in_table(42) возвращает true при компиляци, например, gcc 6.3 (через MinGW) с использованием опций -O2 или -O3. Все результаты ниже относятся именно к этой конфигурации.
А теперь давайте хоть однажды в жизни еще раз почитаем стандарт С.
Да, в разделе, посвященном массивам, он честно предупреждает, что доступ к элементам за границами массива – это UB. Но, как знает каждый, кто когда-либо изучал С, доступ к элементам массива возможен через указатели, или, языком стандарта ISO/IEC 9899 «определение оператора взятия индекса [] таково: E1[E2] эквивалентно (*((E1)+(E2))).» («The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))»).
И тут обнаруживается кое-что интересное. «Идентично» — то есть, тождественно, взаимозаменяемо при любых обстоятельствах. И даже при UB? Давайте узнаем, что будет, если в примере выше для доступа к элементам массива использовать указатели.
Но сначала сделаем код реально безопасным, для чего завернем массив table в структуру так, чтобы рядом с ним гарантированно было выделенное нами место, и заход за границу массива никому не мешал, а наоборот, помогал – например, заодно проверить содержимое соседнего массива за один цикл.
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));
}
Можете поверить или проверить, что данный код также вернет true – с точки зрения UB в нем ничего не изменилось.
А теперь, в соответствии со стандартом, заменим tadam.table[i] на *(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));
}
Запустим программу и убедимся, что теперь exists_in_table возвращает 0, то есть, числа 42 в наших массивах и правда нет. В действительности все не так, как на самом деле.
И объясняется это просто – по стандарту C у использования и разыменования указателей тоже есть свои случаи UB – обращение к реаллоцированной памяти, разыменование нулевого указателя и тд и тп… но никакого случая «выхода за границы массива» среди них нет и быть не может – указатели про массивы ничего не знают, вот и ведут себя вполне ожидаемым образом.
То есть, вопреки общему заблуждению, — индекс массива и соотвествующий ему указатель для компилятора – это совершенно не одно и то же, это скорее – как электрон, который иногда проявляет свойства частицы (в границах массива), а иногда – волны (в области UB).
Причем, данную аналогию можно развить и дальше: если мы, удивившись наличию 42 в массиве, попросим у exists_in_table указать конкретный номер элемента со значением 42, соответственно изменив ее код на
if (table[i] == v) return i;
или, оставив эту строку без изменений, просто вставим перед ней вывод на экран значения соответствующего элемента table[i], то при сохраняющемся выходе за границы массива, эффект UB полностью исчезает – функция вернет false, что абсолютно эквивалентно наличию наблюдателя в эксперименте с электронами – в его присутствии никаких волн, а только хардкор, только частицы.
Теперь, если перейти на более высокий энергетический уровень — отвлечься от массивов и указателей и даже UB, и посмотреть на поведение компилятора в целом, то данный эффект сохранится.
Например, часть моей работы в Intel состоит в оптимизации производительности критических компонент в коде сторонних разработчиков. Так как этот код является коммерческим секретом, то обычно после завершения проекта меня убивают я получаю от них только функцию из нескольких десятков строк, которую и предлагается ускорить. И, так как обычно функция сама по себе работает столь ничтожный отрезок времени, что его с достаточной точностью не покажет ни один профилировщик, а «узким местом» в коде она является просто из за миллионов ее вызовов, то для оценки результата оптимизации мне приходится использовать что-то типа
i1 = __rdtsc();
for (i = 0; i < 100000;i++) {
performance_test();
}
i2 = __rdtsc();
Но именно «что-то типа», а не этот конкретный код. Если использовать для фрагмента кода выше оптимизирующий компилятор, то он просто сведет весь цикл к единственной итерации, выкинув все остальные, и время исполнения будет далеко от ожидаемого. Для честного выполнения всего цикла мы должны что-то выводить наружу, либо просто обращаться к volatile переменной, что тоже является формой взаимодействия с внешним миром:
volatile res = performance_test();// приглашенный наблюдатель.
То есть, в лице оптимизирующего компилятора мы имеем систему, ведущую себя по странным, контринтуитивным законам (но законам!), для которой важны только внешние проявления, а внутреннее состояние можно считать любым, даже неопределенным, а главное – при любой попытке наблюдения за этим внутренним состоянием, магия пропадает и система начинает вести себя скучно и предсказуемо, как в учебнике.
Но это же квантовая механика от слова «совсем» — от кота Шредингера (числа 42), которого мы ищем с выходом за границы массива, и пока не посмотрели внутрь, то можно считать, что там всё что угодно, до каких-нибудь спутанных частиц и квантовой телепортации (например, вызова невызываемой функции). И, наконец, появление квантовомеханического «наблюдателя», то есть ситуации, когда при взаимодействии кода с чем-то (внешним), поведение чего оптимизатору неизвестно, происходит декогеренция, и система схлопывается к классической — глубокая оптимизация этого места, а значит, и «магия» становится невозможной.
Именно эту пару предыдущих абзацев начал рассказывать мне при встрече dibr. Нас с Димой связывает бурная юность, так что я сразу попробовала прервать его, сказав, что я в курсе – тоже совершенно независимо и неоднократно об этом думала. Но остановить Диму не так просто, и иногда это очень здорово.
Так вот, продолжал dibr, — «это означает, что квантовая механика в нашей вселенной оказалась возможной только потому, что наш мир» …. И тут до меня дошло окончание фразы, которую я повторила с ним хором – «был собран с глубокой оптимизацией. То есть, мы живем в финальном релизе, а не в отладочной версии!»
Что, с одной стороны, конечно, радует — хотя поведение отладочной версии и полностью предсказуемо, но в ней, в процессе работы, обычно, багов на порядок больше. Но, с другой стороны, это озадачивает: во-первых, оптимизация нужна там, где ресурсов железа хватает «впритык» без запаса, и наше будущее с учетом возможного развития цивилизации весьма туманно. А во-вторых, получается, что по документации разработки Вселенной предполагалось, что нам будет доступна только классическая механика — то есть, не более чем арифмометры, а современное бурное развитие электроники вообще и компьютеров в частности, вызвано тем, что мы обнаружили внутренние «фичи Вселенной», связанные с глубокой оптимизацией, смогли понять их систему, и создать, фактически, эксплойты, применяющие их нам на пользу.
В этой концепции становится понятно, почему квантовая механика такая неочевидная и «нечеловеческая» — она и не должна быть такой, ведь это «взлом» не предназначенных для наших глаз внутренностей вселенной, а штатный интерфейс к миру — классическая механика, в которой всё просто и логично.
И, в заключение, еще раз процитирую Дмитрия: «А сейчас Разработчик Вселенной, наверное, сидит за терминалом, в ступоре от происходящего (он-то ожидал вяло развивающуюся цивилизацию с классической физикой, а не а это взрывное развитие и «взлом вселенной»), но процесс не прерывает: во-первых, уже много счётных ресурсов вложено, жалко выкидывать, а во-вторых — ветка развития-то интересная, можно и понаблюдать, глядишь нетривиальный результат для статьи по вселеннологии получится, опять же — при компиляции следующей вселенной понятно будет чего избегать.»
yaplakal.com