speedup GmTimeR function

в профиле перфа Маркетного репорта постоянно вижу GmTimeR
там в цикле вычитается по количеству дней в году и прибавляется по 1 году с 1970 по 2022 на каждый вызов

В Маркете проблема стреляла и раньше

в последней итерации функция становится на ~~30% быстрее системной gmtime_r

%%
----------- GmTimeR ---------------
 samples:       20691
 iterations:    264304536
 iterations hr:    264M
 run time:      5.002055225
 per iteration: 39.85866484 cycles
----------- gmtime_r ---------------
 samples:       17452
 iterations:    188034528
 iterations hr:    188M
 run time:      5.001259884
 per iteration: 56.96146577 cycles
%%

текущая верся почти в 2 раза медленнее системной:

%%
----------- GmTimeR ---------------
 samples:       12760
 iterations:    100514931
 iterations hr:    101M
 run time:      5.00096133
 per iteration: 105.4334174 cycles
----------- gmtime_r ---------------
 samples:       17667
 iterations:    192697896
 iterations hr:    193M
 run time:      5.001356603
 per iteration: 55.69031415 cycles
%%

2 files changed, 166 insertions, 34 deletions

diff --git a/util/datetime/base_ut.cpp b/util/datetime/base_ut.cpp
index afc3f802eb..56b7496d19 100644
--- a/util/datetime/base_ut.cpp
+++ b/util/datetime/base_ut.cpp
@@ -10,7 +10,7 @@
 #include <util/system/compat.h>
 #include <util/random/random.h>
 
-#include <limits.h>
+#include <climits>
 
 using namespace std::chrono_literals;
 
@@ -412,6 +412,8 @@ Y_UNIT_TEST_SUITE(DateTimeTest) {
 
     Y_UNIT_TEST(TestInstantToString) {
         UNIT_ASSERT_VALUES_EQUAL(TString("2009-08-06T15:19:06.023455Z"), ToString(TInstant::Seconds(1249571946) + TDuration::MicroSeconds(23455)));
+        UNIT_ASSERT_VALUES_EQUAL(TString("2022-08-23T13:04:43.023455Z"), ToString(TInstant::Seconds(1661259883) + TDuration::MicroSeconds(23455)));
+        UNIT_ASSERT_VALUES_EQUAL(TString("2122-11-23T15:12:26.023455Z"), ToString(TInstant::Seconds(4824889946) + TDuration::MicroSeconds(23455)));
         UNIT_ASSERT_VALUES_EQUAL(TString("2009-08-06T15:19:06.023455Z"), (TInstant::Seconds(1249571946) + TDuration::MicroSeconds(23455)).ToString());
         UNIT_ASSERT_VALUES_EQUAL(TString("2009-08-06T15:19:06Z"), (TInstant::Seconds(1249571946) + TDuration::MicroSeconds(23455)).ToStringUpToSeconds());
     }
diff --git a/util/datetime/systime.cpp b/util/datetime/systime.cpp
index 6ee7e8fc6e..149d715e09 100644
--- a/util/datetime/systime.cpp
+++ b/util/datetime/systime.cpp
@@ -48,12 +48,135 @@ char* ctime_r(const time_t* clock, char* buf) {
 
 #endif /* _win_ */
 
-#define YEAR0 1900
-#define EPOCH_YR 1970
-#define SECS_DAY (24L * 60L * 60L)
-#define LEAPYEAR(year) (!((year) % 4) && (((year) % 100) || !((year) % 400)))
-#define YEARSIZE(year) (LEAPYEAR(year) ? 366 : 365)
-#define FOURCENTURIES (400 * 365 + 100 - 3)
+namespace {
+    constexpr int STRUCT_TM_BASE_YEAR = 1900;
+    constexpr int UNIX_TIME_BASE_YEAR = 1970;
+    constexpr long SECONDS_PER_DAY = (24L * 60L * 60L);
+
+    constexpr bool IsLeapYear(int year) {
+        if (year % 4 != 0) {
+            return false;
+        }
+        if (year % 100 != 0) {
+            return true;
+        }
+        return year % 400 == 0;
+    }
+
+    constexpr ui16 YEAR_PER_YEAR = 365;
+    constexpr ui16 YEAR_PER_LEAP_YEAR = 366;
+
+    constexpr ui16 YearSize(int year) {
+        return IsLeapYear(year) ? YEAR_PER_LEAP_YEAR : YEAR_PER_YEAR;
+    }
+
+    constexpr ui64 FOUR_CENTURIES = (400 * 365 + 100 - 3);
+
+    constexpr ui16 MONTH_TO_DAYS[12] = {
+        0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};
+
+    constexpr ui16 MONTH_TO_DAYS_LEAP[12] = {
+        0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335};
+
+    template <ui8 DaysInFeb>
+    constexpr int DayOfYearToMonth(ui64& day) {
+        Y_ASSERT(day >= 0);
+        Y_ASSERT(day < 366);
+
+        constexpr ui8 JanDays = 31;
+        constexpr ui8 FebDays = JanDays + DaysInFeb;
+        constexpr ui8 MarDays = FebDays + 31;
+        constexpr ui8 AprDays = MarDays + 30;
+        constexpr ui8 MayDays = AprDays + 31;
+        constexpr ui8 JunDays = MayDays + 30;
+        constexpr ui8 JulDays = JunDays + 31;
+        constexpr ui16 AugDays = JulDays + 31;
+        constexpr ui16 SepDays = AugDays + 30;
+        constexpr ui16 OctDays = SepDays + 31;
+        constexpr ui16 NovDays = OctDays + 30;
+
+        // hard-coded binary search
+        // this approach is faster that lookup in array using std::lower_bound()
+        // GmTimeR takes ~40 cycles vs ~60 cycles using std::lower_bound version
+        if (day < JunDays) {
+            if (day < MarDays) {
+                if (day < JanDays) {
+                    return 0;
+                } else if (day < FebDays) {
+                    day -= JanDays;
+                    return 1;
+                } else {
+                    day -= FebDays;
+                    return 2;
+                }
+            } else {
+                if (day < AprDays) {
+                    day -= MarDays;
+                    return 3;
+                } else if (day < MayDays) {
+                    day -= AprDays;
+                    return 4;
+                } else {
+                    day -= MayDays;
+                    return 5;
+                }
+            }
+        } else {
+            if (day < SepDays) {
+                if (day < JulDays) {
+                    day -= JunDays;
+                    return 6;
+                } else if (day < AugDays) {
+                    day -= JulDays;
+                    return 7;
+                } else {
+                    day -= AugDays;
+                    return 8;
+                }
+            } else {
+                if (day < OctDays) {
+                    day -= SepDays;
+                    return 9;
+                } else if (day < NovDays) {
+                    day -= OctDays;
+                    return 10;
+                } else {
+                    day -= NovDays;
+                    return 11;
+                }
+            }
+        }
+    }
+
+    class TDayNoToYearLookupTable {
+    private:
+        static constexpr int TableSize = 128;
+        // lookup table for years in [1970, 1970 + 128 = 2098] range
+        ui16 DaysSinceEpoch[TableSize] = {};
+
+    public:
+        constexpr TDayNoToYearLookupTable() {
+            DaysSinceEpoch[0] = YearSize(UNIX_TIME_BASE_YEAR);
+
+            for (int year = UNIX_TIME_BASE_YEAR + 1; year < UNIX_TIME_BASE_YEAR + TableSize; ++year) {
+                DaysSinceEpoch[year - UNIX_TIME_BASE_YEAR] = DaysSinceEpoch[year - UNIX_TIME_BASE_YEAR - 1] + YearSize(year);
+            }
+        };
+
+        // lookup year by days since epoch, decrement day counter to the corresponding amount of days.
+        // The method returns the last year in the table, if year is too big
+        int GetYear(ui64& days) const {
+            size_t year = std::upper_bound(DaysSinceEpoch, Y_ARRAY_END(DaysSinceEpoch), days) - Y_ARRAY_BEGIN(DaysSinceEpoch);
+            if (year > 0) {
+                days -= DaysSinceEpoch[year - 1];
+            }
+
+            return year + UNIX_TIME_BASE_YEAR;
+        }
+    };
+
+    constexpr TDayNoToYearLookupTable DAYS_TO_YEAR_LOOKUP;
+}
 
 //! Inverse of gmtime: converts struct tm to time_t, assuming the data
 //! in tm is UTC rather than local timezone. This implementation
@@ -62,12 +185,8 @@ char* ctime_r(const time_t* clock, char* buf) {
 //!       http://osdir.com/ml/web.wget.patches/2005-07/msg00010.html
 //!       Subject: A more robust timegm - msg#00010
 time_t TimeGM(const struct tm* t) {
-    static const unsigned short int month_to_days[][13] = {
-        {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334},
-        {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335}};
-
     // Only handles years after 1970
-    if (t->tm_year < 70) {
+    if (Y_UNLIKELY(t->tm_year < 70)) {
         return (time_t)-1;
     }
 
@@ -75,10 +194,15 @@ time_t TimeGM(const struct tm* t) {
     // Take into account the leap days between 1970 and YEAR-1
     days += (t->tm_year - 1 - 68) / 4 - ((t->tm_year - 1) / 100) + ((t->tm_year - 1 + 300) / 400);
 
-    if (t->tm_mon < 0 || t->tm_mon >= 12) {
+    if (Y_UNLIKELY(t->tm_mon < 0 || t->tm_mon >= 12)) {
         return (time_t)-1;
     }
-    days += month_to_days[LEAPYEAR(1900 + t->tm_year)][t->tm_mon];
+    if (IsLeapYear(1900 + t->tm_year)) {
+        days += MONTH_TO_DAYS_LEAP[t->tm_mon];
+    } else {
+        days += MONTH_TO_DAYS[t->tm_mon];
+    }
+
     days += t->tm_mday - 1;
 
     unsigned long secs = days * 86400ul + t->tm_hour * 3600 + t->tm_min * 60 + t->tm_sec;
@@ -86,42 +210,48 @@ time_t TimeGM(const struct tm* t) {
 }
 
 struct tm* GmTimeR(const time_t* timer, struct tm* tmbuf) {
-    static const int _ytab[2][12] = {
-        {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
-        {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
-
     i64 time = static_cast<i64>(*timer);
 
     ui64 dayclock, dayno;
-    int year = EPOCH_YR;
+    int year = UNIX_TIME_BASE_YEAR;
 
-    if (time < 0) {
-        ui64 shift = (ui64)(-time - 1) / ((ui64)FOURCENTURIES * SECS_DAY) + 1;
-        time += shift * ((ui64)FOURCENTURIES * SECS_DAY);
+    if (Y_UNLIKELY(time < 0)) {
+        ui64 shift = (ui64)(-time - 1) / (FOUR_CENTURIES * SECONDS_PER_DAY) + 1;
+        time += shift * (FOUR_CENTURIES * SECONDS_PER_DAY);
         year -= shift * 400;
     }
 
-    dayclock = (ui64)time % SECS_DAY;
-    dayno = (ui64)time / SECS_DAY;
+    dayclock = (ui64)time % SECONDS_PER_DAY;
+    dayno = (ui64)time / SECONDS_PER_DAY;
 
-    year += 400 * (dayno / FOURCENTURIES);
-    dayno = dayno % FOURCENTURIES;
+    if (Y_UNLIKELY(dayno >= FOUR_CENTURIES)) {
+        year += 400 * (dayno / FOUR_CENTURIES);
+        dayno = dayno % FOUR_CENTURIES;
+    }
 
     tmbuf->tm_sec = dayclock % 60;
     tmbuf->tm_min = (dayclock % 3600) / 60;
     tmbuf->tm_hour = dayclock / 3600;
     tmbuf->tm_wday = (dayno + 4) % 7; // Day 0 was a thursday
-    while (dayno >= (ui64)YEARSIZE(year)) {
-        dayno -= YEARSIZE(year);
+
+    if (Y_LIKELY(year == UNIX_TIME_BASE_YEAR)) {
+        year = DAYS_TO_YEAR_LOOKUP.GetYear(dayno);
+    }
+
+    for (;;) {
+        const ui16 yearSize = YearSize(year);
+        if (dayno < yearSize) {
+            break;
+        }
+        dayno -= yearSize;
         ++year;
     }
-    tmbuf->tm_year = year - YEAR0;
+
+    tmbuf->tm_year = year - STRUCT_TM_BASE_YEAR;
     tmbuf->tm_yday = dayno;
-    tmbuf->tm_mon = 0;
-    while (dayno >= (ui64)_ytab[LEAPYEAR(year)][tmbuf->tm_mon]) {
-        dayno -= _ytab[LEAPYEAR(year)][tmbuf->tm_mon];
-        ++tmbuf->tm_mon;
-    }
+    tmbuf->tm_mon = IsLeapYear(year)
+                        ? DayOfYearToMonth<29>(dayno)
+                        : DayOfYearToMonth<28>(dayno);
     tmbuf->tm_mday = dayno + 1;
     tmbuf->tm_isdst = 0;
 #ifndef _win_