[Высокая производительность, Ненормальное программирование, C] Быстрое сравнение double

Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
17-Фев-2021 15:35

Вчера здесь вышла статья о быстром парсинге double, я зашёл во блог к её автору, и нашёл там ещё один интересный трюк. При сравнении чисел с плавающей точкой особое внимание приходится уделять NaN (восемь лет назад я писал про них подробнее); но если сравниваемые числа заведомо не NaN, то сравнить их можно быстрее, чем это делает процессор!
Положительные double сравнивать очень просто: нормализация гарантирует нам, что из чисел с разной экспонентой больше то, чья экспонента больше, а из чисел с равной экспонентой больше то, чья мантисса больше. Стандарт IEEE 754 заботливо поместил экспоненту в старшие биты, так что положительные double можно сравнивать просто как int64_t.

оригинал
С отрицательными числами немного сложнее: они хранятся в прямом коде, тогда как int64_t — в дополнительном. Это значит, что для использования целочисленного сравнения младшие 63 бита double необходимо инвертировать (при этом получится -0. < +0., что не соответствует стандарту, но на практике не представляет проблемы). Явная проверка старшего бита и условный переход уничтожили бы всю выгоду от перехода к целочисленному сравнению; но есть способ проще!
inline int64_t to_int64(double x) {
  int64_t a = *(int64_t*)&x;
  uint64_t mask = (uint64_t)(a >> 63) >> 1;
  return a ^ mask;
}
inline bool is_smaller(double x1, double x2) {
  return to_int64(x1) < to_int64(x2);
}

a>>63 заполняет все 64 бита копиями знакового бита, и затем >>1 обнуляет старший бит.
Во блоге у Daniel Lemire несколько другой код (той же вычислительной сложности), но мой вариант сохраняет то полезное свойство, что to_int64(0.) == 0
===========
Источник:
habr.com
===========

Похожие новости: Теги для поиска: #_vysokaja_proizvoditelnost (Высокая производительность), #_nenormalnoe_programmirovanie (Ненормальное программирование), #_c, #_ieee_754, #_0x5f3759df, #_vysokaja_proizvoditelnost (
Высокая производительность
)
, #_nenormalnoe_programmirovanie (
Ненормальное программирование
)
, #_c
Профиль  ЛС 
Показать сообщения:     

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

Текущее время: 22-Ноя 20:34
Часовой пояс: UTC + 5