O `Vector <float> .Equals` deve ser reflexivo ou deve seguir a semântica da IEEE 754?

9

Ao comparar valores de ponto flutuante para igualdade, existem duas abordagens diferentes:

Os construídas em IEEE flutuante tipos de ponto em C # ( floate double) acompanhar semântica para IEEE ==e !=(e os operadores relacionais como <) mas assegurar reflexividade para object.Equals, IEquatable<T>.Equals(e CompareTo).

Agora considere uma biblioteca que fornece estruturas vetoriais sobre float/ double. Esse tipo de vetor sobrecarregaria ==/ !=e substituía object.Equals/ IEquatable<T>.Equals.

O que todo mundo concorda é que ==/ !=deve seguir a semântica do IEEE. A questão é: essa biblioteca deve implementar o Equalsmétodo (que é separado dos operadores de igualdade) de maneira reflexiva ou de acordo com a semântica do IEEE.

Argumentos para usar a semântica IEEE para Equals:

  • Segue IEEE 754
  • É (possivelmente muito) mais rápido, porque pode tirar proveito das instruções do SIMD

    Fiz uma pergunta separada no stackoverflow sobre como você expressaria igualdade reflexiva usando instruções SIMD e seu impacto no desempenho: instruções SIMD para comparação de igualdade de ponto flutuante

    Atualização: parece possível implementar a igualdade reflexiva com eficiência usando três instruções SIMD.

  • A documentação para Equalsnão requer reflexividade ao envolver ponto flutuante:

    As instruções a seguir devem ser verdadeiras para todas as implementações do método Equals (Object). Na lista, x, y, e zrepresentam referências a objetos que não são nulos.

    x.Equals(x)retorna true, exceto nos casos que envolvem tipos de ponto flutuante. Consulte ISO / IEC / IEEE 60559: 2011, Tecnologia da informação - Sistemas de microprocessadores - Aritmética de ponto flutuante.

  • Se você estiver usando carros alegóricos como chaves de dicionário, estará vivendo um estado de pecado e não deve esperar um comportamento sensato.

Argumentos para ser reflexivo:

  • É consistente com os tipos existentes, incluindo Single, Double, Tuplee System.Numerics.Complex.

    Eu não conheço nenhum precedente na BCL onde Equalssegue o IEEE em vez de ser reflexivo. Contra-exemplos incluem Single, Double, Tuplee System.Numerics.Complex.

  • Equalsé usado principalmente por contêineres e algoritmos de busca que dependem da reflexividade. Para esses algoritmos, um ganho de desempenho é irrelevante se os impedir de funcionar. Não sacrifique a correção pelo desempenho.
  • Rompe todos os conjuntos de hash base e dicionários, Contains, Find, IndexOfem várias colecções / LINQ, operações conjunto baseado LINQ ( Union, Except, etc.), se os dados contém NaNvalores.
  • O código que faz cálculos reais em que a semântica do IEEE é aceitável geralmente funciona em tipos concretos e usa ==/ !=(ou comparações epsilon mais prováveis).

    Atualmente, não é possível gravar cálculos de alto desempenho usando genéricos, pois você precisa de operações aritméticas para isso, mas elas não estão disponíveis por meio de interfaces / métodos virtuais.

    Portanto, um Equalsmétodo mais lento não afetaria a maioria dos códigos de alto desempenho.

  • É possível fornecer um IeeeEqualsmétodo ou um IeeeEqualityComparer<T>para os casos em que você precisa da semântica IEEE ou da vantagem de desempenho.

Na minha opinião, esses argumentos favorecem fortemente uma implementação reflexiva.

A equipe CoreFX da Microsoft planeja introduzir esse tipo de vetor no .NET. Ao contrário de mim, eles preferem a solução IEEE , principalmente devido às vantagens de desempenho. Como essa decisão certamente não será alterada após o lançamento final, quero receber feedback da comunidade sobre o que acredito ser um grande erro.

CodesInChaos
fonte
11
Excelente e instigante pergunta. Para mim (pelo menos), não faz sentido ==e Equalsretornaria resultados diferentes. Muitos programadores assumem que são e fazem a mesma coisa . Além disso - em geral, implementações dos operadores de igualdade invocam o Equalsmétodo. Você argumentou que se pode incluir um IeeeEquals, mas também se pode fazer o contrário e incluir um ReflexiveEqualsmétodo. O Vector<float>tipo-pode ser usado em muitos aplicativos críticos para o desempenho e deve ser otimizado de acordo.
die maus
@diemaus Algumas razões pelas quais eu não acho isso convincente: 1) para float/ doublee vários outros tipos, ==e Equalsjá são diferentes. Eu acho que uma inconsistência com os tipos existentes seria ainda mais confusa do que a inconsistência entre ==e Equalsvocê ainda terá que lidar com outros tipos. 2) Praticamente todos os algoritmos / coleções genéricos usam Equalse dependem de sua reflexividade para funcionar (LINQ e dicionários), enquanto algoritmos concretos de ponto flutuante geralmente usam ==onde obtêm sua semântica IEEE.
CodesInChaos
Eu consideraria Vector<float>um "animal" diferente de um simples floatou double. Por essa medida, não vejo o motivo Equalsou o ==operador de cumprir os padrões deles. Você mesmo disse: "Se você estiver usando carros alegóricos como chaves de dicionário, estará vivendo um estado de pecado e não deve esperar um comportamento sensato". Se alguém armazena NaNem um dicionário, a culpa é deles por usar práticas terríveis. Eu dificilmente acho que a equipe CoreFX não tenha pensado nisso. Eu iria com um ReflexiveEqualsou similar, apenas por uma questão de desempenho.
die maus

Respostas:

5

Eu diria que o comportamento do IEEE está correto. NaNs não são equivalentes entre si de forma alguma; eles correspondem a condições mal definidas onde uma resposta numérica não é apropriada.

Além dos benefícios de desempenho que vêm usando IEEE aritmética que a maioria dos processadores suportam nativamente, eu acho que há um problema de semântica com a dizer que se isnan(x) && isnan(y), então x == y. Por exemplo:

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

Eu argumentaria que não há uma razão significativa pela qual alguém considere xigual y. Você dificilmente poderia concluir que eles são números equivalentes; eles não são números, então parece um conceito totalmente inválido.

Além disso, do ponto de vista do design da API, se você estiver trabalhando em uma biblioteca de uso geral que se destina a ser usada por muitos programadores, faz sentido usar a semântica de ponto flutuante mais típica do setor. O objetivo de uma boa biblioteca é economizar tempo para quem a usa, portanto, criar comportamentos fora do padrão está pronto para confusão.

Jason R
fonte
3
Isso NaN == NaNdeve retornar false é indiscutível. A questão é o que o .Equalsmétodo deve fazer. Por exemplo, se eu usar NaNcomo chave de dicionário, o valor associado se tornará irrecuperável se NaN.Equals(NaN)retornar falso.
CodesInChaos
11
Eu acho que você precisa otimizar para o caso comum. O caso comum de um vetor de números é a computação numérica de alto rendimento (geralmente otimizada com instruções SIMD). Eu argumentaria que o uso de um vetor como chave de dicionário é um caso de uso extremamente raro e dificilmente vale a pena projetar sua semântica. O contra-argumento que parece mais razoável para mim é consistência, já que os existentes Single, Doubleaulas, etc. já têm o comportamento reflexivo. IMHO, essa foi apenas a decisão errada para começar. Mas eu não deixaria a elegância atrapalhar a utilidade / velocidade.
Jason R
Porém, os cálculos numéricos geralmente usam o ==que sempre seguiu o IEEE, para que eles obtenham o código rápido, não importa como Equalsseja implementado. Na IMO, o objetivo de ter um Equalsmétodo separado é usar algoritmos que não se importam com o tipo concreto, como a Distinct()função do LINQ .
CodesInChaos
11
Entendi. Mas eu argumentaria contra uma API que tem um ==operador e uma Equals()função que tem semântica diferente. Eu acho que você está pagando um custo de confusão potencial do ponto de vista do desenvolvedor, sem nenhum benefício real (não atribuo valor a poder usar um vetor de números como uma chave de dicionário). É apenas a minha opinião; Não acho que haja uma resposta objetiva para a pergunta em questão.
Jason R
0

Há um problema: o IEEE754 define operações relacionais e igualdade de uma maneira adequada para aplicativos numéricos. Não é adequado para classificação e hash. Portanto, se você deseja classificar uma matriz com base em valores numéricos, ou se deseja adicionar valores numéricos a um conjunto ou usá-los como chaves em um dicionário, declara que os valores NaN não são permitidos ou não utiliza IEEE754 operações integradas. Sua tabela de hash precisaria garantir que todos os NaNs correspondessem ao mesmo valor e comparassem entre si.

Se você definir Vector, deverá tomar a decisão de design se deseja usá-lo apenas para fins numéricos ou se deve ser compatível com classificação e hash. Pessoalmente, acho que o objetivo numérico deve ser muito mais importante. Se a classificação / hash for necessária, você poderá escrever uma classe com Vector como membro e definir o hash e a igualdade nessa classe da maneira que desejar.

gnasher729
fonte
11
Concordo que propósitos numéricos são mais importantes. Mas já temos os operadores ==e !=para eles. Na minha experiência, o Equalsmétodo é praticamente usado apenas por algoritmos não numéricos.
CodesInChaos