Как я вошёл в клуб бага 323

Это история о баге, который бы заставил вас рвать на себе волосы. Из-за такого бага вы можете подумать: «Но это невозможно, должно быть, компилятор сломался, других вариантов нет!»

А баг компилятора — это серьёзно: за двенадцать лет программирования на C++ я обнаружил (и написал отчёт) всего... об одном. И могу сказать, что перед отправкой отчёта о баге GCC я максимально тщательно протестировал и проверил его, чтобы не выглядеть идиотом.

Впрочем, ладно, вот моя история.

Открытие

Апрель 2023 года. Выпуск игры запланирован на 15 мая, поэтому это достаточно напряжённый период, я упорно старался уложиться в дедлайн. В основном я работал над «художественной» частью (графика, музыка), но иногда добавлял/исправлял небольшие фрагменты кода.

В то время я по привычке компилировал версию для Windows 32-битным вариантом MinGW: эта привычка появилась у меня из-за инерции старых версий Windows, не поддерживавших 64-битную архитектуру; на самом деле, теперь эта привычка больше особо не нужна. Как только я собрался тестировать игру в Windows, внезапно возник баг. Игра просто начала вылетать. Хм.

Я сравнил исполнение программы с версией для GNU/Linux и быстро нашёл, где она крашилась: различия в исполнении возникали, когда я вычислял граф пола, описывающий то пространство в комнате, где персонаж может ходить.

Говоря простым языком, на этом этапе я создавал из пиксельных значений контур пола, представленный в виде графа. Для этого я начинал с описания краёв пола при помощи достаточно сложной полилинии, описывающей границы пикселей, а затем выполнял алгоритм упрощения полилинии.

В этом алгоритме используется очередь с приоритетами: каждая вершина вставляется в него и сортируется в соответствии с «отклонением», то есть расстоянием от вершины до отрезка, соединяющего две соседние ей вершины. Вершины с наименьшим «отклонением» вызывают при их удалении наименьшее «искажение» полилинии, поэтому мы начинаем с их удаления.

Когда мы больше не можем удалить вершину, не вызвав искажения ниже определённого значения, то останавливаемся: на практике это позволяет нам быстро находить простую полилинию, достаточно точно повторяющую края пола.

Я осознал, что по какой-то странной причине спустя несколько итераций алгоритм в Windows начинает отличаться от алгоритма в GNU/Linux (он удаляет другую вершину, в конечном итоге удаляя вершины, которые не должны быть удалены, приводя таким образом к вылету). И это какое-то безумие, ведь алгоритм детерминирован: если передавать ему одно и то же входное изображение, то он должен возвращать одну и ту же полилинию, удалив точно такие же вершины в точно том же порядке.

В то время я немного ругался на Windows/MinGW, потому что многократно перечитав и перепроверив свой код, я подозревал наличие бага компилятора. Но осознав потом основную разницу (мой MinGW был 32-битным, а GCC в Gnunux был 64-битным) я попытался скомпилировать код в GNU/Linux, но в 32-битном режиме... и вуаля. Баг появился. Я попробовал Clang. Тот же баг.

Я решил, что баг, который возникает во многих компиляторах, не может быть багом компилятора. Ха-ха. Я и представления не имел...

Ядро бага

Моя очередь с приоритетами на самом деле представлена std::set (множеством уникальных элементов, хранящихся в отсортированном виде), что позволяет мне удалять элементы, не находящиеся в начале очереди. Тонкость заключается в том, что мы добавляем set адаптированную функцию сравнения.

Сравнение — это первое действие для отклонения, о котором я говорил: когда мы вставляем вершину в set, мы хотим, чтобы вершины с наименьшим отклонением находились в начале set. Давайте сделаем это :

bool operator() (const GVertex& a, const GVertex& b)
{
  double da = deviation(a);
  double db = deviation(b);
  return da < db;
});

Но внимание, опасность! Две вершины могут иметь одинаковое отклонение, что в std::set, гарантирующем уникальность элементов, означает, что в очередь с приоритетами будет вставлена только первая вершина. Очевидно, мы должны иметь возможность добавлять в очередь с приоритетами две вершины с одним отклонением. Разумеется, в таком случае нам неважно, какая из вершин удаляется первой, поэтому мы просто возьмём первую вершину в графе (вершины сравниваются согласно их индексам), чтобы процесс был детерминированным.

Таким образом, функция приобретает следующий вид:

bool operator() (const GVertex& a, const GVertex& b)
{
  double da = deviation(a);
  double db = deviation(b);
  if (da == db)
    return a < b;
  return da < db;
});

Я быстро понял, что проблема находится в этой функции: в какой-то момент if() возвращает true в 64-битном режиме и false в 32-битном.

Отступление о проверках равенства для double

Здесь я должен сделать отступление. Мне пришла в голову плохая идея выложить этот фрагмент кода онлайн. Вы не поверите, сколько я получил комментариев, смысл которых сводился к следующему:

Ну конечно, ты выполняешь проверку равенства для double! Никогда так не делай! В этом и заключается проблема!

Пф-ф-ф, никогда В ЖИЗНИ не проверяй равенство double: если хочешь сравнивать, сравнивай разность с небольшим допуском!

Два double никогда не равны! Разумеется, если ты выполняешь проверку равенства double, то напрашиваешься на неприятности.

Этот список можно продолжать долго.

Что ж.

Меня немного вывела из себя необходимость отвечать на пятнадцать сообщений от людей, которые просто выучили, что «равенство double = опасность» и набросились на меня, не попробовав разобраться, что делает код. И не подумав, что, возможно, я понимаю в этом немного лучше, и о том, что НЕТ, причина была не в этом.

Для протокола: прежде чем стать разработчиком видеоигр, я написал диссертацию по вычислительной геометрии, а потом шесть лет работал в компании, разрабатывавшей ПО для вычислительной геометрии. В частности, я использовал такие библиотеки, как MPFR, которые позволяют выполнять вычисления с многократной точностью, чтобы избежать связанных с double проблем при работе с вещественными числами. Пожалуйста, поверьте мне, когда я говорю, что знаю, на что иду, когда сравниваю double.

Ну да ладно. Если вы тоже увидели проверку равенства double и подумали «лол, нуб, разумеется, проверки равенства с double не работают», то я должен высказаться прямо:

1. Проверки равенства с double допустимы, это не табу и не Волан-де-морт, у вас есть право писать их, мир не рухнет, если вы сделаете это, вам разрешается это делать. Конечно, если вы знаете, что делаете.

2. Проверка равенства double вызывает проблемы, только если вы думаете, что проверяете равенство между вещественными числами (в математическом смысле). Да, при работе с double 1.0/2.0 необязательно равно 0.5, потому что конечная точность означает, что другое описание одного вещественного числа может дать немного отличающиеся значения. С другой стороны (и я настаиваю на этом): 1.0/2.0 гарантированно равно 1.0/2.0; 0.5 гарантированно равно 0.5; да, ДАЖЕ в случае double. Я имею в виду, что если у вас есть два double с одинаковым значением (в компьютерном смысле, то есть с одинаковыми битами в одинаковых байтах), вычисленные абсолютно одинаковым образом, то проверка равенства между этими двумя double вернёт TRUE. И спасибо Вселенной за это!

3. В моём случае всё было даже проще: нас не интересует случай равенства двух double, это просто особый случай, который мы подготовили, чтобы обезопасить себя, потому что если два double различаются, то всё ещё проще. Представим, что вы правы и что «два double никогда не равны» (что, разумеется, совершенно неверно): в таком случае проблем нет, потому что if никогда не будет true, и алгоритм всегда будет использовать в качестве приоритета отклонение. На практике, поскольку полилинии составляются из обычных пикселей, разумеется, существует множество равных отклонений...

4. Использовать допуск? Простите, вы или не прочитали код, или совсем его не поняли. Что произойдёт, если вместо сравнения da и db я выполню do if(std::fabs(da-db)<epsilon)? Если две вершины имеют близкие отклонения, то вместо сортировки их по отклонению мы отсортируем их по индексам. ОТЛИЧНО. В чём смысл, кроме как в снижении оптимальности алгоритма?

Всегда стоит быть аккуратными со сравнениями double, но лучше понимать, почему конкретно и в каких случаях. А ещё было бы здорово, если бы вы сначала поняли код, прежде чем писать комментарии по темам, которые в буквальном смысле изучают в первый год курса программирования.

Отступление завершено.

Сдаюсь

Я потратил на работу с этим багом целый день. Я торопился закончить игру, был в стрессе, но как бы ни исследовал проблему, я просто не мог в ней разобраться. Не говоря уже о том, чтобы устранить её. Ну, на самом деле, я мог. Я мог устранить её множеством способов, которые не имели никакого смысла:

1. Отключив оптимизации компилятора

2. Добавив к сравнениям std::cerr (баг Шрёдингера: он исчезает, когда ты за ним наблюдаешь)

3. Предварительно сохраняя значения отклонений, а не вычисляя их на ходу (нет, они не меняются, я проверял)

4. Целой кучей других странных действий (например, объявлением ещё одной переменной посередине сравнения).

Если вкратце: 64 бит? Без проблем. 32 бит без оптимизаций? Без проблем. 32 бит с оптимизациями? Бум, ошибка.

На этом этапе я видел в отладчике буквально следующее:

1. Программа определяет равенство между double как false (а это ошибка)

2. Не входит в if()

3. Затем определяет неравенство между double как false (что верно, но противоречит пункту 1.)

Всё это пахнет багом компилятора. Только, как я сказал, ошибка возникала и в GCC, и в Clang. Два разных компилятора с одним багом? Маловероятно.

Я потерял день, но не добился никакого прогресса. Более того, баг возникал только в development-версии игры (и в 32-битной версии, которую я вообще не собирался распространять): в продаваемой версии этот граф пола вычисляется предварительно. То есть в целом этот баг ни на что не повлияет, но меня ужасно раздражало, что я его не понимаю.

В конечном итоге я сдался: я потратил на это слишком много времени, а мне нужно было закончить игру. Было решено, что я вернусь к багу после релиза.

Возвращаемся к багу

Я уложился в дедлайн и выпустил игру 15 мая.

Перенесёмся во вчерашний день: в середине августа наступило затишье, поэтому я решил со свежей головой вернуться к этому багу.

Большая проблема этого бага заключалась в том, что он находился посередине очень большой программы (игрового движка) со множеством сложных файлов и зависимостей. Поэтому в этом случае нужно было максимально изолировать часть с багом, чтобы убедиться, что он не возникает из-за чего-то более запутанного (например, утечка памяти в другой части игры могла бы приводить к записи в очередь с приоритетами мусорных данных).

Я работал над ним так:

1. Вытащил вычисление графа из игрового движка: мы загружаем изображение и выполняем только вычисление графа, устранив бесполезные зависимости (LZ4, YAML)

2. Максимально уменьшил изображение до маленького графа

3. В конечном итоге я просто прописал граф в коде (мне удалось воспроизвести баг всего с 16 вершинами вместо 3900), поэтому загрузка изображения больше не требовалась и я удалил зависимость от SDL

4. Я избавился от своей геометрической мини-библиотеки, оставив две или три полезные функции из неё.

5. Максимально уменьшил очередь с приоритетами, ошибка начала возникать после вставки второй вершины.

В конце у меня получилась вызывающая баг программа из пятидесяти строк без зависимостей, за исключением STL. Вот она:

#include <array>
#include <cmath>
#include <iostream>
#include <set>

using double2 = std::array<double, 2>;

struct Comparator
{
  static double deviation (double2 p)
  {
    const double2 p0 { 1, 0 };
    const double2 vp0p1 { -1 / std::sqrt(2), 1 / std::sqrt(2) };
    const double2 vp0p { p[0] - 1, p[1]};
    const double dotprod = vp0p1[0] * vp0p[0] + vp0p1[1] * vp0p[1];
    const double2 proj { 1 + dotprod * vp0p1[0], p0[1] + dotprod * vp0p1[1] };
    return std::sqrt ((proj[0] - p[0]) * (proj[0] - p[0]) +
                      (proj[1] - p[1]) * (proj[1] - p[1]));
  }

  bool operator() (const double2& a, const double2& b) const
  {
    const double da = deviation(a);
    const double db = deviation(b);
    if (da == db)
      return a < b;
    return da < db;
  }
};

void insert (std::set<double2, Comparator>& set, double2 point)
{
  const double deviation = Comparator::deviation(point);

  std::cerr << "Inserting " << std::defaultfloat << point[0] << " " << point[1]
            << " with deviation = " << deviation << " / hex="
            << std::hexfloat << deviation << std::endl;
  if (set.insert (point).second)
    std::cerr << " -> Success" << std::endl;
  else
    std::cerr << " -> Failure" << std::endl;
}

int main (int, char**)
{
  std::cerr.precision(18);
  std::set<double2, Comparator> set;
  insert(set, { 0, 0 });
  insert(set, { 1, 1 });
  return EXIT_SUCCESS;
}

По сути, эта программа вставляет две точки в std::set с использованием функции сравнения: эти точки отличаются ((0,0) и (1,1)), но имеют одинаковое значение отклонения (равное корню из двух, делённому на два).

После компиляции этой программы в 64-битном режиме результат оказывается таким:

Inserting 0 0 with deviation = 0.707106781186547573 / hex=0x1.6a09e667f3bcdp-1
-> Success
Inserting 1 1 with deviation = 0.707106781186547573 / hex=0x1.6a09e667f3bcdp-1
-> Success

И это нужный результат.

Компилируем программу в 32 битах со включенным хотя бы -O1 (-O2 при использовании Clang), и получаем:

Inserting 0 0 with deviation = 0.707106781186547573 / hex=0x1.6a09e667f3bcdp-1
-> Success
Inserting 1 1 with deviation = 0.707106781186547573 / hex=0x1.6a09e667f3bcdp-1
-> Failure

Вторая точка не вставляется, тут есть баг.

Это совершенно точно.

На этом этапе я уже был более уверен в том, что мой код верен, а баг в компиляторе. Я и чётко определил, в чём же ошибка.

Затем я загуглил «c++ O1 optimization double comparison bug branch». И получил ответ.

Печально известный баг 323 GCC

Баг GCC номер 323 под названием «оптимизированный код даёт странные результаты работы с плавающей запятой» датируется ещё 14 июня 2000 года. На момент написания моей статьи под ним уже 229 комментариев, 101 из которых помечен как дубликат (другой баг, который запостил кто-то другой, но на самом деле являющийся тем же). Неплохое начало.

Если этот баг с нами уже так долго, то на самом деле это не баг компилятора: это баг процессора. Да, всё верно.

Если точнее, то это поведение FPU (Floating-Point Unit), вызывающее неожиданное поведение при оптимизации кода.

Смысл в том, что вычисления над числами с плавающей запятой могут выполняться с разной точностью: в ОЗУ числа float имеют 32-битную точность, уже известные нам double — точность 64 бит (и в самом деле, двойная точность)... а вычисления в FPU используют регистры процессора с точностью 80 бит. Эта дополнительная точность во время вычислений минимизирует погрешность округления.

Что же происходит в моём коде? Когда код не оптимизируются, FPU вычисляет значение отклонения для каждой из двух вершин с точностью 80 бит (в регистрах процессора), а затем сохраняет их в 64-битную переменные double в ОЗУ (а потому округляет их, ведь точность снижается) для каждой из двух вершин. Пока всё хорошо.

Но когда код оптимизируется, компилятор понимает, что при вычислении второго отклонения нет смысла помещать его в ОЗУ (что затратно с точки зрения времени исполнения), потому что оно сразу же будет использовано: его вполне можно оставить в регистре процессора и использовать напрямую. Только оно не будет преобразовано в 64 бита, а значит, имеет бОльшую точность, чем отклонение первой вершины. То есть и другое значение. Вот и всё: значения, которые должны быть равными, становятся различными, потому что одно округлили до 64 бит, а другое нет.

Это объясняет, почему баг пропадает, если выполняю в коде, казалось бы, не связанные с ним действия (объявляю ещё одну переменную, добавляю std::cerr и так далее): заставив процессор выполнять в это время что-то ещё, мы просто заставляем сохранить второе отклонение в ОЗУ, что решает проблему.

Очевидно, это поведение было исправлено в последующих поколениях FPU, чтобы соответствовать стандарту IEEE-754, требующему, чтобы вычисления с плавающей запятой были детерминированными. Но поскольку проблема находится внутри процессора, этот баг встречается и в GCC, и в Clang (а также, вероятно, и в других компиляторах). И этот знаменитый баг 323 продолжают регулярно комментировать и дублировать, хотя, строго говоря, это не баг GCC.

Я во многом согласен с этим комментарием:

Вызов тривиальной функции с одинаковым параметром может вернуть значение меньшее, равное или большее чем оно само (в зависимости от распределения регистров в контексте вызовов). Это крайне неприятное недетерминированное поведение. Разве компиляторы и высокоуровневые языки изобрели не для того, чтобы решать именно такие проблемы с аппаратными зависимостями?

И, наконец, небольшой комментарий, который рассмешил меня, потому что он как будто обращается напрямую ко мне:

Мне хотелось бы поприветствовать новых участников сообщества бага 323, в которое приходят умирать все ошибки x87 с плавающей точкой в gcc! Сюда принимают все ошибки с плавающей запятой при использовании x87, несмотря на то, что многие из них легко устранить, а многие нет! Мы — одна большая семья, совершившая очевидную ошибку, возжелав точности от самого точного FPU общего назначения на рынке!

Как это исправить?

Разобравшись, почему может возникать такое поведение, мы должны ответить на практический вопрос: как помешать коду выполнять такое поведение?

Что ж, есть сложное решение: можно воспользоваться опцией -ffloat-store времени компиляции. Эта опция в буквальном смысле заставляет компилятор сохранять все float в ОЗУ (таким образом, делая ошибку невозможной). Да, конечно, это решает проблему, но не позволяет использовать множество потенциально интересных оптимизаций (возможность не сохранять float в ОЗУ, когда это не нужно, даёт очень много преимуществ и в 99% случаев безопасно).

Гораздо более уточнённый способ (потому что его можно интегрировать только в потенциально проблематичные места кода, обычно в проверки равенства double) — это использование ключевого слова «volatile». Процитирую Википедию : «это ключевое слово предотвращает оптимизацию компилятором последовательных операций чтения или записи». Всё довольно просто: оптимизации деактивируются локально, а не глобально.

Для этого достаточно лишь изменить функцию сравнения следующим образом:

  bool operator() (const double2& a, const double2& b) const
  {
    const volatile double da = deviation(a);
    const volatile double db = deviation(b);
    if (da == db)
      return a < b;
    return da < db;
  }

После этого баг пропадёт. Можете попробовать сами: теперь код работает даже в 32-битном режиме с оптимизациями.

ПОБЕДА!

Заключение

Я думал, что баги компилятора — это худшее, что может случиться в программировании (потому что их ожидаешь меньше всего): я ошибался, баги процессора хуже.

Несмотря на то, что я потратил на этот баг много часов, меня радует одно: я был достаточно упорен, чтобы наконец-то разобраться в происходящем. А вишенкой на торте стало простое и оптимальное исправление (использование volatile).

В завершение дам совет: если вы столкнётесь с багом, то не сдавайтесь, пока не доберётесь до первопричин проблемы (конечно, если у вас есть на это время, которое часто бывает ограничением). Часто вам будет удаваться понять реальную проблему в своём коде; иногда вы узнаёте что-то новое о процессорной оптимизации, а такое случается не каждый день.