Равномерное равенство для кэширования дорогостоящих вычислений

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

Представьте, что вы есть этот код:

if(myfloat != _last_float) { 
    refresh_expensive_computation(myfloat); 
    _last_float = myfloat; 
}

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

В случае, если они действительно равны (что означает, что они были бы, если бы мы могли вычислять с помощью реалов вместо плавающей запятой), но ошибочно обнаружены, чтобы не быть, в худшем случае мы делаем дорогостоящие вычисления избыточно, но ответ нашей программы все еще верна. AFAIK они могут ошибочно сравнивать равные, если вычисление было выполнено в регистре, который шире, чем представление памяти float (например, на 32-битном x86, когда 80-битные регистры fp включены), и после преобразования в представление памяти они происходят для обоих поразрядное. В этом случае разница должна быть выше точности представления памяти, которая должна быть ниже эпсилона для сравнения, что имеет значение для меня, потому что в противном случае я бы использовал более широкий тип, такой как double.

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

Во-вторых, если мы предположим, что это безопасно, я хотел бы избежать ошибочного возвращения истины, потому что это вызывает дорогостоящие вычисления. Один из способов избежать этого на машинах с более широкими регистрами, чем представления памяти, - это использовать memcmp, чтобы заставить его сравнивать представления памяти (семантика не будет точно такой же для NaN, которая теперь сравним true с точно идентичным побитовым экземпляром но для кеширования это улучшение, или для +0 и -0, но это может быть специальная оболочка). Однако этот memcmp будет медленнее, чем сравнение с плавающей запятой в регистрах. Есть ли способ обнаружить, когда платформа имеет более широкие регистры, поэтому я могу #ifdef или аналогичный, чтобы получить оптимизированную реализацию на платформах, где это безопасно?

источник

2016-10-05 Joseph Garvin

Откуда вы знаете, правильно ли кэшированное значение, не делая вычисления в любом случае, чтобы выяснить, что это такое * должно быть? – Dmitri

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

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

Большинство версий memcmp имеют небольшие значения для регистров, поэтому должно быть хорошо использовать это. Однако, если вы не хотите полагаться на это, вы также можете сделать что-то вроде reinterpret_cast<int>(). Добавьте compile_assert(sizeof(int) == sizeof(float)), если вы хотите быть более безопасным и используете набор библиотек, который включает такую команду.

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

источник

2016-10-05 22:23:15

Интересно, не думал о небольшой оптимизации стоимости. В моем приложении фактически стоимость, по-видимому, отправляется в memcmp. Мне придется сравнить сгенерированный код для реинтерпрета. –

(C99) Для того, чтобы избежать некоторой более высокой точности FP математики с обеспечивая не точный сравнить, используйте volatile, чтобы заставить вычисление использовать самый последние флоят значения.

if ((volatile float) myfloat != (volatile float) _last_float) { 
    refresh_expensive_computation(myfloat); 
    _last_float = myfloat; 
}

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

Примечание: -0.0f равно + 0.0f.Если эти разные float s, имеющие одинаковое значение, важны, необходим другой код, чем !=.

источник

2016-10-06 02:34:05 chux

Равномерное равенство для кэширования дорогостоящих вычислений

ответ

Смежные вопросы