From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2181) id 9A7E03953424; Wed, 24 Feb 2021 18:52:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9A7E03953424 MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Jonathan Wakely To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r11-7372] libstdc++: More efficient last day of month X-Act-Checkin: gcc X-Git-Author: Cassio Neri X-Git-Refname: refs/heads/master X-Git-Oldrev: 126793971bee0e92bea237823bdc51a594951faa X-Git-Newrev: 8265ab07f3bbeb672488fdfc6418e0bce89dff9c Message-Id: <20210224185224.9A7E03953424@sourceware.org> Date: Wed, 24 Feb 2021 18:52:24 +0000 (GMT) X-BeenThere: libstdc++-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 24 Feb 2021 18:52:24 -0000 https://gcc.gnu.org/g:8265ab07f3bbeb672488fdfc6418e0bce89dff9c commit r11-7372-g8265ab07f3bbeb672488fdfc6418e0bce89dff9c Author: Cassio Neri Date: Wed Feb 24 18:12:47 2021 +0000 libstdc++: More efficient last day of month This patch reimplements std::chrono::year_month_day_last:day() which yields the last day of a particular month. The current implementation uses a look-up table implemented as an unsigned[12] array. The new implementation instead is based on the fact that a month m in [1, 12], except for m == 2 (February), is either 31 or 30 days long and m's length depends on two things: m's parity and whether m >= 8 or not. These two conditions are determined by the 0th and 3th bit of m and, therefore, cheap and straightforward bit-twiddling can provide the right result. Measurements in x86_64 [1] suggest a 10% performance boost. Although this does not seem to be huge, notice that measurements are done in hot L1 cache conditions which might not be very representative of production runs. Also freeing L1 cache from holding the look-up table might allow performance improvements elsewhere. References: [1] https://github.com/cassioneri/calendar libstdc++-v3/ChangeLog: * include/std/chrono (year_month_day_last:day): New implementation. Diff: --- libstdc++-v3/include/std/chrono | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-) diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index 3ba35a5bc86..feb2c2a1fad 100644 --- a/libstdc++-v3/include/std/chrono +++ b/libstdc++-v3/include/std/chrono @@ -1269,9 +1269,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION inline constexpr unsigned __days_per_month[12] = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; - - inline constexpr unsigned __last_day[12] - = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; } // DAY @@ -2576,9 +2573,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION constexpr chrono::day day() const noexcept { - if (!_M_mdl.ok() || (month() == February && _M_y.is_leap())) - return chrono::day{29}; - return chrono::day{__detail::__last_day[unsigned(month()) - 1]}; + const auto __m = static_cast(month()); + + // Excluding February, the last day of month __m is either 30 or 31 or, + // in another words, it is 30 + b = 30 | b, where b is in {0, 1}. + + // If __m in {1, 3, 4, 5, 6, 7}, then b is 1 if, and only if __m is odd. + // Hence, b = __m & 1 = (__m ^ 0) & 1. + + // If __m in {8, 9, 10, 11, 12}, then b is 1 if, and only if __m is even. + // Hence, b = (__m ^ 1) & 1. + + // Therefore, b = (__m ^ c) & 1, where c = 0, if __m < 8, or c = 1 if + // __m >= 8, that is, c = __m >> 3. + + // The above mathematically justifies this implementation whose + // performance does not depend on look-up tables being on the L1 cache. + return chrono::day{__m != 2 ? ((__m ^ (__m >> 3)) & 1) | 30 + : _M_y.is_leap() ? 29 : 28}; } constexpr