Optimize varints

Before: %% Run on (56 X 3200 MHz CPU s) CPU Caches: L1 Data 32 KiB (x28) L1 Instruction 32 KiB (x28) L2 Unified 256 KiB (x28) L3 Unified 35840 KiB (x2) Load Average: 1.29, 2.30, 2.18 ***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead. ----------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------- BM_SmallVarUint 275 ns 275 ns 1843898 BM_MediumVarUint 825 ns 824 ns 843158 BM_LargeVarUint 1200 ns 1200 ns 585964 %% After: %% Run on (56 X 3200 MHz CPU s) CPU Caches: L1 Data 32 KiB (x28) L1 Instruction 32 KiB (x28) L2 Unified 256 KiB (x28) L3 Unified 35840 KiB (x2) Load Average: 1.67, 1.73, 1.74 ***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead. ----------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------- BM_SmallVarUint 131 ns 130 ns 5345527 BM_MediumVarUint 505 ns 505 ns 1000000 BM_LargeVarUint 793 ns 793 ns 871621 %%
author: babenko <babenko@yandex-team.com> 2023-03-10 15:58:08 +0300
committer: babenko <babenko@yandex-team.com> 2023-03-10 15:58:08 +0300
commit: a22464af67422add223a24051527992cf49777a6 (patch)
tree: b2482b85766c8083d9fbff512fe3f910951f9154 /library/cpp/yt/coding/varint-inl.h
parent: 3c4e50751cbe95a6e55c69ce26159de97fdc9a74 (diff)
download: ydb-a22464af67422add223a24051527992cf49777a6.tar.gz
1 files changed, 152 insertions, 89 deletions
diff --git a/library/cpp/yt/coding/varint-inl.h b/library/cpp/yt/coding/varint-inl.h
index f0a09e9d30..ed0bfc508c 100644
--- a/library/cpp/yt/coding/varint-inl.h
+++ b/library/cpp/yt/coding/varint-inl.h
@@ -6,158 +6,216 @@
 
 #include "zig_zag.h"
 
+#include <library/cpp/yt/exception/exception.h>
+
+#include <array>
+
 namespace NYT {
 
 ////////////////////////////////////////////////////////////////////////////////
 
-template <class TWriteCallback>
-Y_FORCE_INLINE int WriteVarUint64Impl(TWriteCallback doWrite, ui64 value)
+inline int WriteVarUint64(char* output, ui64 value)
 {
-    bool stop = false;
-    int bytesWritten = 0;
-    while (!stop) {
-        ++bytesWritten;
-        ui8 byte = static_cast<ui8>(value | 0x80);
+    output[0] = static_cast<ui8>(value);
+    if (Y_LIKELY(value < 0x80)) {
+        return 1;
+    }
+    output[0] |= 0x80;
+    value >>= 7;
+    output[1] = static_cast<ui8>(value);
+    if (Y_LIKELY(value < 0x80)) {
+        return 2;
+    }
+    int count = 2;
+    do {
+        output[count - 1] |= 0x80;
         value >>= 7;
-        if (value == 0) {
-            stop = true;
-            byte &= 0x7F;
-        }
-        doWrite(byte);
+        output[count] = static_cast<ui8>(value);
+        ++count;
+    } while (Y_UNLIKELY(value >= 0x80));
+    return count;
+}
+
+inline int WriteVarUint64(IOutputStream* output, ui64 value)
+{
+    std::array<char, MaxVarUint64Size> buffer;
+    auto size = WriteVarUint64(buffer.data(), value);
+    output->Write(buffer.data(), size);
+    return size;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+namespace NDetail {
+
+template <class T, size_t N>
+T ReadVarUintKnownSize(const char* buffer)
+{
+    auto result = static_cast<T>(static_cast<ui8>(buffer[N - 1])) << (7 * (N - 1));
+    for (size_t i = 0, offset = 0; i < N - 1; i++, offset += 7) {
+        result += static_cast<T>(static_cast<ui8>(buffer[i]) - 0x80) << offset;
     }
-    return bytesWritten;
+    return result;
 }
 
-// These are optimized versions of these Read/Write functions in protobuf/io/coded_stream.cc.
-Y_FORCE_INLINE int WriteVarUint64(IOutputStream* output, ui64 value)
+} // namespace NDetail
+
+#define XX(type, size) \
+    if (static_cast<ui8>(input[size - 1]) < 0x80) { \
+        *value = NYT::NDetail::ReadVarUintKnownSize<type, size>(input); \
+        return size; \
+    }
+
+Y_FORCE_INLINE int ReadVarUint32(const char* input, ui32* value)
 {
-    return WriteVarUint64Impl([&] (ui8 byte) {
-        output->Write(byte);
-    }, value);
+    XX(ui64, 1)
+    XX(ui64, 2)
+    XX(ui64, 3)
+    XX(ui64, 4)
+    XX(ui64, 5)
+    throw TSimpleException("Value is too big for varuint32");
 }
 
-Y_FORCE_INLINE int WriteVarUint64(char* output, ui64 value)
+Y_FORCE_INLINE int ReadVarUint64(const char* input, ui64* value)
 {
-    return WriteVarUint64Impl([&] (ui8 byte) {
-        *output++ = byte;
-    }, value);
+    XX(ui64, 1)
+    XX(ui64, 2)
+    XX(ui64, 3)
+    XX(ui64, 4)
+    XX(ui64, 5)
+    XX(ui64, 6)
+    XX(ui64, 7)
+    XX(ui64, 8)
+    XX(ui64, 9)
+    XX(ui64, 10)
+    throw TSimpleException("Value is too big for varuint64");
 }
 
+#undef XX
+
 ////////////////////////////////////////////////////////////////////////////////
 
+namespace NDetail {
+
 template <class TOutput>
 Y_FORCE_INLINE int WriteVarUint32Impl(TOutput output, ui32 value)
 {
     return WriteVarUint64(output, static_cast<ui64>(value));
 }
 
-Y_FORCE_INLINE int WriteVarUint32(IOutputStream* output, ui32 value)
+template <class TOutput>
+Y_FORCE_INLINE int WriteVarInt32Impl(TOutput output, i32 value)
 {
-    return WriteVarUint32Impl(output, value);
+    return WriteVarUint64(output, ZigZagEncode32(value));
 }
 
-Y_FORCE_INLINE int WriteVarUint32(char* output, ui32 value)
+template <class TOutput>
+Y_FORCE_INLINE int WriteVarInt64Impl(TOutput output, i64 value)
 {
-    return WriteVarUint32Impl(output, value);
+    return WriteVarUint64(output, ZigZagEncode64(value));
 }
 
-////////////////////////////////////////////////////////////////////////////////
+} // namespace NDetail
 
-template <class TOutput>
-Y_FORCE_INLINE int WriteVarInt32Impl(TOutput output, i32 value)
+Y_FORCE_INLINE int WriteVarUint32(IOutputStream* output, ui32 value)
 {
-    return WriteVarUint64(output, static_cast<ui64>(ZigZagEncode32(value)));
+    return NYT::NDetail::WriteVarUint32Impl(output, value);
 }
 
-Y_FORCE_INLINE int WriteVarInt32(IOutputStream* output, i32 value)
+Y_FORCE_INLINE int WriteVarUint32(char* output, ui32 value)
 {
-    return WriteVarInt32Impl(output, value);
+    return NYT::NDetail::WriteVarUint32Impl(output, value);
 }
 
-Y_FORCE_INLINE int WriteVarInt32(char* output, i32 value)
+Y_FORCE_INLINE int WriteVarInt32(IOutputStream* output, i32 value)
 {
-    return WriteVarInt32Impl(output, value);
+    return NYT::NDetail::WriteVarInt32Impl(output, value);
 }
 
-////////////////////////////////////////////////////////////////////////////////
-
-template <class TOutput>
-Y_FORCE_INLINE int WriteVarInt64Impl(TOutput output, i64 value)
+Y_FORCE_INLINE int WriteVarInt32(char* output, i32 value)
 {
-    return WriteVarUint64(output, static_cast<ui64>(ZigZagEncode64(value)));
+    return NYT::NDetail::WriteVarInt32Impl(output, value);
 }
 
 Y_FORCE_INLINE int WriteVarInt64(IOutputStream* output, i64 value)
 {
-    return WriteVarInt64Impl(output, value);
+    return NYT::NDetail::WriteVarInt64Impl(output, value);
 }
 
 Y_FORCE_INLINE int WriteVarInt64(char* output, i64 value)
 {
-    return WriteVarInt64Impl(output, value);
+    return NYT::NDetail::WriteVarInt64Impl(output, value);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 
+namespace NDetail {
+
 template <class TReadCallback>
-Y_FORCE_INLINE int ReadVarUint64Impl(TReadCallback doRead, ui64* value)
+int ReadVarUint64Impl(ui64* value, TReadCallback&& doRead)
 {
     size_t count = 0;
     ui64 result = 0;
 
     ui8 byte;
     do {
-        if (7 * count > 8 * sizeof(ui64) ) {
-            throw TSimpleException("Value is too big for varuint64");
-        }
         byte = doRead();
         result |= (static_cast<ui64> (byte & 0x7F)) << (7 * count);
         ++count;
+        if (count > MaxVarUint64Size) {
+            throw TSimpleException("Value is too big for varuint64");
+        }
     } while (byte & 0x80);
 
     *value = result;
     return count;
 }
 
-Y_FORCE_INLINE int ReadVarUint64(IInputStream* input, ui64* value)
+inline int ReadVarUint64Fallback(const char* input, const char* end, ui64* value)
 {
-    return ReadVarUint64Impl([&] () {
-        char byte;
-        if (input->Read(&byte, 1) != 1) {
-            throw TSimpleException("Premature end of stream while reading varuint64");
-        }
-        return byte;
-    }, value);
+    return ReadVarUint64Impl(
+        value,
+        [&] {
+            if (input == end) {
+                throw TSimpleException("Premature end of data while reading varuint64");
+            }
+            return *input++;
+        });
 }
 
-Y_FORCE_INLINE int ReadVarUint64(const char* input, ui64* value)
+} // namespace NDetail
+
+inline int ReadVarUint64(IInputStream* input, ui64* value)
 {
-    return ReadVarUint64Impl([&] () {
-        char byte = *input;
-        ++input;
-        return byte;
-    }, value);
+    return NYT::NDetail::ReadVarUint64Impl(
+        value,
+        [&] {
+            char byte;
+            if (input->Read(&byte, 1) != 1) {
+                throw TSimpleException("Premature end of stream while reading varuint64");
+            }
+            return byte;
+        });
 }
 
 Y_FORCE_INLINE int ReadVarUint64(const char* input, const char* end, ui64* value)
 {
-    return ReadVarUint64Impl([&] () {
-        if (input == end) {
-            throw TSimpleException("Premature end of data while reading varuint64");
-        }
-        char byte = *input;
-        ++input;
-        return byte;
-    }, value);
+    if (Y_LIKELY(static_cast<size_t>(end - input) >= MaxVarUint64Size)) {
+        return ReadVarUint64(input, value);
+    } else {
+        return NYT::NDetail::ReadVarUint64Fallback(input, end, value);
+    }
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 
-template <class... Args>
-Y_FORCE_INLINE int ReadVarUint32Impl(ui32* value, Args... args)
+namespace NDetail {
+
+template <class... TArgs>
+Y_FORCE_INLINE int ReadVarUint32Impl(ui32* value, TArgs&&... args)
 {
     ui64 varInt;
-    int bytesRead = ReadVarUint64(args..., &varInt);
+    int bytesRead = ReadVarUint64(std::forward<TArgs>(args)..., &varInt);
     if (varInt > std::numeric_limits<ui32>::max()) {
         throw TSimpleException("Value is too big for varuint32");
     }
@@ -165,28 +223,27 @@ Y_FORCE_INLINE int ReadVarUint32Impl(ui32* value, Args... args)
     return bytesRead;
 }
 
-Y_FORCE_INLINE int ReadVarUint32(IInputStream* input, ui32* value)
-{
-    return ReadVarUint32Impl(value, input);
-}
+} // namespace NDetail
 
-Y_FORCE_INLINE int ReadVarUint32(const char* input, ui32* value)
+Y_FORCE_INLINE int ReadVarUint32(IInputStream* input, ui32* value)
 {
-    return ReadVarUint32Impl(value, input);
+    return NYT::NDetail::ReadVarUint32Impl(value, input);
 }
 
 Y_FORCE_INLINE int ReadVarUint32(const char* input, const char* end, ui32* value)
 {
-    return ReadVarUint32Impl(value, input, end);
+    return NYT::NDetail::ReadVarUint32Impl(value, input, end);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 
-template <class... Args>
-Y_FORCE_INLINE int ReadVarInt32Impl(i32* value, Args... args)
+namespace NDetail {
+
+template <class... TArgs>
+Y_FORCE_INLINE int ReadVarInt32Impl(i32* value, TArgs&&... args)
 {
     ui64 varInt;
-    int bytesRead = ReadVarUint64(args..., &varInt);
+    int bytesRead = ReadVarUint64(std::forward<TArgs>(args)..., &varInt);
     if (varInt > std::numeric_limits<ui32>::max()) {
         throw TSimpleException("Value is too big for varint32");
     }
@@ -194,45 +251,51 @@ Y_FORCE_INLINE int ReadVarInt32Impl(i32* value, Args... args)
     return bytesRead;
 }
 
+} // namespace NDetail
+
 Y_FORCE_INLINE int ReadVarInt32(IInputStream* input, i32* value)
 {
-    return ReadVarInt32Impl(value, input);
+    return NYT::NDetail::ReadVarInt32Impl(value, input);
 }
 
 Y_FORCE_INLINE int ReadVarInt32(const char* input, i32* value)
 {
-    return ReadVarInt32Impl(value, input);
+    return NYT::NDetail::ReadVarInt32Impl(value, input);
 }
 
 Y_FORCE_INLINE int ReadVarInt32(const char* input, const char* end, i32* value)
 {
-    return ReadVarInt32Impl(value, input, end);
+    return NYT::NDetail::ReadVarInt32Impl(value, input, end);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 
-template <class... Args>
-Y_FORCE_INLINE int ReadVarInt64Impl(i64* value, Args... args)
+namespace NDetail {
+
+template <class... TArgs>
+Y_FORCE_INLINE int ReadVarInt64Impl(i64* value, TArgs&&... args)
 {
     ui64 varInt;
-    int bytesRead = ReadVarUint64(args..., &varInt);
+    int bytesRead = ReadVarUint64(std::forward<TArgs>(args)..., &varInt);
     *value = ZigZagDecode64(varInt);
     return bytesRead;
 }
 
+} // namespace NDetail
+
 Y_FORCE_INLINE int ReadVarInt64(IInputStream* input, i64* value)
 {
-    return ReadVarInt64Impl(value, input);
+    return NYT::NDetail::ReadVarInt64Impl(value, input);
 }
 
 Y_FORCE_INLINE int ReadVarInt64(const char* input, i64* value)
 {
-    return ReadVarInt64Impl(value, input);
+    return NYT::NDetail::ReadVarInt64Impl(value, input);
 }
 
 Y_FORCE_INLINE int ReadVarInt64(const char* input, const char* end, i64* value)
 {
-    return ReadVarInt64Impl(value, input, end);
+    return NYT::NDetail::ReadVarInt64Impl(value, input, end);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
author	babenko <babenko@yandex-team.com>	2023-03-10 15:58:08 +0300
committer	babenko <babenko@yandex-team.com>	2023-03-10 15:58:08 +0300
commit	a22464af67422add223a24051527992cf49777a6 (patch)
tree	b2482b85766c8083d9fbff512fe3f910951f9154 /library/cpp/yt/coding/varint-inl.h
parent	3c4e50751cbe95a6e55c69ce26159de97fdc9a74 (diff)
download	ydb-a22464af67422add223a24051527992cf49777a6.tar.gz