3 ms·

Protobuf was the first major project I was aware of that uses zigzag encoding for integers. They then encode those integers using the typical 7 bit encoding sch

by eloff 4y ago

Protobuf was the first major project I was aware of that uses zigzag encoding for integers. They then encode those integers using the typical 7 bit encoding scheme where the msb indicates there's another byte following. I'm sure they weren't the first by any means though. I'm currently using this in a binary format for serializing dynamic JSON-like values that I invented and am implementing in Rust. I will release it as open source sometime next year.

tikhonj 4y ago
I first ran into this encoding scheme in Avro, which you could also describe as a format for dynamic JSON-like values :)
deleted 4y ago
[deleted]
ramranch 4y ago
Does your protocol provide any advantages over bincode?
- eloff 4y ago
  Yes, but not as a general purpose encoding. It's more fit for it's intended purpose.
anonymoushn 4y ago
This format makes it impossible to write fast decoders, as discussed elsewhere on the same blog as TFA: https://lemire.me/blog/2017/09/27/stream-vbyte-breaking-new-speed-records-for-integer-compression/ https://lemire.me/blog/2017/09/27/stream-vbyte-breaking-new-... So it would be sweet to instead use a format for which it is possible to write fast decoders
- eloff 4y ago
  Yeah, I don't like that method for encoding variable length integers. I usually use something I came up with years ago where the low 2 or 3 bits are the length - 1 in bytes. It's more compact and can be serialized/deserialized without branches in the common case. It uses the count leading zeroes instruction for encoding. I'm sure somebody else has come up with the idea as well. The downside is you can only represent 30 bits for u32 and 61 for u64. In many cases you know you don't have values that large, so it's fine. If you're encoding arrays of integers, Lemire has a library that uses vector instructions to encode them in the optimal number of bits. That's even better, but the use cases are far more restricted.

by eloff 4y ago

tikhonj 4y ago

I first ran into this encoding scheme in Avro, which you could also describe as a format for dynamic JSON-like values :)

deleted 4y ago

[deleted]

ramranch 4y ago

Does your protocol provide any advantages over bincode?

eloff 4y ago
Yes, but not as a general purpose encoding. It's more fit for it's intended purpose.

anonymoushn 4y ago

This format makes it impossible to write fast decoders, as discussed elsewhere on the same blog as TFA: https://lemire.me/blog/2017/09/27/stream-vbyte-breaking-new-speed-records-for-integer-compression/ https://lemire.me/blog/2017/09/27/stream-vbyte-breaking-new-... So it would be sweet to instead use a format for which it is possible to write fast decoders

eloff 4y ago
Yeah, I don't like that method for encoding variable length integers. I usually use something I came up with years ago where the low 2 or 3 bits are the length - 1 in bytes. It's more compact and can be serialized/deserialized without branches in the common case. It uses the count leading zeroes instruction for encoding. I'm sure somebody else has come up with the idea as well. The downside is you can only represent 30 bits for u32 and 61 for u64. In many cases you know you don't have values that large, so it's fine. If you're encoding arrays of integers, Lemire has a library that uses vector instructions to encode them in the optimal number of bits. That's even better, but the use cases are far more restricted.