«Vector <float> .Equals» doit-il être réflexif ou doit-il suivre la sémantique IEEE 754?

9

Lors de la comparaison des valeurs à virgule flottante pour l'égalité, il existe deux approches différentes:

  • NaNn'étant pas égal à lui-même, ce qui correspond à la spécification IEEE 754 .
  • NaNétant égal à lui-même, ce qui fournit la propriété mathématique de la réflexivité qui est essentielle à la définition d'une relation d'équivalence

Les types à virgule flottante IEEE intégrés en C # ( floatet double) suivent la sémantique IEEE pour ==et !=(et les opérateurs relationnels comme <) mais assurent la réflexivité pour object.Equals, IEquatable<T>.Equals(et CompareTo).

Considérons maintenant une bibliothèque qui fournit des structures vectorielles au-dessus de float/ double. Un tel type de vecteur surchargerait ==/ !=et remplacerait object.Equals/ IEquatable<T>.Equals.

Ce sur quoi tout le monde est d'accord, c'est que ==/ !=devrait suivre la sémantique de l'IEEE. La question est de savoir si une telle bibliothèque doit implémenter la Equalsméthode (qui est distincte des opérateurs d'égalité) d'une manière réflexive ou d'une manière qui correspond à la sémantique IEEE.

Arguments pour utiliser la sémantique IEEE pour Equals:

  • Il suit IEEE 754
  • C'est (peut-être beaucoup) plus rapide car il peut tirer parti des instructions SIMD

    J'ai posé une question distincte sur stackoverflow sur la façon dont vous exprimeriez l'égalité réflexive à l'aide d'instructions SIMD et leur impact sur les performances: instructions SIMD pour la comparaison d'égalité en virgule flottante

    Mise à jour: Il semble possible d'implémenter efficacement l'égalité réflexive à l'aide de trois instructions SIMD.

  • La documentation de Equalsne nécessite pas de réflexivité lors de l'utilisation de virgule flottante:

    Les instructions suivantes doivent être vraies pour toutes les implémentations de la méthode Equals (Object). Dans la liste, x, yet zreprésentent des références d'objets qui ne sont pas nuls.

    x.Equals(x)renvoie true, sauf dans les cas qui impliquent des types à virgule flottante. Voir ISO / CEI / IEEE 60559: 2011, Technologies de l'information - Systèmes à microprocesseurs - Arithmétique à virgule flottante.

  • Si vous utilisez des flottants comme clés de dictionnaire, vous vivez dans un état de péché et ne devez pas vous attendre à un comportement sain.

Arguments pour être réflexif:

  • Il est compatible avec les types existants, y compris Single, Double, Tupleet System.Numerics.Complex.

    Je ne connais aucun précédent dans la BCL où Equalssuit IEEE au lieu d'être réflexif. Les exemples comprennent contre Single, Double, Tupleet System.Numerics.Complex.

  • Equalsest principalement utilisé par les conteneurs et les algorithmes de recherche qui reposent sur la réflexivité. Pour ces algorithmes, un gain de performances n'est pas pertinent s'il les empêche de fonctionner. Ne sacrifiez pas l'exactitude à la performance.
  • Il casse tous les ensembles à base de hachage et des dictionnaires, Contains, Find, IndexOfsur diverses collections / LINQ, ensemble des opérations de LINQ (base Union, Exceptetc.) si les données contiennent des NaNvaleurs.
  • Le code qui effectue des calculs réels où la sémantique IEEE est acceptable fonctionne généralement sur des types concrets et utilise ==/ !=(ou des comparaisons epsilon plus probables).

    Actuellement, vous ne pouvez pas écrire de calculs haute performance à l'aide de génériques car vous avez besoin d'opérations arithmétiques pour cela, mais celles-ci ne sont pas disponibles via des interfaces / méthodes virtuelles.

    Une Equalsméthode plus lente n'affecterait donc pas la plupart des codes hautes performances.

  • Il est possible de fournir une IeeeEqualsméthode ou une IeeeEqualityComparer<T>pour les cas où vous avez besoin de la sémantique IEEE ou si vous avez besoin d'un avantage en termes de performances.

À mon avis, ces arguments favorisent fortement une mise en œuvre réflexive.

L'équipe CoreFX de Microsoft prévoit d'introduire un tel type de vecteur dans .NET. Contrairement à moi, ils préfèrent la solution IEEE , principalement en raison des avantages de performance. Puisqu'une telle décision ne sera certainement pas modifiée après une version finale, je veux obtenir des commentaires de la communauté sur ce que je pense être une grosse erreur.

CodesInChaos
la source
1
Excellente question stimulante. Pour moi (au moins), cela n'a pas de sens ==et Equalsretournerait des résultats différents. De nombreux programmeurs supposent qu'ils le sont et font la même chose . De plus - en général, les implémentations des opérateurs d'égalité invoquent la Equalsméthode. Vous avez fait valoir que l'on pourrait inclure un IeeeEquals, mais on pourrait aussi le faire dans l'autre sens et inclure une ReflexiveEqualsméthode. Le Vector<float>type peut être utilisé dans de nombreuses applications critiques pour les performances et doit être optimisé en conséquence.
die maus
@diemaus Quelques raisons pour lesquelles je ne trouve pas cela convaincant: 1) pour float/ doubleet plusieurs autres types, ==et Equalssont déjà différents. Je pense qu'une incohérence avec les types existants serait encore plus déroutante que l'incohérence entre ==et Equalsvous devrez toujours faire face à d'autres types. 2) Presque tous les algorithmes / collections génériques utilisent Equalset s'appuient sur sa réflexivité pour fonctionner (LINQ et dictionnaires), tandis que les algorithmes concrets à virgule flottante utilisent généralement ==où ils obtiennent leur sémantique IEEE.
CodesInChaos
Je considérerais Vector<float>une "bête" différente d'un simple floatou double. Par cette mesure, je ne vois pas la raison Equalsou l' ==opérateur de se conformer à leurs normes. Vous vous êtes dit: "Si vous utilisez des flotteurs comme clés de dictionnaire, vous vivez dans un état de péché et ne vous attendez pas à un comportement sain". Si l'on devait stocker NaNdans un dictionnaire, c'est leur propre faute pour avoir utilisé une pratique terrible. Je pense à peine que l'équipe CoreFX n'y a pas réfléchi. J'irais avec un ReflexiveEqualsou similaire, juste pour des raisons de performance.
die maus

Réponses:

5

Je dirais que le comportement IEEE est correct. NaNs ne sont en aucun cas équivalents; ils correspondent à des conditions mal définies où une réponse numérique n'est pas appropriée.

Au-delà des avantages de performance qui découlent de l'utilisation de l'arithmétique IEEE que la plupart des processeurs prennent en charge nativement, je pense qu'il y a un problème sémantique à dire que si isnan(x) && isnan(y), alors x == y. Par exemple:

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

Je dirais qu'il n'y a aucune raison valable pour laquelle on considérerait xégal à y. Vous pourriez à peine conclure que ce sont des nombres équivalents; ce ne sont pas du tout des chiffres, donc cela semble être un concept totalement invalide.

De plus, du point de vue de la conception d'API, si vous travaillez sur une bibliothèque à usage général qui est destinée à être utilisée par de nombreux programmeurs, il est logique d'utiliser la sémantique à virgule flottante la plus typique de l'industrie. Le but d'une bonne bibliothèque est de gagner du temps pour ceux qui l'utilisent, donc la construction d'un comportement non standard est prête à confusion.

Jason R
la source
3
Cela NaN == NaNdevrait retourner faux est incontesté. La question est de savoir ce que la .Equalsméthode doit faire. Par exemple, si j'utilise NaNcomme clé de dictionnaire, la valeur associée devient non récupérable si NaN.Equals(NaN)renvoie false.
CodesInChaos
1
Je pense que vous devez optimiser pour le cas commun. Le cas commun pour un vecteur de nombres est le calcul numérique à haut débit (souvent optimisé avec des instructions SIMD). Je dirais que l'utilisation d'un vecteur comme clé de dictionnaire est un cas d'utilisation extrêmement rare et ne vaut guère la peine de concevoir votre sémantique. Le contre - argument qui semble le plus raisonnable pour moi est Consistance, puisque les existants Single, les Doubleclasses, etc. ont déjà le comportement réfléchi. À mon humble avis, c'était juste la mauvaise décision pour commencer. Mais je ne laisserais pas l'élégance entraver l'utilité / la vitesse.
Jason R
Mais les calculs numériques utilisent généralement ==ce qui a toujours suivi IEEE, de sorte qu'ils obtiendraient le code rapide, quelle que soit la façon dont il Equalsest implémenté. IMO, l'intérêt d'avoir une Equalsméthode distincte consiste à utiliser des algorithmes in qui ne se soucient pas du type concret, comme la Distinct()fonction de LINQ .
CodesInChaos
1
Je comprends ça. Mais je plaiderais contre une API qui a un ==opérateur et une Equals()fonction qui ont une sémantique différente. Je pense que vous payez un coût de confusion potentielle du point de vue du développeur, sans réel avantage (je n'attribue aucune valeur à la possibilité d'utiliser un vecteur de nombres comme clé de dictionnaire). C'est juste mon opinion; Je ne pense pas qu'il y ait de réponse objective à la question posée.
Jason R
0

Il y a un problème: IEEE754 définit les opérations relationnelles et l'égalité d'une manière bien adaptée aux applications numériques. Il n'est pas adapté au tri et au hachage. Donc, si vous souhaitez trier un tableau en fonction de valeurs numériques, ou si vous souhaitez ajouter des valeurs numériques à un ensemble ou les utiliser comme clés dans un dictionnaire, vous déclarez que les valeurs NaN ne sont pas autorisées, ou vous n'utilisez pas IEEE754 opérations intégrées. Votre table de hachage devrait s'assurer que tous les NaN sont mis en correspondance avec la même valeur et être comparables les uns aux autres.

Si vous définissez Vector, vous devez décider si vous souhaitez l'utiliser uniquement à des fins numériques ou s'il doit être compatible avec le tri et le hachage. Je pense personnellement que l'objectif numérique devrait être beaucoup plus important. Si le tri / hachage est nécessaire, vous pouvez écrire une classe avec Vector en tant que membre et définir le hachage et l'égalité dans cette classe comme vous le souhaitez.

gnasher729
la source
1
Je conviens que les objectifs numériques sont plus importants. Mais nous avons déjà les opérateurs ==et !=pour eux. D'après mon expérience, la Equalsméthode n'est pratiquement utilisée que par des algorithmes non numériques.
CodesInChaos