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/10/27 19:24:47 UTC
[GitHub] [arrow] Bei-z opened a new pull request #8542: Add BasicDecimal256 Division Support
Bei-z opened a new pull request #8542:
URL: https://github.com/apache/arrow/pull/8542
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r520925174
##########
File path: cpp/src/arrow/util/decimal_test.cc
##########
@@ -1296,6 +1296,56 @@ TEST(Decimal256Test, Multiply) {
}
}
+TEST(Decimal256Test, Divide) {
+ ASSERT_EQ(Decimal256(33), Decimal256(100) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(200) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(-20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256(66), Decimal256(-20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+
+ // Test some random numbers.
+ for (auto x : GetRandomNumbers<Int32Type>(16)) {
+ for (auto y : GetRandomNumbers<Int32Type>(16)) {
+ if (y == 0) {
+ continue;
+ }
+
+ Decimal256 result = Decimal256(x) / Decimal256(y);
+ ASSERT_EQ(Decimal256(static_cast<int64_t>(x) / y), result)
+ << " x: " << x << " y: " << y;
+ }
+ }
+
+ // Test some edge cases
+ for (auto x : std::vector<int128_t>{-INT64_MAX, -INT32_MAX, 0, INT32_MAX, INT64_MAX}) {
+ for (auto y : std::vector<int128_t>{-INT32_MAX, -32, -2, -1, 1, 2, 32, INT32_MAX}) {
Review comment:
Thank you for your suggestions! Added kInt128Max for testing, and also tested -INT64_MAX - 1 and -INT32_MAX - 1
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r519873678
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,33 +395,49 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
-/// Expands the given value into an array of ints so that we can work on
-/// it. The array will be converted to an absolute value and the wasNegative
+/// Expands the given little endian array of uint64_t into a big endian array of
+/// uint32_t. The value of input array is expected to be non-negative. The result_array
+/// will remove leading zeros from the input array.
+/// \param value_array a little endian array to represent the value
+/// \param result_array a big endian array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(const std::array<uint64_t, N>& value_array,
+ uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (int64_t i = N - 1; i >= 0; i--) {
+ if (value_array[i] != 0) {
+ if (value_array[i] <= std::numeric_limits<uint32_t>::max()) {
+ result_array[next_index++] = static_cast<uint32_t>(value_array[i]);
+ i--;
+ }
+ for (int64_t j = i; j >= 0; j--) {
+ result_array[next_index++] = static_cast<uint32_t>(value_array[j] >> 32);
+ result_array[next_index++] = static_cast<uint32_t>(value_array[j]);
+ }
+ break;
+ }
+ }
+ return next_index;
+}
+
+/// Expands the given value into a big endian array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the was_negative
/// flag will be set appropriately. The array will remove leading zeros from
/// the value.
-/// \param array an array of length 4 to set with the value
+/// \param array a big endian array of length 4 to set with the value
/// \param was_negative a flag for whether the value was original negative
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
-
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.high_bits() < 0;
+ uint64_t high = static_cast<uint64_t>(abs_value.high_bits());
+ uint64_t low = abs_value.low_bits();
+
+ // FillInArray(std::array<uint64_t, N>& value_array, uint32_t* result_array) is not
+ // called here as the following code has better performance, to avoid regression on
+ // BasicDecimal128 Division.
if (high != 0) {
if (high > std::numeric_limits<uint32_t>::max()) {
Review comment:
By the way, why do we have strict inequality here, but a non-strict one below for `low`?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -451,6 +467,25 @@ static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
return 1;
}
+/// Expands the given value into a big endian array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the was_negative
+/// flag will be set appropriately. The array will remove leading zeros from
+/// the value.
+/// \param array a big endian array of length 8 to set with the value
+/// \param was_negative a flag for whether the value was original negative
+/// \result the output length of the array
+static int64_t FillInArray(const BasicDecimal256& value, uint32_t* array,
+ bool& was_negative) {
+ BasicDecimal256 positive_value = value;
+ was_negative = false;
+ int64_t highest_bit = positive_value.little_endian_array()[3];
+ if (highest_bit < 0) {
Review comment:
Doesn't/shouldn't `BasicDecimal256` have a `sign` or `is_negative` method to factor out this pattern?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
+ ? lower_bits
+ : ((static_cast<uint64_t>(array[next_index--]) << 32) + lower_bits);
+ }
+ return DecimalStatus::kSuccess;
+}
+
+/// \brief Build a BasicDecimal128 from a big endian array of uint32_t.
static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array,
Review comment:
`const uint32_t*`?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
Review comment:
`const uint32_t* array`?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,33 +395,49 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
-/// Expands the given value into an array of ints so that we can work on
-/// it. The array will be converted to an absolute value and the wasNegative
+/// Expands the given little endian array of uint64_t into a big endian array of
+/// uint32_t. The value of input array is expected to be non-negative. The result_array
+/// will remove leading zeros from the input array.
+/// \param value_array a little endian array to represent the value
+/// \param result_array a big endian array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(const std::array<uint64_t, N>& value_array,
+ uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (int64_t i = N - 1; i >= 0; i--) {
Review comment:
Nit, but the nested loop is a bit confusing. Two separate loops would make the intent more obvious (and might also help the compiler?).
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
Review comment:
The code would look clearer if you had one loop for the non-zero words, and one other loop for the excess (zeroed) words, IMHO.
##########
File path: cpp/src/arrow/util/decimal_test.cc
##########
@@ -1296,6 +1296,56 @@ TEST(Decimal256Test, Multiply) {
}
}
+TEST(Decimal256Test, Divide) {
+ ASSERT_EQ(Decimal256(33), Decimal256(100) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(200) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(-20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256(66), Decimal256(-20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+
+ // Test some random numbers.
+ for (auto x : GetRandomNumbers<Int32Type>(16)) {
+ for (auto y : GetRandomNumbers<Int32Type>(16)) {
+ if (y == 0) {
+ continue;
+ }
+
+ Decimal256 result = Decimal256(x) / Decimal256(y);
+ ASSERT_EQ(Decimal256(static_cast<int64_t>(x) / y), result)
+ << " x: " << x << " y: " << y;
+ }
+ }
+
+ // Test some edge cases
+ for (auto x : std::vector<int128_t>{-INT64_MAX, -INT32_MAX, 0, INT32_MAX, INT64_MAX}) {
+ for (auto y : std::vector<int128_t>{-INT32_MAX, -32, -2, -1, 1, 2, 32, INT32_MAX}) {
Review comment:
Also, what about `-INT64_MAX - 1` and `-INT32_MAX - 1`? Are they expected to work as well? If so, test them.
##########
File path: cpp/src/arrow/util/decimal_test.cc
##########
@@ -1296,6 +1296,56 @@ TEST(Decimal256Test, Multiply) {
}
}
+TEST(Decimal256Test, Divide) {
+ ASSERT_EQ(Decimal256(33), Decimal256(100) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(200) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(-20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256(66), Decimal256(-20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+
+ // Test some random numbers.
+ for (auto x : GetRandomNumbers<Int32Type>(16)) {
+ for (auto y : GetRandomNumbers<Int32Type>(16)) {
+ if (y == 0) {
+ continue;
+ }
+
+ Decimal256 result = Decimal256(x) / Decimal256(y);
+ ASSERT_EQ(Decimal256(static_cast<int64_t>(x) / y), result)
+ << " x: " << x << " y: " << y;
+ }
+ }
+
+ // Test some edge cases
+ for (auto x : std::vector<int128_t>{-INT64_MAX, -INT32_MAX, 0, INT32_MAX, INT64_MAX}) {
+ for (auto y : std::vector<int128_t>{-INT32_MAX, -32, -2, -1, 1, 2, 32, INT32_MAX}) {
Review comment:
Can we define a `INT128_MAX` constant and test it as well?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
+ ? lower_bits
+ : ((static_cast<uint64_t>(array[next_index--]) << 32) + lower_bits);
+ }
+ return DecimalStatus::kSuccess;
+}
+
+/// \brief Build a BasicDecimal128 from a big endian array of uint32_t.
static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array,
int64_t length) {
- switch (length) {
- case 0:
- *value = {static_cast<int64_t>(0)};
- break;
- case 1:
- *value = {static_cast<int64_t>(array[0])};
- break;
- case 2:
- *value = {static_cast<int64_t>(0),
- (static_cast<uint64_t>(array[0]) << 32) + array[1]};
- break;
- case 3:
- *value = {static_cast<int64_t>(array[0]),
- (static_cast<uint64_t>(array[1]) << 32) + array[2]};
- break;
- case 4:
- *value = {(static_cast<int64_t>(array[0]) << 32) + array[1],
- (static_cast<uint64_t>(array[2]) << 32) + array[3]};
- break;
- case 5:
- if (array[0] != 0) {
- return DecimalStatus::kOverflow;
- }
- *value = {(static_cast<int64_t>(array[1]) << 32) + array[2],
- (static_cast<uint64_t>(array[3]) << 32) + array[4]};
- break;
- default:
- return DecimalStatus::kOverflow;
+ std::array<uint64_t, 2> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
}
+ *value = {static_cast<int64_t>(result_array[1]), result_array[0]};
+ return DecimalStatus::kSuccess;
+}
+/// \brief Build a BasicDecimal256 from a big endian array of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal256* value, uint32_t* array,
Review comment:
`const uint32_t* array`?
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r520841038
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
Review comment:
Thank you for your suggestion!
Changed this part of code to 2 loops, but there is a little performance regression. Is there anything I can improve on the current code to help with the performance, or should we consider change back to one loop?
Current benchmark:
BinaryMathOp128 156 ns 156 ns 4316716 items_per_second=64.2915M/s
BinaryMathOp256 152 ns 152 ns 4426239 items_per_second=65.7017M/s
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
+ ? lower_bits
+ : ((static_cast<uint64_t>(array[next_index--]) << 32) + lower_bits);
+ }
+ return DecimalStatus::kSuccess;
+}
+
+/// \brief Build a BasicDecimal128 from a big endian array of uint32_t.
static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array,
Review comment:
Changed accordingly, thank you!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
+ ? lower_bits
+ : ((static_cast<uint64_t>(array[next_index--]) << 32) + lower_bits);
+ }
+ return DecimalStatus::kSuccess;
+}
+
+/// \brief Build a BasicDecimal128 from a big endian array of uint32_t.
static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array,
int64_t length) {
- switch (length) {
- case 0:
- *value = {static_cast<int64_t>(0)};
- break;
- case 1:
- *value = {static_cast<int64_t>(array[0])};
- break;
- case 2:
- *value = {static_cast<int64_t>(0),
- (static_cast<uint64_t>(array[0]) << 32) + array[1]};
- break;
- case 3:
- *value = {static_cast<int64_t>(array[0]),
- (static_cast<uint64_t>(array[1]) << 32) + array[2]};
- break;
- case 4:
- *value = {(static_cast<int64_t>(array[0]) << 32) + array[1],
- (static_cast<uint64_t>(array[2]) << 32) + array[3]};
- break;
- case 5:
- if (array[0] != 0) {
- return DecimalStatus::kOverflow;
- }
- *value = {(static_cast<int64_t>(array[1]) << 32) + array[2],
- (static_cast<uint64_t>(array[3]) << 32) + array[4]};
- break;
- default:
- return DecimalStatus::kOverflow;
+ std::array<uint64_t, 2> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
}
+ *value = {static_cast<int64_t>(result_array[1]), result_array[0]};
+ return DecimalStatus::kSuccess;
+}
+/// \brief Build a BasicDecimal256 from a big endian array of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal256* value, uint32_t* array,
Review comment:
Changed accordingly, thank you!
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r524305460
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +529,64 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
-static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array,
- int64_t length) {
- switch (length) {
- case 0:
- *value = {static_cast<int64_t>(0)};
- break;
- case 1:
- *value = {static_cast<int64_t>(array[0])};
- break;
- case 2:
- *value = {static_cast<int64_t>(0),
- (static_cast<uint64_t>(array[0]) << 32) + array[1]};
- break;
- case 3:
- *value = {static_cast<int64_t>(array[0]),
- (static_cast<uint64_t>(array[1]) << 32) + array[2]};
- break;
- case 4:
- *value = {(static_cast<int64_t>(array[0]) << 32) + array[1],
- (static_cast<uint64_t>(array[2]) << 32) + array[3]};
- break;
- case 5:
- if (array[0] != 0) {
- return DecimalStatus::kOverflow;
- }
- *value = {(static_cast<int64_t>(array[1]) << 32) + array[2],
- (static_cast<uint64_t>(array[3]) << 32) + array[4]};
- break;
- default:
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ const uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ size_t i = 0;
+ for (; i < N && next_index >= 0; i++) {
+ uint64_t lower_bits = array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
+ ? lower_bits
+ : ((static_cast<uint64_t>(array[next_index--]) << 32) + lower_bits);
+ }
+ for (; i < N; i++) {
+ (*result_array)[i] = 0;
}
+ return DecimalStatus::kSuccess;
+}
+/// \brief Build a BasicDecimal128 from a big endian array of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal128* value, const uint32_t* array,
+ int64_t length) {
+ std::array<uint64_t, 2> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
+ }
+ *value = {static_cast<int64_t>(result_array[1]), result_array[0]};
+ return DecimalStatus::kSuccess;
+}
+
+/// \brief Build a BasicDecimal256 from a big endian array of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal256* value, const uint32_t* array,
+ int64_t length) {
+ std::array<uint64_t, 4> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
+ }
+ *value = result_array;
return DecimalStatus::kSuccess;
}
/// \brief Do a division where the divisor fits into a single 32 bit value.
-static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_length,
- uint32_t divisor, BasicDecimal128* remainder,
- bool dividend_was_negative, bool divisor_was_negative,
- BasicDecimal128* result) {
+template <class DecimalClass>
+static inline DecimalStatus SingleDivide(const uint32_t* dividend,
+ int64_t dividend_length, uint32_t divisor,
+ DecimalClass* remainder,
+ bool dividend_was_negative,
+ bool divisor_was_negative,
+ DecimalClass* result) {
uint64_t r = 0;
- uint32_t result_array[5];
+ uint32_t* result_array = new uint32_t[dividend_length];
Review comment:
Is the dynamic allocation really necessary? Isn't a local array of length 9 sufficient?
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#issuecomment-729124206
New PR at #8696. I tried to conserve authorship.
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r521719735
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,33 +395,49 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
-/// Expands the given value into an array of ints so that we can work on
-/// it. The array will be converted to an absolute value and the wasNegative
+/// Expands the given little endian array of uint64_t into a big endian array of
+/// uint32_t. The value of input array is expected to be non-negative. The result_array
+/// will remove leading zeros from the input array.
+/// \param value_array a little endian array to represent the value
+/// \param result_array a big endian array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(const std::array<uint64_t, N>& value_array,
+ uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (int64_t i = N - 1; i >= 0; i--) {
+ if (value_array[i] != 0) {
+ if (value_array[i] <= std::numeric_limits<uint32_t>::max()) {
+ result_array[next_index++] = static_cast<uint32_t>(value_array[i]);
+ i--;
+ }
+ for (int64_t j = i; j >= 0; j--) {
+ result_array[next_index++] = static_cast<uint32_t>(value_array[j] >> 32);
+ result_array[next_index++] = static_cast<uint32_t>(value_array[j]);
+ }
+ break;
+ }
+ }
+ return next_index;
+}
+
+/// Expands the given value into a big endian array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the was_negative
/// flag will be set appropriately. The array will remove leading zeros from
/// the value.
-/// \param array an array of length 4 to set with the value
+/// \param array a big endian array of length 4 to set with the value
/// \param was_negative a flag for whether the value was original negative
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
-
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.high_bits() < 0;
+ uint64_t high = static_cast<uint64_t>(abs_value.high_bits());
+ uint64_t low = abs_value.low_bits();
+
+ // FillInArray(std::array<uint64_t, N>& value_array, uint32_t* result_array) is not
+ // called here as the following code has better performance, to avoid regression on
+ // BasicDecimal128 Division.
if (high != 0) {
if (high > std::numeric_limits<uint32_t>::max()) {
Review comment:
Ah sorry just got what you mean here! And yes it should be strict inequality for both places. Changed accordingly.
----------------------------------------------------------------
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
[GitHub] [arrow] MingyuZhong commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
MingyuZhong commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r517062023
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -404,51 +429,33 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
-
- if (high != 0) {
- if (high > std::numeric_limits<uint32_t>::max()) {
- array[0] = static_cast<uint32_t>(high >> 32);
- array[1] = static_cast<uint32_t>(high);
- array[2] = static_cast<uint32_t>(low >> 32);
- array[3] = static_cast<uint32_t>(low);
- return 4;
- }
-
- array[0] = static_cast<uint32_t>(high);
- array[1] = static_cast<uint32_t>(low >> 32);
- array[2] = static_cast<uint32_t>(low);
- return 3;
- }
-
- if (low >= std::numeric_limits<uint32_t>::max()) {
- array[0] = static_cast<uint32_t>(low >> 32);
- array[1] = static_cast<uint32_t>(low);
- return 2;
- }
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.high_bits() < 0;
+ std::array<uint64_t, 2> abs_big_endian_array = {
+ static_cast<uint64_t>(abs_value.high_bits()),
+ static_cast<uint64_t>(abs_value.low_bits())};
+ return FillInArray(abs_big_endian_array, array);
+}
- if (low == 0) {
- return 0;
+/// Expands the given value into an array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the wasNegative
+/// flag will be set appropriately. The array will remove leading zeros from
+/// the value.
+/// \param array an array of length 8 to set with the value
+/// \param was_negative a flag for whether the value was original negative
+/// \result the output length of the array
+static int64_t FillInArray(const BasicDecimal256& value, uint32_t* array,
+ bool& was_negative) {
+ BasicDecimal256 positive_value = value;
+ was_negative = false;
+ int64_t highest_bit = positive_value.little_endian_array()[3];
+ if (highest_bit < 0) {
+ positive_value.Negate();
+ was_negative = true;
}
-
- array[0] = static_cast<uint32_t>(low);
- return 1;
+ std::array<uint64_t, 4> value_big_endian_array = positive_value.little_endian_array();
+ std::reverse(value_big_endian_array.begin(), value_big_endian_array.end());
Review comment:
Can FillInArray below take little-endian array so you don't need to call std::reverse?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -451,6 +463,27 @@ static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
return 1;
}
+/// Expands the given value into an array of ints so that we can work on
Review comment:
Comment that the output array is in big-endian.
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -451,6 +463,27 @@ static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
return 1;
}
+/// Expands the given value into an array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the wasNegative
Review comment:
was_negative
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -404,23 +429,10 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.high_bits() < 0;
+ uint64_t high = static_cast<uint64_t>(abs_value.high_bits());
Review comment:
Please add a comment about why FillInArray is not called.
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,6 +395,31 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
+/// Expands the given big endian array of uint64_t into an array of uint32_t.
+/// The value of input array is expected to be positive. The result_array will
Review comment:
positive -> non-negative?
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r517702346
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -451,6 +463,27 @@ static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
return 1;
}
+/// Expands the given value into an array of ints so that we can work on
Review comment:
Done. Thank you!
----------------------------------------------------------------
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
[GitHub] [arrow] github-actions[bot] commented on pull request #8542: Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#issuecomment-717487106
<!--
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements. See the NOTICE file
distributed with this work for additional information
regarding copyright ownership. The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied. See the License for the
specific language governing permissions and limitations
under the License.
-->
Thanks for opening a pull request!
Could you open an issue for this pull request on JIRA?
https://issues.apache.org/jira/browse/ARROW
Then could you also rename pull request title in the following format?
ARROW-${JIRA_ID}: [${COMPONENT}] ${SUMMARY}
See also:
* [Other pull requests](https://github.com/apache/arrow/pulls/)
* [Contribution Guidelines - How to contribute patches](https://arrow.apache.org/docs/developers/contributing.html#how-to-contribute-patches)
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r521349565
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,33 +395,49 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
-/// Expands the given value into an array of ints so that we can work on
-/// it. The array will be converted to an absolute value and the wasNegative
+/// Expands the given little endian array of uint64_t into a big endian array of
+/// uint32_t. The value of input array is expected to be non-negative. The result_array
+/// will remove leading zeros from the input array.
+/// \param value_array a little endian array to represent the value
+/// \param result_array a big endian array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(const std::array<uint64_t, N>& value_array,
+ uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (int64_t i = N - 1; i >= 0; i--) {
+ if (value_array[i] != 0) {
+ if (value_array[i] <= std::numeric_limits<uint32_t>::max()) {
+ result_array[next_index++] = static_cast<uint32_t>(value_array[i]);
+ i--;
+ }
+ for (int64_t j = i; j >= 0; j--) {
+ result_array[next_index++] = static_cast<uint32_t>(value_array[j] >> 32);
+ result_array[next_index++] = static_cast<uint32_t>(value_array[j]);
+ }
+ break;
+ }
+ }
+ return next_index;
+}
+
+/// Expands the given value into a big endian array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the was_negative
/// flag will be set appropriately. The array will remove leading zeros from
/// the value.
-/// \param array an array of length 4 to set with the value
+/// \param array a big endian array of length 4 to set with the value
/// \param was_negative a flag for whether the value was original negative
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
-
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.high_bits() < 0;
+ uint64_t high = static_cast<uint64_t>(abs_value.high_bits());
+ uint64_t low = abs_value.low_bits();
+
+ // FillInArray(std::array<uint64_t, N>& value_array, uint32_t* result_array) is not
+ // called here as the following code has better performance, to avoid regression on
+ // BasicDecimal128 Division.
if (high != 0) {
if (high > std::numeric_limits<uint32_t>::max()) {
Review comment:
I'm afraid that doesn't answer my question about non-strict inequality, does 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
[GitHub] [arrow] github-actions[bot] commented on pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#issuecomment-717494154
https://issues.apache.org/jira/browse/ARROW-10407
----------------------------------------------------------------
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
[GitHub] [arrow] MingyuZhong commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
MingyuZhong commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r516330879
##########
File path: cpp/src/arrow/util/decimal_benchmark.cc
##########
@@ -158,6 +158,7 @@ static void BinaryMathOp256(benchmark::State& state) { // NOLINT non-const refe
for (auto _ : state) {
for (int x = 0; x < kValueSize; x += 5) {
benchmark::DoNotOptimize(v1[x + 2] * v2[x + 2]);
+ benchmark::DoNotOptimize(v1[x + 3] / v2[x + 3]);
Review comment:
Can you find the functions that are called only once (e.g., DecimalDivide), make them inline and run the benchmarks again?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -575,8 +572,7 @@ template <class DecimalClass>
static DecimalStatus DecimalDivide(const DecimalClass& dividend,
const DecimalClass& divisor, DecimalClass* result,
DecimalClass* remainder) {
- static int64_t kDecimalArrayLength =
- std::is_same<DecimalClass, BasicDecimal128>::value ? 4 : 8;
+ static constexpr int64_t kDecimalArrayLength = sizeof(DecimalClass) / sizeof(uint32_t);
Review comment:
I don't think you need "static" here.
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r517699770
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -404,23 +429,10 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.high_bits() < 0;
+ uint64_t high = static_cast<uint64_t>(abs_value.high_bits());
Review comment:
Comment added below. Thanks!
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r516910756
##########
File path: cpp/src/arrow/util/decimal_benchmark.cc
##########
@@ -158,6 +158,7 @@ static void BinaryMathOp256(benchmark::State& state) { // NOLINT non-const refe
for (auto _ : state) {
for (int x = 0; x < kValueSize; x += 5) {
benchmark::DoNotOptimize(v1[x + 2] * v2[x + 2]);
+ benchmark::DoNotOptimize(v1[x + 3] / v2[x + 3]);
Review comment:
After several (10+) runs, the benchmark shows mostly consistent with the following result:
BinaryMathOp128 164 ns 164 ns 4054471 items_per_second=61.0408M/s
BinaryMathOp256 162 ns 162 ns 4059481 items_per_second=61.5496M/s
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r516900167
##########
File path: cpp/src/arrow/util/decimal_benchmark.cc
##########
@@ -158,6 +158,7 @@ static void BinaryMathOp256(benchmark::State& state) { // NOLINT non-const refe
for (auto _ : state) {
for (int x = 0; x < kValueSize; x += 5) {
benchmark::DoNotOptimize(v1[x + 2] * v2[x + 2]);
+ benchmark::DoNotOptimize(v1[x + 3] / v2[x + 3]);
Review comment:
Changed DecimalDivide, ShiftArrayRight, SingleDivide to inline, but the benchmark result did not change much...
BinaryMathOp128 164 ns 164 ns 4199726 items_per_second=60.9518M/s
BinaryMathOp256 161 ns 161 ns 4239358 items_per_second=62.0223M/s
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r516251296
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,6 +395,34 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
+/// Expands the given big endian array of uint64_t into an array of uint32_t.
+/// The value of input array is expected to be positive. The result_array will
+/// remove leading zeros from the input array.
+/// \param value_array an big endian array to represent the value
+/// \param result_array an array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(std::array<uint64_t, N>& value_array, uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (size_t i = 0; i < N; i++) {
+ if (value_array[i] == 0) {
Review comment:
Changed accordingly, thanks!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -549,24 +570,28 @@ static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_len
return DecimalStatus::kSuccess;
}
-DecimalStatus BasicDecimal128::Divide(const BasicDecimal128& divisor,
- BasicDecimal128* result,
- BasicDecimal128* remainder) const {
+/// \brief Do a division where the divisor fits into a single 32 bit value.
+template <class DecimalClass>
+static DecimalStatus DecimalDivide(const DecimalClass& dividend,
+ const DecimalClass& divisor, DecimalClass* result,
+ DecimalClass* remainder) {
+ static int64_t kDecimalArrayLength =
+ std::is_same<DecimalClass, BasicDecimal128>::value ? 4 : 8;
Review comment:
Done, thx!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +501,59 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a big endian array of uint64_t from a list of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (int64_t i = N - 1; i >= 0; i--) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
+ ? lower_bits
+ : ((static_cast<uint64_t>(array[next_index--]) << 32) + lower_bits);
+ }
+ return DecimalStatus::kSuccess;
+}
+
+/// \brief Build a BasicDecimal128 from a list of uint32_t.
static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array,
int64_t length) {
- switch (length) {
- case 0:
- *value = {static_cast<int64_t>(0)};
- break;
- case 1:
- *value = {static_cast<int64_t>(array[0])};
- break;
- case 2:
- *value = {static_cast<int64_t>(0),
- (static_cast<uint64_t>(array[0]) << 32) + array[1]};
- break;
- case 3:
- *value = {static_cast<int64_t>(array[0]),
- (static_cast<uint64_t>(array[1]) << 32) + array[2]};
- break;
- case 4:
- *value = {(static_cast<int64_t>(array[0]) << 32) + array[1],
- (static_cast<uint64_t>(array[2]) << 32) + array[3]};
- break;
- case 5:
- if (array[0] != 0) {
- return DecimalStatus::kOverflow;
- }
- *value = {(static_cast<int64_t>(array[1]) << 32) + array[2],
- (static_cast<uint64_t>(array[3]) << 32) + array[4]};
- break;
- default:
- return DecimalStatus::kOverflow;
+ std::array<uint64_t, 2> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
}
+ *value = {static_cast<int64_t>(result_array[0]), result_array[1]};
+ return DecimalStatus::kSuccess;
+}
+/// \brief Build a BasicDecimal256 from a list of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal256* value, uint32_t* array,
+ int64_t length) {
+ std::array<uint64_t, 4> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
+ }
+ std::reverse(result_array.begin(), result_array.end());
Review comment:
done. Thank you!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,6 +395,34 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
+/// Expands the given big endian array of uint64_t into an array of uint32_t.
+/// The value of input array is expected to be positive. The result_array will
+/// remove leading zeros from the input array.
+/// \param value_array an big endian array to represent the value
+/// \param result_array an array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(std::array<uint64_t, N>& value_array, uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (size_t i = 0; i < N; i++) {
+ if (value_array[i] == 0) {
+ if (next_index != 0) {
+ result_array[next_index++] = 0;
+ result_array[next_index++] = 0;
+ }
+ } else if (value_array[i] <= std::numeric_limits<uint32_t>::max()) {
Review comment:
This special case is needed here as we want to remove the leading zero in the result array of uint32_t, so that when the first non-zero uint64_t value is less than the max of uint32_t, we assign the value to the first element of the result array; when the non-zero uint64_t value is not the first value, we reserve the next element of the result array with 0;
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -479,7 +489,8 @@ static void ShiftArrayRight(uint32_t* array, int64_t length, int64_t bits) {
/// \brief Fix the signs of the result and remainder at the end of the division based on
/// the signs of the dividend and divisor.
-static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder,
+template <class DecimalClass>
+static void FixDivisionSigns(DecimalClass* result, DecimalClass* remainder,
Review comment:
Done. Thank you!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -549,24 +570,28 @@ static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_len
return DecimalStatus::kSuccess;
}
-DecimalStatus BasicDecimal128::Divide(const BasicDecimal128& divisor,
- BasicDecimal128* result,
- BasicDecimal128* remainder) const {
+/// \brief Do a division where the divisor fits into a single 32 bit value.
+template <class DecimalClass>
+static DecimalStatus DecimalDivide(const DecimalClass& dividend,
+ const DecimalClass& divisor, DecimalClass* result,
+ DecimalClass* remainder) {
+ static int64_t kDecimalArrayLength =
Review comment:
Done, thx!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -404,51 +432,33 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
-
- if (high != 0) {
- if (high > std::numeric_limits<uint32_t>::max()) {
- array[0] = static_cast<uint32_t>(high >> 32);
- array[1] = static_cast<uint32_t>(high);
- array[2] = static_cast<uint32_t>(low >> 32);
- array[3] = static_cast<uint32_t>(low);
- return 4;
- }
-
- array[0] = static_cast<uint32_t>(high);
- array[1] = static_cast<uint32_t>(low >> 32);
- array[2] = static_cast<uint32_t>(low);
- return 3;
- }
-
- if (low >= std::numeric_limits<uint32_t>::max()) {
- array[0] = static_cast<uint32_t>(low >> 32);
- array[1] = static_cast<uint32_t>(low);
- return 2;
- }
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.Sign() < 0;
Review comment:
Done. Thank you!
##########
File path: cpp/src/arrow/util/decimal_benchmark.cc
##########
@@ -158,6 +158,7 @@ static void BinaryMathOp256(benchmark::State& state) { // NOLINT non-const refe
for (auto _ : state) {
for (int x = 0; x < kValueSize; x += 5) {
benchmark::DoNotOptimize(v1[x + 2] * v2[x + 2]);
+ benchmark::DoNotOptimize(v1[x + 3] / v2[x + 3]);
Review comment:
The change did make Decimal128 a little bit slower:
Benchmark result after adding BasicDecimal256 Division support:
BinaryMathOp128 164 ns 164 ns 4134767 items_per_second=61.0451M/s
BinaryMathOp256 161 ns 161 ns 4197025 items_per_second=62.2226M/s
Benchmark result before adding BasicDecimal256 Division support:
BinaryMathOp128 153 ns 153 ns 4380604 items_per_second=65.4108M/s
BinaryMathOp256 34.5 ns 34.5 ns 19945733 items_per_second=289.557M/s
This metrics is also added to the pr description.
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r524305990
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +529,64 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
-static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array,
- int64_t length) {
- switch (length) {
- case 0:
- *value = {static_cast<int64_t>(0)};
- break;
- case 1:
- *value = {static_cast<int64_t>(array[0])};
- break;
- case 2:
- *value = {static_cast<int64_t>(0),
- (static_cast<uint64_t>(array[0]) << 32) + array[1]};
- break;
- case 3:
- *value = {static_cast<int64_t>(array[0]),
- (static_cast<uint64_t>(array[1]) << 32) + array[2]};
- break;
- case 4:
- *value = {(static_cast<int64_t>(array[0]) << 32) + array[1],
- (static_cast<uint64_t>(array[2]) << 32) + array[3]};
- break;
- case 5:
- if (array[0] != 0) {
- return DecimalStatus::kOverflow;
- }
- *value = {(static_cast<int64_t>(array[1]) << 32) + array[2],
- (static_cast<uint64_t>(array[3]) << 32) + array[4]};
- break;
- default:
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ const uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ size_t i = 0;
+ for (; i < N && next_index >= 0; i++) {
+ uint64_t lower_bits = array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
+ ? lower_bits
+ : ((static_cast<uint64_t>(array[next_index--]) << 32) + lower_bits);
+ }
+ for (; i < N; i++) {
+ (*result_array)[i] = 0;
}
+ return DecimalStatus::kSuccess;
+}
+/// \brief Build a BasicDecimal128 from a big endian array of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal128* value, const uint32_t* array,
+ int64_t length) {
+ std::array<uint64_t, 2> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
+ }
+ *value = {static_cast<int64_t>(result_array[1]), result_array[0]};
+ return DecimalStatus::kSuccess;
+}
+
+/// \brief Build a BasicDecimal256 from a big endian array of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal256* value, const uint32_t* array,
+ int64_t length) {
+ std::array<uint64_t, 4> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
+ }
+ *value = result_array;
return DecimalStatus::kSuccess;
}
/// \brief Do a division where the divisor fits into a single 32 bit value.
-static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_length,
- uint32_t divisor, BasicDecimal128* remainder,
- bool dividend_was_negative, bool divisor_was_negative,
- BasicDecimal128* result) {
+template <class DecimalClass>
+static inline DecimalStatus SingleDivide(const uint32_t* dividend,
+ int64_t dividend_length, uint32_t divisor,
+ DecimalClass* remainder,
+ bool dividend_was_negative,
+ bool divisor_was_negative,
+ DecimalClass* result) {
uint64_t r = 0;
- uint32_t result_array[5];
+ uint32_t* result_array = new uint32_t[dividend_length];
Review comment:
(or compute a `kDecimalArrayLength` as below)
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#issuecomment-726122152
Thanks for the updates. Can you look at the errors on CI and fix them? Thanks!
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r521350486
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
Review comment:
Hmm, I hadn't noticed the `next_index--` above...
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou closed pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou closed pull request #8542:
URL: https://github.com/apache/arrow/pull/8542
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#issuecomment-726531615
> Thanks for the updates. Can you look at the errors on CI and fix them? Thanks!
Thank you for reviewing! The errors on CI are fixed now.
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r517699593
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -404,51 +429,33 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
-
- if (high != 0) {
- if (high > std::numeric_limits<uint32_t>::max()) {
- array[0] = static_cast<uint32_t>(high >> 32);
- array[1] = static_cast<uint32_t>(high);
- array[2] = static_cast<uint32_t>(low >> 32);
- array[3] = static_cast<uint32_t>(low);
- return 4;
- }
-
- array[0] = static_cast<uint32_t>(high);
- array[1] = static_cast<uint32_t>(low >> 32);
- array[2] = static_cast<uint32_t>(low);
- return 3;
- }
-
- if (low >= std::numeric_limits<uint32_t>::max()) {
- array[0] = static_cast<uint32_t>(low >> 32);
- array[1] = static_cast<uint32_t>(low);
- return 2;
- }
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.high_bits() < 0;
+ std::array<uint64_t, 2> abs_big_endian_array = {
+ static_cast<uint64_t>(abs_value.high_bits()),
+ static_cast<uint64_t>(abs_value.low_bits())};
+ return FillInArray(abs_big_endian_array, array);
+}
- if (low == 0) {
- return 0;
+/// Expands the given value into an array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the wasNegative
+/// flag will be set appropriately. The array will remove leading zeros from
+/// the value.
+/// \param array an array of length 8 to set with the value
+/// \param was_negative a flag for whether the value was original negative
+/// \result the output length of the array
+static int64_t FillInArray(const BasicDecimal256& value, uint32_t* array,
+ bool& was_negative) {
+ BasicDecimal256 positive_value = value;
+ was_negative = false;
+ int64_t highest_bit = positive_value.little_endian_array()[3];
+ if (highest_bit < 0) {
+ positive_value.Negate();
+ was_negative = true;
}
-
- array[0] = static_cast<uint32_t>(low);
- return 1;
+ std::array<uint64_t, 4> value_big_endian_array = positive_value.little_endian_array();
+ std::reverse(value_big_endian_array.begin(), value_big_endian_array.end());
Review comment:
Updated accordingly. Thank you!
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r524689693
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +529,64 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
-static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array,
- int64_t length) {
- switch (length) {
- case 0:
- *value = {static_cast<int64_t>(0)};
- break;
- case 1:
- *value = {static_cast<int64_t>(array[0])};
- break;
- case 2:
- *value = {static_cast<int64_t>(0),
- (static_cast<uint64_t>(array[0]) << 32) + array[1]};
- break;
- case 3:
- *value = {static_cast<int64_t>(array[0]),
- (static_cast<uint64_t>(array[1]) << 32) + array[2]};
- break;
- case 4:
- *value = {(static_cast<int64_t>(array[0]) << 32) + array[1],
- (static_cast<uint64_t>(array[2]) << 32) + array[3]};
- break;
- case 5:
- if (array[0] != 0) {
- return DecimalStatus::kOverflow;
- }
- *value = {(static_cast<int64_t>(array[1]) << 32) + array[2],
- (static_cast<uint64_t>(array[3]) << 32) + array[4]};
- break;
- default:
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ const uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ size_t i = 0;
+ for (; i < N && next_index >= 0; i++) {
+ uint64_t lower_bits = array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
+ ? lower_bits
+ : ((static_cast<uint64_t>(array[next_index--]) << 32) + lower_bits);
+ }
+ for (; i < N; i++) {
+ (*result_array)[i] = 0;
}
+ return DecimalStatus::kSuccess;
+}
+/// \brief Build a BasicDecimal128 from a big endian array of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal128* value, const uint32_t* array,
+ int64_t length) {
+ std::array<uint64_t, 2> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
+ }
+ *value = {static_cast<int64_t>(result_array[1]), result_array[0]};
+ return DecimalStatus::kSuccess;
+}
+
+/// \brief Build a BasicDecimal256 from a big endian array of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal256* value, const uint32_t* array,
+ int64_t length) {
+ std::array<uint64_t, 4> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
+ }
+ *value = result_array;
return DecimalStatus::kSuccess;
}
/// \brief Do a division where the divisor fits into a single 32 bit value.
-static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_length,
- uint32_t divisor, BasicDecimal128* remainder,
- bool dividend_was_negative, bool divisor_was_negative,
- BasicDecimal128* result) {
+template <class DecimalClass>
+static inline DecimalStatus SingleDivide(const uint32_t* dividend,
+ int64_t dividend_length, uint32_t divisor,
+ DecimalClass* remainder,
+ bool dividend_was_negative,
+ bool divisor_was_negative,
+ DecimalClass* result) {
uint64_t r = 0;
- uint32_t result_array[5];
+ uint32_t* result_array = new uint32_t[dividend_length];
Review comment:
Thank you! Changed to compute that length as kDecimalArrayLength
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r524304063
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
Review comment:
I think it's ok as it is. We can revisit later if desired.
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r517611814
##########
File path: cpp/src/arrow/util/decimal_benchmark.cc
##########
@@ -158,6 +158,7 @@ static void BinaryMathOp256(benchmark::State& state) { // NOLINT non-const refe
for (auto _ : state) {
for (int x = 0; x < kValueSize; x += 5) {
benchmark::DoNotOptimize(v1[x + 2] * v2[x + 2]);
+ benchmark::DoNotOptimize(v1[x + 3] / v2[x + 3]);
Review comment:
As discussed offline, moved back the if statement in FillInArray for BasicDecimal128, the that the current benchmark result is:
BinaryMathOp128 152 ns 152 ns 4284240 items_per_second=65.6334M/s
BinaryMathOp256 163 ns 163 ns 4186744 items_per_second=61.4706M/s
Compared with the benchmark result without this pr:
BinaryMathOp128 154 ns 154 ns 4423113 items_per_second=64.9309M/s
BinaryMathOp256 35.4 ns 35.4 ns 18341932 items_per_second=282.487M/s
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r517700007
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,6 +395,31 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
+/// Expands the given big endian array of uint64_t into an array of uint32_t.
+/// The value of input array is expected to be positive. The result_array will
Review comment:
Done. Thank you!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -451,6 +463,27 @@ static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
return 1;
}
+/// Expands the given value into an array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the wasNegative
Review comment:
Done. Thank you!
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#issuecomment-729122567
Hmm, I borked this PR while trying to merge changes. Let me open a new one :-S
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r517611814
##########
File path: cpp/src/arrow/util/decimal_benchmark.cc
##########
@@ -158,6 +158,7 @@ static void BinaryMathOp256(benchmark::State& state) { // NOLINT non-const refe
for (auto _ : state) {
for (int x = 0; x < kValueSize; x += 5) {
benchmark::DoNotOptimize(v1[x + 2] * v2[x + 2]);
+ benchmark::DoNotOptimize(v1[x + 3] / v2[x + 3]);
Review comment:
As discussed offline, moved back the if statements in FillInArray for BasicDecimal128, the that the current benchmark result is:
BinaryMathOp128 152 ns 152 ns 4284240 items_per_second=65.6334M/s
BinaryMathOp256 163 ns 163 ns 4186744 items_per_second=61.4706M/s
Compared with the benchmark result without this pr:
BinaryMathOp128 154 ns 154 ns 4423113 items_per_second=64.9309M/s
BinaryMathOp256 35.4 ns 35.4 ns 18341932 items_per_second=282.487M/s
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#issuecomment-724071921
I didn't find any performance regression on an AMD Zen 2 CPU.
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r521719841
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
Review comment:
In this case, would you recommend to keep it this way, or changed back to one loop?
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r521719927
##########
File path: cpp/src/arrow/util/decimal_test.cc
##########
@@ -1296,6 +1296,56 @@ TEST(Decimal256Test, Multiply) {
}
}
+TEST(Decimal256Test, Divide) {
+ ASSERT_EQ(Decimal256(33), Decimal256(100) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(200) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(-20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256(66), Decimal256(-20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+
+ // Test some random numbers.
+ for (auto x : GetRandomNumbers<Int32Type>(16)) {
+ for (auto y : GetRandomNumbers<Int32Type>(16)) {
+ if (y == 0) {
+ continue;
+ }
+
+ Decimal256 result = Decimal256(x) / Decimal256(y);
+ ASSERT_EQ(Decimal256(static_cast<int64_t>(x) / y), result)
+ << " x: " << x << " y: " << y;
+ }
+ }
+
+ // Test some edge cases
+ for (auto x : std::vector<int128_t>{-INT64_MAX, -INT32_MAX, 0, INT32_MAX, INT64_MAX}) {
+ for (auto y : std::vector<int128_t>{-INT32_MAX, -32, -2, -1, 1, 2, 32, INT32_MAX}) {
Review comment:
Changed accordingly. Thank you!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -549,24 +603,27 @@ static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_len
return DecimalStatus::kSuccess;
}
-DecimalStatus BasicDecimal128::Divide(const BasicDecimal128& divisor,
- BasicDecimal128* result,
- BasicDecimal128* remainder) const {
+/// \brief Do a division where the divisor fits into a single 32 bit value.
+template <class DecimalClass>
+static inline DecimalStatus DecimalDivide(const DecimalClass& dividend,
+ const DecimalClass& divisor,
+ DecimalClass* result, DecimalClass* remainder) {
+ constexpr int64_t kDecimalArrayLength = sizeof(DecimalClass) / sizeof(uint32_t);
Review comment:
added DecimalClass::bit_width. Thx!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -549,24 +603,27 @@ static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_len
return DecimalStatus::kSuccess;
}
-DecimalStatus BasicDecimal128::Divide(const BasicDecimal128& divisor,
- BasicDecimal128* result,
- BasicDecimal128* remainder) const {
+/// \brief Do a division where the divisor fits into a single 32 bit value.
Review comment:
Thank you for catching this! This is a typo caused by copy & paste.
##########
File path: cpp/src/arrow/util/decimal_test.cc
##########
@@ -40,6 +40,9 @@ namespace arrow {
using internal::int128_t;
using internal::uint128_t;
+constexpr int128_t kInt128Max = (static_cast<int128_t>(INT64_MAX) << 64) - 1 +
+ 2 * (static_cast<int128_t>(INT64_MAX) + 1);
Review comment:
Changed accordingly. Thx!
----------------------------------------------------------------
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
[GitHub] [arrow] codecov-io commented on pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
codecov-io commented on pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#issuecomment-728347240
# [Codecov](https://codecov.io/gh/apache/arrow/pull/8542?src=pr&el=h1) Report
> Merging [#8542](https://codecov.io/gh/apache/arrow/pull/8542?src=pr&el=desc) (1df4d0c) into [master](https://codecov.io/gh/apache/arrow/commit/cf61fa1b8c1463f8f7c16e55c7275cac3111a0c2?el=desc) (cf61fa1) will **increase** coverage by `0.30%`.
> The diff coverage is `n/a`.
[](https://codecov.io/gh/apache/arrow/pull/8542?src=pr&el=tree)
```diff
@@ Coverage Diff @@
## master #8542 +/- ##
==========================================
+ Coverage 84.24% 84.54% +0.30%
==========================================
Files 152 177 +25
Lines 42175 43647 +1472
==========================================
+ Hits 35529 36902 +1373
- Misses 6646 6745 +99
```
| [Impacted Files](https://codecov.io/gh/apache/arrow/pull/8542?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [rust/parquet/src/arrow/converter.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9wYXJxdWV0L3NyYy9hcnJvdy9jb252ZXJ0ZXIucnM=) | `62.96% <0.00%> (-28.15%)` | :arrow_down: |
| [rust/parquet/src/util/io.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9wYXJxdWV0L3NyYy91dGlsL2lvLnJz) | `90.75% <0.00%> (-6.55%)` | :arrow_down: |
| [rust/parquet/src/arrow/array\_reader.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9wYXJxdWV0L3NyYy9hcnJvdy9hcnJheV9yZWFkZXIucnM=) | `76.88% <0.00%> (-5.59%)` | :arrow_down: |
| [rust/parquet/src/util/cursor.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9wYXJxdWV0L3NyYy91dGlsL2N1cnNvci5ycw==) | `84.78% <0.00%> (-4.97%)` | :arrow_down: |
| [rust/parquet/src/util/test\_common/rand\_gen.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9wYXJxdWV0L3NyYy91dGlsL3Rlc3RfY29tbW9uL3JhbmRfZ2VuLnJz) | `80.00% <0.00%> (-4.22%)` | :arrow_down: |
| [rust/datafusion/src/physical\_plan/group\_scalar.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9kYXRhZnVzaW9uL3NyYy9waHlzaWNhbF9wbGFuL2dyb3VwX3NjYWxhci5ycw==) | `69.23% <0.00%> (-3.85%)` | :arrow_down: |
| [rust/arrow/src/util/integration\_util.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9hcnJvdy9zcmMvdXRpbC9pbnRlZ3JhdGlvbl91dGlsLnJz) | `67.48% <0.00%> (-2.55%)` | :arrow_down: |
| [rust/arrow/src/ipc/reader.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9hcnJvdy9zcmMvaXBjL3JlYWRlci5ycw==) | `81.81% <0.00%> (-2.42%)` | :arrow_down: |
| [rust/arrow/src/util/buffered\_iterator.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9hcnJvdy9zcmMvdXRpbC9idWZmZXJlZF9pdGVyYXRvci5ycw==) | `92.85% <0.00%> (-2.39%)` | :arrow_down: |
| [rust/datafusion/src/optimizer/filter\_push\_down.rs](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree#diff-cnVzdC9kYXRhZnVzaW9uL3NyYy9vcHRpbWl6ZXIvZmlsdGVyX3B1c2hfZG93bi5ycw==) | `95.95% <0.00%> (-2.28%)` | :arrow_down: |
| ... and [129 more](https://codecov.io/gh/apache/arrow/pull/8542/diff?src=pr&el=tree-more) | |
------
[Continue to review full report at Codecov](https://codecov.io/gh/apache/arrow/pull/8542?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/apache/arrow/pull/8542?src=pr&el=footer). Last update [cf61fa1...1df4d0c](https://codecov.io/gh/apache/arrow/pull/8542?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r520841038
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
Review comment:
Thank you for your suggestion!
Changed this part of code to 2 loops, but there is a performance regression. Is there anything I can improve on the current code to help with the performance, or should we consider change back to one loop?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
Review comment:
Changed accordingly, thank you!
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -451,6 +467,25 @@ static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
return 1;
}
+/// Expands the given value into a big endian array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the was_negative
+/// flag will be set appropriately. The array will remove leading zeros from
+/// the value.
+/// \param array a big endian array of length 8 to set with the value
+/// \param was_negative a flag for whether the value was original negative
+/// \result the output length of the array
+static int64_t FillInArray(const BasicDecimal256& value, uint32_t* array,
+ bool& was_negative) {
+ BasicDecimal256 positive_value = value;
+ was_negative = false;
+ int64_t highest_bit = positive_value.little_endian_array()[3];
+ if (highest_bit < 0) {
Review comment:
BasicDecimal256 do have a sign method, but that method need shifting of int64_t value. Would you recommend adding a is_negatvie method?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,33 +395,49 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
-/// Expands the given value into an array of ints so that we can work on
-/// it. The array will be converted to an absolute value and the wasNegative
+/// Expands the given little endian array of uint64_t into a big endian array of
+/// uint32_t. The value of input array is expected to be non-negative. The result_array
+/// will remove leading zeros from the input array.
+/// \param value_array a little endian array to represent the value
+/// \param result_array a big endian array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(const std::array<uint64_t, N>& value_array,
+ uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (int64_t i = N - 1; i >= 0; i--) {
+ if (value_array[i] != 0) {
+ if (value_array[i] <= std::numeric_limits<uint32_t>::max()) {
+ result_array[next_index++] = static_cast<uint32_t>(value_array[i]);
+ i--;
+ }
+ for (int64_t j = i; j >= 0; j--) {
+ result_array[next_index++] = static_cast<uint32_t>(value_array[j] >> 32);
+ result_array[next_index++] = static_cast<uint32_t>(value_array[j]);
+ }
+ break;
+ }
+ }
+ return next_index;
+}
+
+/// Expands the given value into a big endian array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the was_negative
/// flag will be set appropriately. The array will remove leading zeros from
/// the value.
-/// \param array an array of length 4 to set with the value
+/// \param array a big endian array of length 4 to set with the value
/// \param was_negative a flag for whether the value was original negative
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
-
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.high_bits() < 0;
+ uint64_t high = static_cast<uint64_t>(abs_value.high_bits());
+ uint64_t low = abs_value.low_bits();
+
+ // FillInArray(std::array<uint64_t, N>& value_array, uint32_t* result_array) is not
+ // called here as the following code has better performance, to avoid regression on
+ // BasicDecimal128 Division.
if (high != 0) {
if (high > std::numeric_limits<uint32_t>::max()) {
Review comment:
This part of code is from the original version of Decimal128 division, to eliminate the leading zeros from the uint64_t value (high & low) and into uint32_t array.
So that to find the first non-negative uint32_t value, we check the high first, and then low value.
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,33 +395,49 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
-/// Expands the given value into an array of ints so that we can work on
-/// it. The array will be converted to an absolute value and the wasNegative
+/// Expands the given little endian array of uint64_t into a big endian array of
+/// uint32_t. The value of input array is expected to be non-negative. The result_array
+/// will remove leading zeros from the input array.
+/// \param value_array a little endian array to represent the value
+/// \param result_array a big endian array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(const std::array<uint64_t, N>& value_array,
+ uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (int64_t i = N - 1; i >= 0; i--) {
Review comment:
Thank you! Changed to use 2 separate loops.
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r521349186
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +527,60 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a little endian array of uint64_t from a big endian array of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (size_t i = 0; i < N; i++) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
Review comment:
Why is there still a test for `next_index < 0` here? Also, why are some indices `int64_t` and others `size_t`?
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r520841121
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -451,6 +467,25 @@ static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
return 1;
}
+/// Expands the given value into a big endian array of ints so that we can work on
+/// it. The array will be converted to an absolute value and the was_negative
+/// flag will be set appropriately. The array will remove leading zeros from
+/// the value.
+/// \param array a big endian array of length 8 to set with the value
+/// \param was_negative a flag for whether the value was original negative
+/// \result the output length of the array
+static int64_t FillInArray(const BasicDecimal256& value, uint32_t* array,
+ bool& was_negative) {
+ BasicDecimal256 positive_value = value;
+ was_negative = false;
+ int64_t highest_bit = positive_value.little_endian_array()[3];
+ if (highest_bit < 0) {
Review comment:
BasicDecimal256 do have a sign method, but that method need shifting of int64_t value. Added the IsNegavie method.
----------------------------------------------------------------
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
[GitHub] [arrow] pitrou commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r521362458
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -549,24 +603,27 @@ static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_len
return DecimalStatus::kSuccess;
}
-DecimalStatus BasicDecimal128::Divide(const BasicDecimal128& divisor,
- BasicDecimal128* result,
- BasicDecimal128* remainder) const {
+/// \brief Do a division where the divisor fits into a single 32 bit value.
+template <class DecimalClass>
+static inline DecimalStatus DecimalDivide(const DecimalClass& dividend,
+ const DecimalClass& divisor,
+ DecimalClass* result, DecimalClass* remainder) {
+ constexpr int64_t kDecimalArrayLength = sizeof(DecimalClass) / sizeof(uint32_t);
Review comment:
Use of `sizeof(DecimalClass)` here seems a bit fragile. Perhaps add/use `DecimalClass::bit_width`?
##########
File path: cpp/src/arrow/util/decimal_test.cc
##########
@@ -1296,6 +1296,56 @@ TEST(Decimal256Test, Multiply) {
}
}
+TEST(Decimal256Test, Divide) {
+ ASSERT_EQ(Decimal256(33), Decimal256(100) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(200) / Decimal256(3));
+ ASSERT_EQ(Decimal256(66), Decimal256(20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(-20100) / Decimal256(301));
+ ASSERT_EQ(Decimal256(-66), Decimal256(20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256(66), Decimal256(-20100) / Decimal256(-301));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("-269599466671506397946670150910580797473777870509761363"
+ "24636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("5192296858534827628530496329874417"));
+ ASSERT_EQ(Decimal256("-5192296858534827628530496329343552"),
+ Decimal256("2695994666715063979466701509105807974737778705097613632"
+ "4636208709184") /
+ Decimal256("-5192296858534827628530496329874417"));
+
+ // Test some random numbers.
+ for (auto x : GetRandomNumbers<Int32Type>(16)) {
+ for (auto y : GetRandomNumbers<Int32Type>(16)) {
+ if (y == 0) {
+ continue;
+ }
+
+ Decimal256 result = Decimal256(x) / Decimal256(y);
+ ASSERT_EQ(Decimal256(static_cast<int64_t>(x) / y), result)
+ << " x: " << x << " y: " << y;
+ }
+ }
+
+ // Test some edge cases
+ for (auto x : std::vector<int128_t>{-INT64_MAX, -INT32_MAX, 0, INT32_MAX, INT64_MAX}) {
+ for (auto y : std::vector<int128_t>{-INT32_MAX, -32, -2, -1, 1, 2, 32, INT32_MAX}) {
Review comment:
I would expect those additional values to also be part of `y`.
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -549,24 +603,27 @@ static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_len
return DecimalStatus::kSuccess;
}
-DecimalStatus BasicDecimal128::Divide(const BasicDecimal128& divisor,
- BasicDecimal128* result,
- BasicDecimal128* remainder) const {
+/// \brief Do a division where the divisor fits into a single 32 bit value.
Review comment:
The comment here seems wrong (the divisor doesn't fit into a single 32bit value).
##########
File path: cpp/src/arrow/util/decimal_test.cc
##########
@@ -40,6 +40,9 @@ namespace arrow {
using internal::int128_t;
using internal::uint128_t;
+constexpr int128_t kInt128Max = (static_cast<int128_t>(INT64_MAX) << 64) - 1 +
+ 2 * (static_cast<int128_t>(INT64_MAX) + 1);
Review comment:
Why not `(static_cast<int128_t>(INT64_MAX) << 64) + static_cast<int128_t>(UINT64_MAX)` ?
----------------------------------------------------------------
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
[GitHub] [arrow] Bei-z commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
Bei-z commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r516900753
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -575,8 +572,7 @@ template <class DecimalClass>
static DecimalStatus DecimalDivide(const DecimalClass& dividend,
const DecimalClass& divisor, DecimalClass* result,
DecimalClass* remainder) {
- static int64_t kDecimalArrayLength =
- std::is_same<DecimalClass, BasicDecimal128>::value ? 4 : 8;
+ static constexpr int64_t kDecimalArrayLength = sizeof(DecimalClass) / sizeof(uint32_t);
Review comment:
Changed accordingly. Thank you for pointing out!
----------------------------------------------------------------
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
[GitHub] [arrow] MingyuZhong commented on a change in pull request #8542: ARROW-10407: [C++] Add BasicDecimal256 Division Support
Posted by GitBox <gi...@apache.org>.
MingyuZhong commented on a change in pull request #8542:
URL: https://github.com/apache/arrow/pull/8542#discussion_r513015463
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -490,49 +501,59 @@ static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder
}
}
-/// \brief Build a BasicDecimal128 from a list of ints.
+/// \brief Build a big endian array of uint64_t from a list of uint32_t.
+template <size_t N>
+static DecimalStatus BuildFromArray(std::array<uint64_t, N>* result_array,
+ uint32_t* array, int64_t length) {
+ for (int64_t i = length - 2 * N - 1; i >= 0; i--) {
+ if (array[i] != 0) {
+ return DecimalStatus::kOverflow;
+ }
+ }
+ int64_t next_index = length - 1;
+ for (int64_t i = N - 1; i >= 0; i--) {
+ uint64_t lower_bits = (next_index < 0) ? 0 : array[next_index--];
+ (*result_array)[i] =
+ (next_index < 0)
+ ? lower_bits
+ : ((static_cast<uint64_t>(array[next_index--]) << 32) + lower_bits);
+ }
+ return DecimalStatus::kSuccess;
+}
+
+/// \brief Build a BasicDecimal128 from a list of uint32_t.
static DecimalStatus BuildFromArray(BasicDecimal128* value, uint32_t* array,
int64_t length) {
- switch (length) {
- case 0:
- *value = {static_cast<int64_t>(0)};
- break;
- case 1:
- *value = {static_cast<int64_t>(array[0])};
- break;
- case 2:
- *value = {static_cast<int64_t>(0),
- (static_cast<uint64_t>(array[0]) << 32) + array[1]};
- break;
- case 3:
- *value = {static_cast<int64_t>(array[0]),
- (static_cast<uint64_t>(array[1]) << 32) + array[2]};
- break;
- case 4:
- *value = {(static_cast<int64_t>(array[0]) << 32) + array[1],
- (static_cast<uint64_t>(array[2]) << 32) + array[3]};
- break;
- case 5:
- if (array[0] != 0) {
- return DecimalStatus::kOverflow;
- }
- *value = {(static_cast<int64_t>(array[1]) << 32) + array[2],
- (static_cast<uint64_t>(array[3]) << 32) + array[4]};
- break;
- default:
- return DecimalStatus::kOverflow;
+ std::array<uint64_t, 2> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
}
+ *value = {static_cast<int64_t>(result_array[0]), result_array[1]};
+ return DecimalStatus::kSuccess;
+}
+/// \brief Build a BasicDecimal256 from a list of uint32_t.
+static DecimalStatus BuildFromArray(BasicDecimal256* value, uint32_t* array,
+ int64_t length) {
+ std::array<uint64_t, 4> result_array;
+ auto status = BuildFromArray(&result_array, array, length);
+ if (status != DecimalStatus::kSuccess) {
+ return status;
+ }
+ std::reverse(result_array.begin(), result_array.end());
Review comment:
Cna you make BuildFromArray take little endian array so you don't need to reverse it?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -549,24 +570,28 @@ static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_len
return DecimalStatus::kSuccess;
}
-DecimalStatus BasicDecimal128::Divide(const BasicDecimal128& divisor,
- BasicDecimal128* result,
- BasicDecimal128* remainder) const {
+/// \brief Do a division where the divisor fits into a single 32 bit value.
+template <class DecimalClass>
+static DecimalStatus DecimalDivide(const DecimalClass& dividend,
+ const DecimalClass& divisor, DecimalClass* result,
+ DecimalClass* remainder) {
+ static int64_t kDecimalArrayLength =
+ std::is_same<DecimalClass, BasicDecimal128>::value ? 4 : 8;
Review comment:
Use sizeof(DecimalClass) / sizeof(uint64_t)?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -549,24 +570,28 @@ static DecimalStatus SingleDivide(const uint32_t* dividend, int64_t dividend_len
return DecimalStatus::kSuccess;
}
-DecimalStatus BasicDecimal128::Divide(const BasicDecimal128& divisor,
- BasicDecimal128* result,
- BasicDecimal128* remainder) const {
+/// \brief Do a division where the divisor fits into a single 32 bit value.
+template <class DecimalClass>
+static DecimalStatus DecimalDivide(const DecimalClass& dividend,
+ const DecimalClass& divisor, DecimalClass* result,
+ DecimalClass* remainder) {
+ static int64_t kDecimalArrayLength =
Review comment:
Please use constexpr
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -404,51 +432,33 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
/// \result the output length of the array
static int64_t FillInArray(const BasicDecimal128& value, uint32_t* array,
bool& was_negative) {
- uint64_t high;
- uint64_t low;
- const int64_t highbits = value.high_bits();
- const uint64_t lowbits = value.low_bits();
-
- if (highbits < 0) {
- low = ~lowbits + 1;
- high = static_cast<uint64_t>(~highbits);
- if (low == 0) {
- ++high;
- }
- was_negative = true;
- } else {
- low = lowbits;
- high = static_cast<uint64_t>(highbits);
- was_negative = false;
- }
-
- if (high != 0) {
- if (high > std::numeric_limits<uint32_t>::max()) {
- array[0] = static_cast<uint32_t>(high >> 32);
- array[1] = static_cast<uint32_t>(high);
- array[2] = static_cast<uint32_t>(low >> 32);
- array[3] = static_cast<uint32_t>(low);
- return 4;
- }
-
- array[0] = static_cast<uint32_t>(high);
- array[1] = static_cast<uint32_t>(low >> 32);
- array[2] = static_cast<uint32_t>(low);
- return 3;
- }
-
- if (low >= std::numeric_limits<uint32_t>::max()) {
- array[0] = static_cast<uint32_t>(low >> 32);
- array[1] = static_cast<uint32_t>(low);
- return 2;
- }
+ BasicDecimal128 abs_value = BasicDecimal128::Abs(value);
+ was_negative = value.Sign() < 0;
Review comment:
value.high_bits() < 0?
##########
File path: cpp/src/arrow/util/decimal_benchmark.cc
##########
@@ -158,6 +158,7 @@ static void BinaryMathOp256(benchmark::State& state) { // NOLINT non-const refe
for (auto _ : state) {
for (int x = 0; x < kValueSize; x += 5) {
benchmark::DoNotOptimize(v1[x + 2] * v2[x + 2]);
+ benchmark::DoNotOptimize(v1[x + 3] / v2[x + 3]);
Review comment:
Did you verify that your change didn't make Decimal128 slower? What's the performance metrics for Decimal256 before and after your change (please add it to the PR description)?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,6 +395,34 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
+/// Expands the given big endian array of uint64_t into an array of uint32_t.
+/// The value of input array is expected to be positive. The result_array will
+/// remove leading zeros from the input array.
+/// \param value_array an big endian array to represent the value
+/// \param result_array an array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(std::array<uint64_t, N>& value_array, uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (size_t i = 0; i < N; i++) {
+ if (value_array[i] == 0) {
+ if (next_index != 0) {
+ result_array[next_index++] = 0;
+ result_array[next_index++] = 0;
+ }
+ } else if (value_array[i] <= std::numeric_limits<uint32_t>::max()) {
Review comment:
Why do we need this special case?
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -479,7 +489,8 @@ static void ShiftArrayRight(uint32_t* array, int64_t length, int64_t bits) {
/// \brief Fix the signs of the result and remainder at the end of the division based on
/// the signs of the dividend and divisor.
-static void FixDivisionSigns(BasicDecimal128* result, BasicDecimal128* remainder,
+template <class DecimalClass>
+static void FixDivisionSigns(DecimalClass* result, DecimalClass* remainder,
Review comment:
I think this method should be declared as inline.
##########
File path: cpp/src/arrow/util/basic_decimal.cc
##########
@@ -395,6 +395,34 @@ BasicDecimal128& BasicDecimal128::operator*=(const BasicDecimal128& right) {
return *this;
}
+/// Expands the given big endian array of uint64_t into an array of uint32_t.
+/// The value of input array is expected to be positive. The result_array will
+/// remove leading zeros from the input array.
+/// \param value_array an big endian array to represent the value
+/// \param result_array an array of length N*2 to set with the value
+/// \result the output length of the array
+template <size_t N>
+static int64_t FillInArray(std::array<uint64_t, N>& value_array, uint32_t* result_array) {
+ int64_t next_index = 0;
+ for (size_t i = 0; i < N; i++) {
+ if (value_array[i] == 0) {
Review comment:
For efficiency, once we find a non-zero element, the subsequent iterations don't need to check zero again. So the following would be better:
```
for (size_t i = 0; i < N; i++) {
if (value_array[i] != 0) {
for (size_t j = i; j < N; j++ ) {
...
}
break;
}
}
```
----------------------------------------------------------------
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