From b6a8eb2e3e7dae0c48cf1ace5299bc777b2753cd Mon Sep 17 00:00:00 2001 From: Marcin Pawlowski Date: Tue, 15 Jul 2014 15:30:57 -0700 Subject: [PATCH] reserve capacity in toAppend(...) Summary: I modified the toAppend(args..., StringType* dest) so that before appending it reserves enough space for data to be appended. It is still work in progress (floats and doubles are really bad: we only do very naive approximation of the size). On float like workload we gain ~10% perf, on strings/ints/chars we gain as much as 25% of perf. Probably on bigger strings it will be even faster. We only modify the case when toAppend() has more than 1 element to append as it would be just overhead in case of one argument. Test Plan: with this change: ============================================================================ folly/test/ConvTest.cpp relative time/iter iters/s ============================================================================ preallocateTestNoFloat 1.59us 627.85K preallocateTestFloat 1.09us 920.70K ---------------------------------------------------------------------------- ============================================================================ without the change: ============================================================================ folly/test/ConvTest.cpp relative time/iter iters/s ============================================================================ preallocateTestNoFloat 2.12us 471.43K preallocateTestFloat 1.22us 818.25K ---------------------------------------------------------------------------- ============================================================================ Reviewed By: marcelo.juchem@fb.com FB internal diff: D1420588 Tasks: 4632421 --- folly/Conv.h | 219 +++++++++++++++++++++++++++++++++++++++- folly/test/ConvTest.cpp | 27 +++++ 2 files changed, 242 insertions(+), 4 deletions(-) diff --git a/folly/Conv.h b/folly/Conv.h index 79397262..83b36be8 100644 --- a/folly/Conv.h +++ b/folly/Conv.h @@ -241,6 +241,14 @@ void toAppend(char value, Tgt * result) { *result += value; } +template +constexpr typename std::enable_if< + std::is_same::value, + size_t>::type +estimateSpaceNeeded(T) { + return 1; +} + /** * Ubiquitous helper template for writing string appenders */ @@ -265,6 +273,37 @@ toAppend(Src value, Tgt * result) { } } +template +typename std::enable_if< + std::is_convertible::value, + size_t>::type +estimateSpaceNeeded(Src value) { + const char *c = value; + if (c) { + return folly::StringPiece(value).size(); + }; + return 0; +} + +template +typename std::enable_if< + (std::is_convertible::value || + IsSomeString::value) && + !std::is_convertible::value, + size_t>::type +estimateSpaceNeeded(Src value) { + return folly::StringPiece(value).size(); +} + +template +typename std::enable_if< + std::is_pointer::value && + IsSomeString>::value, + size_t>::type +estimateSpaceNeeded(Src value) { + return value->size(); +} + /** * Strings get appended, too. */ @@ -329,6 +368,22 @@ toAppend(unsigned __int128 value, Tgt * result) { result->append(buffer + p, buffer + sizeof(buffer)); } +template +constexpr typename std::enable_if< + std::is_same::value, + size_t>::type +estimateSpaceNeeded(T) { + return detail::digitsEnough<__int128>(); +} + +template +constexpr typename std::enable_if< + std::is_same::value, + size_t>::type +estimateSpaceNeeded(T) { + return detail::digitsEnough(); +} + #endif /** @@ -353,6 +408,19 @@ toAppend(Src value, Tgt * result) { } } +template +typename std::enable_if< + std::is_integral::value && std::is_signed::value + && sizeof(Src) >= 4 && sizeof(Src) < 16, + size_t>::type +estimateSpaceNeeded(Src value) { + if (value < 0) { + return 1 + digits10(static_cast(-value)); + } + + return digits10(static_cast(value)); +} + /** * As above, but for uint32_t and uint64_t. */ @@ -365,6 +433,15 @@ toAppend(Src value, Tgt * result) { result->append(buffer, buffer + uint64ToBufferUnsafe(value, buffer)); } +template +typename std::enable_if< + std::is_integral::value && !std::is_signed::value + && sizeof(Src) >= 4 && sizeof(Src) < 16, + size_t>::type +estimateSpaceNeeded(Src value) { + return digits10(value); +} + /** * All small signed and unsigned integers to string go through 32-bit * types int32_t and uint32_t, respectively. @@ -380,6 +457,19 @@ toAppend(Src value, Tgt * result) { toAppend(static_cast(value), result); } +template +typename std::enable_if< + std::is_integral::value + && sizeof(Src) < 4 + && !std::is_same::value, + size_t>::type +estimateSpaceNeeded(Src value) { + typedef typename + std::conditional::value, int64_t, uint64_t>::type + Intermediate; + return estimateSpaceNeeded(static_cast(value)); +} + #if defined(__clang__) || __GNUC_PREREQ(4, 7) // std::underlying_type became available by gcc 4.7.0 @@ -394,6 +484,14 @@ toAppend(Src value, Tgt * result) { static_cast::type>(value), result); } +template +typename std::enable_if< + std::is_enum::value, size_t>::type +estimateSpaceNeeded(Src value) { + return estimateSpaceNeeded( + static_cast::type>(value)); +} + #else /** @@ -418,6 +516,25 @@ toAppend(Src value, Tgt * result) { } } +template +typename std::enable_if< + std::is_enum::value, size_t>::type +estimateSpaceNeeded(Src value) { + /* static */ if (Src(-1) < 0) { + /* static */ if (sizeof(Src) <= sizeof(int)) { + return estimateSpaceNeeded(static_cast(value)); + } else { + return estimateSpaceNeeded(static_cast(value)); + } + } else { + /* static */ if (sizeof(Src) <= sizeof(int)) { + return estimateSpaceNeeded(static_cast(value)); + } else { + return estimateSpaceNeeded(static_cast(value)); + } + } +} + #endif // gcc 4.7 onwards /******************************************************************************* @@ -474,17 +591,111 @@ toAppend(Src value, Tgt * result) { } /** - * Variadic conversion to string. Appends each element in turn. + * Very primitive, lets say its our best effort + */ +template +typename std::enable_if< + std::is_floating_point::value, size_t>::type +estimateSpaceNeeded(Src value) { + size_t sofar = 0; + if (value < 0) { + ++sofar; + value = -value; + } + + if (value < 1) { + return sofar + 10; // lets assume 0 + '.' + 8 precision digits + } + + if (value < static_cast(std::numeric_limits::max())) { + sofar += digits10(static_cast(value)); + } else { + return 64; // give up, it will be more than 23 anyway + } + + return sofar + 10; // integral part + '.' + 8 precision digits +} + +/** + * This can be specialized, together with adding specialization + * for estimateSpaceNeed for your type, so that we allocate + * as much as you need instead of the default + */ +template +struct HasLengthEstimator : std::false_type {}; + +template +constexpr typename std::enable_if< + !std::is_fundamental::value + && !IsSomeString::value + && !std::is_convertible::value + && !std::is_convertible::value + && !std::is_enum::value + && !HasLengthEstimator::value, + size_t>::type +estimateSpaceNeeded(const Src&) { + return sizeof(Src) + 1; // dumbest best effort ever? +} + +namespace detail { + +inline size_t estimateSpaceToReserve(size_t sofar) { + return sofar; +} + +template +size_t estimateSpaceToReserve(size_t sofar, const T& v, const Ts&... vs) { + return estimateSpaceToReserve(sofar + estimateSpaceNeeded(v), vs...); +} + +template +size_t estimateSpaceToReserve(size_t sofar, const T& v) { + return sofar + estimateSpaceNeeded(v); +} + +template +void reserveInTarget(const Ts&...vs) { + getLastElement(vs...)->reserve(detail::estimateSpaceToReserve(0, vs...)); +} + +/** + * Variadic base case: append one element */ +template +typename std::enable_if< + IsSomeString::type> + ::value>::type +toAppendStrImpl(const T& v, Tgt result) { + toAppend(v, result); +} + template typename std::enable_if= 2 && IsSomeString< typename std::remove_pointer< typename detail::last_element::type >::type>::value>::type -toAppend(const T& v, const Ts&... vs) { - toAppend(v, detail::getLastElement(vs...)); - toAppend(vs...); +toAppendStrImpl(const T& v, const Ts&... vs) { + toAppend(v, getLastElement(vs...)); + toAppendStrImpl(vs...); +} +} // folly::detail + + +/** + * Variadic conversion to string. Appends each element in turn. + * If we have two or more things to append, we will reserve + * the space for them (at least we will try). + */ +template +typename std::enable_if= 3 + && IsSomeString< + typename std::remove_pointer< + typename detail::last_element::type + >::type>::value>::type +toAppend(const Ts&... vs) { + detail::reserveInTarget(vs...); + detail::toAppendStrImpl(vs...); } /** diff --git a/folly/test/ConvTest.cpp b/folly/test/ConvTest.cpp index e0416c35..ffe7934e 100644 --- a/folly/test/ConvTest.cpp +++ b/folly/test/ConvTest.cpp @@ -958,6 +958,33 @@ struct StringVariadicToBM { } }; +static size_t bigInt = 11424545345345; +static size_t smallInt = 104; +static char someString[] = "this is some nice string"; +static char otherString[] = "this is a long string, so it's not so nice"; +static char reallyShort[] = "meh"; +static std::string stdString = "std::strings are very nice"; +static float fValue = 1.2355; +static double dValue = 345345345.435; + +BENCHMARK(preallocateTestNoFloat, n) { + for (int i=0; i < n; ++i) { + auto val1 = to(bigInt, someString, stdString, otherString); + auto val3 = to(reallyShort, smallInt); + auto val2 = to(bigInt, stdString); + auto val4 = to(bigInt, stdString, dValue, otherString); + auto val5 = to(bigInt, someString, reallyShort); + } +} + +BENCHMARK(preallocateTestFloat, n) { + for (int i=0; i < n; ++i) { + auto val1 = to(stdString, ',', fValue, dValue); + auto val2 = to(stdString, ',', dValue); + } +} +BENCHMARK_DRAW_LINE(); + static const StringIdenticalToBM stringIdenticalToBM; static const StringVariadicToBM stringVariadicToBM; static const StringIdenticalToBM fbstringIdenticalToBM; -- 2.34.1