You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by GitBox <gi...@apache.org> on 2022/09/20 01:49:35 UTC
[GitHub] [druid] imply-cheddar commented on a diff in pull request #13086: Optimize CompressedBigDecimal compareTo()
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: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org