Qual é o objetivo do boxe NaN?

44

Lendo o século XXI C , cheguei ao capítulo 6 na seção "Marcando valores numéricos excepcionais com NaNs" , onde explica o uso dos bits na mantissa para armazenar alguns padrões arbitrários de bits, para usá-los como marcadores ou ponteiros (o livro menciona que o WebKit usa essa técnica).

Não tenho muita certeza de ter entendido a utilidade dessa técnica, que vejo como um hack (depende do hardware não se importar com o valor da mantissa em um NaN), mas proveniente de um background Java ao qual não estou acostumado. a rugosidade de C.

Aqui está o trecho de código que define e lê um marcador em um NaN

#include <stdio.h>
#include <math.h> //isnan

double ref;

double set_na(){
    if (!ref) {
        ref=0/0.;
        char *cr = (char *)(&ref);
        cr[2]='a';
    }
    return ref;
}

int is_na(double in){
    if (!ref) return 0;  //set_na was never called==>no NAs yet.

    char *cc = (char *)(&in);
    char *cr = (char *)(&ref);
    for (int i=0; i< sizeof(double); i++)
        if (cc[i] != cr[i]) return 0;
    return 1;
}

int main(){
    double x = set_na();
    double y = x;
    printf("Is x=set_na() NA? %i\n", is_na(x));
    printf("Is x=set_na() NAN? %i\n", isnan(x));
    printf("Is y=x NA? %i\n", is_na(y));
    printf("Is 0/0 NA? %i\n", is_na(0/0.));
    printf("Is 8 NA? %i\n", is_na(8));
}

imprime:

Is x=set_na() NA? 1
Is x=set_na() NAN? 1
Is y=x NA? 1
Is 0/0 NA? 0
Is 8 NA? 0

e no JSValue.h webkit explica a codificação, mas não por que é usada.

Qual é o objetivo dessa técnica? Os benefícios do espaço / desempenho são altos o suficiente para equilibrar sua natureza hackish?

andijcr
fonte
você pode fornecer um exemplo simples?
BЈовић
Para ser claro o OP é perguntando onde NaNs sinalização pode ser usado
catraca aberração
1
@ratchetfreak, o que faz você pensar isso?
Winston Ewert
@ratchetfreak: a questão não é sobre sinalizar NaN, como explica o webkit JSValue.h, mas obrigado por me deixar descobrir algo novo!
andijcr 31/01
1
@Hudson isnan () é usado na segunda impressão principal. O objetivo de is_an () é testar se o padrão de bits da entrada dupla é igual ao salvo dentro da variável global ref.
andijcr 31/01

Respostas:

63

Ao implementar uma linguagem de tipo dinâmico, você precisa ter um único tipo que possa conter qualquer um dos seus objetos. Estou ciente de três abordagens diferentes para isso:

Em primeiro lugar, você pode passar os ponteiros. É isso que a implementação do CPython faz. Todo objeto é um PyObjectponteiro. Esses ponteiros são repassados ​​e as operações são executadas observando detalhes na estrutura do PyObject para descobrir o tipo.

A desvantagem é que valores pequenos, como números, são armazenados como valores em caixa. Portanto, seus 5 pequenos são armazenados como um bloco de memória em algum lugar. Portanto, isso nos leva à abordagem da união, usada por Lua. Em vez de a PyObject*, cada valor é uma estrutura em que campo especificar o tipo e, em seguida, uma união de todos os diferentes tipos suportados. Dessa forma, evitamos alocar qualquer memória para valores pequenos, em vez de armazená-los diretamente na união.

A NaNabordagem armazena tudo como dobra e reutiliza a parte não utilizada NaNpara o armazenamento extra. A vantagem sobre o método union é que salvamos o campo type. Se é um duplo válido, é um duplo, caso contrário a mantissa é um ponteiro para o objeto real.

Lembre-se, este é todo objeto javascript. Toda variável, todo valor em um objeto, toda expressão. Se pudermos reduzir todos esses de 96 bits para 64 bits, isso é impressionante.

Vale a pena o hack? Lembre-se de que há muita demanda por Javascript eficiente. Javascript é o gargalo em muitos aplicativos da Web e, portanto, torná-lo mais rápido é uma prioridade mais alta. É razoável introduzir um certo grau de imprudência por razões de desempenho. Para a maioria dos casos, seria uma péssima ideia, pois está introduzindo um grau de complexidade com pouco ganho. Mas, neste caso específico, vale a pena melhorar a memória e a velocidade.

Winston Ewert
fonte
2
Na verdade, o CPython armazena em cache pequenos números. Veja hg.python.org/cpython/file/e6cc582cafce/Objects/longobject.c
Phillip Cloud
1
@ cpcloud, é verdade, mas esse detalhe não parecia pertinente.
Winston Ewert
1
@WinstonEwert Você está certo. Pensei a mesma coisa depois de ler o que havia escrito.
Phillip Cloud
2
Usar bits de um tipo primitivo para evitar o "encaixotamento" de todos os valores é uma técnica consagrada pelo tempo. O Smalltalk o usou na década de 1970, roubando um bit de números inteiros de 16 bits para sinalizar um ponteiro de objeto ou 15 bits SmallInteger.
Jonathan Eunice
2
@JonathanEunice, sério? Isso me surpreende, porque não há realmente um longo alcance em 16 bits que eu estaria disposto a desistir um pouco.
Winston Ewert 26/03
7

Usar NaN para "valores excepcionais" é uma técnica bem conhecida e às vezes útil para evitar a necessidade de uma variável booleana extra this_value_is_invalid. Usada com sabedoria, pode ajudar a tornar seu código mais conciso, mais limpo, mais simples, melhor legível, sem quaisquer compensações de desempenho.

Essa técnica tem algumas armadilhas, é claro (veja aqui http://ppkwok.blogspot.co.uk/2012/11/java-cafe-1-never-write-nan-nan_24.html ), mas em idiomas como Java ( ou C # muito semelhante), existem funções de biblioteca padrão como Float.isNaNsimplificar o tratamento de NaNs. Claro que, em Java você pode usar como alternativa o Floate Doubleclasse e em C # a anulável tipos de valor float?e double?, dando-lhe a possibilidade de utilizar null, em vez de NaN para números de ponto flutuante inválidos, mas essas técnicas podem ter uma influência negativa significativa no desempenho e memória uso do seu programa.

Em C, o uso de NaN não é 100% portátil, isso é verdade, mas você pode usá-lo em qualquer lugar em que o padrão de ponto flutuante IEEE 754 esteja disponível. AFAIK, hoje é quase todo hardware convencional (ou pelo menos o ambiente de tempo de execução da maioria dos compiladores o suporta). Por exemplo, esta publicação do SO contém algumas informações para descobrir mais detalhes sobre o uso de NaN em C.

Doc Brown
fonte
a auto-boxing em java é confuso e deve ser evitado, apenas usá-lo para ser capaz de fornecer um valor nulo é ridículo e propenso a erros
catraca aberração
Eu editei a pergunta para criar um link para onde o webkit usa NaN-boxing. Parece que o webkit tem um uso mais amplo do NaN, além de sinalizar 'NaN'
andijcr
2
@ratchetfreak: isso apoia meu argumento, é claro #
Doc Brown