From 0cc632cdcd156d07b36df666a7f92ecab99b9a08 Mon Sep 17 00:00:00 2001 From: Marcus Holland-Moritz Date: Thu, 23 Jun 2016 19:38:40 -0700 Subject: [PATCH] Fix code for anything-to-string space estimation Summary: When looking at the benchmark for 64-bit integer-to-string conversion, I noticed something strange: =================================================== folly/test/ConvBenchmark.cpp time/iter =================================================== u64ToStringFollyMeasure(12) 26.59ns u64ToStringFollyMeasure(13) 26.89ns u64ToStringFollyMeasure(14) 28.26ns <--- u64ToStringFollyMeasure(15) 52.06ns <--- u64ToStringFollyMeasure(16) 54.44ns u64ToStringFollyMeasure(17) 55.96ns =================================================== There was a sudden, unexpected jump in latency going from 14 digits to 15 digits. Profiling showed that this was due to malloc() and free() calls for the 15 digit benchmark that didn't occur when converting only 14 digit numbers. This was surprising, knowing that fbstrings should be able to store up to 23 digits inline. Even though the code to estimate the number of digits is correct, the code to estimate the space needed within the string was off by 9 bytes. The reason for that is that reserveInTarget() and reserveInTargetDelim() are called with the target string as the last parameter. However, the parameter processing in estimateSpaceToReserve() didn't consider this, and so reserved space for the size of the pointer + 1, which explains the wrap at 15 digits. The fix is to make all overloads of estimateSpaceToReserve() consider the target parameter correctly. The benchmark shows there's no jump in latency with the fix: ============================================================== folly/test/ConvBenchmark.cpp time/iter time/iter ============================================================== preallocateTestNoFloat 590.12ns 599.20ns preallocateTestFloat 580.25ns 581.72ns preallocateTestInt8 116.27ns 119.08ns preallocateTestInt16 130.03ns 131.89ns preallocateTestInt32 156.24ns 154.91ns preallocateTestInt64 210.66ns 207.04ns preallocateTestInt128 4.56us 4.54us preallocateTestNoFloatWithInt128 4.27us 4.26us -------------------------------------------------------------- u64ToStringFollyMeasure(1) 15.49ns 15.19ns u64ToStringFollyMeasure(2) 16.10ns 15.80ns u64ToStringFollyMeasure(3) 17.32ns 17.01ns u64ToStringFollyMeasure(4) 18.53ns 18.23ns u64ToStringFollyMeasure(5) 18.84ns 18.53ns u64ToStringFollyMeasure(6) 20.19ns 19.83ns u64ToStringFollyMeasure(7) 21.42ns 21.11ns u64ToStringFollyMeasure(8) 22.48ns 22.33ns u64ToStringFollyMeasure(9) 22.94ns 22.63ns u64ToStringFollyMeasure(10) 24.12ns 23.82ns u64ToStringFollyMeasure(11) 25.53ns 25.25ns u64ToStringFollyMeasure(12) 26.59ns 26.36ns u64ToStringFollyMeasure(13) 26.89ns 26.67ns u64ToStringFollyMeasure(14) 28.26ns 28.01ns u64ToStringFollyMeasure(15) 52.06ns 29.44ns u64ToStringFollyMeasure(16) 54.44ns 31.05ns u64ToStringFollyMeasure(17) 55.96ns 34.64ns u64ToStringFollyMeasure(18) 57.69ns 35.10ns u64ToStringFollyMeasure(19) 59.45ns 36.46ns u64ToStringFollyMeasure(20) 60.91ns 38.17ns ============================================================== Reviewed By: meyering Differential Revision: D3455825 fbshipit-source-id: 0146cbfc0105f0d709b64bcf1ed297c4e27d1129 --- folly/Conv.h | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) diff --git a/folly/Conv.h b/folly/Conv.h index 6103849a..08628a0e 100644 --- a/folly/Conv.h +++ b/folly/Conv.h @@ -719,7 +719,9 @@ estimateSpaceNeeded(const Src&) { namespace detail { -inline size_t estimateSpaceToReserve(size_t sofar) { +template +typename std::enable_if::value, size_t>::type +estimateSpaceToReserve(size_t sofar, Tgt*) { return sofar; } @@ -728,11 +730,6 @@ 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(estimateSpaceToReserve(0, vs...)); @@ -741,7 +738,8 @@ void reserveInTarget(const Ts&...vs) { template void reserveInTargetDelim(const Delimiter& d, const Ts&...vs) { static_assert(sizeof...(vs) >= 2, "Needs at least 2 args"); - size_t fordelim = (sizeof...(vs) - 2) * estimateSpaceToReserve(0, d); + size_t fordelim = (sizeof...(vs) - 2) * + estimateSpaceToReserve(0, d, static_cast(nullptr)); getLastElement(vs...)->reserve(estimateSpaceToReserve(fordelim, vs...)); } -- 2.34.1