Há sempre um bom momento para usar int32 em vez de sint32 no Google Protocol Buffers?

Question

Eu estive lendo sobre Google Protocol Buffers recentemente, o que permite uma variedade de tipos de valores escalares para ser usado nas mensagens.

De acordo com a sua documentação , há três tipos de variáveis primitivas inteiros -length - int32, uint32 e sint32. Na sua documentação, eles observam que int32 é "ineficiente para codificar números negativos - se o seu campo é provável que tenha valores negativos, o uso sint32 vez." Mas se você tem um campo que não tem números negativos, presumo que uint32 seria um melhor tipo de usar do que int32 de qualquer maneira (devido ao pouco extra e diminuiu o custo da CPU de processamento de números negativos).

Assim, quando se int32 ser uma boa escalar para uso? É a documentação que implica que é mais eficiente somente quando você raramente recebem números negativos? Ou é sempre preferível a utilização sint32 e uint32, dependendo do conteúdo do campo?

(As mesmas questões se aplicam às versões de 64 bits desses escalares assim: int64, uint64 e sint64, mas deixei-os para fora da descrição do problema por causa da legibilidade.)

Answer 1

Eu não estou familiarizado com o Google Protocol Buffers, mas a minha interpretação da documentação é a seguinte:

• uso uint32 se o valor não pode ser negativo
• uso sint32 se o valor é bastante mais probabilidades de ser negativo como não (por alguma definição fuzzy "como susceptíveis de ser")
• uso int32 se o valor pode ser negativo, mas isso é muito menos provável do que o valor ser positivo (por exemplo, se a aplicação às vezes usa -1 para indicar um erro ou valor de 'desconhecido' e esta é uma situação relativamente incomum)

Aqui está o que os médicos têm a dizer sobre as codificações ( http: / /code.google.com/apis/protocolbuffers/docs/encoding.html#types ):

existe uma diferença importante entre os tipos assinados int (sint32 e sint64) e os tipos int "padrão" (int32 e int64) quando se trata de codificação de números negativos. Se você usar int32 ou int64 como o tipo para um número negativo, o varint resultante é sempre dez bytes de comprimento - é, efetivamente, tratado como um grande inteiro sem sinal. Se você usar um dos tipos assinados, o varint resultando utiliza codificação ZigZag, que é muito mais eficiente.

ziguezague codificação mapas inteiros assinado para números inteiros sem sinal de modo que os números, com um pequeno valor absoluto (por exemplo, -1) têm um pequeno valor varint codificado demasiado. Ele faz isso de uma maneira que "ziguezagues" para trás e para a frente através dos números inteiros positivos e negativos, de modo que -1 é codificado como uma, 1 é codificado como 2, -2 é codificado como 3, e assim por diante ...

Portanto, parece que mesmo que o seu uso de números negativos é rara, desde que a magnitude dos números (incluindo números não negativos) que você está passando no protocolo está no lado menor, você pode ser melhor fora usando sint32. Se não tiver certeza, perfilando estaria em ordem.

Answer 2

Há muito pouco bom motivo para int uso cada vez * em vez de * sint. A existência destes tipos extras é provavelmente por razões de compatibilidade históricos, para trás, que Protocol Buffers tenta manter mesmo em suas próprias versões de protocolo.

Meu melhor palpite é que na versão mais antiga que dumbly codificado inteiros negativos na representação do complemento de 2, o que exige a codificação VarInt máximo tamanho de 9 bytes (sem contar o tipo byte extra). Em seguida, eles foram presos com que a codificação de modo a não quebrar o código antigo e serializations que já usaram. Então, eles precisavam para adicionar um novo tipo de codificação, * sint, para obter uma codificação melhor de tamanho variável para números negativos, enquanto não quebrar o código existente. Como os designers não percebem esta questão a partir do get-go é totalmente além de mim.

A codificação VarInt (sem especificação tipo, que requer mais de 1 byte) pode codificar um valor inteiro sem sinal no seguinte número de bytes:

[0, 2 ^ 7): um byte

[2 ^ 7, 2 ^ 14): dois bytes

[2 ^ 14, 2 ^ 21): três bytes

[2 ^ 21, 2 ^ 28): quatro bytes

[2 ^ 28, 2 ^ 35): cinco bytes

[2 ^ 35, 2 ^ 42): seis bytes

[2 ^ 42, 2 ^ 49): bytes sete

[2 ^ 49, 2 ^ 56): oito bytes

[2 ^ 56, 2 ^ 64): nove bytes

Se você quiser semelhante codificar números inteiros pequenos magnitude negativos compacta, então você terá de "usar-se" um pouco para indicar o sinal. Você pode fazer isso através de um pouco explícita sinal (em alguma posição reservada) e representação magnitude. Ou, você pode fazer zig zag de codificação, o que efetivamente faz a mesma coisa pela esquerda mudando a magnitude de 1 bit e subtraindo 1 para números negativos (de modo que o bit menos significativo indica o sinal: nivela são não-negativo, as probabilidades são negativos).

De qualquer forma, o corte mais pontos em que positivo inteiros requerem mais espaço agora vem um fator de 2 anteriormente:

[0, 2 ^ 6): um byte

[2 ^ 6, 2 ^ 13): dois bytes

[2 ^ 13, 2 ^ 20): três bytes

[2 ^ 20, 2 ^ 27): quatro bytes

[2 ^ 27, 2 ^ 34): cinco bytes

[2 ^ 34, 2 ^ 41): seis bytes

[2 ^ 41, 2 ^ 48): bytes sete

[2 ^ 48, 2 ^ 55): oito bytes

[2 ^ 55, 2 ^ 63): nove bytes

Para tornar o caso para o uso int * sobre sint *, os números negativos teria que ser extremamente raro, mas possível, e / ou os valores positivos mais comuns que você espera para codificar teria que cair para a direita em torno de um corte mais Os pontos que conduz a uma codificação de maior em * sint em oposição a int * (por exemplo, - 2 ^ 6 x 2 ^ 7 levando a 2x tamanho de codificação).

Basicamente, se você estiver indo para ter números onde alguns podem ser negativos, em seguida, por sint uso padrão * em vez de int *. int * muito raramente será superior e, geralmente, não vai mesmo ser vale extra que você tem que dedicar no sentido de julgar se vale a pena ou não IMHO.