Re: A varint implementation for PG?

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.

> 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.

Greetings,

Andres Freund