imply-cheddar commented on code in PR #13086:
URL: https://github.com/apache/druid/pull/13086#discussion_r974812934
##########
extensions-contrib/compressed-bigdecimal/src/main/java/org/apache/druid/compressedbigdecimal/CompressedBigDecimal.java:
##########
@@ -271,16 +273,82 @@ protected static <S> int signumInternal(int size, S rhs,
ToIntBiFunction<S, Inte
}
}
- /* (non-Javadoc)
- * @see java.lang.Comparable#compareTo(java.lang.Object)
- */
@Override
public int compareTo(CompressedBigDecimal o)
+ {
+ return compareTo(o, false);
+ }
+
+ public int compareTo(CompressedBigDecimal o, boolean expectOptimized)
{
if (super.equals(o)) {
return 0;
+ } else if (getScale() == o.getScale()) {
+ return directCompareCompressedBigDecimal(this, o,
Math.max(getArraySize(), o.getArraySize()));
+ } else {
+ if (expectOptimized) {
+ throw new IAE("expected optimized path");
+ }
+
+ return this.toBigDecimal().compareTo(o.toBigDecimal());
+ }
+ }
+
+ /**
+ * performs a subtraction of lhs - rhs to compare elements
+ *
+ * @param lhs
+ * @param rhs
+ * @param length - length of both lhs and rhs
+ * @return
+ */
+ private static int directCompareCompressedBigDecimal(CompressedBigDecimal
lhs, CompressedBigDecimal rhs, int length)
+ {
+ int[] result = new int[length];
+ int borrow = 0;
+ // for each argument, if it's negative, our extension will be
Integer.MIN_VALUE (all 1s). else, all 0s
+ long lhsExtension = lhs.getArrayEntry(lhs.getArraySize() - 1) < 0 ?
INT_MASK : 0;
+ long rhsExtension = rhs.getArrayEntry(rhs.getArraySize() - 1) < 0 ?
INT_MASK : 0;
+
+ for (int i = 0; i < length; i++) {
+ // "dynamically" extend lhs/rhs if it's shorter than the other using
extensions computed above
+ long leftElement = i < lhs.getArraySize() ? (INT_MASK &
lhs.getArrayEntry(i)) : lhsExtension;
+ long rightElement = i < rhs.getArraySize() ? (INT_MASK &
rhs.getArrayEntry(i)) : rhsExtension;
+ long resultElement = leftElement - rightElement - borrow;
Review Comment:
Is there room for overflow from this? I'm asking without thinking about it,
so "no" is a totally possible answer.
##########
extensions-contrib/compressed-bigdecimal/src/main/java/org/apache/druid/compressedbigdecimal/CompressedBigDecimal.java:
##########
@@ -271,16 +273,82 @@ protected static <S> int signumInternal(int size, S rhs,
ToIntBiFunction<S, Inte
}
}
- /* (non-Javadoc)
- * @see java.lang.Comparable#compareTo(java.lang.Object)
- */
@Override
public int compareTo(CompressedBigDecimal o)
+ {
+ return compareTo(o, false);
+ }
+
+ public int compareTo(CompressedBigDecimal o, boolean expectOptimized)
{
if (super.equals(o)) {
return 0;
+ } else if (getScale() == o.getScale()) {
+ return directCompareCompressedBigDecimal(this, o,
Math.max(getArraySize(), o.getArraySize()));
+ } else {
+ if (expectOptimized) {
+ throw new IAE("expected optimized path");
+ }
+
+ return this.toBigDecimal().compareTo(o.toBigDecimal());
+ }
+ }
+
+ /**
+ * performs a subtraction of lhs - rhs to compare elements
+ *
+ * @param lhs
+ * @param rhs
+ * @param length - length of both lhs and rhs
+ * @return
+ */
+ private static int directCompareCompressedBigDecimal(CompressedBigDecimal
lhs, CompressedBigDecimal rhs, int length)
+ {
+ int[] result = new int[length];
+ int borrow = 0;
+ // for each argument, if it's negative, our extension will be
Integer.MIN_VALUE (all 1s). else, all 0s
+ long lhsExtension = lhs.getArrayEntry(lhs.getArraySize() - 1) < 0 ?
INT_MASK : 0;
+ long rhsExtension = rhs.getArrayEntry(rhs.getArraySize() - 1) < 0 ?
INT_MASK : 0;
+
+ for (int i = 0; i < length; i++) {
+ // "dynamically" extend lhs/rhs if it's shorter than the other using
extensions computed above
+ long leftElement = i < lhs.getArraySize() ? (INT_MASK &
lhs.getArrayEntry(i)) : lhsExtension;
+ long rightElement = i < rhs.getArraySize() ? (INT_MASK &
rhs.getArrayEntry(i)) : rhsExtension;
+ long resultElement = leftElement - rightElement - borrow;
+
+ borrow = 0;
+
+ if (resultElement < 0) {
+ borrow = 1;
+ resultElement += 1L << 32;
+ }
+
+ result[i] = (int) resultElement;
+ }
+
+ int signum = signumInternalArray(result.length, result);
+
+ return signum;
+ }
+
+ /**
+ * specialized signumInternal to avoid meagmorphic callsite in
signumInternal's array accessor lambda
+ */
+ private static int signumInternalArray(int size, int[] valueArray)
+ {
+ if (valueArray[size - 1] < 0) {
+ return -1;
+ } else {
+ int agg = 0;
+ for (int i = 0; i < size; ++i) {
+ agg |= valueArray[i];
+ }
+ if (agg == 0) {
Review Comment:
Totally random, probably over-optimization (if even an optimization), but it
strikes me that you could keep track of whether the `result` values are always
0 while doing the subtraction and then you would already know if they are
already 0 without needing to pass over the valueArray again.
##########
extensions-contrib/compressed-bigdecimal/src/main/java/org/apache/druid/compressedbigdecimal/CompressedBigDecimal.java:
##########
@@ -271,16 +273,82 @@ protected static <S> int signumInternal(int size, S rhs,
ToIntBiFunction<S, Inte
}
}
- /* (non-Javadoc)
- * @see java.lang.Comparable#compareTo(java.lang.Object)
- */
@Override
public int compareTo(CompressedBigDecimal o)
+ {
+ return compareTo(o, false);
+ }
+
+ public int compareTo(CompressedBigDecimal o, boolean expectOptimized)
{
if (super.equals(o)) {
return 0;
+ } else if (getScale() == o.getScale()) {
+ return directCompareCompressedBigDecimal(this, o,
Math.max(getArraySize(), o.getArraySize()));
+ } else {
+ if (expectOptimized) {
+ throw new IAE("expected optimized path");
+ }
+
+ return this.toBigDecimal().compareTo(o.toBigDecimal());
+ }
+ }
+
+ /**
+ * performs a subtraction of lhs - rhs to compare elements
+ *
+ * @param lhs
+ * @param rhs
+ * @param length - length of both lhs and rhs
+ * @return
+ */
+ private static int directCompareCompressedBigDecimal(CompressedBigDecimal
lhs, CompressedBigDecimal rhs, int length)
+ {
+ int[] result = new int[length];
+ int borrow = 0;
+ // for each argument, if it's negative, our extension will be
Integer.MIN_VALUE (all 1s). else, all 0s
+ long lhsExtension = lhs.getArrayEntry(lhs.getArraySize() - 1) < 0 ?
INT_MASK : 0;
+ long rhsExtension = rhs.getArrayEntry(rhs.getArraySize() - 1) < 0 ?
INT_MASK : 0;
+
+ for (int i = 0; i < length; i++) {
+ // "dynamically" extend lhs/rhs if it's shorter than the other using
extensions computed above
+ long leftElement = i < lhs.getArraySize() ? (INT_MASK &
lhs.getArrayEntry(i)) : lhsExtension;
+ long rightElement = i < rhs.getArraySize() ? (INT_MASK &
rhs.getArrayEntry(i)) : rhsExtension;
+ long resultElement = leftElement - rightElement - borrow;
+
+ borrow = 0;
+
+ if (resultElement < 0) {
+ borrow = 1;
+ resultElement += 1L << 32;
+ }
+
+ result[i] = (int) resultElement;
+ }
+
+ int signum = signumInternalArray(result.length, result);
+
+ return signum;
+ }
+
+ /**
+ * specialized signumInternal to avoid meagmorphic callsite in
signumInternal's array accessor lambda
Review Comment:
typo: megamorphic
##########
extensions-contrib/compressed-bigdecimal/src/main/java/org/apache/druid/compressedbigdecimal/CompressedBigDecimal.java:
##########
@@ -271,16 +273,82 @@ protected static <S> int signumInternal(int size, S rhs,
ToIntBiFunction<S, Inte
}
}
- /* (non-Javadoc)
- * @see java.lang.Comparable#compareTo(java.lang.Object)
- */
@Override
public int compareTo(CompressedBigDecimal o)
+ {
+ return compareTo(o, false);
+ }
+
+ public int compareTo(CompressedBigDecimal o, boolean expectOptimized)
{
if (super.equals(o)) {
return 0;
+ } else if (getScale() == o.getScale()) {
+ return directCompareCompressedBigDecimal(this, o,
Math.max(getArraySize(), o.getArraySize()));
Review Comment:
Is there a reason to do this `max` here instead of as the first thing after
entering into the `directCompareCompressedBigDecimal` call?
--
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.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
