Должен ли я использовать NaN с плавающей запятой или плавающую точку + bool для набора данных, который содержит недопустимые значения?

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

Это делает свойство NaN представлять значения, которые не являются числом, и распространяться на арифметические операции очень убедительно. Однако, кажется, также требуется отключить некоторые оптимизации, такие как gcc -ffast-math, плюс мы должны быть кроссплатформенными. Наш текущий дизайн использует простую структуру, которая содержит значение с плавающей запятой и логическое значение, указывающее на достоверность.

Хотя кажется, что NaN был разработан с учетом этого использования, другие считают, что это больше проблем, чем оно того стоит. Есть ли у кого-нибудь совет, основанный на их более тесном опыте с IEEE754 с учетом производительности?

3 ответа

Решение

КРАТКОЕ ОПИСАНИЕ: для строгой переносимости не используйте NaN. Используйте отдельный действительный бит. Например, шаблон как Valid. Однако, если вы знаете, что вы когда-либо будете работать только на машинах IEEE 754-2008, а не на IEEE 754-1985 (см. Ниже), то вам это может сойти с рук.

Для повышения производительности, вероятно, быстрее не использовать NaN на большинстве машин, к которым у вас есть доступ. Тем не менее, я участвовал в разработке аппаратного обеспечения FP на нескольких машинах, которые улучшают производительность обработки NaN, поэтому существует тенденция ускорять работу NaN, и, в частности, сигнализация NaN вскоре должна быть быстрее, чем Valid.

ДЕТАЛЬ:

Не все форматы с плавающей запятой имеют NaN. Не все системы используют IEEE с плавающей запятой. Шестнадцатеричное число с плавающей точкой IBM все еще можно найти на некоторых машинах - фактически в системах, поскольку IBM теперь поддерживает IEEE FP на более поздних машинах.

Кроме того, у IEEE Floating Point были проблемы совместимости с NaN, в IEEE 754-1985. Например, см. Википедию http://en.wikipedia.org/wiki/NaN:

Исходный стандарт IEEE 754 от 1985 года (IEEE 754-1985) только описывал двоичные форматы с плавающей запятой и не определял, как должно быть помечено сигнальное / спокойное состояние. На практике наиболее значимый бит значимого и определяет, является ли NaN сигнальным или тихим. В результате были получены две разные реализации с обратными значениями. * большинство процессоров (включая процессоры семейства Intel/AMD x86-32/x86-64, семейства Motorola 68000, семейства AIM PowerPC, семейства ARM и семейства Sun SPARC) устанавливают бит сигнала / тишины в ненулевой если NaN тихий, и к нулю, если NaN сигнализирует. Таким образом, на этих процессорах бит представляет флаг is_quiet. * в NaN, генерируемых процессорами PA-RISC и MIPS, сигнальный / тихий бит равен нулю, если NaN является тихим, и ненулевым, если NaN сигнализирует. Таким образом, на этих процессорах бит представляет флаг is_signaling.

Таким образом, если ваш код может выполняться на старых машинах HP или на современных машинах MIPS (которые широко распространены во встроенных системах), вы не должны зависеть от фиксированной кодировки NaN, но должны иметь машинно-зависимый #ifdef для ваших специальных NaN.

IEEE 754-2008 стандартизирует кодирование NaN, так что это становится лучше. Это зависит от вашего рынка.

Что касается производительности: многие машины по существу перехватывают или иным образом сильно падают в производительности при выполнении вычислений с участием как SNaN (которые должны перехватывать), так и QNaN (которые не должны перехватывать, то есть которые могут быть быстрыми - и которые получают быстрее на некоторых машинах как мы говорим.)

Я могу с уверенностью сказать, что на старых машинах, особенно на старых машинах Intel, вы НЕ хотели использовать NaN, если заботились о производительности. Например, http://www.cygnus-software.com/papers/x86andinfinity.html говорит: "Intel Pentium 4 очень плохо обрабатывает бесконечности, NAN и денормалы.... Если вы пишете код, который добавляет числа с плавающей запятой со скоростью по одному на такт, а затем добавляем бесконечность в качестве входных данных, производительность падает. Очень много. Огромное количество.... NAN еще медленнее. Добавление с NAN занимает около 930 циклов... Денормали немного сложнее измерения ".

Получить картину? Почти в 1000 раз медленнее использовать NaN, чем при обычной операции с плавающей запятой? В этом случае почти гарантируется, что использование шаблона, такого как Valid, будет быстрее.

Однако смотрите ссылку на "Pentium 4"? Это действительно старая веб-страница. В течение многих лет такие люди, как я, говорили: "QNaNs должны быть быстрее", и это постепенно укоренилось.

Совсем недавно (2009 г.) Microsoft говорит, что если вы занимаетесь математикой для массивов, http://connect.microsoft.com/VisualStudio/feedback/details/498934/big-performance-penalty-for-checking-for-nans-or-infinity "сообщает двойного числа, которое содержит большое количество NaN или Infinities, есть штраф за производительность на порядок ".

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

Это должно измениться, потому что не так сложно быстро сделать QNaN. Но это всегда была проблема курицы и яйца: парни из аппаратных средств, подобные тем, с которыми я работаю, говорят: "Никто не использует NaN, поэтому мы не выигрываем; они делают это быстро", в то время как парни из программного обеспечения не используют NaN, потому что они медленные. Тем не менее, прилив медленно меняется.

Черт возьми, если вы используете gcc и хотите добиться максимальной производительности, вы включаете оптимизацию, например "-ffinite-math-only ... Разрешить оптимизацию для арифметики с плавающей точкой, в которой предполагается, что аргументы и результаты не являются NaN или +-Infs". Подобное верно для большинства компиляторов.

Кстати, вы можете Google, как я сделал, "NaN производительности с плавающей запятой" и проверить ссылки самостоятельно. И / или запустить свои собственные микробенчмарки.

Наконец, я предполагаю, что вы используете шаблон, как

template<typename T> class Valid {
    ...
    bool valid;
    T value;
    ...
};

Мне нравятся подобные шаблоны, потому что они могут принести "отслеживание достоверности" не только в FP, но и в целочисленные (действительные) и т. Д.

Но они могут иметь большую стоимость. Операции, вероятно, не намного дороже, чем обработка NaN на старых машинах, но плотность данных может быть очень плохой. sizeof(Действительный) может иногда быть 2*sizeof(float). Эта плохая плотность может повредить производительности гораздо больше, чем операции.

Кстати, вы должны рассмотреть специализацию шаблонов, чтобы Valid использовал NaN, если они доступны и быстро, и действительный бит в противном случае.

template <> class Valid<float> { 
    float value; 
    bool is_valid() { 
        return value != my_special_NaN; 
    } 
}

и т.п.

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

struct Point { float x, y, z; };
Valid<Point> pt;

лучше (по плотности) чем

struct Point_with_Valid_Coords { Valid<float> x, y, z; };

если вы не используете NaN - или какую-то другую специальную кодировку.

А также

struct Point_with_Valid_Coords { float x, y, z; bool valid_x, valid_y, valid_z };

между ними - но тогда вы должны сделать весь код самостоятельно.

Кстати, я предполагаю, что вы используете C++. Если Фортран или Ява...

НИЖНЯЯ ЛИНИЯ: отдельные действительные биты, вероятно, быстрее и более переносимы.

Но обработка NaN ускоряется, и однажды скоро будет достаточно

Кстати, мои предпочтения: создать шаблон Valid. Тогда вы можете использовать его для всех типов данных. Специализируйте это для NaNs, если это помогает. Хотя моя жизнь делает вещи быстрее, ИМХО, как правило, важнее сделать код чистым.

Если неверные данные встречаются очень часто, вы, конечно, тратите много времени на обработку этих данных. Если неверные данные достаточно распространены, вероятно, лучше использовать некую разреженную структуру данных только из достоверных данных. Если это не очень часто, вы, конечно, можете сохранить редкую структуру данных, данные которой являются недействительными. Таким образом, вы не будете тратить впустую bool для каждого значения. Но, возможно, память не проблема для вас...

Если вы выполняете такие операции, как умножение двух, возможно, недействительных записей данных, я понимаю, что вам необходимо использовать NaN вместо проверки обеих переменных, чтобы проверить, действительны ли они, и установить один и тот же флаг в результате.

Насколько портативным вы должны быть? Вам когда-нибудь понадобится перенести его на архитектуру с поддержкой только фиксированной точки? Если это так, я думаю, ваш выбор очевиден.

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

Так как числа с плавающей точкой приходят от устройства, они, вероятно, имеют ограниченный диапазон. Вы можете использовать другое специальное число, а не NaN, чтобы указать на отсутствие данных, например, 1e37. Это решение является портативным. Я не знаю, является ли для вас более удобным, чем использование флага bool.

Другие вопросы по тегам