Optimize calendar date conversion#1634
Conversation
|
Benchmark code: #include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <random>
#include <ratio>
#include <vector>
using namespace std;
using namespace std::chrono;
int main() {
constexpr int min_year = -32767;
constexpr int max_year = 32767;
constexpr int runs = 5;
cout << fixed << setprecision(1);
vector<year_month_day> ymds;
ymds.reserve((max_year - min_year + 1) * 366);
for (int y = min_year; y <= max_year; ++y) {
for (unsigned int m = 1; m <= 12; ++m) {
for (unsigned int d = 1; d <= 31; ++d) {
auto ymd = year{y} / month{m} / day{d};
if (!ymd.ok()) {
break;
}
ymds.push_back(ymd);
}
}
}
mt19937 rng(random_device{}());
const size_t total = ymds.size();
vector<sys_days> sds(total);
for (int i = 0; i < runs; ++i) {
ranges::shuffle(ymds, rng);
const auto start_t = steady_clock::now();
ranges::transform(ymds, sds.begin(), [](const auto& ymd) { return sys_days{ymd}; });
const auto end_t = steady_clock::now();
unsigned int dummy = 0;
for (const auto& sd : sds) {
dummy += sd.time_since_epoch().count();
}
cout << "year_month_day => sys_days: " << setw(6) << (duration<double, nano>{end_t - start_t} / total)
<< " (dummy: " << dummy << ")\n";
}
for (int i = 0; i < runs; ++i) {
ranges::shuffle(sds, rng);
const auto start_t = steady_clock::now();
ranges::transform(sds, ymds.begin(), [](const auto& sd) { return year_month_day{sd}; });
const auto end_t = steady_clock::now();
unsigned int dummy = 0;
for (const auto& ymd : ymds) {
dummy += static_cast<int>(ymd.year());
dummy += static_cast<unsigned int>(ymd.month());
dummy += static_cast<unsigned int>(ymd.day());
}
cout << "sys_days => year_month_day: " << setw(6) << (duration<double, nano>{end_t - start_t} / total)
<< " (dummy: " << dummy << ")\n";
}
return 0;
}Results on Intel Core i5-8400, MSVC 19.28.29812, clang 11.0.0:
|
StephanTLavavej
left a comment
There was a problem hiding this comment.
Thanks for the optimization and detailed benchmark results! Everything looks good to me.
[time.cal.ymd.members]/19:
Returns: If `ok()`, [...]. Otherwise, if `y_.ok() && m_.ok()` is `true`,
returns `sys_days{y_/m_/1d} + (d_ - 1d). Otherwise [...]
Removed incorrect comment on the range of `_Day_of_year`, and changed
its type from `unsigned int` to `int` to clarify that it could be
negative.
Added test cases for this clause.
|
mnatsuhara
left a comment
There was a problem hiding this comment.
Thanks for this optimization! This looks great from what I can tell, just a small ask for further documentation of these clever algorithms at some point :)
| const int _Century = (_Zx >= 0 ? 4 * _Zx + 3 : 4 * _Zx - 146093) / 146097; | ||
| const unsigned int _Day_of_century = | ||
| static_cast<unsigned int>(_Zx - ((146097 * _Century) >> 2)); // [0, 36524] | ||
| const unsigned int _Year_of_century = (91867 * (_Day_of_century + 1)) >> 25; // [0, 99] | ||
| const int _Year = static_cast<int>(_Year_of_century) + _Century * 100; // Where March is the first month | ||
| const unsigned int _Day_of_year = _Day_of_century - ((1461 * _Year_of_century) >> 2); // [0, 365] | ||
| const unsigned int _Mp = (535 * _Day_of_year + 333) >> 14; // [0, 11] | ||
| const unsigned int _Day = _Day_of_year - ((979 * _Mp + 19) >> 5) + 1; // [1, 31] |
There was a problem hiding this comment.
Thanks so much for these optimized algorithms! Given the thorough testing, I am fairly confident in their correctness, but confess that I am having trouble following the logic behind a few of the calculations. I don't want this to hold up merging, but have filed #1641 so we can add a short explanation here in future (applies to both _Civil_from_days and _Days_from_civil).
|
Thanks for significantly optimizing these core algorithms so |
Micro-optimize codegen of conversion between
year_month_dayandsys_days.