diff options
author | tobo <tobo@yandex-team.com> | 2025-02-18 07:25:33 +0300 |
---|---|---|
committer | tobo <tobo@yandex-team.com> | 2025-02-18 07:41:34 +0300 |
commit | b9824e1dc11c30a60d6416b9d345758bc7901544 (patch) | |
tree | 8902d1a7af11870c2958ee3ed5681318bcfec3d3 | |
parent | 8fe93946bc369873a7ffbb3a7403463aa80e3117 (diff) | |
download | ydb-b9824e1dc11c30a60d6416b9d345758bc7901544.tar.gz |
[util] speedup GmTimeR outside LUT interval
commit_hash:d57be220df393c193619ef5ed129ec4436540629
-rw-r--r-- | util/datetime/base_ut.cpp | 18 | ||||
-rw-r--r-- | util/datetime/systime.cpp | 181 | ||||
-rw-r--r-- | util/datetime/systime.h | 15 |
3 files changed, 133 insertions, 81 deletions
diff --git a/util/datetime/base_ut.cpp b/util/datetime/base_ut.cpp index cc2e776e48..3ac1a90a90 100644 --- a/util/datetime/base_ut.cpp +++ b/util/datetime/base_ut.cpp @@ -310,10 +310,8 @@ Y_UNIT_TEST_SUITE(TDateTimeTest) { && true; } - Y_UNIT_TEST(TestGmTimeR) { - time_t starttime = static_cast<time_t>(Max<i64>(-12244089600LL, Min<time_t>())); // 1-Jan-1582 - time_t finishtime = static_cast<time_t>(Min<i64>(0xFFFFFFFF * 20, Max<time_t>())); - time_t step = (finishtime - starttime) / 25; + void TestGmTimeR(time_t starttime, time_t finishtime, int steps) { + time_t step = (finishtime - starttime) / steps; struct tm tms0, tms1; struct tm* ptm0 = nullptr; struct tm* ptm1 = nullptr; @@ -336,6 +334,18 @@ Y_UNIT_TEST_SUITE(TDateTimeTest) { UNIT_ASSERT(CompareTMFull(ptm0, ptm1)); } } + + Y_UNIT_TEST(TestGmTimeRLongRange) { + time_t starttime = static_cast<time_t>(-86397839500LL); // 29-Jan-2668 B.C. + time_t finishtime = static_cast<time_t>(0xFFFFFFFF * 20); + TestGmTimeR(starttime, finishtime, 101); + } + + Y_UNIT_TEST(TestGmTimeRNowdays) { + time_t starttime = static_cast<time_t>(0); // 1970 + time_t finishtime = static_cast<time_t>(6307200000LL); // 2170 + TestGmTimeR(starttime, finishtime, 303); + } } // Y_UNIT_TEST_SUITE(TDateTimeTest) Y_UNIT_TEST_SUITE(DateTimeTest) { diff --git a/util/datetime/systime.cpp b/util/datetime/systime.cpp index a2dd48e3b0..04972b6e48 100644 --- a/util/datetime/systime.cpp +++ b/util/datetime/systime.cpp @@ -75,7 +75,7 @@ char* ctime_r(const time_t* clock, char* buf) { namespace { constexpr int STRUCT_TM_BASE_YEAR = 1900; constexpr int UNIX_TIME_BASE_YEAR = 1970; - constexpr long SECONDS_PER_DAY = (24L * 60L * 60L); + constexpr ui64 SECONDS_PER_DAY = (24L * 60L * 60L); constexpr bool IsLeapYear(int year) { if (year % 4 != 0) { @@ -94,7 +94,29 @@ namespace { return IsLeapYear(year) ? DAYS_IN_LEAP_YEAR : DAYS_IN_YEAR; } - constexpr ui64 FOUR_CENTURIES = (400 * 365 + 100 - 3); + constexpr ui32 FOUR_CENTURY_YEARS = 400; + + constexpr ui32 LeapYearCount(ui32 years) { + return years / 4 - years / 100 + years / 400; + } + + constexpr ui32 FOUR_CENTURY_DAYS = FOUR_CENTURY_YEARS * DAYS_IN_YEAR + LeapYearCount(FOUR_CENTURY_YEARS); + + constexpr int FindYearWithin4Centuries(ui32& dayno) { + Y_ASSERT(dayno < FOUR_CENTURY_DAYS); + ui32 years = dayno / DAYS_IN_YEAR; + + const ui32 diff = years * DAYS_IN_YEAR + LeapYearCount(years); + + if (diff <= dayno) { + dayno -= diff; + } else { + dayno -= diff - YearSize(static_cast<int>(years)); + --years; + } + + return static_cast<int>(years); + } constexpr ui16 MONTH_TO_DAYS[12] = { 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}; @@ -103,73 +125,73 @@ namespace { 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335}; struct TMonth32LUT { - char LastMonthDay32[12]; - char FirstMonthDay32[12]; + ui8 LastMonthDay32[12]; + ui8 FirstMonthDay32[12]; }; - constexpr TMonth32LUT MONTH_32_LUT[2] = { - { - // common year - .LastMonthDay32 = {31, 27, 26, 24, 23, 21, 20, 19, 17, 16, 14, 13}, - .FirstMonthDay32 = {0, 1, 5, 6, 8, 9, 11, 12, 13, 15, 16, 18}, - }, - { - // leap year - .LastMonthDay32 = {31, 28, 27, 25, 24, 22, 21, 20, 18, 17, 15, 14}, - .FirstMonthDay32 = {0, 1, 4, 5, 7, 8, 10, 11, 12, 14, 15, 17}, - }, + constexpr TMonth32LUT COMMON_YEAR = { + .LastMonthDay32 = {31, 27, 26, 24, 23, 21, 20, 19, 17, 16, 14, 13}, + .FirstMonthDay32 = {0, 1, 5, 6, 8, 9, 11, 12, 13, 15, 16, 18}, }; - constexpr int DayOfYearToMonth(ui64& yearDay, bool leapYear) { - Y_ASSERT(yearDay < 366); - int approxMonth = yearDay / 32; - int approxMDay = yearDay % 32; - int dayThreshold = MONTH_32_LUT[leapYear].LastMonthDay32[approxMonth]; - int currentMonthMDayOffset = MONTH_32_LUT[leapYear].FirstMonthDay32[approxMonth]; - bool nextMonth = (approxMDay >= dayThreshold); - int dayCorrection = nextMonth ? -dayThreshold : currentMonthMDayOffset; - int day = approxMDay + dayCorrection; - int month = approxMonth + nextMonth; - yearDay = day; + constexpr int DayOfYearToMonth(ui32& yearDay, const bool leapYear) { + Y_ASSERT(yearDay < DAYS_IN_YEAR + leapYear); + if (leapYear) { + if (yearDay > 59) { + --yearDay; + } else if (yearDay == 59) { + // February, 29th + yearDay = 28; + return 1; + } + } + const int approxMonth = static_cast<int>(yearDay / 32); + const int approxMDay = static_cast<int>(yearDay % 32); + const int dayThreshold = COMMON_YEAR.LastMonthDay32[approxMonth]; + const int currentMonthMDayOffset = COMMON_YEAR.FirstMonthDay32[approxMonth]; + const bool nextMonth = (approxMDay >= dayThreshold); + const int dayCorrection = nextMonth ? -dayThreshold : currentMonthMDayOffset; + yearDay = approxMDay + dayCorrection; + const int month = approxMonth + nextMonth; return month; } class TDayNoToYearLookupTable { static constexpr int TableSize = 128; - // lookup table for years in [1970, 1970 + 128 = 2098] range + // lookup table for years in [StartYear, StartYear + TableSize] range ui16 DaysSinceEpoch[TableSize] = {}; public: + static constexpr int StartYear = 1970; + static constexpr int StartDays = (StartYear - UNIX_TIME_BASE_YEAR) * DAYS_IN_YEAR + LeapYearCount(StartYear - 1) - LeapYearCount(UNIX_TIME_BASE_YEAR - 1); + static constexpr i64 MinTimestamp = StartDays * static_cast<i64>(SECONDS_PER_DAY); + static constexpr i64 MaxTimestamp = MinTimestamp + static_cast<i64>(TableSize) * DAYS_IN_LEAP_YEAR * SECONDS_PER_DAY - 1; constexpr TDayNoToYearLookupTable() { ui16 daysAccumulated = 0; - for (int year = UNIX_TIME_BASE_YEAR; year < UNIX_TIME_BASE_YEAR + TableSize; ++year) { + for (int year = StartYear; year < StartYear + TableSize; ++year) { daysAccumulated += YearSize(year); - DaysSinceEpoch[year - UNIX_TIME_BASE_YEAR] = daysAccumulated; + DaysSinceEpoch[year - StartYear] = 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 FindYear(ui64& days) const { - if (days >= DaysSinceEpoch[TableSize - 1]) { - days -= DaysSinceEpoch[TableSize - 1]; - return TableSize + UNIX_TIME_BASE_YEAR; - } - const ui64 yearIndex = days / DAYS_IN_LEAP_YEAR; + int FindYear(ui32& days) const { + const ui32 yearIndex = days / DAYS_IN_LEAP_YEAR; // we can miss by at most 1 year Y_ASSERT(yearIndex < TableSize); if (const auto diff = DaysSinceEpoch[yearIndex]; diff <= days) { days -= diff; - return static_cast<int>(yearIndex + UNIX_TIME_BASE_YEAR + 1); + return static_cast<int>(yearIndex + StartYear + 1); } if (yearIndex > 0) { days -= DaysSinceEpoch[yearIndex - 1]; } - return static_cast<int>(yearIndex + UNIX_TIME_BASE_YEAR); + return static_cast<int>(yearIndex + StartYear); } }; @@ -209,55 +231,72 @@ time_t TimeGM(const struct tm* t) { struct tm* GmTimeR(const time_t* timer, struct tm* tmbuf) { i64 time = static_cast<i64>(*timer); + tm* resut = tmbuf; + int dayClock; + ui32 daysRemaining; + bool isLeapYear; + + if (time >= TDayNoToYearLookupTable::MinTimestamp && time <= TDayNoToYearLookupTable::MaxTimestamp) + { + dayClock = static_cast<int>(time % SECONDS_PER_DAY); + daysRemaining = time / SECONDS_PER_DAY; + tmbuf->tm_wday = static_cast<int>((daysRemaining + 4) % 7); // Day 0 was a thursday + daysRemaining -= TDayNoToYearLookupTable::StartDays; + const int year = DAYS_TO_YEAR_LOOKUP.FindYear(daysRemaining); + isLeapYear = IsLeapYear(year); + tmbuf->tm_year = year - STRUCT_TM_BASE_YEAR; + } else { + i64 year = UNIX_TIME_BASE_YEAR; - ui64 dayclock, dayno; - int year = UNIX_TIME_BASE_YEAR; - - 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; - } + if (Y_UNLIKELY(time < 0)) { + const ui64 shift = (ui64)(-time - 1) / (static_cast<ui64>(FOUR_CENTURY_DAYS) * SECONDS_PER_DAY) + 1; + time += static_cast<i64>(shift * FOUR_CENTURY_DAYS * SECONDS_PER_DAY); + year -= static_cast<i64>(shift * FOUR_CENTURY_YEARS); + } - dayclock = (ui64)time % SECONDS_PER_DAY; - dayno = (ui64)time / SECONDS_PER_DAY; + dayClock = static_cast<int>(time % SECONDS_PER_DAY); + ui64 dayNo = (ui64)time / SECONDS_PER_DAY; + tmbuf->tm_wday = (dayNo + 4) % 7; // Day 0 was a thursday - if (Y_UNLIKELY(dayno >= FOUR_CENTURIES)) { - year += 400 * (dayno / FOUR_CENTURIES); - dayno = dayno % FOUR_CENTURIES; - } + if (int shiftYears = (year - 1) % FOUR_CENTURY_YEARS; shiftYears != 0) { + if (shiftYears < 0) { + shiftYears += FOUR_CENTURY_YEARS; + } + year -= shiftYears; + dayNo += shiftYears * DAYS_IN_YEAR + LeapYearCount(shiftYears); + } - 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 + if (Y_UNLIKELY(dayNo >= FOUR_CENTURY_DAYS)) { + year += FOUR_CENTURY_YEARS * (dayNo / FOUR_CENTURY_DAYS); + dayNo = dayNo % FOUR_CENTURY_DAYS; + } - if (Y_LIKELY(year == UNIX_TIME_BASE_YEAR)) { - year = DAYS_TO_YEAR_LOOKUP.FindYear(dayno); - } + daysRemaining = dayNo; + const int yearDiff = FindYearWithin4Centuries(daysRemaining); + year += yearDiff; + isLeapYear = IsLeapYear(yearDiff + 1); + tmbuf->tm_year = static_cast<int>(year - STRUCT_TM_BASE_YEAR); - bool isLeapYear = IsLeapYear(year); - for (;;) { - const ui16 yearSize = isLeapYear ? DAYS_IN_LEAP_YEAR : DAYS_IN_YEAR; - if (dayno < yearSize) { - break; + // check year overflow + if (Y_UNLIKELY(year - STRUCT_TM_BASE_YEAR != tmbuf->tm_year)) { + resut = nullptr; } - dayno -= yearSize; - ++year; - isLeapYear = IsLeapYear(year); } - tmbuf->tm_year = year - STRUCT_TM_BASE_YEAR; - tmbuf->tm_yday = dayno; - tmbuf->tm_mon = DayOfYearToMonth(dayno, isLeapYear); - tmbuf->tm_mday = dayno + 1; + tmbuf->tm_sec = dayClock % 60; + tmbuf->tm_min = (dayClock % 3600) / 60; + tmbuf->tm_hour = dayClock / 3600; + + tmbuf->tm_yday = static_cast<int>(daysRemaining); + tmbuf->tm_mon = DayOfYearToMonth(daysRemaining, isLeapYear); + tmbuf->tm_mday = static_cast<int>(daysRemaining + 1); tmbuf->tm_isdst = 0; #ifndef _win_ tmbuf->tm_gmtoff = 0; tmbuf->tm_zone = (char*)"UTC"; #endif - return tmbuf; + return resut; } TString CTimeR(const time_t* timer) { diff --git a/util/datetime/systime.h b/util/datetime/systime.h index 760c28d6e6..7810ec5f36 100644 --- a/util/datetime/systime.h +++ b/util/datetime/systime.h @@ -5,26 +5,29 @@ #include <ctime> -// timegm and gmtime_r versions that don't need access to filesystem or a big stack +// timegm and gmtime_r versions that don't need access to the file system or a large stack time_t TimeGM(const struct tm* t); + +// the same as gmtime_r, but 3–5 times faster struct tm* GmTimeR(const time_t* timer, struct tm* tmbuf); -// safe version of ctime, convinient version of ctime_r + +// safe version of ctime, convenient version of ctime_r TString CTimeR(const time_t* timer); #ifdef _win_ #include <util/system/winint.h> #include <winsock2.h> -// Convert FILETIME to timeval - seconds and microseconds. +// Convert FILETIME to timeval: seconds and microseconds. void FileTimeToTimeval(const FILETIME* ft, struct timeval* tv); -// Convert FILETIME to timespec - seconds and nanoseconds. +// Convert FILETIME to timespec: seconds and nanoseconds. void FileTimeToTimespec(const FILETIME& ft, struct timespec* ts); -// obtains the current time, expressed as seconds and microseconds since 00:00 UTC, January 1, 1970 +// Obtain the current time, expressed as seconds and microseconds since 00:00 UTC, January 1, 1970 int gettimeofday(struct timeval* tp, void*); -// thou should not mix these with non-_r functions +// You should not mix these with non-_r functions tm* localtime_r(const time_t* clock, tm* result); tm* gmtime_r(const time_t* clock, tm* result); char* ctime_r(const time_t* clock, char* buf); |