Хорошо ли использовать int32 вместо sint32 в буферах протокола Google?

Недавно я читал Google Protocol Buffers, который позволяет использовать в сообщениях различные типы значений в виде скалярных значений.

Согласно их документации, существует три типа целочисленных примитивов переменной длины - int32, uint32 и sint32. В своей документации они отмечают, что int32 "Неэффективно для кодирования отрицательных чисел", если ваше поле, скорее всего, имеет отрицательные значения, вместо этого используйте sint32. " Но если у вас есть поле, у которого нет отрицательных чисел, я предполагаю, что uint32 будет лучшим типом для использования, чем int32 в любом случае (из-за дополнительного бита и снижения стоимости ЦП обработки отрицательных чисел).

Итак, когда int32 был бы хорошим скаляром для использования? Является ли документация подразумевающей, что она наиболее эффективна только тогда, когда вы редко получаете отрицательные числа? Или всегда предпочтительнее использовать sint32 и uint32, в зависимости от содержимого поля?

(Эти же вопросы относятся и к 64-битным версиям этих скаляров: int64, uint64 и sint64, но я оставил их вне описания проблемы для удобства чтения.)

Ответ 1

Я не знаком с буферами протокола Google, но моя интерпретация документации:

используйте uint32, если значение не может быть отрицательным
используйте sint32, если значение в значительной степени скорее отрицательно, чем нет (для некоторого нечеткого определения "как можно скорее" )
используйте int32, если значение может быть отрицательным, но гораздо менее вероятным, чем значение является положительным (например, если приложение иногда использует -1 для указания ошибки или "неизвестного" значения, и это относительно необычно ситуация)

Здесь, что документы должны сказать о кодировках (http://code.google.com/apis/protocolbuffers/docs/encoding.html#types):

существует значительное различие между подписанными типами int (sint32 и sint64) и "стандартными" типами int (int32 и int64), когда дело доходит до кодирования отрицательных чисел. Если вы используете int32 или int64 в качестве типа для отрицательного числа, результирующий varint всегда имеет длину в десять байт - он эффективно обрабатывается как очень большое целое число без знака. Если вы используете один из подписанных типов, результирующий varint использует кодировку ZigZag, что намного эффективнее.

ZigZag-кодирование отображает целые числа со знаком в целые числа без знака, так что числа с малым абсолютным значением (например, -1) также имеют небольшое значение varint. Он делает это так, чтобы "zig-zags" обратно и вперед через положительные и отрицательные целые числа, так что -1 кодируется как 1, 1 кодируется как 2, -2 кодируется как 3 и так далее...

Так выглядит, даже если ваше использование отрицательных чисел встречается редко, пока величина чисел (включая неотрицательные числа), которые вы передаете в протоколе, находится на меньшей стороне, вам может быть лучше используя sint32. Если вы не уверены, профилирование будет в порядке.

Ответ 2

Существует очень мало веских причин использовать int * вместо sint *. Существование этих дополнительных типов наиболее вероятно по историческим причинам обратной совместимости, которые буферы протокола пытаются поддерживать даже в своих собственных версиях протокола.

Мое лучшее предположение состоит в том, что в самой ранней версии они тупо кодировали отрицательные целые числа в представлении в 2 дополнения, что требует кодирования varint максимально размера 9 байтов (не считая байта дополнительного типа). Затем они застряли с этой кодировкой, чтобы не сломать старый код и сериализации, которые уже использовали его. Таким образом, им нужно было добавить новый тип кодирования, sint *, чтобы получить лучшую кодировку переменного размера для отрицательных чисел, не нарушая существующий код. То, как дизайнеры не поняли эту проблему с самого начала, совершенно вне меня.

Кодировка varint (без спецификации типа, для которой требуется еще 1 байт) может кодировать целочисленное значение без знака в следующем количестве байтов:

[0, 2 ^ 7): один байт

[2 ^ 7, 2 ^ 14): два байта

[2 ^ 14, 2 ^ 21): три байта

[2 ^ 21, 2 ^ 28): четыре байта

[2 ^ 28, 2 ^ 35): пять байтов

[2 ^ 35, 2 ^ 42): шесть байтов

[2 ^ 42, 2 ^ 49): семь байтов

[2 ^ 49, 2 ^ 56): восемь байтов

[2 ^ 56, 2 ^ 64): девять байтов

Если вы хотите компактно подобным образом кодировать отрицательные целые числа малой величины, вам потребуется "использовать" один бит для обозначения знака. Вы можете сделать это через явный бит знака (в некоторой зарезервированной позиции) и представление величины. Или вы можете выполнить зигзагообразное кодирование, которое фактически делает то же самое, сдвигая левую величину на 1 бит и вычитая 1 для отрицательных чисел (поэтому младший значащий бит указывает знак: четные значения неотрицательны, вероятностные значения отрицательны).

В любом случае, точки пересечения, в которых положительные целые числа требуют больше места, теперь имеют коэффициент 2 раньше:

[0, 2 ^ 6): один байт

[2 ^ 6, 2 ^ 13): два байта

[2 ^ 13, 2 ^ 20): три байта

[2 ^ 20, 2 ^ 27): четыре байта

[2 ^ 27, 2 ^ 34): пять байтов

[2 ^ 34, 2 ^ 41): шесть байтов

[2 ^ 41, 2 ^ 48): семь байтов

[2 ^ 48, 2 ^ 55): восемь байтов

[2 ^ 55, 2 ^ 63): девять байтов

Чтобы использовать случай int * over sint *, отрицательные числа должны быть чрезвычайно редкими, но возможными, и/или наиболее распространенные положительные значения, которые вы ожидаете кодировать, должны упасть прямо вокруг одной из точек перерезания, которая приводит к большей кодировке в sint *, в отличие от int * (например, - 2 ^ 6 против 2 ^ 7, приводящих к 2x размеру кодировки).

По сути, если у вас будут числа, где некоторые могут быть отрицательными, то по умолчанию используйте sint * вместо int *. int * очень редко будет превосходить и, как правило, даже не будет стоить дополнительной мысли, которую вы должны посвятить оценке того, стоит ли это того или нет, ИМХО.