intermediate changes

ref:2d4f292087954c9344efdabb7b2a67f466263c65
author: arcadia-devtools <arcadia-devtools@yandex-team.ru> 2022-06-09 14:39:19 +0300
committer: arcadia-devtools <arcadia-devtools@yandex-team.ru> 2022-06-09 14:39:19 +0300
commit: c04b663c7bb4b750deeb8f48f620497ec13da8fa (patch)
tree: 151ebc8bfdd2ad918caf5e6e2d8013e14272ddf8 /tools/enum_parser
parent: 0d55ca22c507d18c2f35718687e0b06d9915397b (diff)
download: ydb-c04b663c7bb4b750deeb8f48f620497ec13da8fa.tar.gz
5 files changed, 180 insertions, 16 deletions
diff --git a/tools/enum_parser/enum_parser/main.cpp b/tools/enum_parser/enum_parser/main.cpp
index 1985f2d42f..4ad43d4a35 100644
--- a/tools/enum_parser/enum_parser/main.cpp
+++ b/tools/enum_parser/enum_parser/main.cpp
@@ -246,7 +246,15 @@ void GenerateEnum(
     out << "    using TNameBufsBase = ::NEnumSerializationRuntime::TEnumDescription<" << name << ">;\n\n";
 
     // Initialization data
-    defineConstArray("    ", "TNameBufsBase::TEnumStringPair", "NAMES_INITIALIZATION_PAIRS", nameInitializerPairs);
+    {
+        out << "    static constexpr const std::array<TNameBufsBase::TEnumStringPair, " << nameInitializerPairs.size() << "> NAMES_INITIALIZATION_PAIRS_PAYLOAD = ::NEnumSerializationRuntime::TryStableSortKeys(";
+        out << "std::array<TNameBufsBase::TEnumStringPair, " << nameInitializerPairs.size() << ">{{\n";
+        for (const auto& it : nameInitializerPairs) {
+            out << "        " << it << ",\n";
+        }
+        out << "    }});\n";
+        out << "    " << "static constexpr const TArrayRef<const TNameBufsBase::TEnumStringPair> " << "NAMES_INITIALIZATION_PAIRS{NAMES_INITIALIZATION_PAIRS_PAYLOAD};\n\n";
+    }
     {
         StableSortBy(valueInitializerPairsUnsorted, [](const auto& pair) -> const TString& { return pair.second; });
         TVector<TString> valueInitializerPairs(Reserve(valueInitializerPairsUnsorted.size()));
diff --git a/tools/enum_parser/enum_serialization_runtime/ordered_pairs.h b/tools/enum_parser/enum_serialization_runtime/ordered_pairs.h
index 874c709418..4dce4dc3f3 100644
--- a/tools/enum_parser/enum_serialization_runtime/ordered_pairs.h
+++ b/tools/enum_parser/enum_serialization_runtime/ordered_pairs.h
@@ -1,20 +1,23 @@
 #pragma once
 
+#include <util/generic/algorithm.h>
 #include <util/generic/array_ref.h>
 #include <util/generic/strbuf.h>
+#include <array>
+#include <functional>
 
 namespace NEnumSerializationRuntime {
     enum class ESortOrder: int {
-        Unordered = 0,
-        Ascending = 1,
-        StrictlyAscending = 2,
-        DirectMapping = 3,
+        Unordered = 0,         // беспорядок
+        Ascending = 1,         // можно искать бинарным поиском, но есть эквивалентные ключи. Гланый ключ находится через lower_bound
+        StrictlyAscending = 2, //   + все ключи уникальны
+        DirectMapping = 3,     // последовательность целых чисел без пропусков, индекс элемента можно вычислить из его значения не делая поиск
     };
 
     template <typename TEnumRepresentationType>
     struct TEnumStringPair {
-        const TEnumRepresentationType Key;
-        const TStringBuf Name;
+        TEnumRepresentationType Key;
+        TStringBuf Name;
     };
 
     template <typename TEnumRepresentationType>
@@ -25,10 +28,12 @@ namespace NEnumSerializationRuntime {
         bool direct = true;
         bool strict = true;
         bool sorted = true;
-        TEnumRepresentationType expected = initializer.data()[0].Key;
-        for (size_t i = 1; i < initializer.size(); ++i) {
-            const auto& prev = initializer.data()[i - 1].Key;
-            const auto& next = initializer.data()[i - 0].Key;
+        const auto* data = initializer.data();
+        const size_t size = initializer.size();
+        TEnumRepresentationType expected = data[0].Key;
+        for (size_t i = 1; i < size; ++i) {
+            const auto& prev = data[i - 1].Key;
+            const auto& next = data[i - 0].Key;
             if (++expected != next) {
                 direct = false;
             }
@@ -53,13 +58,16 @@ namespace NEnumSerializationRuntime {
         }
         bool strict = true;
         bool sorted = true;
-        for (size_t i = 1; i < initializer.size(); ++i) {
-            const std::string_view prev = initializer.data()[i - 1].Name;
-            const std::string_view next = initializer.data()[i - 0].Name;
-            if (prev >= next) {
+        const auto* data = initializer.data();
+        const size_t size = initializer.size();
+        for (size_t i = 1; i < size; ++i) {
+            const std::string_view& prev = data[i - 1].Name;
+            const std::string_view& next = data[i - 0].Name;
+            const int cmp = prev.compare(next);
+            if (cmp >= 0) {
                 strict = false;
             }
-            if (prev > next) {
+            if (cmp > 0) {
                 sorted = false;
                 break;
             }
@@ -68,4 +76,59 @@ namespace NEnumSerializationRuntime {
                : sorted ? ESortOrder::Ascending
                         : ESortOrder::Unordered;
     }
+
+#if defined(__cpp_lib_array_constexpr) && defined(__cpp_lib_constexpr_algorithms) && defined(__cpp_lib_constexpr_functional)
+
+    // Функция должна состоять из единственного вызова
+    // std::stable_sort(v.begin(), v.end(), [](const T& a, const T& b) { return a.Key < b.Key; });
+    // и возврата отсортированного массива.
+    // Но в C++20 stable_sort ещё не имеет спецификатора constexpr и не может использоваться тут.
+    // Поэтому в текущей реализации вместо этого делается обычная нестабильная сортировка пар {ключ элемента, положение элемента}.
+    template <class T, size_t N>
+    constexpr std::array<T, N> TryStableSortKeys(std::array<T, N> v) {
+        // Компилятор обычно ограничивает число шагов, которые можно сделать при вычислении constexpr-функции (см. опции `-fconstexpr-steps=N` или `/constexpr:stepsN`).
+        // Число же шагов, необходимых для сортировки, зависит не только от длины массива,
+        // но и от используемого алгоритма, от числа вложенных функций в его реализации, и от наличия assert'ов в ней.
+        // Что также означает, что число шагов может меняться в несколько раз при смене реализации STL или при сборке с NDEBUG и без.
+        //
+        // Исчерпание бюджета на действия приведёт к ошибки компиляции без возможности восстановления.
+        // То есть без возможности обнаружить эту ситуацию и переключится на другой алгоритм.
+        //
+        // Поэтому максимальный размер сортируемого массива заранее ограничивается безопасной константой.
+        // А все массивы большего размера досортировываются уже во время исполнения программы.
+        constexpr size_t MAX_COMPILE_TIME_SORT_ARRAY_SIZE = 2'000;
+        if (v.size() > MAX_COMPILE_TIME_SORT_ARRAY_SIZE) {
+            return v;
+        }
+
+        // Многие перечисления уже отсортированы. Но текущая реализация constexpr std::sort в libcxx не проверяет этот случай и всегда работает за время Θ(NlogN)
+        if (IsSortedBy(v.begin(), v.end(), std::mem_fn(&T::Key))) {
+            return v;
+        }
+
+        std::array<const T*, N> ptrs;
+        Iota(ptrs.begin(), ptrs.end(), &v[0]);
+        auto cmpKeyPointersFn = [](const T* a, const T* b) {
+            if (a->Key != b->Key) {
+                return a->Key < b->Key;
+            }
+            return a < b; // ensure stable sort order
+        };
+        Sort(ptrs.begin(), ptrs.end(), cmpKeyPointersFn);
+
+        std::array<T, N> r;
+        for (size_t i = 0; i < N; ++i) {
+            r[i] = *ptrs[i];
+        }
+        return r;
+    }
+
+#else
+
+    template <class T, size_t N>
+    constexpr std::array<T, N> TryStableSortKeys(std::array<T, N> v) {
+        return v; // skip sort in case of old language version
+    }
+
+#endif
 }
diff --git a/tools/enum_parser/parse_enum/benchmark_build/README.md b/tools/enum_parser/parse_enum/benchmark_build/README.md
new file mode 100644
index 0000000000..255592bc99
--- /dev/null
+++ b/tools/enum_parser/parse_enum/benchmark_build/README.md
@@ -0,0 +1,2 @@
+Модуль для проверки компилируемости больших перечислений и замера времени.
+Размечен как unittest, но проверки делаются во время компиляции.
diff --git a/tools/enum_parser/parse_enum/benchmark_build/lib/gen.py b/tools/enum_parser/parse_enum/benchmark_build/lib/gen.py
new file mode 100644
index 0000000000..783ab9f181
--- /dev/null
+++ b/tools/enum_parser/parse_enum/benchmark_build/lib/gen.py
@@ -0,0 +1,60 @@
+#!/usr/bin/env python3
+# - * - encoding: UTF-8 - * -
+
+from argparse import ArgumentParser
+import random
+import sys
+import math
+
+
+def parse_args():
+    parser = ArgumentParser(description="")
+    parser.add_argument('--range', type=int)
+    parser.add_argument('--enum', nargs=2, action="append", metavar=("NAME", "SIZE"))
+    parser.add_argument('--namespace', type=str)
+    args = parser.parse_args()
+    return args
+
+
+def gen_enum(name, n):
+    rg = random.Random(n)
+    h1 = list(range(n))
+    h2 = list(range(n))
+    rg.shuffle(h1)
+    rg.shuffle(h2)
+
+    print("enum class %s {" % name)
+    for  k, v in zip(h1, h2):
+        print("    V%x = 0x%04x," % (k, v))
+    print("};")
+    print()
+
+
+def main():
+    args = parse_args()
+
+    print("#pragma once\n\n")
+
+    gr = {}
+    for name, size in args.enum or []:
+        assert name not in gr
+        gr[name] = int(size)
+    if args.range:
+        step = max(int(math.sqrt(args.range)), 1)
+        for s in range(args.range, -1, -step):
+            gr["EDenseEnum%04d" % s] = s
+
+    if args.namespace:
+        print(f"namespace {args.namespace} {{")
+
+    for name, size in sorted(gr.items(), key=lambda kv: -kv[1]):
+        gen_enum(name, size)
+
+    if args.namespace:
+        print(f"}} // namespace {args.namespace}")
+
+    return 0
+
+
+if __name__ == '__main__':
+    sys.exit(main())
diff --git a/tools/enum_parser/parse_enum/benchmark_build/ut/huge_enums_fallback_ut.cpp b/tools/enum_parser/parse_enum/benchmark_build/ut/huge_enums_fallback_ut.cpp
new file mode 100644
index 0000000000..8d6800946f
--- /dev/null
+++ b/tools/enum_parser/parse_enum/benchmark_build/ut/huge_enums_fallback_ut.cpp
@@ -0,0 +1,31 @@
+#include <tools/enum_parser/parse_enum/benchmark_build/lib/enum_huge.h_serialized.h>
+#include <tools/enum_parser/parse_enum/benchmark_build/lib/enum_enormous.h_serialized.h>
+#include <library/cpp/testing/unittest/registar.h>
+#include <util/generic/serialized_enum.h>
+#include <util/string/cast.h>
+
+
+namespace {
+    template <class EEnum>
+    void EnumerateEnum() {
+        const auto& allValues = GetEnumAllValues<EEnum>();
+
+        TString s;
+        for (EEnum e : allValues) {
+            UNIT_ASSERT_NO_EXCEPTION(s = ToString(e));
+            UNIT_ASSERT_NO_EXCEPTION(e = FromString<EEnum>(s));
+        }
+
+        EEnum tmp;
+        UNIT_ASSERT_VALUES_EQUAL(TryFromString<EEnum>("", tmp), false);
+    }
+}
+
+Y_UNIT_TEST_SUITE(TTestHugeEnums) {
+    Y_UNIT_TEST(Huge) {
+        EnumerateEnum<NHuge::EHuge>();
+    }
+    Y_UNIT_TEST(Enormous) {
+        EnumerateEnum<EEnormous>();
+    }
+};
author	arcadia-devtools <arcadia-devtools@yandex-team.ru>	2022-06-09 14:39:19 +0300
committer	arcadia-devtools <arcadia-devtools@yandex-team.ru>	2022-06-09 14:39:19 +0300
commit	c04b663c7bb4b750deeb8f48f620497ec13da8fa (patch)
tree	151ebc8bfdd2ad918caf5e6e2d8013e14272ddf8 /tools/enum_parser
parent	0d55ca22c507d18c2f35718687e0b06d9915397b (diff)
download	ydb-c04b663c7bb4b750deeb8f48f620497ec13da8fa.tar.gz