From bde089f91c7da54aea5b3694c6ce58cb020e06fe Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 27 Feb 2024 04:34:27 -0800 Subject: Optimize `absl::Duration` division and modulo: Allow the compiler to inline `time_internal::IDivDuration`, by splitting the slow path to a separate function. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit With that change, the compiler can inline the fast path. This is specially important in the context of `Duration::operator%=`, because it allows proving that the return value is unused, therefore avoiding expensive multiplies and divides (e.g. `*q = num_hi / den_hi;`). ``` name old cpu/op new cpu/op delta BM_Duration_Modulo 23.1ns ± 0% 22.5ns ± 0% -2.42% (p=0.000 n=20+16) BM_Duration_Modulo_FastPath 7.05ns ± 0% 4.85ns ± 0% -31.17% (p=0.000 n=20+20) name old time/op new time/op delta BM_Duration_Modulo 23.1ns ± 0% 22.6ns ± 0% -2.43% (p=0.000 n=20+16) BM_Duration_Modulo_FastPath 7.06ns ± 0% 4.86ns ± 0% -31.18% (p=0.000 n=20+20) name old INSTRUCTIONS/op new INSTRUCTIONS/op delta BM_Duration_Modulo 188 ± 0% 178 ± 0% -5.32% (p=0.000 n=20+20) BM_Duration_Modulo_FastPath 84.0 ± 0% 62.0 ± 0% -26.19% (p=0.000 n=20+20) name old CYCLES/op new CYCLES/op delta BM_Duration_Modulo 73.8 ± 0% 72.1 ± 0% -2.27% (p=0.000 n=19+20) BM_Duration_Modulo_FastPath 22.5 ± 0% 15.5 ± 0% -31.13% (p=0.000 n=19+20) ``` Note: We don't need to expose `absl::time_internal::IDivDuration` at all given that we have a public `absl::IDivDuration`. PiperOrigin-RevId: 610710635 Change-Id: Ief7c3d5b1c000b397d931e9249edcaef96e7151e --- absl/time/duration.cc | 53 +++++++++++++++++++++------------------- absl/time/duration_benchmark.cc | 20 +++++++++++++++ absl/time/time.h | 54 +++++++++++++++++++---------------------- 3 files changed, 73 insertions(+), 54 deletions(-) (limited to 'absl') diff --git a/absl/time/duration.cc b/absl/time/duration.cc index 13b268c0..4c25dc40 100644 --- a/absl/time/duration.cc +++ b/absl/time/duration.cc @@ -342,19 +342,10 @@ inline bool IDivFastPath(const Duration num, const Duration den, int64_t* q, } // namespace -namespace time_internal { +namespace { -// The 'satq' argument indicates whether the quotient should saturate at the -// bounds of int64_t. If it does saturate, the difference will spill over to -// the remainder. If it does not saturate, the remainder remain accurate, -// but the returned quotient will over/underflow int64_t and should not be used. -int64_t IDivDuration(bool satq, const Duration num, const Duration den, +int64_t IDivSlowPath(bool satq, const Duration num, const Duration den, Duration* rem) { - int64_t q = 0; - if (IDivFastPath(num, den, &q, rem)) { - return q; - } - const bool num_neg = num < ZeroDuration(); const bool den_neg = den < ZeroDuration(); const bool quotient_neg = num_neg != den_neg; @@ -391,7 +382,27 @@ int64_t IDivDuration(bool satq, const Duration num, const Duration den, return -static_cast(Uint128Low64(quotient128 - 1) & kint64max) - 1; } -} // namespace time_internal +// The 'satq' argument indicates whether the quotient should saturate at the +// bounds of int64_t. If it does saturate, the difference will spill over to +// the remainder. If it does not saturate, the remainder remain accurate, +// but the returned quotient will over/underflow int64_t and should not be used. +ABSL_ATTRIBUTE_ALWAYS_INLINE inline int64_t IDivDurationImpl(bool satq, + const Duration num, + const Duration den, + Duration* rem) { + int64_t q = 0; + if (IDivFastPath(num, den, &q, rem)) { + return q; + } + return IDivSlowPath(satq, num, den, rem); +} + +} // namespace + +int64_t IDivDuration(Duration num, Duration den, Duration* rem) { + return IDivDurationImpl(true, num, den, + rem); // trunc towards zero +} // // Additive operators. @@ -475,7 +486,7 @@ Duration& Duration::operator/=(double r) { } Duration& Duration::operator%=(Duration rhs) { - time_internal::IDivDuration(false, *this, rhs, this); + IDivDurationImpl(false, *this, rhs, this); return *this; } @@ -501,9 +512,7 @@ double FDivDuration(Duration num, Duration den) { // Trunc/Floor/Ceil. // -Duration Trunc(Duration d, Duration unit) { - return d - (d % unit); -} +Duration Trunc(Duration d, Duration unit) { return d - (d % unit); } Duration Floor(const Duration d, const Duration unit) { const absl::Duration td = Trunc(d, unit); @@ -591,15 +600,9 @@ double ToDoubleMicroseconds(Duration d) { double ToDoubleMilliseconds(Duration d) { return FDivDuration(d, Milliseconds(1)); } -double ToDoubleSeconds(Duration d) { - return FDivDuration(d, Seconds(1)); -} -double ToDoubleMinutes(Duration d) { - return FDivDuration(d, Minutes(1)); -} -double ToDoubleHours(Duration d) { - return FDivDuration(d, Hours(1)); -} +double ToDoubleSeconds(Duration d) { return FDivDuration(d, Seconds(1)); } +double ToDoubleMinutes(Duration d) { return FDivDuration(d, Minutes(1)); } +double ToDoubleHours(Duration d) { return FDivDuration(d, Hours(1)); } timespec ToTimespec(Duration d) { timespec ts; diff --git a/absl/time/duration_benchmark.cc b/absl/time/duration_benchmark.cc index 56820f37..fdb26bb3 100644 --- a/absl/time/duration_benchmark.cc +++ b/absl/time/duration_benchmark.cc @@ -290,6 +290,26 @@ void BM_Duration_IDivDuration_Hours(benchmark::State& state) { } BENCHMARK(BM_Duration_IDivDuration_Hours); +void BM_Duration_Modulo(benchmark::State& state) { + int i = 0; + while (state.KeepRunning()) { + auto mod = absl::Seconds(i) % absl::Nanoseconds(12345); + benchmark::DoNotOptimize(mod); + ++i; + } +} +BENCHMARK(BM_Duration_Modulo); + +void BM_Duration_Modulo_FastPath(benchmark::State& state) { + int i = 0; + while (state.KeepRunning()) { + auto mod = absl::Seconds(i) % absl::Milliseconds(1); + benchmark::DoNotOptimize(mod); + ++i; + } +} +BENCHMARK(BM_Duration_Modulo_FastPath); + void BM_Duration_ToInt64Nanoseconds(benchmark::State& state) { absl::Duration d = absl::Seconds(100000); while (state.KeepRunning()) { diff --git a/absl/time/time.h b/absl/time/time.h index 37580805..d367ace2 100644 --- a/absl/time/time.h +++ b/absl/time/time.h @@ -98,7 +98,6 @@ class Time; // Defined below class TimeZone; // Defined below namespace time_internal { -int64_t IDivDuration(bool satq, Duration num, Duration den, Duration* rem); ABSL_ATTRIBUTE_CONST_FUNCTION constexpr Time FromUnixDuration(Duration d); ABSL_ATTRIBUTE_CONST_FUNCTION constexpr Duration ToUnixDuration(Time t); ABSL_ATTRIBUTE_CONST_FUNCTION constexpr int64_t GetRepHi(Duration d); @@ -338,30 +337,6 @@ ABSL_ATTRIBUTE_CONST_FUNCTION inline Duration operator-(Duration lhs, return lhs -= rhs; } -// Multiplicative Operators -// Integer operands must be representable as int64_t. -template -ABSL_ATTRIBUTE_CONST_FUNCTION Duration operator*(Duration lhs, T rhs) { - return lhs *= rhs; -} -template -ABSL_ATTRIBUTE_CONST_FUNCTION Duration operator*(T lhs, Duration rhs) { - return rhs *= lhs; -} -template -ABSL_ATTRIBUTE_CONST_FUNCTION Duration operator/(Duration lhs, T rhs) { - return lhs /= rhs; -} -ABSL_ATTRIBUTE_CONST_FUNCTION inline int64_t operator/(Duration lhs, - Duration rhs) { - return time_internal::IDivDuration(true, lhs, rhs, - &lhs); // trunc towards zero -} -ABSL_ATTRIBUTE_CONST_FUNCTION inline Duration operator%(Duration lhs, - Duration rhs) { - return lhs %= rhs; -} - // IDivDuration() // // Divides a numerator `Duration` by a denominator `Duration`, returning the @@ -390,10 +365,7 @@ ABSL_ATTRIBUTE_CONST_FUNCTION inline Duration operator%(Duration lhs, // // Here, q would overflow int64_t, so rem accounts for the difference. // int64_t q = absl::IDivDuration(a, b, &rem); // // q == std::numeric_limits::max(), rem == a - b * q -inline int64_t IDivDuration(Duration num, Duration den, Duration* rem) { - return time_internal::IDivDuration(true, num, den, - rem); // trunc towards zero -} +int64_t IDivDuration(Duration num, Duration den, Duration* rem); // FDivDuration() // @@ -409,6 +381,30 @@ inline int64_t IDivDuration(Duration num, Duration den, Duration* rem) { // // d == 1.5 ABSL_ATTRIBUTE_CONST_FUNCTION double FDivDuration(Duration num, Duration den); +// Multiplicative Operators +// Integer operands must be representable as int64_t. +template +ABSL_ATTRIBUTE_CONST_FUNCTION Duration operator*(Duration lhs, T rhs) { + return lhs *= rhs; +} +template +ABSL_ATTRIBUTE_CONST_FUNCTION Duration operator*(T lhs, Duration rhs) { + return rhs *= lhs; +} +template +ABSL_ATTRIBUTE_CONST_FUNCTION Duration operator/(Duration lhs, T rhs) { + return lhs /= rhs; +} +ABSL_ATTRIBUTE_CONST_FUNCTION inline int64_t operator/(Duration lhs, + Duration rhs) { + return IDivDuration(lhs, rhs, + &lhs); // trunc towards zero +} +ABSL_ATTRIBUTE_CONST_FUNCTION inline Duration operator%(Duration lhs, + Duration rhs) { + return lhs %= rhs; +} + // ZeroDuration() // // Returns a zero-length duration. This function behaves just like the default -- cgit v1.2.3