From 6d7c6d55f0f4b7b75607608ef9037db58083368f Mon Sep 17 00:00:00 2001 From: Yedidya Feldblum Date: Wed, 30 Aug 2017 19:26:32 -0700 Subject: [PATCH] Extract non-portability constexpr math functions to new header Summary: [Folly] Extract non-portability `constexpr` math functions to new header. This new header, `folly/ConstexprMath.h`, is specifically for compile-time-computable math functions. We start with `min`, `max`, `abs`, and `log2`. Included substantive changes: * Add new tests for `constexpr_strlen`, which remains in the portability header. * Make `constexpr_min` and `constexpr_max` variadic. * Make `constexpr_log2` tail-recursive, remove `const_log2` in `FixedString.h`, and move the related comment. Reviewed By: Orvid Differential Revision: D5739715 fbshipit-source-id: 29d3cc846ce98bb4bdddcc8b0fa80e4d32075fe0 --- folly/ConstexprMath.h | 102 +++++++++++++++++++++++ folly/FixedString.h | 22 +++-- folly/Format.cpp | 2 +- folly/Makefile.am | 1 + folly/fibers/FiberManager.cpp | 1 + folly/portability/Constexpr.h | 64 -------------- folly/portability/test/ConstexprTest.cpp | 80 +++--------------- folly/small_vector.h | 2 +- folly/test/ConstexprMathTest.cpp | 94 +++++++++++++++++++++ folly/test/Makefile.am | 4 + 10 files changed, 226 insertions(+), 146 deletions(-) create mode 100644 folly/ConstexprMath.h create mode 100644 folly/test/ConstexprMathTest.cpp diff --git a/folly/ConstexprMath.h b/folly/ConstexprMath.h new file mode 100644 index 00000000..1650c02c --- /dev/null +++ b/folly/ConstexprMath.h @@ -0,0 +1,102 @@ +/* + * Copyright 2017 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#include + +namespace folly { + +// TLDR: Prefer using operator< for ordering. And when +// a and b are equivalent objects, we return b to make +// sorting stable. +// See http://stepanovpapers.com/notes.pdf for details. +template +constexpr T constexpr_max(T a) { + return a; +} +template +constexpr T constexpr_max(T a, T b, Ts... ts) { + return b < a ? constexpr_max(a, ts...) : constexpr_max(b, ts...); +} + +// When a and b are equivalent objects, we return a to +// make sorting stable. +template +constexpr T constexpr_min(T a) { + return a; +} +template +constexpr T constexpr_min(T a, T b, Ts... ts) { + return b < a ? constexpr_max(b, ts...) : constexpr_max(a, ts...); +} + +namespace detail { + +template +struct constexpr_abs_helper {}; + +template +struct constexpr_abs_helper< + T, + typename std::enable_if::value>::type> { + static constexpr T go(T t) { + return t < static_cast(0) ? -t : t; + } +}; + +template +struct constexpr_abs_helper< + T, + typename std::enable_if< + std::is_integral::value && !std::is_same::value && + std::is_unsigned::value>::type> { + static constexpr T go(T t) { + return t; + } +}; + +template +struct constexpr_abs_helper< + T, + typename std::enable_if< + std::is_integral::value && !std::is_same::value && + std::is_signed::value>::type> { + static constexpr typename std::make_unsigned::type go(T t) { + return typename std::make_unsigned::type(t < static_cast(0) ? -t : t); + } +}; +} // namespace detail + +template +constexpr auto constexpr_abs(T t) + -> decltype(detail::constexpr_abs_helper::go(t)) { + return detail::constexpr_abs_helper::go(t); +} + +namespace detail { +template +constexpr T constexpr_log2(T a, T e) { + return e == T(1) ? a : constexpr_log2(a + T(1), e / T(2)); +} +} // namespace detail + +template +constexpr T constexpr_log2(T t) { + return detail::constexpr_log2(T(0), t); +} + +} // namespace folly diff --git a/folly/FixedString.h b/folly/FixedString.h index 8964a4b1..1465070c 100644 --- a/folly/FixedString.h +++ b/folly/FixedString.h @@ -28,6 +28,7 @@ #include #include +#include #include #include #include @@ -314,18 +315,6 @@ FOLLY_CPP14_CONSTEXPR void constexpr_swap(T& a, T& b) noexcept( b = std::move(tmp); } -// FUTURE: use const_log2 to fold instantiations of BasicFixedString together. -// All BasicFixedString instantiations could share the implementation -// of BasicFixedString, where M is the next highest power of 2 after N. -// -// Also, because of alignment of the data_ and size_ members, N should never be -// smaller than `(alignof(std::size_t)/sizeof(C))-1` (-1 because of the null -// terminator). OR, create a specialization for BasicFixedString that -// does not have a size_ member, since it is unnecessary. -constexpr std::size_t const_log2(std::size_t N, std::size_t log2 = 0u) { - return N / 2u == 0u ? log2 : const_log2(N / 2u, log2 + 1u); -} - // For constexpr reverse iteration over a BasicFixedString template struct ReverseIterator { @@ -528,6 +517,15 @@ class BasicFixedString : private detail::fixedstring::FixedStringBase { friend class BasicFixedString; friend struct detail::fixedstring::Helper; + // FUTURE: use constexpr_log2 to fold instantiations of BasicFixedString + // together. All BasicFixedString instantiations could share the + // implementation of BasicFixedString, where M is the next highest power + // of 2 after N. + // + // Also, because of alignment of the data_ and size_ members, N should never + // be smaller than `(alignof(std::size_t)/sizeof(C))-1` (-1 because of the + // null terminator). OR, create a specialization for BasicFixedString + // that does not have a size_ member, since it is unnecessary. Char data_[N + 1u]; // +1 for the null terminator std::size_t size_; // Nbr of chars, not incl. null terminator. size_ <= N. diff --git a/folly/Format.cpp b/folly/Format.cpp index 9a711e46..bbcd2d00 100644 --- a/folly/Format.cpp +++ b/folly/Format.cpp @@ -16,8 +16,8 @@ #include +#include #include -#include #include diff --git a/folly/Makefile.am b/folly/Makefile.am index e42b0eaf..442c1e1c 100644 --- a/folly/Makefile.am +++ b/folly/Makefile.am @@ -60,6 +60,7 @@ nobase_follyinclude_HEADERS = \ concurrency/ConcurrentHashMap.h \ concurrency/CoreCachedSharedPtr.h \ concurrency/detail/ConcurrentHashMap-detail.h \ + ConstexprMath.h \ detail/AtomicHashUtils.h \ detail/AtomicUnorderedMapUtils.h \ detail/AtomicUtils.h \ diff --git a/folly/fibers/FiberManager.cpp b/folly/fibers/FiberManager.cpp index 9a3d2446..9155078c 100644 --- a/folly/fibers/FiberManager.cpp +++ b/folly/fibers/FiberManager.cpp @@ -25,6 +25,7 @@ #include #include +#include #include #include #include diff --git a/folly/portability/Constexpr.h b/folly/portability/Constexpr.h index a7620918..64005e3c 100644 --- a/folly/portability/Constexpr.h +++ b/folly/portability/Constexpr.h @@ -22,70 +22,6 @@ namespace folly { -// TLDR: Prefer using operator< for ordering. And when -// a and b are equivalent objects, we return b to make -// sorting stable. -// See http://stepanovpapers.com/notes.pdf for details. -template -constexpr T constexpr_max(T a, T b) { - return b < a ? a : b; -} - -// When a and b are equivalent objects, we return a to -// make sorting stable. -template -constexpr T constexpr_min(T a, T b) { - return b < a ? b : a; -} - -namespace detail { - -template -struct constexpr_abs_helper {}; - -template -struct constexpr_abs_helper< - T, - typename std::enable_if::value>::type> { - static constexpr T go(T t) { - return t < static_cast(0) ? -t : t; - } -}; - -template -struct constexpr_abs_helper< - T, - typename std::enable_if< - std::is_integral::value && !std::is_same::value && - std::is_unsigned::value>::type> { - static constexpr T go(T t) { - return t; - } -}; - -template -struct constexpr_abs_helper< - T, - typename std::enable_if< - std::is_integral::value && !std::is_same::value && - std::is_signed::value>::type> { - static constexpr typename std::make_unsigned::type go(T t) { - return typename std::make_unsigned::type(t < static_cast(0) ? -t : t); - } -}; -} // namespace detail - -template -constexpr auto constexpr_abs(T t) - -> decltype(detail::constexpr_abs_helper::go(t)) { - return detail::constexpr_abs_helper::go(t); -} - -template -constexpr T constexpr_log2(T t) { - return t == T(1) ? T(0) : T(1) + constexpr_log2(t / T(2)); -} - namespace detail { template diff --git a/folly/portability/test/ConstexprTest.cpp b/folly/portability/test/ConstexprTest.cpp index d2f6dbe3..2891d797 100644 --- a/folly/portability/test/ConstexprTest.cpp +++ b/folly/portability/test/ConstexprTest.cpp @@ -23,72 +23,16 @@ namespace { class ConstexprTest : public testing::Test {}; } -TEST_F(ConstexprTest, constexpr_abs_unsigned) { - constexpr auto v = uint32_t(17); - constexpr auto a = folly::constexpr_abs(v); - EXPECT_EQ(17, a); - EXPECT_TRUE((std::is_same::value)); -} - -TEST_F(ConstexprTest, constexpr_abs_signed_positive) { - constexpr auto v = int32_t(17); - constexpr auto a = folly::constexpr_abs(v); - EXPECT_EQ(17, a); - EXPECT_TRUE((std::is_same::value)); -} - -TEST_F(ConstexprTest, constexpr_abs_signed_negative) { - constexpr auto v = int32_t(-17); - constexpr auto a = folly::constexpr_abs(v); - EXPECT_EQ(17, a); - EXPECT_TRUE((std::is_same::value)); -} - -TEST_F(ConstexprTest, constexpr_abs_float_positive) { - constexpr auto v = 17.5f; - constexpr auto a = folly::constexpr_abs(v); - EXPECT_EQ(17.5, a); - EXPECT_TRUE((std::is_same::value)); -} - -TEST_F(ConstexprTest, constexpr_abs_float_negative) { - constexpr auto v = -17.5f; - constexpr auto a = folly::constexpr_abs(v); - EXPECT_EQ(17.5, a); - EXPECT_TRUE((std::is_same::value)); -} - -TEST_F(ConstexprTest, constexpr_abs_double_positive) { - constexpr auto v = 17.5; - constexpr auto a = folly::constexpr_abs(v); - EXPECT_EQ(17.5, a); - EXPECT_TRUE((std::is_same::value)); -} - -TEST_F(ConstexprTest, constexpr_abs_double_negative) { - constexpr auto v = -17.5; - constexpr auto a = folly::constexpr_abs(v); - EXPECT_EQ(17.5, a); - EXPECT_TRUE((std::is_same::value)); -} - -TEST_F(ConstexprTest, constexpr_log2_1) { - constexpr auto v = 1ull; - constexpr auto a = folly::constexpr_log2(v); - EXPECT_EQ(0ull, a); - EXPECT_TRUE((std::is_same::value)); -} - -TEST_F(ConstexprTest, constexpr_log2_2) { - constexpr auto v = 2ull; - constexpr auto a = folly::constexpr_log2(v); - EXPECT_EQ(1ull, a); - EXPECT_TRUE((std::is_same::value)); -} - -TEST_F(ConstexprTest, constexpr_log2_64) { - constexpr auto v = 64ull; - constexpr auto a = folly::constexpr_log2(v); - EXPECT_EQ(6ull, a); - EXPECT_TRUE((std::is_same::value)); +TEST_F(ConstexprTest, constexpr_strlen_cstr) { + constexpr auto v = "hello"; + constexpr auto a = folly::constexpr_strlen(v); + EXPECT_EQ(5, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprTest, constexpr_strlen_ints) { + constexpr int v[] = {5, 3, 4, 0, 7}; + constexpr auto a = folly::constexpr_strlen(v); + EXPECT_EQ(3, a); + EXPECT_TRUE((std::is_same::value)); } diff --git a/folly/small_vector.h b/folly/small_vector.h index 64add098..f70b2a8f 100644 --- a/folly/small_vector.h +++ b/folly/small_vector.h @@ -44,13 +44,13 @@ #include #include +#include #include #include #include #include #include #include -#include #include #include diff --git a/folly/test/ConstexprMathTest.cpp b/folly/test/ConstexprMathTest.cpp new file mode 100644 index 00000000..166175a3 --- /dev/null +++ b/folly/test/ConstexprMathTest.cpp @@ -0,0 +1,94 @@ +/* + * Copyright 2017 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include + +#include + +namespace { + +class ConstexprMathTest : public testing::Test {}; +} + +TEST_F(ConstexprMathTest, constexpr_abs_unsigned) { + constexpr auto v = uint32_t(17); + constexpr auto a = folly::constexpr_abs(v); + EXPECT_EQ(17, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprMathTest, constexpr_abs_signed_positive) { + constexpr auto v = int32_t(17); + constexpr auto a = folly::constexpr_abs(v); + EXPECT_EQ(17, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprMathTest, constexpr_abs_signed_negative) { + constexpr auto v = int32_t(-17); + constexpr auto a = folly::constexpr_abs(v); + EXPECT_EQ(17, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprMathTest, constexpr_abs_float_positive) { + constexpr auto v = 17.5f; + constexpr auto a = folly::constexpr_abs(v); + EXPECT_EQ(17.5, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprMathTest, constexpr_abs_float_negative) { + constexpr auto v = -17.5f; + constexpr auto a = folly::constexpr_abs(v); + EXPECT_EQ(17.5, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprMathTest, constexpr_abs_double_positive) { + constexpr auto v = 17.5; + constexpr auto a = folly::constexpr_abs(v); + EXPECT_EQ(17.5, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprMathTest, constexpr_abs_double_negative) { + constexpr auto v = -17.5; + constexpr auto a = folly::constexpr_abs(v); + EXPECT_EQ(17.5, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprMathTest, constexpr_log2_1) { + constexpr auto v = 1ull; + constexpr auto a = folly::constexpr_log2(v); + EXPECT_EQ(0ull, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprMathTest, constexpr_log2_2) { + constexpr auto v = 2ull; + constexpr auto a = folly::constexpr_log2(v); + EXPECT_EQ(1ull, a); + EXPECT_TRUE((std::is_same::value)); +} + +TEST_F(ConstexprMathTest, constexpr_log2_64) { + constexpr auto v = 64ull; + constexpr auto a = folly::constexpr_log2(v); + EXPECT_EQ(6ull, a); + EXPECT_TRUE((std::is_same::value)); +} diff --git a/folly/test/Makefile.am b/folly/test/Makefile.am index ed0fd977..f0ca1460 100644 --- a/folly/test/Makefile.am +++ b/folly/test/Makefile.am @@ -49,6 +49,10 @@ array_test_SOURCES = ArrayTest.cpp array_test_LDADD = libfollytestmain.la TESTS += array_test +constexpr_math_test_SOURCES = ConstexprMathTest.cpp +constexpr_math_test_LDADD = libfollytestmain.la +TESTS += constexpr_math_test + if RUN_ARCH_SPECIFIC_TESTS small_locks_test_SOURCES = SmallLocksTest.cpp small_locks_test_LDADD = libfollytestmain.la -- 2.34.1