Re: A varint implementation for PG?

On 8/5/21 1:05 AM, Andres Freund wrote:
> Hi,
>
> On 2021-08-04 23:44:10 +0200, Tomas Vondra wrote:
>> How is that better than the two varint flavors that are already out there,
>> i.e. the bitcoin [1] and protocol buffers [2]?
>
> The protobuf one is *terrible* for CPU efficiency. You need to go through each
> byte, do masking and shifting for each byte and then have a conditional
> branch. That's bad from the the amount of instructions you need to execute,
> and *really* bad for the branch predictor.
>

Yeah, probably true - particularly for longer values. No argument here.

>
>> The first one seems quite efficient in how it encodes the length into very
>> few bits (which matters especially for small values). It's designed for
>> integers with 1B, 2B, 4B or 8B, but it can be extended to arbitrary lengths
>> fairly easily, I think:
>
>> Look at the first byte, and
>>
>> 0 - 243 - encoded as is
>> 244 - 1 byte
>> 245 - 2 bytes
>> 246 - 3 bytes
>> 247 - 4 bytes
>> 248 - 5 bytes
>> 249 - 6 bytes
>> 250 - 7 bytes
>> 251 - 8 bytes
>> 252 - next 1 byte is length
>> 253 - next 2 bytes are length
>> 254 - next 3 bytes are length
>> 255 - next 4 bytes are length
>
>> If we want to support longer lengths, we'd have to reserve an extra value
>> (which reduces the number of values that require a single byte).
>
> I think that's not a bad scheme. I think it may end up being a bit more
> expensive to decode because you need more branches instead of using
> find-first-set type instructions.
>

I don't think it requires many branches, because you can essentially do

if (byte[0] <= 243)
length = 0
else if (byte[0] <= 251)
length = byte[0] - 243
else
{
length_bytes = byte[0] - 251;
... read length_bytes, decode length
}

but I haven't tried implementing it and maybe my intuition is wrong.

Or maybe it'd be a good scheme for on-disk format, but poor for memory.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company