[protobuf] what does "(log2value * 9 + 73) / 64" do in calculate the size of a varint?

[Yafei Liu]

I read the code `size_t CodedOutputStream::VarintSize32(uint32 value)` and found that after getting the most significant bits of a value, the code use "(log2value * 9 + 73) / 64" instead of "log2value / 7 + 1" to calculate the size need for this varint.

I'm curious how this "(log2value * 9 + 73) / 64" come? What's the mathematical principle here? The comment said: "Use an explicit multiplication to implement the divide of a number in the 1..63 range." but I just can't understand.

[Adam Cozzette]

I don't claim to fully understand this, but I believe it's a common kind of compiler optimization used for dividing an integer by a constant. See this article by Matt Godbolt under "Integer division by a constant". Ordinarily the compiler would handle this for you, but my guess is that we can be smarter than the compiler in this case since we know that the dividend is between 1 and 63.

On Tue, Sep 8, 2020 at 12:50 AM Yafei Liu <yf...@mobvoi.com> wrote:

I read the code `size_t CodedOutputStream::VarintSize32(uint32 value)` and found that after getting the most significant bits of a value, the code use "(log2value * 9 + 73) / 64" instead of "log2value / 7 + 1" to calculate the size need for this varint.

I'm curious how this "(log2value * 9 + 73) / 64" come? What's the mathematical principle here? The comment said: "Use an explicit multiplication to implement the divide of a number in the 1..63 range." but I just can't understand.

--
You received this message because you are subscribed to the Google Groups "Protocol Buffers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to protobuf+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/protobuf/CAMUQRevU9qOFO6qig_VVkSmk_iLHXOC008ua8jfGHNZNN8KsMw%40mail.gmail.com.

[Yafei Liu]

Adam I think you are right, after researching and considered the comment, I think this is the code to turns the division "log2value / 7 + 1" into multiplication. Never know this knowledge before, thanks.