[KIKIMR-15108] Add perf programs to build

ref:8f081efde09627da76e52231d32a83e34b78c1e4

20 files changed, 2339 insertions, 0 deletions

diff --git a/library/cpp/balloc/CMakeLists.txt b/library/cpp/balloc/CMakeLists.txt
new file mode 100644
index 0000000000..d4ed3b53d2
--- /dev/null
+++ b/library/cpp/balloc/CMakeLists.txt
@@ -0,0 +1,21 @@
+
+# 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-balloc)
+target_compile_options(library-cpp-balloc PRIVATE
+  -Wno-everything
+)
+target_link_libraries(library-cpp-balloc PUBLIC
+  contrib-libs-cxxsupp
+  cpp-balloc-lib
+)
+target_sources(library-cpp-balloc PRIVATE
+  ${CMAKE_SOURCE_DIR}/library/cpp/balloc/balloc.cpp
+  ${CMAKE_SOURCE_DIR}/library/cpp/balloc/malloc-info.cpp
+)
diff --git a/library/cpp/balloc/aba_agri_test/balloc_aba_ut.cpp b/library/cpp/balloc/aba_agri_test/balloc_aba_ut.cpp
new file mode 100644
index 0000000000..0d12dc6764
--- /dev/null
+++ b/library/cpp/balloc/aba_agri_test/balloc_aba_ut.cpp
@@ -0,0 +1,221 @@
+#include <util/generic/algorithm.h>
+#include <util/generic/noncopyable.h>
+#include <util/generic/ptr.h>
+#include <util/generic/vector.h>
+#include <library/cpp/deprecated/atomic/atomic.h>
+#include <util/system/info.h>
+#include <util/system/spinlock.h>
+#include <util/system/thread.h>
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <utility>
+
+#define PLATFORM_CACHE_LINE 64
+
+template <typename T>
+struct TNode: private TNonCopyable {
+    TNode* Next;
+    T Item;
+
+    TNode(const T& item)
+        : Next(nullptr)
+        , Item(item)
+    {
+    }
+
+    TNode(T&& item)
+        : Next(nullptr)
+        , Item(std::move(item))
+    {
+    }
+
+    char Padding[4000];
+};
+
+template <typename TNode>
+inline void DeleteList(TNode* node) {
+    while (node != nullptr) {
+        TNode* next = node->Next;
+        delete node;
+        node = next;
+    }
+}
+
+typedef void* TMessageLink;
+
+////////////////////////////////////////////////////////////////////////////////
+// http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue
+// Very fast (as there is no CAS operation), but not exactly lock-free:
+// one blocked producer could prevent consumer from obtaining new nodes.
+
+template <typename T = TMessageLink>
+class TFastLF_M1_Queue: private TNonCopyable {
+private:
+    union {
+        TNode<T>* Head;
+        char Pad1[PLATFORM_CACHE_LINE];
+    };
+    union {
+        TNode<T>* Tail;
+        char Pad2[PLATFORM_CACHE_LINE];
+    };
+
+public:
+    using TItem = T;
+
+    TFastLF_M1_Queue() {
+        Head = Tail = new TNode<T>(T());
+    }
+
+    ~TFastLF_M1_Queue() {
+        DeleteList(Head);
+    }
+
+    template <typename TT>
+    void Push(TT&& item) {
+        Enqueue(new TNode<T>(std::forward<TT>(item)));
+    }
+
+    void Enqueue(TNode<T>* node) {
+        // our goal is to avoid expensive CAS here,
+        // but now consumer will be blocked until new tail linked.
+        // fortunately 'window of inconsistency' is extremely small.
+        TNode<T>* prev = AtomicSwap(&Tail, node);
+        AtomicSet(prev->Next, node);
+    }
+
+    T Pop() {
+        TNode<T>* next = AtomicGet(Head->Next);
+        if (next) {
+            auto item = std::move(next->Item);
+            std::swap(Head, next); // no need atomic here
+            delete next;
+            return item;
+        }
+        return nullptr;
+    }
+
+    bool IsEmpty() const {
+        TNode<T>* next = AtomicGet(Head->Next);
+        return (next == nullptr);
+    }
+};
+
+const size_t NUMBER_OF_PUSHERS = NSystemInfo::NumberOfCpus() + 4;
+const size_t NUMBER_OF_QUEUES = NSystemInfo::NumberOfCpus() / 4;
+
+template <typename TQueueType>
+class TQueueTestProcs: public TTestBase {
+private:
+    UNIT_TEST_SUITE_DEMANGLE(TQueueTestProcs<TQueueType>);
+    UNIT_TEST(RndPush1M_Queues)
+    UNIT_TEST_SUITE_END();
+
+public:
+    void RndPush1M_Queues() {
+        TQueueType* queue = new TQueueType[NUMBER_OF_QUEUES];
+
+        class TPusherThread: public ISimpleThread {
+        public:
+            TPusherThread(TQueueType* queues, char* start)
+                : Queues(queues)
+                , Arg(start)
+            {
+            }
+
+            TQueueType* Queues;
+            char* Arg;
+
+            void* ThreadProc() override {
+                auto counters = new int[NUMBER_OF_QUEUES];
+                for (size_t i = 0; i < NUMBER_OF_QUEUES; ++i)
+                    counters[i] = 0;
+#if defined(_msan_enabled_) || defined(_asan_enabled_)
+                int limit = 100000;
+#else
+                int limit = 1000000;
+#endif
+                for (int i = 0; i < limit; ++i) {
+                    size_t rnd = GetCycleCount() % NUMBER_OF_QUEUES;
+                    int cookie = counters[rnd]++;
+                    Queues[rnd].Push(Arg + cookie);
+                }
+
+                for (size_t i = 0; i < NUMBER_OF_QUEUES; ++i) {
+                    Queues[i].Push((void*)1ULL);
+                }
+
+                delete[] counters;
+                return nullptr;
+            }
+        };
+
+        class TPopperThread: public ISimpleThread {
+        public:
+            TPopperThread(TQueueType* queue, char* base)
+                : Queue(queue)
+                , Base(base)
+            {
+            }
+
+            TQueueType* Queue;
+            char* Base;
+
+            void* ThreadProc() override {
+                auto counters = new int[NUMBER_OF_PUSHERS];
+                for (size_t i = 0; i < NUMBER_OF_PUSHERS; ++i)
+                    counters[i] = 0;
+
+                for (size_t fin = 0; fin < NUMBER_OF_PUSHERS;) {
+                    auto msg = Queue->Pop();
+                    if (msg == nullptr)
+                        continue;
+                    if (msg == (void*)1ULL) {
+                        ++fin;
+                        continue;
+                    }
+                    auto shift = (char*)msg - Base;
+                    auto pusherNum = shift / 20000000;
+                    auto msgNum = shift % 20000000;
+
+                    if (counters[pusherNum] != msgNum) {
+                        Cerr << counters[pusherNum] << " " << msgNum << Endl;
+                    }
+
+                    UNIT_ASSERT_EQUAL(counters[pusherNum], msgNum);
+                    ++counters[pusherNum];
+                }
+
+                delete[] counters;
+                return nullptr;
+            }
+        };
+
+        TVector<TAutoPtr<TPopperThread>> poppers;
+        TVector<TAutoPtr<TPusherThread>> pushers;
+
+        for (size_t i = 0; i < NUMBER_OF_QUEUES; ++i) {
+            poppers.emplace_back(new TPopperThread(&queue[i], (char*)queue));
+            poppers.back()->Start();
+        }
+
+        for (size_t i = 0; i < NUMBER_OF_PUSHERS; ++i) {
+            pushers.emplace_back(
+                new TPusherThread(queue, (char*)queue + 20000000 * i));
+            pushers.back()->Start();
+        }
+
+        for (size_t i = 0; i < NUMBER_OF_QUEUES; ++i) {
+            poppers[i]->Join();
+        }
+
+        for (size_t i = 0; i < NUMBER_OF_PUSHERS; ++i) {
+            pushers[i]->Join();
+        }
+
+        delete[] queue;
+    }
+};
+
+UNIT_TEST_SUITE_REGISTRATION(TQueueTestProcs<TFastLF_M1_Queue<>>);
diff --git a/library/cpp/balloc/lib/CMakeLists.darwin.txt b/library/cpp/balloc/lib/CMakeLists.darwin.txt
new file mode 100644
index 0000000000..6ce3b4e072
--- /dev/null
+++ b/library/cpp/balloc/lib/CMakeLists.darwin.txt
@@ -0,0 +1,21 @@
+
+# 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(cpp-balloc-lib)
+target_compile_options(cpp-balloc-lib PRIVATE
+  -Wno-everything
+)
+target_link_libraries(cpp-balloc-lib PUBLIC
+  contrib-libs-cxxsupp
+  cpp-balloc-setup
+  cpp-malloc-api
+)
+target_sources(cpp-balloc-lib PRIVATE
+  ${CMAKE_SOURCE_DIR}/library/cpp/balloc/lib/alloc_stats.cpp
+)
diff --git a/library/cpp/balloc/lib/CMakeLists.linux.txt b/library/cpp/balloc/lib/CMakeLists.linux.txt
new file mode 100644
index 0000000000..7cd6c1e33b
--- /dev/null
+++ b/library/cpp/balloc/lib/CMakeLists.linux.txt
@@ -0,0 +1,22 @@
+
+# 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(cpp-balloc-lib)
+target_compile_options(cpp-balloc-lib PRIVATE
+  -Wno-everything
+)
+target_link_libraries(cpp-balloc-lib PUBLIC
+  contrib-libs-cxxsupp
+  contrib-libs-linuxvdso
+  cpp-balloc-setup
+  cpp-malloc-api
+)
+target_sources(cpp-balloc-lib PRIVATE
+  ${CMAKE_SOURCE_DIR}/library/cpp/balloc/lib/alloc_stats.cpp
+)
diff --git a/library/cpp/balloc/lib/CMakeLists.txt b/library/cpp/balloc/lib/CMakeLists.txt
new file mode 100644
index 0000000000..fc7b1ee73c
--- /dev/null
+++ b/library/cpp/balloc/lib/CMakeLists.txt
@@ -0,0 +1,13 @@
+
+# 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.
+
+
+if (APPLE)
+  include(CMakeLists.darwin.txt)
+elseif (UNIX AND NOT APPLE)
+  include(CMakeLists.linux.txt)
+endif()
diff --git a/library/cpp/balloc/lib/alloc_stats.cpp b/library/cpp/balloc/lib/alloc_stats.cpp
new file mode 100644
index 0000000000..3481cad56c
--- /dev/null
+++ b/library/cpp/balloc/lib/alloc_stats.cpp
@@ -0,0 +1,106 @@
+#include <library/cpp/balloc/lib/alloc_stats.h>
+
+#include <util/system/compiler.h>
+#include <atomic>
+
+
+namespace NAllocStats {
+
+struct TThreadAllocStats {
+    i64 CurrSize = 0;
+    i64 MaxSize = 0;
+};
+
+struct TGlobalAllocStats {
+    std::atomic<ui64> LiveLock = {0};
+    std::atomic<ui64> Mmap = {0};
+};
+
+#if defined(_unix_) && !defined(_darwin_)
+
+__thread bool isEnabled = false;
+
+bool IsEnabled() noexcept {
+    return isEnabled;
+}
+
+void EnableAllocStats(bool enable) noexcept {
+    isEnabled = enable;
+}
+
+__thread TThreadAllocStats threadAllocStats;
+
+void IncThreadAllocStats(i64 size) noexcept {
+    threadAllocStats.CurrSize += size;
+    if (Y_UNLIKELY(threadAllocStats.CurrSize > threadAllocStats.MaxSize)) {
+        threadAllocStats.MaxSize = threadAllocStats.CurrSize;
+    }
+}
+
+void DecThreadAllocStats(i64 size) noexcept {
+    threadAllocStats.CurrSize -= size;
+}
+
+void ResetThreadAllocStats() noexcept {
+    threadAllocStats.CurrSize = 0;
+    threadAllocStats.MaxSize = 0;
+}
+
+i64 GetThreadAllocMax() noexcept {
+    return threadAllocStats.MaxSize;
+}
+
+#else // _unix_ && ! _darwin_
+
+bool IsEnabled() noexcept {
+    return false;
+}
+void EnableAllocStats(bool /*enable*/) noexcept {
+}
+void IncThreadAllocStats(i64 /*size*/) noexcept {
+}
+void DecThreadAllocStats(i64 /*size*/) noexcept {
+}
+void ResetThreadAllocStats() noexcept {
+}
+i64 GetThreadAllocMax() noexcept {
+    return 0;
+}
+
+#endif // _unix_ && ! _darwin_
+
+
+#if defined(_x86_64_) || defined(_i386_)
+    static constexpr size_t CACHE_LINE_SIZE = 64;
+#elif defined(_arm64_) || defined(_ppc64_)
+    static constexpr size_t CACHE_LINE_SIZE = 128;
+#else
+    static constexpr size_t CACHE_LINE_SIZE = 256; // default large enough
+#endif
+
+template <typename T>
+struct alignas(sizeof(T)) TCacheLineDoublePaddedAtomic {
+    char Prefix[CACHE_LINE_SIZE - sizeof(T)];
+    T Value;
+    char Postfix[CACHE_LINE_SIZE - sizeof(T)];
+};
+
+TCacheLineDoublePaddedAtomic<TGlobalAllocStats> GlobalCounters;
+
+void IncLiveLockCounter() noexcept {
+    GlobalCounters.Value.LiveLock.fetch_add(1, std::memory_order_seq_cst);
+}
+
+ui64 GetLiveLockCounter() noexcept {
+    return GlobalCounters.Value.LiveLock.load(std::memory_order_acquire);
+}
+
+void IncMmapCounter(ui64 amount) noexcept {
+    GlobalCounters.Value.Mmap.fetch_add(amount, std::memory_order_seq_cst);
+}
+
+ui64 GetMmapCounter() noexcept {
+    return GlobalCounters.Value.Mmap.load(std::memory_order_acquire);
+}
+
+}  // namespace NAllocStats
diff --git a/library/cpp/balloc/lib/alloc_stats.h b/library/cpp/balloc/lib/alloc_stats.h
new file mode 100644
index 0000000000..a36686cc85
--- /dev/null
+++ b/library/cpp/balloc/lib/alloc_stats.h
@@ -0,0 +1,18 @@
+#pragma once
+
+#include <util/system/types.h>
+
+namespace NAllocStats {
+
+bool IsEnabled() noexcept;
+void EnableAllocStats(bool enable) noexcept;
+void IncThreadAllocStats(i64 size) noexcept;
+void DecThreadAllocStats(i64 size) noexcept;
+void ResetThreadAllocStats() noexcept;
+i64 GetThreadAllocMax() noexcept;
+void IncLiveLockCounter() noexcept;
+ui64 GetLiveLockCounter() noexcept;
+void IncMmapCounter(ui64 amount) noexcept;
+ui64 GetMmapCounter() noexcept;
+
+}  // namespace NAllocStats
diff --git a/library/cpp/balloc/lib/balloc.h b/library/cpp/balloc/lib/balloc.h
new file mode 100644
index 0000000000..019c9cb7de
--- /dev/null
+++ b/library/cpp/balloc/lib/balloc.h
@@ -0,0 +1,589 @@
+#pragma once
+
+#include <sys/mman.h>
+#include <pthread.h>
+#include <dlfcn.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <memory.h>
+#include <new>
+#include <util/system/defaults.h>
+#include <library/cpp/malloc/api/malloc.h>
+#include <library/cpp/balloc/lib/alloc_stats.h>
+#include <library/cpp/balloc/setup/alloc.h>
+
+#ifndef NDEBUG
+#define DBG_FILL_MEMORY
+#endif
+
+#if defined(Y_COVER_PTR)
+#define DBG_FILL_MEMORY
+#endif
+
+#if (defined(_i386_) || defined(_x86_64_)) && defined(_linux_)
+#define HAVE_VDSO_GETCPU 1
+
+#include <contrib/libs/linuxvdso/interface.h>
+#endif
+
+namespace NBalloc {
+#if HAVE_VDSO_GETCPU
+    // glibc does not provide a wrapper around getcpu, we'll have to load it manually
+    static int (*getcpu)(unsigned* cpu, unsigned* node, void* unused) = nullptr;
+#endif
+
+    static Y_FORCE_INLINE void* Advance(void* block, size_t size) {
+        return (void*)((char*)block + size);
+    }
+
+    static constexpr size_t PAGE_CACHE = 16;
+#if defined(_ppc64_) || defined(_arm64_)
+    static constexpr size_t PAGE_ELEM = 65536;
+#else
+    static constexpr size_t PAGE_ELEM = 4096;
+#endif
+    static constexpr size_t SINGLE_ALLOC = (PAGE_ELEM / 2);
+    static constexpr size_t ORDERS = 1024;
+    static constexpr size_t DUMP_STAT = 0;
+
+    static void* (*LibcMalloc)(size_t) = nullptr;
+    static void (*LibcFree)(void*) = nullptr;
+
+    static size_t Y_FORCE_INLINE Align(size_t value, size_t align) {
+        return (value + align - 1) & ~(align - 1);
+    }
+
+#define RDTSC(eax, edx) __asm__ __volatile__("rdtsc" \
+                                             : "=a"(eax), "=d"(edx));
+#define CPUID(func, eax, ebx, ecx, edx) __asm__ __volatile__("cpuid"                                      \
+                                                             : "=a"(eax), "=b"(ebx), "=c"(ecx), "=d"(edx) \
+                                                             : "a"(func));
+
+    static int GetNumaNode() {
+#if HAVE_VDSO_GETCPU
+        if (Y_LIKELY(getcpu)) {
+            unsigned node = 0;
+            if (getcpu(nullptr, &node, nullptr)) {
+                return 0;
+            }
+            return node;
+        }
+#endif
+#if defined(_i386_) or defined(_x86_64_)
+        int a = 0, b = 0, c = 0, d = 0;
+        CPUID(0x1, a, b, c, d);
+        int acpiID = (b >> 24);
+        int numCPU = (b >> 16) & 255;
+        if (numCPU == 0)
+            return 0;
+        int ret = acpiID / numCPU;
+        return ret;
+#else
+        return 0;
+#endif
+    }
+
+    static void AbortFromSystemError() {
+        char buf[512] = {0};
+#if defined(_freebsd_) or defined(_darwin_) or defined(_musl_) or defined(_bionic_)
+        strerror_r(errno, buf, sizeof(buf));
+        const char* msg = buf;
+#elif defined(_linux_) or defined(_cygwin_)
+        const char* msg = strerror_r(errno, buf, sizeof(buf));
+#endif
+        NMalloc::AbortFromCorruptedAllocator(msg);
+    }
+
+    static pthread_key_t key;
+    static volatile long init = 0;
+    static unsigned long long counter = 0;
+
+    static void Destructor(void* data);
+
+    template <class T>
+    Y_FORCE_INLINE bool DoCas(T* volatile* target, T* exchange, T* compare) {
+        return __sync_bool_compare_and_swap(target, compare, exchange);
+    }
+
+    class TLFAllocFreeList {
+        struct TNode {
+            TNode* Next;
+        };
+
+        TNode* volatile Head;
+        TNode* volatile Pending;
+        long long volatile PendingToFreeListCounter;
+        TNode* volatile Destroyed;
+        long long AllocCount;
+
+        static Y_FORCE_INLINE void Enqueue(TNode* volatile* headPtr, TNode* n) {
+            for (;;) {
+                TNode* volatile prevHead = *headPtr;
+                n->Next = prevHead;
+                if (DoCas(headPtr, n, prevHead))
+                    break;
+            }
+        }
+        Y_FORCE_INLINE void* DoAlloc() {
+            TNode* res;
+            for (res = Head; res; res = Head) {
+                TNode* keepNext = res->Next;
+                if (DoCas(&Head, keepNext, res)) {
+                    //Y_VERIFY(keepNext == res->Next);
+                    break;
+                }
+            }
+            return res;
+        }
+        void FreeList(TNode* fl) {
+            if (!fl)
+                return;
+            TNode* flTail = fl;
+            while (flTail->Next)
+                flTail = flTail->Next;
+            for (;;) {
+                TNode* volatile prevHead = Head;
+                flTail->Next = prevHead;
+                if (DoCas(&Head, fl, prevHead))
+                    break;
+            }
+        }
+
+    public:
+        Y_FORCE_INLINE void Free(void* ptr) {
+            TNode* newFree = (TNode*)ptr;
+            if (__sync_add_and_fetch(&AllocCount, 0) == 0)
+                Enqueue(&Head, newFree);
+            else
+                Enqueue(&Pending, newFree);
+        }
+        Y_FORCE_INLINE void Destroy(void* ptr, size_t length) {
+            TNode* newFree = (TNode*)ptr;
+            TNode* fl = nullptr;
+            if (__sync_add_and_fetch(&AllocCount, 1) == 1) {
+                fl = Destroyed;
+                if (fl && !DoCas(&Destroyed, (TNode*)nullptr, fl)) {
+                    fl = nullptr;
+                }
+                Enqueue(&fl, newFree);
+            } else {
+                Enqueue(&Destroyed, newFree);
+            }
+            __sync_sub_and_fetch(&AllocCount, 1);
+
+            // TODO try to merge blocks to minimize number of syscalls
+            while (nullptr != fl) {
+                TNode* next = fl->Next;
+                if (-1 == munmap(fl, length)) {
+                    AbortFromSystemError();
+                }
+                fl = next;
+            }
+        }
+        Y_FORCE_INLINE void* Alloc() {
+            long long volatile keepCounter = __sync_add_and_fetch(&PendingToFreeListCounter, 0);
+            TNode* fl = Pending;
+            if (__sync_add_and_fetch(&AllocCount, 1) == 1) {
+                // No other allocs in progress.
+                // If (keepCounter == PendingToFreeListCounter) then Pending was not freed by other threads.
+                // Hence Pending is not used in any concurrent DoAlloc() atm and can be safely moved to FreeList
+                if (fl &&
+                    keepCounter == __sync_add_and_fetch(&PendingToFreeListCounter, 0) &&
+                    DoCas(&Pending, (TNode*)nullptr, fl))
+                {
+                    // pick first element from Pending and return it
+                    void* res = fl;
+                    fl = fl->Next;
+                    // if there are other elements in Pending list, add them to main free list
+                    FreeList(fl);
+                    __sync_sub_and_fetch(&PendingToFreeListCounter, 1);
+                    __sync_sub_and_fetch(&AllocCount, 1);
+                    return res;
+                }
+            }
+            void* res = DoAlloc();
+            if (!res && __sync_add_and_fetch(&Pending, 0)) {
+                // live-lock situation: there are no free items in the "Head"
+                // list and there are free items in the "Pending" list
+                // but the items are forbidden to allocate to prevent ABA
+                NAllocStats::IncLiveLockCounter();
+            }
+            __sync_sub_and_fetch(&AllocCount, 1);
+            return res;
+        }
+    };
+
+    TLFAllocFreeList nodes[2][ORDERS];
+    unsigned long long sizesGC[2][16];
+    unsigned long long sizeOS, totalOS;
+
+    struct TBlockHeader {
+        size_t Size;
+        int RefCount;
+        unsigned short AllCount;
+        unsigned short NumaNode;
+    };
+
+    static bool PushPage(void* page, size_t order) {
+        if (order < ORDERS) {
+            int node = ((TBlockHeader*)page)->NumaNode;
+            __sync_add_and_fetch(&sizesGC[node][order % 16], order);
+            TBlockHeader* blockHeader = (TBlockHeader*)page;
+            if (!__sync_bool_compare_and_swap(&blockHeader->RefCount, 0, -1)) {
+                NMalloc::AbortFromCorruptedAllocator();
+            }
+            nodes[node][order].Free(page);
+            return true;
+        }
+        return false;
+    }
+
+    static void* PopPage(size_t order) {
+        if (order < ORDERS) {
+            int numaNode = GetNumaNode() & 1;
+            void* alloc = nodes[numaNode][order].Alloc();
+            if (alloc == nullptr) {
+                alloc = nodes[1 - numaNode][order].Alloc();
+                if (alloc) {
+                    __sync_sub_and_fetch(&sizesGC[1 - numaNode][order % 16], order);
+                }
+            } else {
+                __sync_sub_and_fetch(&sizesGC[numaNode][order % 16], order);
+            }
+            if (alloc) {
+                TBlockHeader* blockHeader = (TBlockHeader*)alloc;
+                if (!__sync_bool_compare_and_swap(&blockHeader->RefCount, -1, 0)) {
+                    NMalloc::AbortFromCorruptedAllocator();
+                }
+            }
+            return alloc;
+        }
+        return nullptr;
+    }
+
+#if DUMP_STAT
+    static unsigned long long TickCounter() {
+        int lo = 0, hi = 0;
+        RDTSC(lo, hi);
+        return (((unsigned long long)hi) << 32) + (unsigned long long)lo;
+    }
+
+    struct TTimeHold {
+        unsigned long long Start;
+        unsigned long long Finish;
+        const char* Name;
+        TTimeHold(const char* name)
+            : Start(TickCounter())
+            , Name(name)
+        {
+        }
+        ~TTimeHold() {
+            Finish = TickCounter();
+            double diff = Finish > Start ? (Finish - Start) / 1000000.0 : 0.0;
+            if (diff > 20.0) {
+                fprintf(stderr, "%s %f mticks\n", diff, Name);
+            }
+        }
+    };
+#endif
+
+    long long allocs[ORDERS];
+
+    static void Map(size_t size, void* pages[], size_t num) {
+#if DUMP_STAT
+        TTimeHold hold("mmap");
+        size_t order = size / PAGE_ELEM;
+        if (order < ORDERS) {
+            __sync_add_and_fetch(&allocs[order], num);
+        }
+#endif
+        if (!NAllocSetup::CanAlloc(__sync_add_and_fetch(&sizeOS, size * num), totalOS)) {
+            NMalloc::AbortFromCorruptedAllocator();
+        }
+        void* map = mmap(nullptr, size * num, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
+        if (map == MAP_FAILED) {
+            AbortFromSystemError();
+        }
+        unsigned short numaNode = (GetNumaNode() & 1);
+        NAllocStats::IncMmapCounter(size * num / PAGE_ELEM);
+        for (size_t i = 0; i < num; ++i) {
+            TBlockHeader* blockHeader = static_cast<TBlockHeader*>(map);
+            blockHeader->NumaNode = numaNode;
+            pages[i] = map;
+            map = Advance(map, size);
+        }
+    }
+
+    static void* SysAlloc(size_t& size) {
+        size = Align(size, PAGE_ELEM);
+        size_t order = size / PAGE_ELEM;
+        void* result = PopPage(order);
+        if (result) {
+            return result;
+        }
+        void* pages[1] = {nullptr};
+        Map(size, pages, 1);
+        return pages[0];
+    }
+
+    static void UnMap(void* block, size_t order) {
+#if DUMP_STAT
+        TTimeHold hold("munmap");
+        if (order < ORDERS) {
+            __sync_sub_and_fetch(&allocs[order], 1);
+        }
+#endif
+        size_t size = order * PAGE_ELEM;
+        __sync_sub_and_fetch(&sizeOS, size);
+        TBlockHeader* blockHeader = (TBlockHeader*)block;
+        if (!__sync_bool_compare_and_swap(&blockHeader->RefCount, 0, -1)) {
+            NMalloc::AbortFromCorruptedAllocator();
+        }
+        if (order < ORDERS) {
+            int node = blockHeader->NumaNode;
+            nodes[node][order].Destroy(block, size);
+        } else {
+            if (-1 == munmap(block, size)) {
+                AbortFromSystemError();
+            }
+        }
+    }
+
+    static void SysClear(size_t order) {
+        void* page = PopPage(order);
+        if (page) {
+            UnMap(page, order);
+        }
+    }
+
+    static void Y_FORCE_INLINE GlobalInit() {
+        if (__sync_bool_compare_and_swap(&init, 0, 1)) {
+#if HAVE_VDSO_GETCPU
+            getcpu = (int (*)(unsigned*, unsigned*, void*))NVdso::Function("__vdso_getcpu", "LINUX_2.6");
+#endif
+            LibcMalloc = (void* (*)(size_t))dlsym(RTLD_NEXT, "malloc");
+            LibcFree = (void (*)(void*))dlsym(RTLD_NEXT, "free");
+            pthread_key_create(&key, Destructor);
+            __sync_bool_compare_and_swap(&init, 1, 2);
+        }
+        while (init < 2) {
+        };
+    }
+
+    enum EMode {
+        Empty = 0,
+        Born,
+        Alive,
+        Disabled,
+        Dead,
+        ToBeEnabled
+    };
+
+    struct TLS {
+        void* PageCache[PAGE_CACHE];
+        size_t Cached;
+        void* Chunk;
+        size_t Ptr;
+        void* Block;
+        int Counter;
+        EMode Mode;
+        unsigned char Count0;
+        unsigned long Count1;
+        bool NeedGC() {
+            if (Count0++ != 0)
+                return false;
+            __sync_add_and_fetch(&totalOS, 1);
+            unsigned long long count = 0;
+            for (size_t i = 0; i < 16; ++i) {
+                count += sizesGC[0][i];
+                count += sizesGC[1][i];
+            }
+            return NAllocSetup::NeedReclaim(count * PAGE_ELEM, ++Count1);
+        }
+        void ClearCount() {
+            Count1 = 0;
+        }
+    };
+
+#if defined(_darwin_)
+
+    static Y_FORCE_INLINE TLS* PthreadTls() {
+        GlobalInit();
+        TLS* ptls = (TLS*)pthread_getspecific(key);
+        if (!ptls) {
+            ptls = (TLS*)LibcMalloc(sizeof(TLS));
+            if (!ptls) {
+                NMalloc::AbortFromCorruptedAllocator(); // what do we do here?
+            }
+            memset(ptls, 0, sizeof(TLS));
+            pthread_setspecific(key, ptls);
+        }
+        return ptls;
+    }
+
+#define tls (*PthreadTls())
+
+#else
+
+    __thread TLS tls;
+
+#endif
+
+    static void UnRefHard(void* block, int add, TLS& ltls) {
+        TBlockHeader* blockHeader = (TBlockHeader*)block;
+        if ((blockHeader->RefCount == add ? (blockHeader->RefCount = 0, true) : false) || __sync_sub_and_fetch(&blockHeader->RefCount, add) == 0) {
+            size_t order = blockHeader->Size / PAGE_ELEM;
+            if (ltls.Mode == Alive) {
+                // page cache has first priority
+                if (order == 1 && ltls.Cached < PAGE_CACHE) {
+                    ltls.PageCache[ltls.Cached] = block;
+                    ++ltls.Cached;
+                    return;
+                }
+                if (ltls.NeedGC()) {
+                    ltls.ClearCount();
+                    size_t index = __sync_add_and_fetch(&counter, 1);
+                    SysClear(index % ORDERS);
+                    UnMap(block, order);
+                    return;
+                }
+            }
+            if (!PushPage(block, order)) {
+                UnMap(block, order);
+            }
+        }
+    }
+
+    static void Init(TLS& ltls) {
+        bool ShouldEnable = (NAllocSetup::IsEnabledByDefault() || ltls.Mode == ToBeEnabled);
+        ltls.Mode = Born;
+        GlobalInit();
+        pthread_setspecific(key, (void*)&ltls);
+        if (ShouldEnable) {
+            ltls.Mode = Alive;
+        } else {
+            ltls.Mode = Disabled;
+        }
+    }
+
+    static void Y_FORCE_INLINE UnRef(void* block, int counter, TLS& ltls) {
+        if (ltls.Mode != Alive) {
+            UnRefHard(block, counter, ltls);
+            return;
+        }
+        if (ltls.Block == block) {
+            ltls.Counter += counter;
+        } else {
+            if (ltls.Block) {
+                UnRefHard(ltls.Block, ltls.Counter, ltls);
+            }
+            ltls.Block = block;
+            ltls.Counter = counter;
+        }
+    }
+
+    static void Destructor(void* data) {
+        TLS& ltls = *(TLS*)data;
+        ltls.Mode = Dead;
+        if (ltls.Chunk) {
+            TBlockHeader* blockHeader = (TBlockHeader*)ltls.Chunk;
+            UnRef(ltls.Chunk, PAGE_ELEM - blockHeader->AllCount, ltls);
+        }
+        if (ltls.Block) {
+            UnRef(ltls.Block, ltls.Counter, ltls);
+        }
+        for (size_t i = 0; i < ltls.Cached; ++i) {
+            PushPage(ltls.PageCache[i], 1);
+        }
+#if defined(_darwin_)
+        LibcFree(data);
+#endif
+    }
+
+    using TAllocHeader = NMalloc::TAllocHeader;
+
+    static Y_FORCE_INLINE TAllocHeader* AllocateRaw(size_t size, size_t signature) {
+        TLS& ltls = tls;
+        size = Align(size, sizeof(TAllocHeader));
+        if (Y_UNLIKELY(ltls.Mode == Empty || ltls.Mode == ToBeEnabled)) {
+            Init(ltls);
+        }
+        size_t extsize = size + sizeof(TAllocHeader) + sizeof(TBlockHeader);
+        if (extsize > SINGLE_ALLOC || ltls.Mode != Alive) {
+            // The dlsym() function in GlobalInit() may call malloc() resulting in recursive call
+            // of the NBalloc::Malloc(). We have to serve such allocation request via balloc even
+            // when (IsEnabledByDefault() == false) because at this point we don't know where the
+            // libc malloc is.
+            if (extsize > 64 * PAGE_ELEM) {
+                extsize = Align(extsize, 16 * PAGE_ELEM);
+            }
+            NAllocSetup::ThrowOnError(extsize);
+            void* block = SysAlloc(extsize);
+            TBlockHeader* blockHeader = (TBlockHeader*)block;
+            blockHeader->RefCount = 1;
+            blockHeader->Size = extsize;
+            blockHeader->AllCount = 0;
+            TAllocHeader* allocHeader = (TAllocHeader*)Advance(block, sizeof(TBlockHeader));
+            allocHeader->Encode(blockHeader, size, signature);
+            if (NAllocStats::IsEnabled()) {
+                NAllocStats::IncThreadAllocStats(size);
+            }
+#ifdef DBG_FILL_MEMORY
+            memset(allocHeader + 1, 0xec, size);
+#endif
+            return allocHeader;
+        }
+
+        size_t ptr = ltls.Ptr;
+        void* chunk = ltls.Chunk;
+
+        if (ptr < extsize) {
+            NAllocSetup::ThrowOnError(PAGE_ELEM);
+            if (chunk) {
+                TBlockHeader* blockHeader = (TBlockHeader*)chunk;
+                UnRef(chunk, PAGE_ELEM - blockHeader->AllCount, ltls);
+            }
+            void* block = nullptr;
+            while (1) {
+                if (ltls.Cached > 0) {
+                    --ltls.Cached;
+                    block = ltls.PageCache[ltls.Cached];
+                    break;
+                }
+                block = PopPage(1);
+                if (block) {
+                    break;
+                }
+                Map(PAGE_ELEM, ltls.PageCache, PAGE_CACHE);
+                ltls.Cached = PAGE_CACHE;
+            }
+            TBlockHeader* blockHeader = (TBlockHeader*)block;
+            blockHeader->RefCount = PAGE_ELEM;
+            blockHeader->Size = PAGE_ELEM;
+            blockHeader->AllCount = 0;
+            ltls.Ptr = PAGE_ELEM;
+            ltls.Chunk = block;
+            ptr = ltls.Ptr;
+            chunk = ltls.Chunk;
+        }
+        ptr = ptr - size - sizeof(TAllocHeader);
+        TAllocHeader* allocHeader = (TAllocHeader*)Advance(chunk, ptr);
+        allocHeader->Encode(chunk, size, signature);
+        TBlockHeader* blockHeader = (TBlockHeader*)chunk;
+        ++blockHeader->AllCount;
+        ltls.Ptr = ptr;
+        if (NAllocStats::IsEnabled()) {
+            NAllocStats::IncThreadAllocStats(size);
+        }
+#ifdef DBG_FILL_MEMORY
+        memset(allocHeader + 1, 0xec, size);
+#endif
+        return allocHeader;
+    }
+
+    static void Y_FORCE_INLINE FreeRaw(void* ptr) {
+        UnRef(ptr, 1, tls);
+    }
+}
diff --git a/library/cpp/balloc/setup/CMakeLists.txt b/library/cpp/balloc/setup/CMakeLists.txt
new file mode 100644
index 0000000000..82c9d69c0c
--- /dev/null
+++ b/library/cpp/balloc/setup/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(cpp-balloc-setup)
+target_link_libraries(cpp-balloc-setup PUBLIC
+  contrib-libs-cxxsupp
+)
+target_sources(cpp-balloc-setup PRIVATE
+  ${CMAKE_SOURCE_DIR}/library/cpp/balloc/setup/alloc.cpp
+  ${CMAKE_SOURCE_DIR}/library/cpp/balloc/setup/enable.cpp
+)
diff --git a/library/cpp/balloc/setup/alloc.cpp b/library/cpp/balloc/setup/alloc.cpp
new file mode 100644
index 0000000000..f32b15df39
--- /dev/null
+++ b/library/cpp/balloc/setup/alloc.cpp
@@ -0,0 +1,102 @@
+#include <new>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "alloc.h"
+#include "enable.h"
+#include <util/system/platform.h>
+
+namespace NAllocSetup {
+    size_t softLimit = size_t(-1);
+    size_t hardLimit = size_t(-1);
+    size_t allocationThreshold = size_t(-1);
+    size_t softReclaimDivisor = 100;
+    size_t angryReclaimDivisor = 100;
+
+    struct TThrowInfo {
+        size_t CurrSize;
+        size_t MaxSize;
+    };
+#if defined(_unix_) && !defined(_darwin_)
+    __thread TThrowInfo info;
+    void ThrowOnError(size_t allocSize) {
+        info.CurrSize += allocSize;
+        if (info.MaxSize && info.MaxSize < info.CurrSize) {
+#ifndef NDEBUG
+            __builtin_trap();
+#endif
+            info.CurrSize = 0;
+            throw std::bad_alloc();
+        }
+    }
+    void SetThrowConditions(size_t currSize, size_t maxSize) {
+        info.CurrSize = currSize;
+        info.MaxSize = maxSize;
+    }
+#else  // _unix_ && ! _darwin_
+    void ThrowOnError(size_t /*allocSize*/) {
+    }
+    void SetThrowConditions(size_t /*currSize*/, size_t /*maxSize*/) {
+    }
+#endif // _unix_ && ! _darwin_
+
+    void SetSoftLimit(size_t softLimit_) {
+        softLimit = softLimit_;
+    }
+    void SetHardLimit(size_t hardLimit_) {
+        hardLimit = hardLimit_;
+    }
+    void SetAllocationThreshold(size_t allocationThreshold_) {
+        allocationThreshold = allocationThreshold_;
+    }
+    void SetSoftReclaimDivisor(size_t softReclaimDivisor_) {
+        softReclaimDivisor = softReclaimDivisor_;
+    }
+    void SetAngryReclaimDivisor(size_t angryReclaimDivisor_) {
+        angryReclaimDivisor = angryReclaimDivisor_;
+    }
+    size_t GetSoftLimit() {
+        return softLimit;
+    }
+    size_t GetHardLimit() {
+        return hardLimit;
+    }
+    size_t GetAllocationThreshold() {
+        return allocationThreshold;
+    }
+    size_t GetSoftReclaimDivisor() {
+        return softReclaimDivisor;
+    }
+    size_t GetAngryReclaimDivisor() {
+        return angryReclaimDivisor;
+    }
+
+    size_t allocSize;
+    size_t totalAllocSize;
+    size_t gcSize;
+
+    size_t GetTotalAllocSize() {
+        return totalAllocSize;
+    }
+    size_t GetCurSize() {
+        return allocSize;
+    }
+    size_t GetGCSize() {
+        return gcSize;
+    }
+
+    bool CanAlloc(size_t allocSize_, size_t totalAllocSize_) {
+        allocSize = allocSize_;
+        totalAllocSize = totalAllocSize_;
+        return allocSize_ < hardLimit || totalAllocSize_ < allocationThreshold;
+    }
+    bool NeedReclaim(size_t gcSize_, size_t counter) {
+        gcSize = gcSize_;
+        size_t limit = gcSize_ < softLimit ? softReclaimDivisor : angryReclaimDivisor;
+        return counter > limit;
+    }
+
+    bool IsEnabledByDefault() {
+        return EnableByDefault;
+    }
+}
diff --git a/library/cpp/balloc/setup/alloc.h b/library/cpp/balloc/setup/alloc.h
new file mode 100644
index 0000000000..89fee3e3e7
--- /dev/null
+++ b/library/cpp/balloc/setup/alloc.h
@@ -0,0 +1,35 @@
+#pragma once
+
+#include <stddef.h>
+
+namespace NAllocSetup {
+    void ThrowOnError(size_t allocSize);
+    void SetThrowConditions(size_t currSize, size_t maxSize);
+    void SetSoftLimit(size_t softLimit);
+    void SetHardLimit(size_t hardLimit);
+    void SetAllocationThreshold(size_t allocationThreshold);
+    void SetSoftReclaimDivisor(size_t softReclaimDivisor);
+    void SetAngryReclaimDivisor(size_t angryReclaimDivisor);
+    bool CanAlloc(size_t allocSize, size_t totalAllocSize);
+    bool NeedReclaim(size_t gcSize_, size_t counter);
+    size_t GetTotalAllocSize();
+    size_t GetCurSize();
+    size_t GetGCSize();
+
+    size_t GetSoftLimit();
+    size_t GetHardLimit();
+    size_t GetAllocationThreshold();
+    size_t GetSoftReclaimDivisor();
+    size_t GetAngryReclaimDivisor();
+
+    bool IsEnabledByDefault();
+
+    struct TAllocGuard {
+        TAllocGuard(size_t maxSize) {
+            SetThrowConditions(0, maxSize);
+        }
+        ~TAllocGuard() {
+            SetThrowConditions(0, 0);
+        }
+    };
+}
diff --git a/library/cpp/balloc/setup/disable_by_default/disable.cpp b/library/cpp/balloc/setup/disable_by_default/disable.cpp
new file mode 100644
index 0000000000..fe39d5c559
--- /dev/null
+++ b/library/cpp/balloc/setup/disable_by_default/disable.cpp
@@ -0,0 +1,9 @@
+#include <library/cpp/balloc/setup/enable.h>
+
+#include <util/system/compiler.h>
+
+namespace NAllocSetup {
+    // Overriding a weak symbol defined in library/cpp/balloc/setup/enable.cpp.
+    // Don't link with this object if your platform doesn't support weak linkage.
+    extern const bool EnableByDefault = false;
+}
diff --git a/library/cpp/balloc/setup/enable.cpp b/library/cpp/balloc/setup/enable.cpp
new file mode 100644
index 0000000000..9eba81e7a7
--- /dev/null
+++ b/library/cpp/balloc/setup/enable.cpp
@@ -0,0 +1,9 @@
+#include "enable.h"
+
+#include <util/system/compiler.h>
+
+namespace NAllocSetup {
+    // This constant can be overridden on platforms that support weak linkage.
+    // See library/cpp/balloc/setup/disable_by_default/disabled.cpp
+    extern const bool EnableByDefault Y_WEAK = true;
+}
diff --git a/library/cpp/balloc/setup/enable.h b/library/cpp/balloc/setup/enable.h
new file mode 100644
index 0000000000..78449c1000
--- /dev/null
+++ b/library/cpp/balloc/setup/enable.h
@@ -0,0 +1,11 @@
+#pragma once
+
+namespace NAllocSetup {
+    // The IsEnabledByDefault variable should always have static initialization. It is safe to use it in initialization
+    // of global and thread-local objects because standard guarantees that static initalization always takes place
+    // before dynamic initialization:
+    // * C++11 3.6.2.2: "Static initialization shall be performed before any dynamic initialization takes place."
+    // * C++17 6.6.2.2: "All static initialization strongly happens before any dynamic initialization."
+    // On practice a constant value is just baked into the executable during the linking.
+    extern const bool EnableByDefault;
+}
diff --git a/library/cpp/balloc/test/do_with_disabled/main.cpp b/library/cpp/balloc/test/do_with_disabled/main.cpp
new file mode 100644
index 0000000000..245887cb66
--- /dev/null
+++ b/library/cpp/balloc/test/do_with_disabled/main.cpp
@@ -0,0 +1,24 @@
+#include <library/cpp/balloc/optional/operators.h>
+
+#undef NDEBUG
+
+#include <cstdlib>
+#include <cstring>
+#include <cassert>
+
+// internal hook for the testing
+extern "C" bool IsOwnedByBalloc(void* ptr);
+
+int main() {
+    char* buf = (char*)malloc(100);
+    assert(false == IsOwnedByBalloc(buf));
+
+    ThreadEnableBalloc();
+    char* buf2 = (char*)malloc(100);
+    assert(true == IsOwnedByBalloc(buf2));
+
+    free(buf);
+    free(buf2);
+
+    return 0;
+}
diff --git a/library/cpp/balloc/test/do_with_enabled/main.cpp b/library/cpp/balloc/test/do_with_enabled/main.cpp
new file mode 100644
index 0000000000..02c165ccc3
--- /dev/null
+++ b/library/cpp/balloc/test/do_with_enabled/main.cpp
@@ -0,0 +1,24 @@
+#include <library/cpp/balloc/optional/operators.h>
+
+#undef NDEBUG
+
+#include <cstdlib>
+#include <cstring>
+#include <cassert>
+
+// internal hook for the testing
+extern "C" bool IsOwnedByBalloc(void* ptr);
+
+int main() {
+    char* buf = (char*)malloc(100);
+    assert(true == IsOwnedByBalloc(buf));
+
+    ThreadDisableBalloc();
+    char* buf2 = (char*)malloc(100);
+    assert(false == IsOwnedByBalloc(buf2));
+
+    free(buf);
+    free(buf2);
+
+    return 0;
+}
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");
+    }
+}