[KIKIMR-15108] Add perf programs to build

ref:8f081efde09627da76e52231d32a83e34b78c1e4

4 files changed, 1097 insertions, 0 deletions

diff --git a/library/cpp/presort/CMakeLists.txt b/library/cpp/presort/CMakeLists.txt
new file mode 100644
index 0000000000..7fd3c07814
--- /dev/null
+++ b/library/cpp/presort/CMakeLists.txt
@@ -0,0 +1,17 @@
+
+# This file was gererated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+
+add_library(library-cpp-presort)
+target_link_libraries(library-cpp-presort PUBLIC
+  contrib-libs-cxxsupp
+  yutil
+)
+target_sources(library-cpp-presort PRIVATE
+  ${CMAKE_SOURCE_DIR}/library/cpp/presort/presort.cpp
+)
diff --git a/library/cpp/presort/presort.cpp b/library/cpp/presort/presort.cpp
new file mode 100644
index 0000000000..01a9634a6c
--- /dev/null
+++ b/library/cpp/presort/presort.cpp
@@ -0,0 +1 @@
+#include "presort.h"
diff --git a/library/cpp/presort/presort.h b/library/cpp/presort/presort.h
new file mode 100644
index 0000000000..0294892580
--- /dev/null
+++ b/library/cpp/presort/presort.h
@@ -0,0 +1,553 @@
+#pragma once
+
+#include <util/generic/bitops.h>
+#include <util/generic/maybe.h>
+#include <util/generic/strbuf.h>
+#include <util/generic/string.h>
+#include <util/stream/output.h>
+
+#include <cfloat>
+#include <cmath>
+
+// TODO: remove when switched to c++11 stl
+#if _LIBCPP_STD_VER >= 11
+#include <limits>
+#else
+#define PRESORT_FP_DISABLED
+#endif
+
+/*
+    Serialization PREServing ORder of Tuples of numbers, strings and optional numbers or strings
+    Lexicographic ordering of serialized tuples will be the same as of non-serialized
+    Descending order is supported
+*/
+
+namespace NPresort {
+    namespace NImpl {
+        enum ECode {
+            StringEnd = 0x00,
+            StringPart = 0x10,
+            IntNeg = 0x20,
+            IntNonNeg = 0x30,
+            Unsigned = 0x40,
+            Float = 0x50,
+            Double = 0x60,
+            Extension = 0x70,
+            Descending = 0x80,
+        };
+
+        static const ui8 CodeMask = 0xf0;
+        static const ui8 LengthMask = 0x0f;
+        static const ui8 Optional = 0x01;
+        static const ui8 OptionalFilled = 0x02;
+
+        enum EFPCode {
+            NegInf = 0x00,
+            NegFar = 0x01,
+            NegNear = 0x02,
+            NegSub = 0x03,
+            Zero = 0x04,
+            PosSub = 0x05,
+            PosNear = 0x06,
+            PosFar = 0x07,
+            PosInf = 0x08,
+            Nan = 0x09,
+            Disabled = 0x0f
+        };
+
+        static const ui8 FPCodeMask = 0x0f;
+
+        static const size_t BlockLength = 15;
+        static const size_t BufferLength = BlockLength + 1;
+
+        static const float FloatSignificandBase = pow((float)FLT_RADIX, FLT_MANT_DIG);
+        static const double DoubleSignificandBase = pow((double)FLT_RADIX, DBL_MANT_DIG);
+
+        template <typename T>
+        struct TSignificandBase {
+            static double Value() {
+                return DoubleSignificandBase;
+            }
+        };
+
+        template <>
+        struct TSignificandBase<float> {
+            static float Value() {
+                return FloatSignificandBase;
+            }
+        };
+
+        struct TDecodeContext {
+            ECode Code;
+            TString Err;
+            TString Str;
+            ui32 StrBlocks = 0;
+            i64 SignedVal = 0;
+            ui64 UnsignedVal = 0;
+            float FloatVal = 0;
+            double DoubleVal = 0;
+            bool Optional = false;
+            bool Filled = false;
+        };
+
+        class TBlock {
+        public:
+            TBlock()
+                : Len(0)
+            {
+                memset(Buf, 0, BufferLength);
+            }
+
+            void Put(IOutputStream& out) const {
+                out.Write(Buf, Len);
+            }
+
+            ui8 GetLen() const {
+                return Len;
+            }
+
+            void EncodeSignedInt(i64 val, bool desc) {
+                const bool neg = val < 0;
+                const ui8 bytes = val ? EncodeInt(neg ? -val : val) : 0;
+                Set(neg ? ((~IntNeg) & CodeMask) : IntNonNeg, bytes, neg != desc);
+            }
+
+            void EncodeUnsignedInt(ui64 val, bool desc, bool end = false) {
+                const ui8 bytes = val ? EncodeInt(val) : 0;
+                Set(end ? StringEnd : Unsigned, bytes, desc);
+            }
+
+            bool EncodeFloating(float val, bool desc) {
+                const EFPCode code = FPCode(val);
+                Set(Float | code, 0, desc);
+                return FPNeedEncodeValue(code);
+            }
+
+            bool EncodeFloating(double val, bool desc) {
+                const EFPCode code = FPCode(val);
+                Set(Double | code, 0, desc);
+                return FPNeedEncodeValue(code);
+            }
+
+            void EncodeString(TStringBuf str, bool desc) {
+                memcpy(Buf + 1, str.data(), str.size());
+                Set(StringPart, BlockLength, desc);
+            }
+
+            void EncodeOptional(bool filled, bool desc) {
+                Set(Extension | Optional | (filled ? OptionalFilled : 0), 0, desc);
+            }
+
+            bool Decode(TDecodeContext& ctx, TStringBuf str) {
+                if (str.empty()) {
+                    ctx.Err = "No data";
+                    return false;
+                }
+                Len = 1;
+                bool desc = false;
+                ui8 byte = str[0];
+                ui8 code = byte & CodeMask;
+                if (code >= Descending) {
+                    desc = true;
+                    byte = ~byte;
+                    code = byte & CodeMask;
+                }
+                switch (code) {
+                    case StringPart:
+                        if (!Init(ctx, str, byte, desc)) {
+                            return false;
+                        }
+                        ctx.Str.append((const char*)Buf + 1, Len - 1);
+                        ++ctx.StrBlocks;
+                        break;
+                    case StringEnd: {
+                        if (!Init(ctx, str, byte, desc)) {
+                            return false;
+                        }
+                        const ui64 val = DecodeInt();
+                        if (val) {
+                            if (!ctx.StrBlocks) {
+                                ctx.Err = "Unexpected end of string";
+                                return false;
+                            }
+                            if (val > BlockLength) {
+                                ctx.Err = "Invalid string terminal";
+                                return false;
+                            }
+                            ctx.Str.erase(BlockLength * (ctx.StrBlocks - 1) + val);
+                        }
+                        ctx.StrBlocks = 0;
+                        break;
+                    }
+                    case IntNeg:
+                        if (!Init(ctx, str, ~byte, !desc)) {
+                            return false;
+                        }
+                        ctx.SignedVal = -(i64)DecodeInt();
+                        break;
+                    case IntNonNeg:
+                        if (!Init(ctx, str, byte, desc)) {
+                            return false;
+                        }
+                        ctx.SignedVal = DecodeInt();
+                        break;
+                    case Unsigned:
+                        if (!Init(ctx, str, byte, desc)) {
+                            return false;
+                        }
+                        ctx.UnsignedVal = DecodeInt();
+                        break;
+                    case Float:
+                        if (!DecodeFloating((EFPCode)(byte & FPCodeMask), ctx.FloatVal, ctx, str.Skip(Len))) {
+                            return false;
+                        }
+                        break;
+                    case Double:
+                        if (!DecodeFloating((EFPCode)(byte & FPCodeMask), ctx.DoubleVal, ctx, str.Skip(Len))) {
+                            return false;
+                        }
+                        break;
+                    case Extension:
+                        ctx.Optional = byte & Optional;
+                        ctx.Filled = byte & OptionalFilled;
+                        break;
+                    default:
+                        Y_FAIL("Invalid record code: %d", (int)code);
+                }
+                ctx.Code = (ECode)code;
+                return true;
+            }
+
+        private:
+            bool Init(TDecodeContext& ctx, TStringBuf str, ui8 byte, bool invert) {
+                Len = (byte & LengthMask) + 1;
+                if (Len > BufferLength) {
+                    ctx.Err = "Invalid block length";
+                    return false;
+                }
+                if (Len > str.size()) {
+                    ctx.Err = "Unexpected end of data";
+                    return false;
+                }
+                memcpy(Buf, str.data(), Len);
+                if (invert) {
+                    Invert();
+                }
+                return true;
+            }
+
+            ui64 DecodeInt() const {
+                ui64 val = 0;
+                for (ui8 b = 1; b < Len; ++b) {
+                    const ui8 shift = Len - b - 1;
+                    if (shift < sizeof(ui64)) {
+                        val |= ((ui64)Buf[b]) << (8 * shift);
+                    }
+                }
+                return val;
+            }
+
+            ui8 EncodeInt(ui64 val) {
+                const ui8 bytes = GetValueBitCount(val) / 8 + 1;
+                for (ui8 b = 1; b <= bytes; ++b) {
+                    const ui8 shift = bytes - b;
+                    if (shift < sizeof(ui64)) {
+                        Buf[b] = val >> (8 * shift);
+                    }
+                }
+                return bytes;
+            }
+
+            static bool FPNeedEncodeValue(EFPCode code) {
+                return code != Nan && code != Zero && code != NegInf && code != PosInf && code != Disabled;
+            }
+
+            template <typename T>
+            static EFPCode FPCode(T val) {
+#ifdef PRESORT_FP_DISABLED
+                Y_UNUSED(val);
+                return Disabled;
+#else
+                switch (std::fpclassify(val)) {
+                    case FP_INFINITE:
+                        return val < 0 ? NegInf : PosInf;
+                    case FP_NAN:
+                        return Nan;
+                    case FP_ZERO:
+                        return Zero;
+                    case FP_SUBNORMAL:
+                        return val < 0 ? NegSub : PosSub;
+                    case FP_NORMAL:
+                        break;
+                }
+                if (val < 0) {
+                    return val > -1 ? NegNear : NegFar;
+                }
+                return val < 1 ? PosNear : PosFar;
+#endif
+            }
+
+            template <typename T>
+            bool DecodeFloating(EFPCode code, T& val, TDecodeContext& ctx, TStringBuf data) {
+#ifdef PRESORT_FP_DISABLED
+                Y_UNUSED(code);
+                Y_UNUSED(val);
+                Y_UNUSED(data);
+                ctx.Err = "Floating point numbers support is disabled";
+                return false;
+#else
+                switch (code) {
+                    case Zero:
+                        val = 0;
+                        return true;
+                    case NegInf:
+                        val = -std::numeric_limits<T>::infinity();
+                        return true;
+                    case PosInf:
+                        val = std::numeric_limits<T>::infinity();
+                        return true;
+                    case Nan:
+                        val = std::numeric_limits<T>::quiet_NaN();
+                        return true;
+                    case Disabled:
+                        ctx.Err = "Floating point numbers support was disabled on encoding";
+                        return false;
+                    default:
+                        break;
+                }
+                i64 exp = 0;
+                i64 sig = 0;
+                if (!DecodeFloatingPart(exp, ctx, data) || !DecodeFloatingPart(sig, ctx, data)) {
+                    return false;
+                }
+                val = ldexp(sig / TSignificandBase<T>::Value(), exp);
+                return true;
+#endif
+            }
+
+            bool DecodeFloatingPart(i64& val, TDecodeContext& ctx, TStringBuf& data) {
+                TBlock block;
+                if (!block.Decode(ctx, data)) {
+                    return false;
+                }
+                if (ctx.Code != IntNeg && ctx.Code != IntNonNeg) {
+                    ctx.Err = "Invalid floating part";
+                    return false;
+                }
+                val = ctx.SignedVal;
+                ctx.SignedVal = 0;
+                data.Skip(block.GetLen());
+                Len += block.GetLen();
+                return true;
+            }
+
+            void Set(ui8 code, ui8 size, bool invert) {
+                Y_ASSERT(size <= BlockLength);
+                Buf[0] = code | size;
+                Len = size + 1;
+                if (invert) {
+                    Invert();
+                }
+            }
+
+            void Invert() {
+                Y_ASSERT(Len <= BufferLength);
+                for (ui8 b = 0; b < Len; ++b) {
+                    Buf[b] = ~Buf[b];
+                }
+            }
+
+        private:
+            ui8 Buf[BufferLength];
+            ui8 Len;
+        };
+    }
+
+    inline void EncodeSignedInt(IOutputStream& out, i64 val, bool desc = false) {
+        NImpl::TBlock block;
+        block.EncodeSignedInt(val, desc);
+        block.Put(out);
+    }
+
+    inline void EncodeUnsignedInt(IOutputStream& out, ui64 val, bool desc = false) {
+        NImpl::TBlock block;
+        block.EncodeUnsignedInt(val, desc);
+        block.Put(out);
+    }
+
+    template <typename T>
+    inline void EncodeFloating(IOutputStream& out, T val, bool desc = false) {
+        NImpl::TBlock head;
+        const bool encodeValue = head.EncodeFloating(val, desc);
+        head.Put(out);
+
+        if (encodeValue) {
+            int exponent = 0;
+            i64 significand = 0;
+            significand = frexp(val, &exponent) * NImpl::TSignificandBase<T>::Value();
+
+            NImpl::TBlock exp;
+            exp.EncodeSignedInt(exponent, desc);
+            exp.Put(out);
+
+            NImpl::TBlock sig;
+            sig.EncodeSignedInt(significand, desc);
+            sig.Put(out);
+        }
+    }
+
+    inline void EncodeString(IOutputStream& out, TStringBuf str, bool desc = false) {
+        size_t part = 0;
+        while (!str.empty()) {
+            part = Min(str.size(), NImpl::BlockLength);
+            NImpl::TBlock block;
+            block.EncodeString(str.Head(part), desc);
+            block.Put(out);
+            str.Skip(part);
+        }
+        // Encode string end token
+        NImpl::TBlock end;
+        end.EncodeUnsignedInt(part, desc, true);
+        end.Put(out);
+    }
+
+    template <bool Signed>
+    struct TEncodeInt {
+        static void Do(IOutputStream& out, i64 val, bool desc) {
+            EncodeSignedInt(out, val, desc);
+        }
+    };
+
+    template <>
+    struct TEncodeInt<false> {
+        static void Do(IOutputStream& out, ui64 val, bool desc) {
+            EncodeUnsignedInt(out, val, desc);
+        }
+    };
+
+    template <typename T, bool Integral>
+    struct TEncodeNumber {
+        static void Do(IOutputStream& out, const T& val, bool desc) {
+            TEncodeInt<std::is_signed<T>::value>::Do(out, val, desc);
+        }
+    };
+
+    template <typename T>
+    struct TEncodeNumber<T, false> {
+        static void Do(IOutputStream& out, const T& val, bool desc) {
+            EncodeFloating(out, val, desc);
+        }
+    };
+
+    template <typename T, bool Arithmetic>
+    struct TEncodeValue {
+        static void Do(IOutputStream& out, const T& val, bool desc) {
+            TEncodeNumber<T, std::is_integral<T>::value>::Do(out, val, desc);
+        }
+    };
+
+    template <typename T>
+    struct TEncodeValue<T, false> {
+        static void Do(IOutputStream& out, TStringBuf str, bool desc) {
+            EncodeString(out, str, desc);
+        }
+    };
+
+    template <typename T>
+    static void Encode(IOutputStream& out, const T& val, bool desc = false) {
+        TEncodeValue<T, std::is_arithmetic<T>::value>::Do(out, val, desc);
+    }
+
+    template <typename T>
+    inline void EncodeOptional(IOutputStream& out, const TMaybe<T>& val, bool desc = false) {
+        NImpl::TBlock block;
+        block.EncodeOptional(val.Defined(), desc);
+        block.Put(out);
+        if (val.Defined()) {
+            Encode(out, *val, desc);
+        }
+    }
+
+    template <typename T>
+    static void Encode(IOutputStream& out, const TMaybe<T>& val, bool desc = false) {
+        EncodeOptional(out, val, desc);
+    }
+
+    struct TResultOps {
+        void SetError(const TString&) {
+            return;
+        }
+        void SetSignedInt(i64) {
+            return;
+        }
+        void SetUnsignedInt(ui64) {
+            return;
+        }
+        void SetFloat(float) {
+            return;
+        }
+        void SetDouble(double) {
+            return;
+        }
+        void SetString(const TString&) {
+            return;
+        }
+        void SetOptional(bool) {
+            return;
+        }
+    };
+
+    template <typename TResult>
+    bool Decode(TResult& res, TStringBuf data) {
+        static_assert(std::is_base_of<TResultOps, TResult>::value, "Result must be derived from NPresort::TResultOps");
+
+        using namespace NImpl;
+
+        TDecodeContext ctx;
+        while (!data.empty()) {
+            TBlock block;
+            if (!block.Decode(ctx, data)) {
+                res.SetError(ctx.Err);
+                return false;
+            }
+            if (ctx.StrBlocks && ctx.Code != StringPart) {
+                res.SetError("Unexpected integer");
+                return false;
+            }
+            switch (ctx.Code) {
+                case StringEnd:
+                    res.SetString(ctx.Str);
+                    ctx.Str = TString();
+                    break;
+                case IntNeg:
+                case IntNonNeg:
+                    res.SetSignedInt(ctx.SignedVal);
+                    ctx.SignedVal = 0;
+                    break;
+                case Unsigned:
+                    res.SetUnsignedInt(ctx.UnsignedVal);
+                    ctx.UnsignedVal = 0;
+                    break;
+                case Float:
+                    res.SetFloat(ctx.FloatVal);
+                    ctx.FloatVal = 0;
+                    break;
+                case Double:
+                    res.SetDouble(ctx.DoubleVal);
+                    ctx.DoubleVal = 0;
+                    break;
+                case Extension:
+                    if (ctx.Optional) {
+                        res.SetOptional(ctx.Filled);
+                        ctx.Optional = false;
+                        ctx.Filled = false;
+                    }
+                    break;
+                default:
+                    break;
+            }
+            data.Skip(block.GetLen());
+        }
+        return true;
+    }
+}
diff --git a/library/cpp/presort/presort_ut.cpp b/library/cpp/presort/presort_ut.cpp
new file mode 100644
index 0000000000..b184877faf
--- /dev/null
+++ b/library/cpp/presort/presort_ut.cpp
@@ -0,0 +1,526 @@
+#include "presort.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+#include <util/generic/algorithm.h>
+#include <util/stream/format.h>
+#include <util/string/escape.h>
+
+using namespace NPresort;
+
+class TEscapedOutput: public IOutputStream {
+public:
+    TEscapedOutput(IOutputStream* out)
+        : Out(out)
+    {
+    }
+
+    ~TEscapedOutput() override {
+    }
+
+private:
+    void DoWrite(const void* data, size_t size) override {
+        *Out << EscapeC((const char*)data, size);
+    }
+
+private:
+    IOutputStream* Out;
+};
+
+Y_UNIT_TEST_SUITE(PresortTests) {
+    struct TTester: public TResultOps {
+        TStringStream Enc;
+        TStringStream Raw;
+        TEscapedOutput Dec;
+        bool First;
+        bool Hex;
+        TVector<TString> Rows;
+
+        TTester(bool hex = false)
+            : Dec(&Raw)
+            , First(true)
+            , Hex(hex)
+        {
+        }
+
+        template <typename T>
+        TTester& Asc(const T& val) {
+            Encode(Enc, val);
+            return *this;
+        }
+
+        template <typename T>
+        TTester& Desc(const T& val) {
+            Encode(Enc, val, true);
+            return *this;
+        }
+
+        TTester& AscU(ui64 val) {
+            EncodeUnsignedInt(Enc, val);
+            return *this;
+        }
+
+        TTester& DescU(ui64 val) {
+            EncodeUnsignedInt(Enc, val, true);
+            return *this;
+        }
+
+        TTester& AscS(const TString& str) {
+            EncodeString(Enc, UnescapeC(str));
+            return *this;
+        }
+
+        TTester& DescS(const TString& str) {
+            EncodeString(Enc, UnescapeC(str), true);
+            return *this;
+        }
+
+        void AddRow() {
+            Rows.push_back(Enc.Str());
+            Enc.clear();
+        }
+
+        void TestCodec(const TString& good) {
+            Decode(*this, Enc.Str());
+
+            TStringStream s;
+            s << EscapeC(Enc.Str()) << Endl;
+            s << Raw.Str() << Endl;
+
+            //~ Y_UNUSED(good);
+            //~ Cerr << s.Str() << Endl;
+            UNIT_ASSERT_NO_DIFF(good, s.Str());
+        }
+
+        void TestOrder(const TString& good) {
+            Sort(Rows.begin(), Rows.end());
+            TStringStream s;
+            for (auto row : Rows) {
+                Decode(*this, row);
+                s << Raw.Str() << Endl;
+                Raw.clear();
+                First = true;
+            }
+
+            //~ Y_UNUSED(good);
+            //~ Cerr << s.Str() << Endl;
+            UNIT_ASSERT_NO_DIFF(good, s.Str());
+        }
+
+        void Clear() {
+            Enc.clear();
+            Raw.clear();
+            First = true;
+            Rows.clear();
+        }
+
+        void SetError(const TString& err) {
+            Raw.clear();
+            Raw << err;
+        }
+
+        void SetSignedInt(i64 val) {
+            Put() << val;
+        }
+
+        void SetUnsignedInt(ui64 val) {
+            if (Hex) {
+                Put() << ::Hex(val, HF_ADDX);
+            } else {
+                Put() << val;
+            }
+        }
+
+        void SetFloat(float val) {
+            Put() << val;
+        }
+
+        void SetDouble(double val) {
+            Put() << val;
+        }
+
+        void SetString(const TString& str) {
+            Put() << str;
+        }
+
+        void SetOptional(bool filled) {
+            Put() << (filled ? "" : "[]");
+            First = filled;
+        }
+
+        IOutputStream& Put() {
+            if (!First) {
+                Raw << "\t";
+            }
+            First = false;
+            return Dec;
+        }
+    };
+
+    Y_UNIT_TEST(BasicIntsCodec) {
+        TTester tester;
+        tester.Asc(0).Asc(1);
+        tester.TestCodec("01\\1\n0\t1\n");
+        tester.Clear();
+        tester.Desc(0).Desc(1);
+        tester.TestCodec("\\xCF\\xCE\\xFE\n0\t1\n");
+    }
+
+    Y_UNIT_TEST(BasicNegativeIntsCodec) {
+        TTester tester;
+        tester.Asc(-1).Asc(-1000);
+        tester.TestCodec(".\\xFE-\\xFC\\x17\n-1\t-1000\n");
+        tester.Clear();
+        tester.Desc(-1).Desc(-1000);
+        tester.TestCodec("\\xD1\\1\\xD2\\3\\xE8\n-1\t-1000\n");
+    }
+
+#ifndef PRESORT_FP_DISABLED
+    Y_UNIT_TEST(BasicDoublesCodec) {
+        TTester tester;
+        tester.Asc(0.0).Asc(3.1415).Asc(-3.1415);
+        tester.TestCodec(
+            "dg1\\0027\\x19!\\xCA\\xC0\\x83\\x12oa1\\2(\\xE6\\3365?|\\xED\\x90\n"
+            "0\t3.1415\t-3.1415\n");
+        tester.Clear();
+        tester.Desc(0.0).Desc(3.1415).Desc(-3.1415);
+        tester.TestCodec(
+            "\\x9B\\x98\\xCE\\xFD\\xC8\\xE6\\3365?|\\xED\\x90\\x9E\\xCE\\xFD\\xD7\\x19!\\xCA\\xC0\\x83\\x12o\n"
+            "0\t3.1415\t-3.1415\n");
+    }
+
+    Y_UNIT_TEST(NegExpDoublesCodec) {
+        TTester tester;
+        tester.Asc(-0.1).Asc(0.1);
+        tester.TestCodec(
+            "b.\\xFC(\\346fffffef.\\3747\\x19\\x99\\x99\\x99\\x99\\x99\\x9A\n"
+            "-0.1\t0.1\n");
+        tester.Clear();
+        tester.Desc(-0.1).Desc(0.1);
+        tester.TestCodec(
+            "\\x9D\\xD1\\3\\xD7\\x19\\x99\\x99\\x99\\x99\\x99\\x9A\\x99\\xD1\\3\\xC8\\346fffffe\n"
+            "-0.1\t0.1\n");
+    }
+
+    Y_UNIT_TEST(DenormDoublesCodec) {
+        TTester tester;
+        const double val = std::numeric_limits<double>::denorm_min();
+        //~ Cerr << val << Endl;
+        tester.Asc(val);
+        tester.TestCodec(
+            "e-\\xFB\\3167\\x10\\0\\0\\0\\0\\0\\0\n"
+            "4.940656458e-324\n");
+        tester.Clear();
+        tester.Desc(val);
+        tester.TestCodec(
+            "\\x9A\\xD2\\0041\\xC8\\xEF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\n"
+            "4.940656458e-324\n");
+    }
+
+    Y_UNIT_TEST(ExtremalDoublesCodec) {
+        TTester tester;
+        const double inf = std::numeric_limits<double>::infinity();
+        const double nan = std::sqrt(-1.0);
+        tester.Asc(-inf).Asc(inf).Asc(nan);
+        tester.TestCodec(
+            "`hi\n"
+            "-inf\tinf\tnan\n");
+        tester.Clear();
+        tester.Desc(-inf).Desc(inf).Desc(nan);
+        tester.TestCodec(
+            "\\x9F\\x97\\x96\n"
+            "-inf\tinf\tnan\n");
+    }
+
+    Y_UNIT_TEST(NegExpFloatsCodec) {
+        TTester tester;
+        const float val = 0.1;
+        tester.Asc(-val).Asc(val);
+        tester.TestCodec(
+            "R.\\xFC+\\377332V.\\3744\\0\\xCC\\xCC\\xCD\n"
+            "-0.1\t0.1\n");
+        tester.Clear();
+        tester.Desc(-val).Desc(val);
+        tester.TestCodec(
+            "\\xAD\\xD1\\3\\xD4\\0\\xCC\\xCC\\xCD\\xA9\\xD1\\3\\xCB\\377332\n"
+            "-0.1\t0.1\n");
+    }
+
+    Y_UNIT_TEST(DenormFloatsCodec) {
+        TTester tester;
+        const float val = std::numeric_limits<float>::denorm_min();
+        //~ Cerr << val << Endl;
+        tester.Asc(val);
+        tester.TestCodec(
+            "U-\\xFFk4\\0\\x80\\0\\0\n"
+            "1.4013e-45\n");
+        tester.Clear();
+        tester.Desc(val);
+        tester.TestCodec(
+            "\\xAA\\xD2\\0\\x94\\xCB\\xFF\\x7F\\xFF\\xFF\n"
+            "1.4013e-45\n");
+    }
+
+    Y_UNIT_TEST(ExtremalFloatsCodec) {
+        TTester tester;
+        const float inf = std::numeric_limits<float>::infinity();
+        const float nan = std::sqrt(-1.0);
+        tester.Asc(-inf).Asc(inf).Asc(nan);
+        tester.TestCodec(
+            "PXY\n"
+            "-inf\tinf\tnan\n");
+        tester.Clear();
+        tester.Desc(-inf).Desc(inf).Desc(nan);
+        tester.TestCodec(
+            "\\xAF\\xA7\\xA6\n"
+            "-inf\tinf\tnan\n");
+    }
+
+    Y_UNIT_TEST(DisabledDoublesCodec) {
+        TTester tester;
+        Decode(tester, "o");
+
+        //~ Cerr << tester.Raw.Str() << Endl;
+        UNIT_ASSERT_NO_DIFF("Floating point numbers support was disabled on encoding", tester.Raw.Str());
+    }
+#else
+    Y_UNIT_TEST(DisabledDoublesCodec) {
+        TTester tester;
+        tester.Asc(3.1415);
+        tester.TestCodec(
+            "o\n"
+            "Floating point numbers support is disabled\n");
+    }
+#endif
+
+    Y_UNIT_TEST(BasicStringsCodec) {
+        TTester tester;
+        tester.Asc("aaaa").Asc("aaaabbbbccccdddd");
+        tester.TestCodec(
+            "\\037aaaa\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\1\\4"
+            "\\037aaaabbbbccccddd\\037d\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\1\\1\n"
+            "aaaa\taaaabbbbccccdddd\n");
+        tester.Clear();
+        tester.Desc("aaaa").Desc("aaaabbbbccccdddd");
+        tester.TestCodec(
+            "\\xE0\\x9E\\x9E\\x9E\\x9E\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFE\\xFB"
+            "\\xE0\\x9E\\x9E\\x9E\\x9E\\x9D\\x9D\\x9D\\x9D\\x9C\\x9C\\x9C\\x9C\\x9B\\x9B\\x9B"
+            "\\xE0\\x9B\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFE\\xFE\n"
+            "aaaa\taaaabbbbccccdddd\n");
+    }
+
+    Y_UNIT_TEST(LongIntsCodec) {
+        TTester tester;
+        tester.Asc(LL(1234567890123456789)).Asc(LL(-1234567890123456789));
+        tester.TestCodec(
+            "8\\x11\\\"\\x10\\xF4}\\xE9\\x81\\x15'\\xEE\\xDD\\xEF\\x0B\\x82\\x16~\\xEA\n"
+            "1234567890123456789\t-1234567890123456789\n");
+        tester.Clear();
+        tester.Desc(1234567890123456789).Desc(-1234567890123456789);
+        tester.TestCodec(
+            "\\xC7\\xEE\\xDD\\xEF\\x0B\\x82\\x16~\\xEA\\xD8\\x11\\\"\\x10\\xF4}\\xE9\\x81\\x15\n"
+            "1234567890123456789\t-1234567890123456789\n");
+    }
+
+    Y_UNIT_TEST(LongUnsignedIntsCodec) {
+        TTester tester(true);
+        tester.AscU(ULL(0xABCDEF1234567890));
+        tester.TestCodec(
+            "I\\0\\xAB\\xCD\\xEF\\0224Vx\\x90\n"
+            "0xABCDEF1234567890\n");
+        tester.Clear();
+        tester.DescU(ULL(0xABCDEF1234567890));
+        tester.TestCodec(
+            "\\xB6\\xFFT2\\x10\\xED\\xCB\\xA9\\x87o\n"
+            "0xABCDEF1234567890\n");
+    }
+
+    Y_UNIT_TEST(BasicOptionalsCodec) {
+        TTester tester;
+        tester.Asc(TMaybe<ui64>(1)).Asc(TMaybe<ui64>()).Asc(TMaybe<TStringBuf>("FOO")).Asc(TMaybe<TStringBuf>());
+        tester.TestCodec(
+            "sA\\1qs\\037FOO\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\0\\1\\3q\n"
+            "1\t[]\tFOO\t[]\n");
+        tester.Clear();
+        tester.Desc(TMaybe<ui64>(1)).Desc(TMaybe<ui64>()).Desc(TMaybe<TStringBuf>("FOO")).Desc(TMaybe<TStringBuf>());
+        tester.TestCodec(
+            "\\x8C\\xBE\\xFE\\x8E\\x8C\\xE0\\xB9\\xB0\\xB0\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFF\\xFE\\xFC\\x8E\n"
+            "1\t[]\tFOO\t[]\n");
+    }
+
+    Y_UNIT_TEST(BasicIntsOrder) {
+        TTester tester;
+        tester.Asc(1).Asc(0).AddRow();
+        tester.Asc(0).Asc(-1).AddRow();
+        tester.Asc(0).Asc(1).AddRow();
+
+        tester.TestOrder("0\t-1\n0\t1\n1\t0\n");
+        tester.Clear();
+
+        tester.Desc(0).Desc(1).AddRow();
+        tester.Desc(1).Desc(0).AddRow();
+        tester.Desc(0).Desc(-1).AddRow();
+
+        tester.TestOrder("1\t0\n0\t1\n0\t-1\n");
+    }
+
+#ifndef PRESORT_FP_DISABLED
+    Y_UNIT_TEST(BasicDoublesOrder) {
+        TTester tester;
+        tester.Asc(-1.1).Asc(0.0).AddRow();
+        tester.Asc(0.0).Asc(1.1).AddRow();
+        tester.Asc(0.0).Asc(0.0).AddRow();
+
+        tester.TestOrder("-1.1\t0\n0\t0\n0\t1.1\n");
+        tester.Clear();
+
+        tester.Desc(1.1).Desc(-1.0).AddRow();
+        tester.Desc(1.1).Desc(0.0).AddRow();
+        tester.Desc(1.0).Desc(0.0).AddRow();
+
+        tester.TestOrder("1.1\t0\n1.1\t-1\n1\t0\n");
+    }
+
+    Y_UNIT_TEST(DoublesOrder) {
+        TTester tester;
+
+        const double den = std::numeric_limits<double>::denorm_min();
+        const double inf = std::numeric_limits<double>::infinity();
+        const double nan = std::sqrt(-1.0);
+
+        tester.Asc(1.1).AddRow();
+        tester.Asc(0.1).AddRow();
+        tester.Asc(0.0).AddRow();
+        tester.Asc(-0.1).AddRow();
+        tester.Asc(-1.1).AddRow();
+        tester.Asc(inf).AddRow();
+        tester.Asc(-inf).AddRow();
+        tester.Asc(nan).AddRow();
+        tester.Asc(den).AddRow();
+        tester.Asc(-den).AddRow();
+
+        tester.TestOrder("-inf\n-1.1\n-0.1\n-4.940656458e-324\n0\n4.940656458e-324\n0.1\n1.1\ninf\nnan\n");
+    }
+
+    Y_UNIT_TEST(FloatsOrder) {
+        TTester tester;
+
+        const float a = 1.1;
+        const float b = 0.1;
+        const float z = 0.0;
+        const float den = std::numeric_limits<float>::denorm_min();
+        const float inf = std::numeric_limits<float>::infinity();
+        const float nan = std::sqrt(-1.0);
+
+        tester.Asc(a).AddRow();
+        tester.Asc(b).AddRow();
+        tester.Asc(z).AddRow();
+        tester.Asc(-b).AddRow();
+        tester.Asc(-a).AddRow();
+        tester.Asc(inf).AddRow();
+        tester.Asc(-inf).AddRow();
+        tester.Asc(nan).AddRow();
+        tester.Asc(den).AddRow();
+        tester.Asc(-den).AddRow();
+
+        tester.TestOrder("-inf\n-1.1\n-0.1\n-1.4013e-45\n0\n1.4013e-45\n0.1\n1.1\ninf\nnan\n");
+    }
+#endif
+
+    Y_UNIT_TEST(BasicIntsMixedOrder) {
+        TTester tester;
+        tester.Asc(1).Desc(0).AddRow();
+        tester.Asc(0).Desc(1).AddRow();
+        tester.Asc(0).Desc(0).AddRow();
+
+        tester.TestOrder("0\t1\n0\t0\n1\t0\n");
+    }
+
+    Y_UNIT_TEST(BasicStringsAndIntsOrder) {
+        TTester tester;
+        tester.Asc("foo").Desc(0).AddRow();
+        tester.Asc("bar").Desc(1).AddRow();
+        tester.Asc("foo").Desc(1).AddRow();
+
+        tester.TestOrder("bar\t1\nfoo\t1\nfoo\t0\n");
+    }
+
+    Y_UNIT_TEST(LongIntsOrder) {
+        TTester tester;
+        tester.Asc(LL(1234567890123456789)).AddRow();
+        tester.Asc(LL(-1234567890123456789)).AddRow();
+        tester.TestOrder("-1234567890123456789\n1234567890123456789\n");
+        tester.Clear();
+        tester.Desc(-1234567890123456789).AddRow();
+        tester.Desc(1234567890123456789).AddRow();
+        tester.TestOrder("1234567890123456789\n-1234567890123456789\n");
+    }
+
+    Y_UNIT_TEST(LongUnsignedIntsOrder) {
+        TTester tester(true);
+        tester.AscU(ULL(0xABCDEF1234567890)).AddRow();
+        tester.AscU(ULL(0xABCDEF1234567891)).AddRow();
+        tester.TestOrder("0xABCDEF1234567890\n0xABCDEF1234567891\n");
+        tester.Clear();
+        tester.DescU(ULL(0xABCDEF1234567891)).AddRow();
+        tester.DescU(ULL(0xABCDEF1234567890)).AddRow();
+        tester.TestOrder("0xABCDEF1234567891\n0xABCDEF1234567890\n");
+    }
+
+    Y_UNIT_TEST(ZeroSuffixStringsOrder) {
+        TTester tester;
+        tester.Asc("foo").Asc(1).AddRow();
+        tester.Asc("bar").Asc(0).AddRow();
+        tester.AscS("foo\\0\\0").Asc(3).AddRow();
+        tester.AscS("foo\\0").Asc(2).AddRow();
+
+        tester.TestOrder("bar\t0\nfoo\t1\nfoo\\0\t2\nfoo\\0\\0\t3\n");
+        tester.Clear();
+
+        tester.Desc("foo").Asc(1).AddRow();
+        tester.Desc("bar").Asc(0).AddRow();
+        tester.DescS("foo\\0\\0").Asc(3).AddRow();
+        tester.DescS("foo\\0").Asc(2).AddRow();
+
+        tester.TestOrder("foo\\0\\0\t3\nfoo\\0\t2\nfoo\t1\nbar\t0\n");
+    }
+
+    Y_UNIT_TEST(SimpleStringsOrder) {
+        TTester tester;
+        tester.Asc("q").Asc(4).AddRow();
+        tester.Asc("q").Asc(5).AddRow();
+        tester.Asc("abc").Asc(1).AddRow();
+        tester.Asc("ddd").Asc(3).AddRow();
+        tester.Asc("ddd").Asc(2).AddRow();
+        tester.Asc("qzz").Asc(6).AddRow();
+
+        tester.TestOrder("abc\t1\nddd\t2\nddd\t3\nq\t4\nq\t5\nqzz\t6\n");
+        tester.Clear();
+
+        tester.Desc("q").Desc(4).AddRow();
+        tester.Desc("q").Desc(5).AddRow();
+        tester.Desc("abc").Desc(1).AddRow();
+        tester.Desc("ddd").Desc(3).AddRow();
+        tester.Desc("ddd").Desc(2).AddRow();
+        tester.Desc("qzz").Desc(6).AddRow();
+
+        tester.TestOrder("qzz\t6\nq\t5\nq\t4\nddd\t3\nddd\t2\nabc\t1\n");
+    }
+
+    Y_UNIT_TEST(SimpleOptionalsOrder) {
+        TTester tester;
+        tester.Asc(TMaybe<ui64>(1)).Asc(TMaybe<TStringBuf>()).AddRow();
+        tester.Asc(TMaybe<ui64>()).Asc(TMaybe<TStringBuf>("FOO")).AddRow();
+        tester.Asc(TMaybe<ui64>(1)).Asc(TMaybe<TStringBuf>("BAR")).AddRow();
+        tester.Asc(TMaybe<ui64>(1)).Asc(TMaybe<TStringBuf>("")).AddRow();
+
+        tester.TestOrder("[]\tFOO\n1\t[]\n1\t\n1\tBAR\n");
+        tester.Clear();
+
+        tester.Desc(TMaybe<ui64>(1)).Desc(TMaybe<TStringBuf>()).AddRow();
+        tester.Desc(TMaybe<ui64>()).Desc(TMaybe<TStringBuf>("FOO")).AddRow();
+        tester.Desc(TMaybe<ui64>(1)).Desc(TMaybe<TStringBuf>("BAR")).AddRow();
+        tester.Desc(TMaybe<ui64>(1)).Desc(TMaybe<TStringBuf>("")).AddRow();
+
+        tester.TestOrder("1\tBAR\n1\t\n1\t[]\n[]\tFOO\n");
+    }
+}