numeric/str: Improve base10 encode performance
This adds a generic mechanism for coalescing writes into multi-digit
chunks in order to reduce the number of division operations that
bottleneck the encoding process.
Change-Id: Iaf0967b2a44820c75cad73390b81a6a53d97b27a
Signed-off-by: William A. Kennington III <wak@google.com>
diff --git a/include/stdplus/numeric/str.hpp b/include/stdplus/numeric/str.hpp
index ee80905..fa5ba86 100644
--- a/include/stdplus/numeric/str.hpp
+++ b/include/stdplus/numeric/str.hpp
@@ -16,6 +16,16 @@
namespace detail
{
+template <typename T>
+constexpr auto pow(T t, uint8_t n) noexcept
+{
+ if (n == 0)
+ {
+ return T{1};
+ }
+ return t * pow(t, n - 1);
+}
+
inline constexpr auto maxBase = 36;
inline constexpr auto singleIntTable = []() {
@@ -32,27 +42,74 @@
return ret;
}();
+template <uint8_t size, uint8_t base>
+inline constexpr auto multiIntTable = []() {
+ static_assert(size > 1);
+ static_assert(base <= maxBase);
+ std::array<char, pow<size_t>(base, size) * size> ret;
+ for (size_t i = 0; i < pow<size_t>(base, size); ++i)
+ {
+ for (size_t j = 0; j < size; ++j)
+ {
+ ret[i * size + j] = singleIntTable[i / pow<size_t>(base, j) % base];
+ }
+ }
+ return ret;
+}();
+
+template <uint8_t size, uint8_t base>
+constexpr void intStrWrite(auto str, auto v) noexcept
+{
+ if constexpr (size > 1)
+ {
+ auto it = &detail::multiIntTable<size, base>[v * size];
+ std::copy(it, it + size, str);
+ }
+ else
+ {
+ *str = detail::singleIntTable[v];
+ }
+}
+
+inline constexpr auto multiIntSupport = []() {
+ std::array<uint8_t, maxBase> ret;
+ std::fill(ret.begin(), ret.end(), 1);
+ // Decimals are common enough and have slow division
+ ret[10] = 2;
+ return ret;
+}();
+
template <uint8_t base, typename T, typename CharT>
constexpr CharT* uintToStr(CharT* buf, T v, uint8_t min_width) noexcept
{
static_assert(std::is_unsigned_v<T>);
uint8_t i = 0;
+ constexpr auto multi = detail::multiIntSupport[base];
do
{
+ constexpr auto div = detail::pow<size_t>(base, multi);
if constexpr (std::popcount(base) == 1)
{
- constexpr auto shift = std::countr_zero(base);
+ constexpr auto shift = std::countr_zero(div);
constexpr auto mask = (1 << shift) - 1;
- buf[i] = detail::singleIntTable[v & mask];
+ intStrWrite<multi, base>(buf + i, v & mask);
v >>= shift;
}
else
{
- buf[i] = detail::singleIntTable[v % base];
- v /= base;
+ intStrWrite<multi, base>(buf + i, v % div);
+ v /= div;
}
- i += 1;
+ i += multi;
} while (v > 0);
+ if constexpr (multi > 1)
+ {
+ const auto width = std::max<uint8_t>(min_width, 1);
+ while (i > width && buf[i - 1] == '0')
+ {
+ --i;
+ }
+ }
auto end = buf + std::max(i, min_width);
std::fill(buf + i, end, '0');
std::reverse(buf, end);
@@ -87,7 +144,9 @@
{
v /= base;
}
- return i + std::is_signed_v<T>;
+ // Normalize to support multi-int
+ auto div = detail::multiIntSupport[base];
+ return (i + div - 1) / div * div + std::is_signed_v<T>;
}();
template <typename CharT>
diff --git a/test/numeric/str.cpp b/test/numeric/str.cpp
index 5646045..008cbe5 100644
--- a/test/numeric/str.cpp
+++ b/test/numeric/str.cpp
@@ -10,7 +10,7 @@
TEST(IntToStr, Uint8_10)
{
IntToStr<10, uint8_t> enc;
- static_assert(enc.buf_size == 3);
+ static_assert(enc.buf_size == 4);
char buf[enc.buf_size];
EXPECT_EQ("0", std::string_view(buf, enc(buf, 0)));
EXPECT_EQ("42", std::string_view(buf, enc(buf, 42)));
@@ -22,7 +22,7 @@
TEST(IntToStr, Int8_10)
{
IntToStr<10, int8_t> enc;
- static_assert(enc.buf_size == 4);
+ static_assert(enc.buf_size == 5);
char buf[enc.buf_size];
EXPECT_EQ("42", std::string_view(buf, enc(buf, 42)));
EXPECT_EQ("-127", std::string_view(buf, enc(buf, -127)));
@@ -31,7 +31,7 @@
TEST(IntToStr, Uint16_10)
{
IntToStr<10, uint16_t> enc;
- static_assert(enc.buf_size == 5);
+ static_assert(enc.buf_size == 6);
char buf[enc.buf_size];
EXPECT_EQ("55255", std::string_view(buf, enc(buf, 55255, 3)));
}