Должен ли `Vector <float> .Equals 'быть рефлексивным или соответствовать семантике IEEE 754?

9

При сравнении значений с плавающей запятой на равенство существует два разных подхода:

Встроенный в IEEE с плавающей точкой типа в C # ( floatи double) следует IEEE семантике ==и !=(и реляционные операторы , как <) , но обеспечить возвратность для object.Equals, IEquatable<T>.EqualsCompareTo).

Теперь рассмотрим библиотеку , которая обеспечивает вектор структур сверху float/ double. Такой тип вектора перегрузит ==/ !=и переопределит object.Equals/ IEquatable<T>.Equals.

Все согласны с тем, что ==/ !=должны следовать семантике IEEE. Вопрос в том, должна ли такая библиотека реализовывать Equalsметод (который отделен от операторов равенства) рефлексивным способом или способом, соответствующим семантике IEEE.

Аргументы для использования семантики IEEE для Equals:

  • Следует IEEE 754
  • Это (возможно, намного) быстрее, потому что он может использовать SIMD инструкции

    Я задал отдельный вопрос о стековом потоке о том, как вы выражаете рефлексивное равенство с помощью инструкций SIMD и их влияние на производительность: инструкции SIMD для сравнения равенства с плавающей запятой

    Обновление: кажется, что можно эффективно реализовать рефлексивное равенство, используя три SIMD-инструкции.

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

    Следующие операторы должны быть истинными для всех реализаций метода Equals (Object). В списке x, yи zпредставляют собой ссылку на объекты, которые не являются пустыми.

    x.Equals(x)возвращает true, кроме случаев, когда используются типы с плавающей точкой. См. ISO / IEC / IEEE 60559: 2011, Информационные технологии. Микропроцессорные системы. Арифметика с плавающей точкой.

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

Аргументы за рефлексивность:

  • Это согласуется с существующими типами, в том числе Single, Double, Tupleи System.Numerics.Complex.

    Я не знаю ни одного прецедента в BCL, где Equalsследует IEEE вместо того, чтобы быть рефлексивным. Счетчик примеры включают Single, Double, Tupleи System.Numerics.Complex.

  • Equalsв основном используется контейнерами и алгоритмами поиска, основанными на рефлексивности. Для этих алгоритмов выигрыш в производительности не имеет значения, если мешает им работать. Не жертвуйте правильностью ради производительности.
  • Он ломает все хэш на основе наборов и словари, Contains, Find, IndexOfна различных сборниках / LINQ, набор на основе LINQ операции ( Union, Exceptи т.д.) , если данные содержат NaNзначение.
  • Код, который выполняет фактические вычисления, где семантика IEEE является приемлемой, обычно работает на конкретных типах и использует ==/ !=(или, более вероятно, сравнения эпсилона).

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

    Поэтому более медленный Equalsметод не повлияет на большинство высокопроизводительных программ.

  • Можно предоставить IeeeEqualsметод или метод IeeeEqualityComparer<T>для случаев, когда вам нужна семантика IEEE или вам нужно повысить производительность.

На мой взгляд, эти аргументы решительно поддерживают рефлексивную реализацию.

Команда Microsoft CoreFX планирует представить такой векторный тип в .NET. В отличие от меня они предпочитают решение IEEE , в основном из-за преимуществ в производительности. Поскольку такое решение, безусловно, не будет изменено после окончательного релиза, я хочу получить отзывы сообщества, что я считаю большой ошибкой.

CodesInChaos
источник
1
Отличный и задумчивый вопрос. Для меня (по крайней мере) это не имеет смысла ==и Equalsбудет давать разные результаты. Многие программисты предполагают, что это так, и делают то же самое . Кроме того, в общем случае реализации операторов равенства вызывают Equalsметод. Вы утверждали, что можно включить IeeeEquals, но можно сделать и наоборот и включить ReflexiveEquals-метод. Тип Vector<float>может использоваться во многих приложениях, критичных к производительности, и должен быть соответственно оптимизирован.
умереть
@diemaus Некоторые причины, почему я не нахожу это убедительным: 1) для float/ doubleи некоторых других типов, ==и Equalsони уже разные. Я думаю, что несоответствие с существующими типами будет еще более запутанным, чем несоответствие между ними, ==и Equalsвам все равно придется иметь дело с другими типами. 2) Практически все универсальные алгоритмы / коллекции используют Equalsи полагаются на его рефлексивность для функций (LINQ и словари), тогда как конкретные алгоритмы с плавающей точкой обычно используют ==там, где они получают свою семантику IEEE.
CodesInChaos
Я бы посчитал Vector<float>другим "зверем", чем простым floatили double. По той мере, я не могу понять причину Equalsили ==оператор соблюдать стандарты них. Вы сказали себе: «Если вы используете float в качестве словарных ключей, вы живете в состоянии греха и не должны ожидать нормального поведения». Если кто-то хранит NaNв словаре, то это их собственная чертова вина за использование ужасной практики. Я не думаю, что команда CoreFX не продумала это до конца. Я бы пошел с ReflexiveEqualsили аналогичным, только для производительности.
умереть

Ответы:

5

Я бы сказал, что поведение IEEE правильное. NaNs не эквивалентны друг другу в любом случае; они соответствуют плохо определенным условиям, в которых числовой ответ не подходит.

Помимо преимуществ в производительности, которые дает использование арифметики IEEE, которую большинство процессоров поддерживают изначально, я думаю, что существует семантическая проблема с утверждением, что если isnan(x) && isnan(y), то x == y. Например:

// C++
double inf = std::numeric_limits<double>::infinity();
double x = 0.0 / 0.0;
double y = inf - inf;

Я бы сказал, что нет веской причины, по которой можно считать xравным y. Вы вряд ли могли бы заключить, что они являются эквивалентными числами; они вовсе не числа, так что это кажется совершенно неверным понятием.

Кроме того, с точки зрения разработки API, если вы работаете с универсальной библиотекой, которая предназначена для использования многими программистами, имеет смысл использовать наиболее типичную для отрасли семантику с плавающей точкой. Цель хорошей библиотеки - сэкономить время для тех, кто ею пользуется, поэтому создание нестандартного поведения созрело для путаницы.

Джейсон Р
источник
3
Это NaN == NaNдолжно вернуть ложь неоспоримо. Вопрос в том, что .Equalsдолжен делать метод. Например, если я использую NaNв качестве ключа словаря, связанное значение становится необратимым, если NaN.Equals(NaN)возвращать false.
CodesInChaos
1
Я думаю, что вы должны оптимизировать для общего случая. Распространенным случаем для вектора чисел являются численные вычисления с высокой пропускной способностью (часто оптимизированные с помощью SIMD-инструкций). Я бы сказал, что использование вектора в качестве ключа словаря является чрезвычайно редким случаем, и вряд ли стоит разрабатывать свою семантику. Контраргумент , что представляется наиболее разумным для меня консистенция, так как существующие Single, Doubleи т.д. классы уже имеют рефлекторное поведение. ИМХО, это было просто неправильное решение для начала. Но я бы не позволил элегантности встать на пути полезности / скорости.
Джейсон Р
Но при численных вычислениях обычно используются те, ==которые всегда следовали IEEE, поэтому они получали бы быстрый код независимо от того, как Equalsон реализован. IMO весь смысл наличия отдельного Equalsметода заключается в использовании в алгоритмах, которые не заботятся о конкретном типе, таком как Distinct()функция LINQ .
CodesInChaos
1
Я понимаю. Но я бы поспорил с API, у которого есть ==оператор и Equals()функция с разной семантикой. Я думаю, что вы платите за возможную путаницу с точки зрения разработчика, без реальной выгоды (я не назначаю никакого значения возможности использовать вектор чисел в качестве словарного ключа). Это только мое мнение; Я не думаю, что есть объективный ответ на данный вопрос.
Джейсон Р
0

Существует проблема: IEEE754 определяет реляционные операции и равенство способом, который хорошо подходит для числовых приложений. Он плохо подходит для сортировки и хеширования. Поэтому, если вы хотите отсортировать массив на основе числовых значений или добавить числовые значения в набор или использовать их в качестве ключей в словаре, вы либо объявляете, что значения NaN недопустимы, либо не используете IEEE754. встроенные операции. Ваша хеш-таблица должна была бы удостовериться, что все NaN совпадают с одним и тем же значением, и сравнить их друг с другом.

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

gnasher729
источник
1
Я согласен, что числовые цели важнее. Но у нас уже есть ==и !=операторы для них. По моему опыту, этот Equalsметод в основном используется не числовыми алгоритмами.
CodesInChaos