Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Let's Make a Varint

carlmastrangelo.com

Post reply on HN
Print view View original

11–20 of 22 posts

Re: Let's Make a Varint

#11

Post by arielweisberg »

daurnimator wrote: post #6
JonathonW wrote: post #3

Something probably not particularly important to the author (given that he's just using these essentially as a serial number), but worth mentioning for general use: > Varints can represent negative numbers too, by casting them to unsigned numbers first. But, assuming you're working with twos-complement numbers, it's going to be really inefficient, because small negative numbers are going to end up represented as extr…

FWIW the protobuf varint encoding was seen as a mistake by the inventor. https://groups.google.com/d/msg/capnproto/Qxw7YSoPP18/HS06Kc...

The mistake wasn't that particular varint encoding, but that it was variable length. That means you need to perform more complex decoding which is not the tradeoff chosen for Cap N Proto.

Re: Let's Make a Varint

#12

Post by [deleted] »

jholman wrote: post #8
daurnimator wrote: post #6

Earlier quoted context omitted.

FWIW the protobuf varint encoding was seen as a mistake by the inventor. https://groups.google.com/d/msg/capnproto/Qxw7YSoPP18/HS06Kc...

First of all, I believe that Kenton Varda is not the inventor of protobuffs, but rather a Google engineer who did a bunch of work on Protobuffs v2 (I believe on both of the v2 specs for protobuffs, because there are two different v2s). He is certainly quite knowledgeable, but not "the inventor". Second, while he does characterize it as a "huge mistake" for encoding/decoding performance reasons, there are a few caveat…

[deleted]

Re: Let's Make a Varint

#13

Post by deckar01 »

hyperpape wrote: post #5

"No “u”, (and no “o” or “i”) so accidental profanity cannot happen." h0ly fvcking sh1t! It's a good try, and making all the letters lowercase makes the numbers as vowels less legible. But if you're creating random strings you will create profanity and slurs.

I find the entire premise of the chosen alphabet rediculous. Long, random IDs are not for typing nor reading. It doesn't sound like they are even being used for user facing URLs.

Re: Let's Make a Varint

#14

Post by JonathonW »

arielweisberg wrote: post #11
daurnimator wrote: post #6

Earlier quoted context omitted.

FWIW the protobuf varint encoding was seen as a mistake by the inventor. https://groups.google.com/d/msg/capnproto/Qxw7YSoPP18/HS06Kc...

The mistake wasn't that particular varint encoding, but that it was variable length. That means you need to perform more complex decoding which is not the tradeoff chosen for Cap N Proto.

The protobuf varint format itself actually is pretty expensive to decode-- the way it's encoded pretty much mandates a branch per seven bit chunk (of the resulting integer); you can't tell in advance how long an integer is (as opposed to a length-prefixed varint, where you can).

That's in addition to the encoding-independent overhead inherent to any variable-length integer scheme, which is what mandates the encoding/decoding step in protobuf. Combined, this makes protobuf pretty expensive to decode (protobuf varints are everywhere; they're used for field keys and length delimiters for length-delimited field types).

That's unrelated to ZigZag encoding of negative numbers, though, which is fairly straightforward and computationally inexpensive (it's a couple bitshifts and an XOR).

Re: Let's Make a Varint

#15

Post by groovy2shoes »

JonathonW wrote: post #3

Something probably not particularly important to the author (given that he's just using these essentially as a serial number), but worth mentioning for general use: > Varints can represent negative numbers too, by casting them to unsigned numbers first. But, assuming you're working with twos-complement numbers, it's going to be really inefficient, because small negative numbers are going to end up represented as extr…

Any good reason not to just use a single sign bit?

Re: Let's Make a Varint

#16

Post by kentonv »

daurnimator wrote: post #6
JonathonW wrote: post #3

Something probably not particularly important to the author (given that he's just using these essentially as a serial number), but worth mentioning for general use: > Varints can represent negative numbers too, by casting them to unsigned numbers first. But, assuming you're working with twos-complement numbers, it's going to be really inefficient, because small negative numbers are going to end up represented as extr…

FWIW the protobuf varint encoding was seen as a mistake by the inventor. https://groups.google.com/d/msg/capnproto/Qxw7YSoPP18/HS06Kc...

I'm not the inventor of protobuf, just a guy who rewrote and open sourced it. My rewrite did not change the underlying encoding.

Re: Let's Make a Varint

#17

Post by kentonv »

jholman wrote: post #8
daurnimator wrote: post #6

Earlier quoted context omitted.

FWIW the protobuf varint encoding was seen as a mistake by the inventor. https://groups.google.com/d/msg/capnproto/Qxw7YSoPP18/HS06Kc...

First of all, I believe that Kenton Varda is not the inventor of protobuffs, but rather a Google engineer who did a bunch of work on Protobuffs v2 (I believe on both of the v2 specs for protobuffs, because there are two different v2s). He is certainly quite knowledgeable, but not "the inventor". Second, while he does characterize it as a "huge mistake" for encoding/decoding performance reasons, there are a few caveat…

FWIW, before I even joined Google, there were notes from Sanjay (the actual inventor) saying that varint was a poorly-chosen format due to excessive branching. IIRC he was arguing for a format where you can tell the length based on the first byte although I don't completely remember. In theory you could design such a format that is just as space-efficient as varint, by re-arranging bits.

Protobuf -- like most successful systems -- was not so much "designed" as it was "evolved" as a series of decisions made out of expediency rather than because they were the best possible answer. Overall it has obviously worked extremely well, but I would not assume that just because protobuf does something, it is good. (But I'd say that about just about everything, not just protobuf.)

Re: Let's Make a Varint

#18

Post by kentonv »

JonathonW wrote: post #14
arielweisberg wrote: post #11

Earlier quoted context omitted.

The mistake wasn't that particular varint encoding, but that it was variable length. That means you need to perform more complex decoding which is not the tradeoff chosen for Cap N Proto.

The protobuf varint format itself actually is pretty expensive to decode-- the way it's encoded pretty much mandates a branch per seven bit chunk (of the resulting integer); you can't tell in advance how long an integer is (as opposed to a length-prefixed varint, where you can). That's in addition to the encoding-independent overhead inherent to any variable-length integer scheme, which is what mandates the encoding/…

Funny thing is, despite all this, protobuf beats almost everything in benchmarks, in part due to excessive micro-optimization. Almost all varints in practice are 1-byte, so the larger ones don't really matter.

That said, the fact that you can't skip forward in a protobuf without parsing through all the previous fields is unfortunate in some use cases, hence Cap'n Proto.

Re: Let's Make a Varint

#19

Post by kentonv »

groovy2shoes wrote: post #15
JonathonW wrote: post #3

Something probably not particularly important to the author (given that he's just using these essentially as a serial number), but worth mentioning for general use: > Varints can represent negative numbers too, by casting them to unsigned numbers first. But, assuming you're working with twos-complement numbers, it's going to be really inefficient, because small negative numbers are going to end up represented as extr…

Any good reason not to just use a single sign bit?

Honestly, no, there's no "good" reason.

In practice the reason it ended up designed this way is because varint was introduced first with no special support for negative numbers, and then zigzag was introduced years later. Zigzag worked well because it stacked on top of the existing varint parser without changing it.

But for a new format with no backwards-compatibility constraints, it would probably make much more sense to use sign extension (so, the first encoded bit becomes the sign bit).

(I am the person who rewrote and open sourced protobufs at Google, though I am not the inventor.)

Re: Let's Make a Varint

#20

Post by groovy2shoes »

kentonv wrote: post #19
groovy2shoes wrote: post #15

Earlier quoted context omitted.

Any good reason not to just use a single sign bit?

Honestly, no, there's no "good" reason. In practice the reason it ended up designed this way is because varint was introduced first with no special support for negative numbers, and then zigzag was introduced years later. Zigzag worked well because it stacked on top of the existing varint parser without changing it. But for a new format with no backwards-compatibility constraints, it would probably make much more sen…

Cool. Thanks :)
Post reply on HN