Браузер и числа с плавающей запятой

_{Изображение — www.freepik.com}

Несколько лет назад я много думал и писал о математике с плавающей запятой. Это было очень интересно, и в процессе исследований я многое узнал, но иногда я долгое время не использую на практике все эти полученные тяжким трудом знания. Поэтому мне необыкновенно приятно каждый раз, когда приходится работать над багом, требующим различных специализированных знаний. В статье я расскажу три истории о багах чисел с плавающей запятой, изученных мной в Chromium.

Часть 1: нереальные ожидания

Баг назывался «JSON некорректно парсит 64-битные Integer»; поначалу это непохоже на проблему с плавающей запятой или браузером, но его отправили на crbug.com, поэтому меня попросили взглянуть. Проще всего воссоздать его, открыв инструменты разработчика Chrome (F12 или Ctrl+Shift+I) и вставив в консоль разработчика следующий код:

json = JSON.parse(‘{“x”: 2940078943461317278}’); alert(json[‘x’]);

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

Каково ожидаемое поведение? Должно возвращаться целочисленное значение 2940078943461317278.
В чём ошибка? Вместо него возвращается целочисленное 2940078943461317000.

«Баг» обнаружили под Linux, а я работаю над Chrome для Windows, но это поведение кроссплатформенное, а у меня были знания о числах с плавающей запятой, поэтому я его исследовал.

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

Вводимое число довольно велико, оно примерно равно 2.9e18. И в том-то и проблема. Поскольку в JavaScript нет типа integer, он использует для чисел IEEE-754 floating-point double-precision. Этот двоичный формат с плавающей запятой имеет бит знака, 11-битную экспоненту и 53-битную мантиссу (да, это 65 бит, один бит прячется благодаря магии). Этот тип double так хорошо подходит для хранения integer, что многие программисты на JavaScript никогда не замечали, что типа integer нет. Однако очень большие числа разрушают эту иллюзию.

Число JavaScript может с точностью хранить любое целое значение до 2^53. После этого оно может хранить все чётные числа до 2^54. А после этого оно может хранить все кратные четырём числа до 2^55, и так далее.

Проблемное число выражено в экспоненциальной записи по основанию 2, оно примерно равно 1,275 * 2^61. В этом интервале можно выразить только очень малое количество целых чисел — расстояние между числами равно 512. Вот три соответствующих числа:

• 2 940 078 943 461 317 278 — число, которое хотел сохранить автор отчёта о баге
• 2 940 078 943 461 317 120 — ближайшее к этому числу double (меньше него)
• 2 940 078 943 461 317 632 — следующее ближайшее к числу double (больше него)

Нужное нам число находится в промежутке между этими двумя double и модуль JSON (например сам JavaScript или любая другая корректно реализованная функция преобразования текста в double) сделал всё возможное и вернул ближайшее double. Проще говоря, число, которое хотел сохранить автор отчёта, нельзя сохранить во встроенном числовом типе JavaScript.

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

2 940 078 943 461 317 000

Ситуация любопытная, потому что это не введённое число, не ближайшее double и, на самом деле, даже не число, которое можно представить как double!

Эта загадка тоже объясняется спецификацией JavaScript. В спецификации сказано, что при печати числа реализация должна выводить достаточное для его уникальной идентификации количество цифр, и не больше. Это удобно при печати чисел наподобие 0,1, которые невозможно точно представить в виде double. Например, если бы JavaScript требовал, чтобы 0,1 выводилось как хранимое значение, то он бы вывел:

0.1000000000000000055511151231257827021181583404541015625

Это будет точным результатом, но такое бы просто сбивало людей с толку, не добавляя ничего полезного. Конкретные правила можно найти здесь (ищите строку «ToString Applied to the Number Type»). Не думаю, что спецификация требует конечных нулей, но она определённо их допускает.

Итак, при работе программы JavaScript выводит 2 940 078 943 461 317 000, потому что:

• Значение исходного числа было потеряно при сохранении в виде числа JavaScript
• Выводимое число достаточно близко к хранимому значению, чтобы уникально идентифицировать его
• Выводимое число — это простейшее число, уникальным образом идентифицирующее хранимое значение

Всё работает, как и должно, это не баг, проблема закрыта как WontFix («неисправимая»). Исходный баг можно найти здесь.

Часть 2: плохой эпсилон

В этот раз я на самом деле устранил баг, сначала в Chromium, а потом в googletest, чтобы избавить от путаницы будущие поколения разработчиков.

Этот баг был недетерминированным сбоем теста, который начал происходить внезапно. Мы ненавидим такие нечёткие сбои тестов. Особенно они сбивают с толку, когда начинают происходить в тесте, который не менялся годами. Спустя несколько недель к расследованию привлекли меня. Сообщения об ошибках (немного изменённые для длины строк) начинались примерно так:

The difference between expected_microseconds and converted_microseconds is 512, which exceeds 1.0 [Разность между expected_microseconds и converted_microseconds равна 512, что превышает 1.0]

Да, звучит плохо. Это сообщение об ошибке googletest, говорящее, что два значения с плавающей запятой, которые расстояние между которыми должно быть не больше 1.0, на самом деле отдалены друг от друга на 512.

Первой уликой стала разность между числами с плавающей запятой. Казалось очень подозрительным, что два числа разделены ровно значением 2^9. Совпадение? Не думаю. Оставшаяся часть сообщения, в которой указывались два сравниваемых значения, ещё сильнее убедили меня в причине:

expected_microseconds evaluates to 4.2934311416234112e+18,
converted_microseconds evaluates to 4.2934311416234107e+18

Если вы достаточно долго боролись с IEEE 754, то сразу же поймёте, что происходит.

Вы прочитали первую часть, поэтому можете ощутить дежавю из-за одинаковых величин чисел. Однако это чистое совпадение — я просто использую те числа, с которыми столкнулся. На этот раз они выводились в экспоненциальном формате, что немного разнообразит статью.

Основная проблема является вариацией проблемы из первой части: числа с плавающей запятой в компьютерах отличаются от используемых математиками вещественных чисел. При увеличении они становятся менее точными, и в интервале чисел непройденного теста все значения с двойной точностью обязательно были кратными 512. Double имеет 53 бит точности, а эти числа были намного больше 2^53, поэтому значительное снижение точности было неизбежным. И теперь мы можем понять проблему.

Тест вычислял одинаковое значение двумя разными способами. Затем он проверял, близки ли результаты, причём под «близостью» подразумевалась разность в пределах 1.0. Способы вычислений давали очень схожие ответы, поэтому в большинстве случаев результаты округлялись до одинакового значения с двойной точностью. Однако время от времени правильный ответ оказывается рядом с перегибом, и одно вычисление округляет одним образом, а второе — другим.

Если конкретнее, то в результате сравнивались следующие числа:

• 4293431141623410688
• 4293431141623411200

Без экспонент заметнее, что они разделены ровно 512. Два бесконечно точных результата, генерируемых тестовыми функциями, всегда отличались менее чем на 1.0, то есть когда они были значениями типа 429…10653.5 and 429…10654.3, оба округлялись до 429…10688. Проблема возникала, когда бесконечно точные результаты были близки к значению типа 4293431141623410944. Это значение ровно посередине между двумя double. Если одна функция генерирует 429…10943.9, а другая 429…10944.1, то эти результаты, разделённые величиной всего 0.2, округлялись в разных направлениях и оказывались на расстоянии 512!

Такова природа перегиба, или ступенчатой функции. Можно получить два результата, произвольно близкие друг к другу, но находящиеся на противоположных сторонах перегиба — точки ровно посередине между двумя — а потому округляющиеся в разных направлениях. Часто рекомендуется сменить режим округления, однако это не помогает — при этом всего лишь смещается точка перегиба.

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

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

commit 6c2427457b0c5ebaefa5c1a6003117ca8126e7bc
Author: Bruce Dawson
Date: Fri Dec 08 21:58:50 2017

Fix epsilon calculation for large-double comparisons

My whole life has been leading up to this bug fix. [Вся моя жизнь вела меня к устранению этого бага.]

И в самом деле, мне нечасто удаётся внести изменение в Chromium с примечанием к коммиту, в котором вполне обоснованно есть ссылки на два (2!) моих поста.

Исправление в этом случае заключалось в вычислении разности между двумя соседними double с величиной вычисляемых значений. Это было реализовано при помощи редко используемой функции nextafter. Примерно так:

epsilon = nextafter(expected, INFINITY)  –  expected;
if (epsilon < 1.0)
      epsilon = 1.0;

Функция nextafter находит следующее double (в данном случае в направлении бесконечности), а вычитание (которое выполняется точно, и это очень удобно) затем находит разность между double при их величине. Тестируемый алгоритм давал погрешность 1.0, поэтому epsilon должен быть не больше этого значения. Благодаря такому вычислению epsilon стало очень легко проверять, находятся ли значения на расстоянии меньше 1.0 или являются соседними double.

Я так и не изучал причину того, почему тест внезапно начал давать сбои, но подозреваю, что дело в частоте таймера или изменении точки запуска таймера, из-за чего числа стали больше.

Только что проверил. Тест использует несколько симулируемых счётчиков QueryPerformanceCounter (QPC), в том числе <int64>::max(), или 2^63-1. Это нереалистично высокое число, и именно оно приводит к сбоям. Применив вычисления к выводимым ошибкам, можно понять, что при появлении сбоя использовалась частота QPC 2 148 МГц. Когда тест был надёжным, частота QPC, вероятно, была выше, возможно, равной частоте процессора, или около 3 ГГц. При такой высокой частоте QPC тестовое значение 2^63-1 интерпретировалось бы как гораздо более короткое время, что позволило бы избежать такого недетерминированного сбоя.

Следовательно, этот сбой начал проявляться, когда смена машины или ОС снизила частоту QueryPerformanceCounter.

Исправляем googletest

Меня раздражало то, что для понимания проблемы требовались эзотерические знания об особенностях чисел с плавающей запятой, поэтому я захотел исправить googletest. Моя первая попытка закончилась плохо.

Изначально я попробовал исправить googletest, сделав так, чтобы EXPECT_NEAR выдавал сбой при передаче незначимо малого эпсилон, однако, похоже, множество тестов внутри Google, а также, вероятно, гораздо большее количество за пределами Google, неправильно используют EXPECT_NEAR при значениях double. Они передают значение эпсилон, которое слишком мало, чтобы быть полезным, однако сравниваемые ими числа одинаковы, поэтому тест завершается успешно. Я исправил с десяток точек использования EXPECT_NEAR, не приблизившись к решению проблемы, поэтому сдался.

И только при написании этого поста (почти спустя три года после появления бага!) я осознал, как можно безопасно и легко исправить googletest. Если код использует EXPECT_NEAR со слишком малым эпсилон, и тест проходит успешно (то есть значения на самом деле равны), то это не вызывает проблем. Проблемой это становится только тогда, когда тест выдаёт сбой, поэтому мне достаточно было искать слишком малые значения эпсилон только в случае сбоя и отображать при этом информативное сообщение.

Я внёс это изменение и теперь сообщение об ошибке для этого сбоя 2017 года выглядит так:

Разность между expected_microseconds и converted_microseconds равна 512, где
expected_microseconds равно 4.2934311416234112e+18,
converted_microseconds evaluates to 4.2934311416234107e+18.
Параметр abs_error равен 1.0, что меньше минимального расстояния между double для чисел этого порядка величин, равного 512; поэтому эта проверка EXPECT_NEAR становится эквивалентной EXPECT_EQUAL. Рекомендуется использовать вместо неё EXPECT_DOUBLE_EQ.

Следует учесть, что EXPECT_DOUBLE_EQ на самом деле не проверяет равенство, она проверяет, равны ли double в четырёх единицах в последнем знаке (units in the last place, ULP). Подробнее об этой концепции можно прочитать в моём посте Comparing Floating Point Numbers.

Я надеюсь, что большинство разработчиков ПО увидит это новое сообщение об ошибке и выберет нужный путь, и считаю, что исправление googletest в конечном итоге более важно, чем исправление теста Chromium.

Часть 3: когда x+y=x (y != 0)

Это ещё одна вариация проблем с точностью при приближении к границам: возможно, я просто снова и снова нахожу один баг чисел с плавающей запятой?

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

Когда я наткнулся эту проблему, то отправил отчёт о баге с названием "Сбой с ошибкой OOM (Out of Memory) в chrome://tracing при увеличении изображения зумом"; это не походит на баг чисел с плавающей запятой.

Как обычно, я не искал себе проблем, а просто изучал трассировки chrome://tracing, пытаясь понять некоторые события; внезапно появилась печальная вкладка — произошёл сбой.

Просматривать и загружать последние сбои Chrome можно по адресу chrome://crashes, но я хотел загрузить аварийный дамп в отладчик, поэтому посмотрел, где они хранятся локально:

%localappdata%GoogleChromeUser DataCrashpadreports

Я загрузил самый последний аварийный дамп в windbg (подойдёт и Visual Studio), а затем приступил к расследованию. Так как у меня были сконфигурированы серверы символов Chrome и Microsoft, а также включен сервер исходных кодов, отладчик автоматически скачал PDB (отладочную информацию) и необходимые исходные файлы. Учтите, что подобная схема доступна всем — вам не нужно быть сотрудником Google или разработчиком Chromium, чтобы эта магия работала. Инструкции по настройке отладки Chrome/Chromium можно найти здесь. Для автоматического скачивания исходного кода требуется установка Python.

Анализ сбоя показал, что ошибка out-of-memory происходит из-за того, что функция v8 (движка JavaScript) NewFixedDoubleArray пытается выделить массив с 75 209 227 элементами, а максимальный размер, допускаемый в этом контексте, составляет 67 108 863 (0x3FFFFFF в шестнадцатеричном виде).

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

Проблема здесь заключалась в том, что я запросто мог просмотреть стек вызовов для этого сбоя, но только в части кода Chrome на C++. Однако, по видимому, сам баг возникал в JavaScript-коде chrome://tracing. Я попробовал потестировать его с canary-сборкой Chrome (ежедневной) под отладчиком, и получил следующее любопытное сообщение:

==== JS stack trace ======================================

К сожалению, за этой интересной строчкой не шло никакой трассировки стека. Немного побродив в дебрях git, я выяснил, что возможность вывода стеков вызовов JS по OOM была добавлена в 2015 году, после чего удалена в декабре 2019 года.

Я исследовал этот баг в начале января 2020 года (помните те старые добрые времена, когда всё было невинней и проще?), и это значило, что код трассировки стека OOM был удалён из ежедневной сборки, но по-прежнему оставался в стабильной сборке…

Поэтому моим следующим шагом стала попытка воссоздания бага в стабильной версии Chrome. Это дало мне следующие результаты (я немного подредактировал их для понятности):

0: ExitFrame [pc: 00007FFDCD887FBD]
1: drawGrid_ [000016011D504859] [chrome://tracing/tracing.js:~4750]
2: draw [000016011D504821] [chrome://tracing/tracing.js:4750]

Если вкратце, то сбой OOM вызывался drawGrid_, которую я нашёл (при помощи страницы поиска кода Chromium) в x_axis_track.html. Немного похакав этот файл, я сузил проблему до вызова updateMajorMarkData. Эта функция содержит цикл, выполняющий вызов функции majorMarkWorldPositions_.push, которая и является виновницей проблемы.

Здесь стоит сказать, что хотя я и разрабатываю браузер, я остаюсь худшим в мире программистом на JavaScript. Навык системного программирования на C++ не даёт мне магических навыков «фронтендера». Хакинг JavaScript для понимания этого бага был для меня довольно мучительным процессом.

Цикл (который можно посмотреть здесь) выглядел примерно так:

for (let curX = firstMajorMark;
curX < viewRWorld;
         curX += majorMarkDistanceWorld) {
    this.majorMarkWorldPositions_.push(
        Math.floor(MAJOR_MARK_ROUNDING_FACTOR * curX) /
        MAJOR_MARK_ROUNDING_FACTOR);
}

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

firstMajorMark: 885.0999999642371
majorMarkDistanceWorld: 1e-13

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

firstMajorMark: 885.0999999642371
majorMarkDistanceWorld: 5e-14

Число 885, разделённое на 5e-14, равно 1.8e16, а точность числа двойной точности с плавающей запятой равна 2^53, то есть 9.0e15. Следовательно, баг возникает, когда majorMarkDistanceWorld (расстояние между точками сетки) настолько мало относительно firstMajorMark (расположения первой основной метки сетки), что сложение в цикле… ничего не делает. То есть если мы прибавляем маленькое число к большому, то когда маленькое «слишком мало», большое число может (в стандартном/sane режиме округления к ближайшему) оставаться равным тому же значению.

Из-за этого цикл работает бесконечно, а команда push выполняется, пока массив не упрётся в пределы размеров. Если бы ограничений размера не было, то команда push продолжала бы выполняться, пока память не закончится у всей машины. Так что ура, проблема решена?

Исправление оказалось довольно простым — не выводить метки сетки, если мы не можем этого сделать:

if (firstMajorMark / majorMarkDistanceWorld > 1e15) return;

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

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

Итак, если вы JavaScript-разработчик, пытающийся использовать чрезвычайно большие числа, создатель тестов, пытающийся использовать самое большое значение integer или реализуете UI с неограниченным зумом, то важно помнить, что при приближении к границам математики с плавающей запятой эти границы можно и пробить.

---

На правах рекламы

Серверы для разработки — это эпичные от Вдсины.
Используем исключительно быстрые NVMe накопители от Intel и не экономим на железе — только брендовое оборудование и самые современные решения на рынке!

Автор: Mikhail

Источник