Есть ли когда-нибудь подходящее время для использования int32 вместо sint32 в буферах протокола Google?

Question

я читал Буферы протоколов Google недавно это позволило использовать в сообщениях различные типы скалярных значений.

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

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

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

Answer 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 закодированное значение тоже.Он делает это таким образом, что «зигзаги» перемещаются вперед и назад по положительным и отрицательным целым числам, так что -1 кодируется как 1, 1 кодируется как 2, -2 кодируется как 3 и так далее...

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

Answer 2

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

Я предполагаю, что в самой ранней версии они тупо кодировали отрицательные целые числа в представлении с дополнением до 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 для отрицательных чисел (таким образом, младший бит указывает на знак:четы неотрицательны, шансы отрицательны).

В любом случае, точки пересечения, в которых позитивный целые числа требуют больше места, теперь в два раза раньше:

[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* вместо sint*, отрицательные числа должны быть чрезвычайно редкими, но возможными, и/или наиболее распространенные положительные значения, которые вы ожидаете закодировать, должны были бы попадать прямо вокруг одной из точек пересечения, которая ведет к большей кодировке в sint*, а не в int* (например.- 2^6 против.2^7, что приводит к увеличению размера кодировки в 2 раза).

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