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 16:25:55 UTC
[GitHub] [arrow] emkornfield 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.
emkornfield commented on a change in pull request #7945:
URL: https://github.com/apache/arrow/pull/7945#discussion_r469962283
##########
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;
Review comment:
nit kNumBits?
##########
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});
Review comment:
consider using [LeastSignficantBitMask](https://github.com/apache/arrow/blob/e0a9d0f28affdccb45bf76fde58d0eec1328cd40/cpp/src/arrow/util/bit_util.h#L144)
##########
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
Review comment:
nit: if you move buf initialization before str->insert(), you can then string::reserve(2 + str.size()). In most cases this probably won't be a huge deal
##########
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;
Review comment:
i think this code could be easier to read if iterators where used (also allows while loops below which I think are more common so easier to read the do/while.
```
auto most_significat_non_zero = find_if(array.rbegin(), array.rend(), [](uint64_t v) {v != 0;})
if (most_significat_non_zero == array.rend()) {
result->push_back('0');
return;
}
```
This is somewhat subjective, so I'm OK if this stays this way.
##########
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:
nit: &result->at(old_size)
but really iterator might be better 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.
Review comment:
```suggestion
// Segments will contain the twos complement array split into groups that map to decimal digits
// Each segment will hold at most 9 decimal digits.
```
##########
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() {
Review comment:
nit: making a struct instead of pair can make the code easier to read.
##########
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.
Review comment:
There is probably a better description for segments, but that was my first pass.
##########
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);
Review comment:
Please add a comment (or make the loop its own method with a descriptive name) indicating what this is doing in little bit more detail, it took me a while to grok it.
----------------------------------------------------------------
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