You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2020/08/13 14:03:45 UTC
[GitHub] [arrow] pitrou commented on a change in pull request #7945: ARROW-9710: [C++] Improve performance of Decimal128::ToString by 10x, and make the implementation reusable for Decimal256.
pitrou commented on a change in pull request #7945:
URL: https://github.com/apache/arrow/pull/7945#discussion_r469967040
##########
File path: cpp/src/arrow/util/decimal.cc
##########
@@ -241,64 +284,43 @@ Decimal128::operator int64_t() const {
return static_cast<int64_t>(low_bits());
}
-static std::string ToStringNegativeScale(const std::string& str,
- int32_t adjusted_exponent, bool is_negative) {
- std::stringstream buf;
-
- size_t offset = 0;
- buf << str[offset++];
-
- if (is_negative) {
- buf << str[offset++];
- }
-
- buf << '.' << str.substr(offset, std::string::npos) << 'E' << std::showpos
- << adjusted_exponent;
- return buf.str();
-}
-
-std::string Decimal128::ToString(int32_t scale) const {
- const std::string str(ToIntegerString());
-
+static void AdjustIntegerStringWithScale(int32_t scale, std::string* str) {
if (scale == 0) {
- return str;
+ return;
}
- const bool is_negative = *this < 0;
-
- const auto len = static_cast<int32_t>(str.size());
+ const bool is_negative = str->front() == '-';
const auto is_negative_offset = static_cast<int32_t>(is_negative);
- const int32_t adjusted_exponent = -scale + (len - 1 - is_negative_offset);
+ const auto len = static_cast<int32_t>(str->size());
+ const int32_t num_digits = len - is_negative_offset;
+ const int32_t adjusted_exponent = num_digits - 1 - scale;
/// Note that the -6 is taken from the Java BigDecimal documentation.
if (scale < 0 || adjusted_exponent < -6) {
- return ToStringNegativeScale(str, adjusted_exponent, is_negative);
+ str->insert(str->begin() + 1 + is_negative_offset, '.');
+ str->push_back('E');
+ // Use stringstream only for printing the exponent integer. It should be short
+ // enough to avoid memory allocations.
+ std::stringstream buf;
+ buf << std::showpos << adjusted_exponent;
+ *str += buf.str();
+ return;
}
- if (is_negative) {
- if (len - 1 > scale) {
- const auto n = static_cast<size_t>(len - scale);
- return str.substr(0, n) + "." + str.substr(n, static_cast<size_t>(scale));
- }
-
- if (len - 1 == scale) {
- return "-0." + str.substr(1, std::string::npos);
- }
-
- std::string result("-0." + std::string(static_cast<size_t>(scale - len + 1), '0'));
- return result + str.substr(1, std::string::npos);
- }
-
- if (len > scale) {
+ if (num_digits > scale) {
const auto n = static_cast<size_t>(len - scale);
- return str.substr(0, n) + "." + str.substr(n, static_cast<size_t>(scale));
+ str->insert(str->begin() + n, '.');
+ return;
}
- if (len == scale) {
- return "0." + str;
- }
+ str->insert(is_negative_offset, scale - num_digits + 2, '0');
Review comment:
Same: can you explain what happens here?
##########
File path: cpp/src/arrow/util/decimal.cc
##########
@@ -195,42 +191,89 @@ double Decimal128::ToDouble(int32_t scale) const {
return DecimalDoubleConversion::ToReal(*this, scale);
}
-std::string Decimal128::ToIntegerString() const {
- Decimal128 remainder;
- std::stringstream buf;
- bool need_fill = false;
-
- // get anything above 10 ** 36 and print it
- Decimal128 top;
- std::tie(top, remainder) = Divide(kTenTo36).ValueOrDie();
-
- if (top != 0) {
- buf << static_cast<int64_t>(top);
- remainder.Abs();
- need_fill = true;
+template <size_t n>
+static void AppendLittleEndianArrayToString(const std::array<uint64_t, n>& array,
+ std::string* result) {
+ static_assert(n > 0, "Array size must be positive");
+ size_t most_significant_elem_idx = n - 1;
+ while (array[most_significant_elem_idx] == 0) {
+ if (most_significant_elem_idx == 0) {
+ result->push_back('0');
+ return;
+ }
+ --most_significant_elem_idx;
+ }
+
+ std::array<uint64_t, n> copy = array;
+ constexpr uint32_t k1e9 = 1000000000U;
+ constexpr size_t num_bits = n * 64;
+ // Each segment holds at most 9 decimal digits.
+ // The number of segments needed = ceil(num_bits * log(2) / log(1e9))
+ // = ceil(num_bits / 29.897352854) <= ceil(num_bits / 29).
+ std::array<uint32_t, (num_bits + 28) / 29> segments;
+ size_t num_segments = 0;
+ uint64_t* most_significant_elem = ©[most_significant_elem_idx];
+ do {
+ // Compute remainder = copy % 1e9 and copy = copy / 1e9.
+ uint32_t remainder = 0;
+ uint64_t* elem = most_significant_elem;
+ do {
+ uint32_t hi = static_cast<uint32_t>(*elem >> 32);
+ uint32_t lo = static_cast<uint32_t>(*elem & ~uint32_t{0});
+ uint64_t dividend_hi = (static_cast<uint64_t>(remainder) << 32) | hi;
+ uint64_t quotient_hi = dividend_hi / k1e9;
+ remainder = static_cast<uint32_t>(dividend_hi % k1e9);
+ uint64_t dividend_lo = (static_cast<uint64_t>(remainder) << 32) | lo;
+ uint64_t quotient_lo = dividend_lo / k1e9;
+ remainder = static_cast<uint32_t>(dividend_lo % k1e9);
+ *elem = (quotient_hi << 32) | quotient_lo;
+ } while (elem-- != copy.data());
+
+ segments[num_segments++] = remainder;
+ } while (*most_significant_elem != 0 || most_significant_elem-- != copy.data());
+
+ size_t old_size = result->size();
+ size_t new_size = old_size + num_segments * 9;
+ result->resize(new_size);
+ char* output = &result->at(0) + old_size;
Review comment:
`char* output = &result[old_size]` perhaps?
##########
File path: cpp/src/arrow/util/decimal.cc
##########
@@ -195,42 +191,89 @@ double Decimal128::ToDouble(int32_t scale) const {
return DecimalDoubleConversion::ToReal(*this, scale);
}
-std::string Decimal128::ToIntegerString() const {
- Decimal128 remainder;
- std::stringstream buf;
- bool need_fill = false;
-
- // get anything above 10 ** 36 and print it
- Decimal128 top;
- std::tie(top, remainder) = Divide(kTenTo36).ValueOrDie();
-
- if (top != 0) {
- buf << static_cast<int64_t>(top);
- remainder.Abs();
- need_fill = true;
+template <size_t n>
+static void AppendLittleEndianArrayToString(const std::array<uint64_t, n>& array,
+ std::string* result) {
+ static_assert(n > 0, "Array size must be positive");
+ size_t most_significant_elem_idx = n - 1;
+ while (array[most_significant_elem_idx] == 0) {
+ if (most_significant_elem_idx == 0) {
+ result->push_back('0');
+ return;
+ }
+ --most_significant_elem_idx;
+ }
+
+ std::array<uint64_t, n> copy = array;
+ constexpr uint32_t k1e9 = 1000000000U;
+ constexpr size_t num_bits = n * 64;
+ // Each segment holds at most 9 decimal digits.
+ // The number of segments needed = ceil(num_bits * log(2) / log(1e9))
+ // = ceil(num_bits / 29.897352854) <= ceil(num_bits / 29).
+ std::array<uint32_t, (num_bits + 28) / 29> segments;
+ size_t num_segments = 0;
+ uint64_t* most_significant_elem = ©[most_significant_elem_idx];
+ do {
+ // Compute remainder = copy % 1e9 and copy = copy / 1e9.
+ uint32_t remainder = 0;
+ uint64_t* elem = most_significant_elem;
+ do {
+ uint32_t hi = static_cast<uint32_t>(*elem >> 32);
+ uint32_t lo = static_cast<uint32_t>(*elem & ~uint32_t{0});
+ uint64_t dividend_hi = (static_cast<uint64_t>(remainder) << 32) | hi;
+ uint64_t quotient_hi = dividend_hi / k1e9;
+ remainder = static_cast<uint32_t>(dividend_hi % k1e9);
+ uint64_t dividend_lo = (static_cast<uint64_t>(remainder) << 32) | lo;
+ uint64_t quotient_lo = dividend_lo / k1e9;
+ remainder = static_cast<uint32_t>(dividend_lo % k1e9);
+ *elem = (quotient_hi << 32) | quotient_lo;
+ } while (elem-- != copy.data());
+
+ segments[num_segments++] = remainder;
+ } while (*most_significant_elem != 0 || most_significant_elem-- != copy.data());
+
+ size_t old_size = result->size();
+ size_t new_size = old_size + num_segments * 9;
+ result->resize(new_size);
+ char* output = &result->at(0) + old_size;
+ const uint32_t* segment = &segments[num_segments - 1];
+ size_t num_digits_in_first_segment = 9;
+ uint32_t digits = *segment;
+ for (int j = 8; j >= 0; --j) {
+ output[j] = static_cast<char>(digits % 10) + '0';
Review comment:
We have formatting utilities in `arrow/util/formatting.h`, you should ideally reuse them instead of reinventing the wheel.
##########
File path: cpp/src/arrow/util/decimal_test.cc
##########
@@ -106,6 +99,33 @@ TEST(DecimalTest, TestFromDecimalString128) {
ASSERT_NE(result.high_bits(), 0);
}
+TEST(DecimalTest, TestStringRoundTrip) {
+ static constexpr uint64_t kTestBits[] = {
+ 0,
+ 1,
+ 999,
+ 1000,
+ std::numeric_limits<int32_t>::max(),
+ (1ull << 31),
+ std::numeric_limits<uint32_t>::max(),
+ (1ull << 32),
+ std::numeric_limits<int64_t>::max(),
+ (1ull << 63),
+ std::numeric_limits<uint64_t>::max(),
+ };
+ static constexpr int32_t kScales[] = {-10, -1, 0, 1, 10};
+ for (uint64_t high_bits : kTestBits) {
Review comment:
We should probably test negative numbers as well.
##########
File path: cpp/src/arrow/util/decimal.cc
##########
@@ -241,64 +284,43 @@ Decimal128::operator int64_t() const {
return static_cast<int64_t>(low_bits());
}
-static std::string ToStringNegativeScale(const std::string& str,
- int32_t adjusted_exponent, bool is_negative) {
- std::stringstream buf;
-
- size_t offset = 0;
- buf << str[offset++];
-
- if (is_negative) {
- buf << str[offset++];
- }
-
- buf << '.' << str.substr(offset, std::string::npos) << 'E' << std::showpos
- << adjusted_exponent;
- return buf.str();
-}
-
-std::string Decimal128::ToString(int32_t scale) const {
- const std::string str(ToIntegerString());
-
+static void AdjustIntegerStringWithScale(int32_t scale, std::string* str) {
if (scale == 0) {
- return str;
+ return;
}
- const bool is_negative = *this < 0;
-
- const auto len = static_cast<int32_t>(str.size());
+ const bool is_negative = str->front() == '-';
const auto is_negative_offset = static_cast<int32_t>(is_negative);
- const int32_t adjusted_exponent = -scale + (len - 1 - is_negative_offset);
+ const auto len = static_cast<int32_t>(str->size());
+ const int32_t num_digits = len - is_negative_offset;
+ const int32_t adjusted_exponent = num_digits - 1 - scale;
/// Note that the -6 is taken from the Java BigDecimal documentation.
if (scale < 0 || adjusted_exponent < -6) {
- return ToStringNegativeScale(str, adjusted_exponent, is_negative);
+ str->insert(str->begin() + 1 + is_negative_offset, '.');
Review comment:
Can you explain what this is doing? It's not really obvious why `1 + is_negative_offset` is used as index.
##########
File path: cpp/src/arrow/util/decimal_benchmark.cc
##########
@@ -26,14 +26,36 @@
namespace arrow {
namespace Decimal {
-static void FromString(benchmark::State& state) { // NOLINT non-const reference
- std::vector<std::string> values = {"0",
- "1.23",
- "12.345e6",
- "-12.345e-6",
- "123456789.123456789",
- "1231234567890.451234567890"};
+static const std::vector<std::string>& GetValuesAsString() {
+ static const std::vector<std::string>* values =
+ new std::vector<std::string>{"0",
Review comment:
This sounds like a really complicated way of creating a global static constant. Am I missing something?
Otherwise simply:
```c++
static const std::vector<std::string> kDecimalStrings = {...};
```
##########
File path: cpp/src/arrow/util/decimal_benchmark.cc
##########
@@ -26,14 +26,36 @@
namespace arrow {
namespace Decimal {
-static void FromString(benchmark::State& state) { // NOLINT non-const reference
- std::vector<std::string> values = {"0",
- "1.23",
- "12.345e6",
- "-12.345e-6",
- "123456789.123456789",
- "1231234567890.451234567890"};
+static const std::vector<std::string>& GetValuesAsString() {
+ static const std::vector<std::string>* values =
+ new std::vector<std::string>{"0",
+ "1.23",
+ "12.345e6",
+ "-12.345e-6",
+ "123456789.123456789",
+ "1231234567890.451234567890"};
+ return *values;
+}
+
+static std::vector<std::pair<Decimal128, int32_t>> BuildDecimalValuesAndScales() {
+ const std::vector<std::string>& value_strs = GetValuesAsString();
+ std::vector<std::pair<Decimal128, int32_t>> result(value_strs.size());
+ for (size_t i = 0; i < value_strs.size(); ++i) {
+ int32_t precision;
+ Decimal128::FromString(value_strs[i], &result[i].first, &result[i].second,
+ &precision);
+ }
+ return result;
+}
+
+static const std::vector<std::pair<Decimal128, int32_t>>& GetDecimalValuesAndScales() {
+ static const auto* values =
+ new std::vector<std::pair<Decimal128, int32_t>>(BuildDecimalValuesAndScales());
Review comment:
The caching is really pointless. The small setup is cheap enough.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org