0002-optimize-varint-with-lookup-table.patch

gistfile1.txt

From 2eee837216e575abd9e48a30c65161a42ad59117 Mon Sep 17 00:00:00 2001
From: Yibo Cai <[email protected]>
Date: Wed, 21 Aug 2024 06:40:48 -0400
Subject: [PATCH 2/2] optimize varint with lookup table

---
 src/google/protobuf/io/coded_stream.h | 20 ++++++++++++--------
 1 file changed, 12 insertions(+), 8 deletions(-)

diff --git a/src/google/protobuf/io/coded_stream.h b/src/google/protobuf/io/coded_stream.h
index dc03435b2..6a1bee6d1 100644
--- a/src/google/protobuf/io/coded_stream.h
+++ b/src/google/protobuf/io/coded_stream.h
@@ -1726,6 +1726,14 @@ inline uint8_t* CodedOutputStream::WriteTagToArray(uint32_t value,
 #define PROTOBUF_CODED_STREAM_H_PREFER_BSR 1
 #else
 #define PROTOBUF_CODED_STREAM_H_PREFER_BSR 0
+alignas(64) static constexpr uint8_t _varint64_lut[65] = {
+  10,9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 7,
+  7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5,
+  5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3,
+  3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
+  1
+};
+static const uint8_t* _varint32_lut = _varint64_lut + 32;
 #endif
 inline size_t CodedOutputStream::VarintSize32(uint32_t value) {
 #if PROTOBUF_CODED_STREAM_H_PREFER_BSR
@@ -1736,8 +1744,7 @@ inline size_t CodedOutputStream::VarintSize32(uint32_t value) {
   return static_cast<size_t>((log2value * 9 + (64 + 9)) / 64);
 #else
   uint32_t clz = absl::countl_zero(value);
-  return static_cast<size_t>(
-      ((std::numeric_limits<uint32_t>::digits * 9 + 64) - (clz * 9)) / 64);
+  return static_cast<size_t>(_varint32_lut[clz]);
 #endif
 }
 
@@ -1749,8 +1756,7 @@ inline size_t CodedOutputStream::VarintSize32PlusOne(uint32_t value) {
   return static_cast<size_t>((log2value * 9 + (64 + 9) + 64) / 64);
 #else
   uint32_t clz = absl::countl_zero(value);
-  return static_cast<size_t>(
-      ((std::numeric_limits<uint32_t>::digits * 9 + 64 + 64) - (clz * 9)) / 64);
+  return static_cast<size_t>(_varint32_lut[clz]) + 1;
 #endif
 }
 
@@ -1763,8 +1769,7 @@ inline size_t CodedOutputStream::VarintSize64(uint64_t value) {
   return static_cast<size_t>((log2value * 9 + (64 + 9)) / 64);
 #else
   uint32_t clz = absl::countl_zero(value);
-  return static_cast<size_t>(
-      ((std::numeric_limits<uint64_t>::digits * 9 + 64) - (clz * 9)) / 64);
+  return _varint64_lut[clz];
 #endif
 }
 
@@ -1776,8 +1781,7 @@ inline size_t CodedOutputStream::VarintSize64PlusOne(uint64_t value) {
   return static_cast<size_t>((log2value * 9 + (64 + 9) + 64) / 64);
 #else
   uint32_t clz = absl::countl_zero(value);
-  return static_cast<size_t>(
-      ((std::numeric_limits<uint64_t>::digits * 9 + 64 + 64) - (clz * 9)) / 64);
+  return _varint64_lut[clz] + 1;
 #endif
 }
 
-- 
2.39.2