GmTimeR x2 speedup

performance comparison againt standard gmtime\_r

```
-------------------------------------------------------------------------------
Benchmark                                     Time             CPU   Iterations
-------------------------------------------------------------------------------
BM_GmTimeR                                 3.66 ns         3.66 ns    189855900
BM_gmtime_r                                18.7 ns         18.7 ns     37340999
BM_GmTimeRRandom/last_hour                 5.12 ns         5.12 ns    136126173
BM_gmtime_r_Random/last_hour               19.2 ns         19.2 ns     36556971
BM_GmTimeRRandom/last_day                  5.10 ns         5.10 ns    138257644
BM_gmtime_r_Random/last_day                19.2 ns         19.2 ns     37025160
BM_GmTimeRRandom/last_month                7.10 ns         7.10 ns     98235494
BM_gmtime_r_Random/last_month              20.4 ns         20.4 ns     34637975
BM_GmTimeRRandom/last_year                 15.0 ns         15.0 ns     46664304
BM_gmtime_r_Random/last_year               26.8 ns         26.8 ns     26135911
BM_GmTimeRRandom/last_decade               17.2 ns         17.2 ns     40105536
BM_gmtime_r_Random/last_decade             27.0 ns         27.0 ns     25817056
BM_GmTimeRRandom/last_half_centry          17.1 ns         17.0 ns     41066079
BM_gmtime_r_Random/last_half_century       26.8 ns         26.7 ns     26215076
```
commit_hash:33747760ad46412f50fe3cb06f4c438794a44492

1 files changed, 24 insertions, 13 deletions

diff --git a/util/datetime/systime.cpp b/util/datetime/systime.cpp
index fd0c69dc7c..d9f31fbc5a 100644
--- a/util/datetime/systime.cpp
+++ b/util/datetime/systime.cpp
@@ -104,7 +104,6 @@ namespace {
 
     template <ui8 DaysInFeb>
     constexpr int DayOfYearToMonth(ui64& day) {
-        Y_ASSERT(day >= 0);
         Y_ASSERT(day < 366);
 
         constexpr ui8 JanDays = 31;
@@ -173,29 +172,39 @@ namespace {
     }
 
     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);
+            ui16 daysAccumulated = 0;
 
-            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);
+            for (int year = UNIX_TIME_BASE_YEAR; year < UNIX_TIME_BASE_YEAR + TableSize; ++year) {
+                daysAccumulated += YearSize(year);
+                DaysSinceEpoch[year - UNIX_TIME_BASE_YEAR] = daysAccumulated;
             }
         }
 
         // 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];
+        int FindYear(ui64& days) const {
+            if (days >= DaysSinceEpoch[TableSize - 1]) {
+                days -= DaysSinceEpoch[TableSize - 1];
+                return TableSize + UNIX_TIME_BASE_YEAR;
             }
+            ui64 yearIndex = days / DAYS_IN_YEAR;
 
-            return year + UNIX_TIME_BASE_YEAR;
+            // we can miss by at most 1 year
+            if (yearIndex > 0 && DaysSinceEpoch[yearIndex - 1] >= days) {
+                --yearIndex;
+            }
+
+            if (yearIndex > 0) {
+                days -= DaysSinceEpoch[yearIndex - 1];
+            }
+
+            return static_cast<int>(yearIndex + UNIX_TIME_BASE_YEAR);
         }
     };
 
@@ -259,21 +268,23 @@ struct tm* GmTimeR(const time_t* timer, struct tm* tmbuf) {
     tmbuf->tm_wday = (dayno + 4) % 7; // Day 0 was a thursday
 
     if (Y_LIKELY(year == UNIX_TIME_BASE_YEAR)) {
-        year = DAYS_TO_YEAR_LOOKUP.GetYear(dayno);
+        year = DAYS_TO_YEAR_LOOKUP.FindYear(dayno);
     }
 
+    bool isLeapYear = IsLeapYear(year);
     for (;;) {
-        const ui16 yearSize = YearSize(year);
+        const ui16 yearSize = isLeapYear ? DAYS_IN_LEAP_YEAR : DAYS_IN_YEAR;
         if (dayno < yearSize) {
             break;
         }
         dayno -= yearSize;
         ++year;
+        isLeapYear = IsLeapYear(year);
     }
 
     tmbuf->tm_year = year - STRUCT_TM_BASE_YEAR;
     tmbuf->tm_yday = dayno;
-    tmbuf->tm_mon = IsLeapYear(year)
+    tmbuf->tm_mon = isLeapYear
                         ? DayOfYearToMonth<29>(dayno)
                         : DayOfYearToMonth<28>(dayno);
     tmbuf->tm_mday = dayno + 1;