[ https://issues.apache.org/jira/browse/HBASE-26566?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Yutong Xiao updated HBASE-26566: -------------------------------- Description: Found current estimate E step in OrderedBytes is to search step by step in loops. We can directly calculate the length to move the point and let the time complexity become to O(1). >From the comments of the method encodeNumericLarge: {panel:title=encodeNumericLarge} Encode the large magnitude floating point number *val* using the key encoding. The caller guarantees that *val* will be finite and abs({*}val{*}) >= 1.0. A floating point value is encoded as an integer exponent *E* and a mantissa {*}M{*}. The original value is equal to {*}(M * 100^E){*}. *E* is set to the smallest value possible without making *M* greater than or equal to 1.0. Each centimal digit of the mantissa is stored in a byte. If the value of the centimal digit is *X* (hence X>=0 and X<=99) then the byte value will be 2*X+1 for every byte of the mantissa, except for the last byte which will be 2*X+0. The mantissa must be the minimum number of bytes necessary to represent the value; trailing *X==0* digits are omitted. This means that the mantissa will never contain a byte with the value 0x00. The function could be divided into 4 steps: # Confirm the sign (Negative or not) # Normalise the abs({*}val{*}), transformed to *(M * 100^E)* # Encode *M* by peeling off centimal digit and # Encode *X*{panel} At the step 2, we normalise abs(*val*) and determine the exponent *E*. The current implementation is : {code:java} while (abs.compareTo(E32) >= 0 && e <= 350) { abs = abs.movePointLeft(32); e +=16; } while (abs.compareTo(E8) >= 0 && e <= 350) { abs = abs.movePointLeft(8); e+= 4; } while (abs.compareTo(BigDecimal.ONE) >= 0 && e <= 350) { abs = abs.movePointLeft(2); e++; } {code} Which just move the point of abs(*val*), (which is in form yyyy.zzzz, where y & z are digits, e.g. 1000.0001) from right to left step by step, until abs(val) < 1. We can find that e is the half of point moved length. So that we could save the above three loops and calculate the moved length and e directly. My implementation: {code:java} // This is the number of digits of the Integer part of abs(val) when val > 10 int integerDigits = abs.precision() - abs.scale(); // If length is odd, from the last loop above, we actually moved one more step forward. int lengthToMoveLeft = integerDigits % 2 == 0 ? integerDigits : integerDigits + 1; e = lengthToMoveLeft / 2; // The edge condition. if (e > 350) { e = 351; lengthToMoveLeft = 702; } abs = abs.movePointLeft(lengthToMoveLeft); {code} In this case, we only move the point once. The time complexity is O(1). Same idea to the method of encodeNumericSmall. was: Found current estimate E step in OrderedBytes is to search step by step in loops. We can directly calculate the length to move the point and let the time complexity become to O(1). >From the comments of the method encodeNumericLarge: {panel:title=encodeNumericLarge} Encode the large magnitude floating point number *val* using the key encoding. The caller guarantees that *val* will be finite and abs({*}val{*}) >= 1.0. A floating point value is encoded as an integer exponent *E* and a mantissa {*}M{*}. The original value is equal to {*}(M * 100^E){*}. *E* is set to the smallest value possible without making *M* greater than or equal to 1.0. Each centimal digit of the mantissa is stored in a byte. If the value of the centimal digit is *X* (hence X>=0 and X<=99) then the byte value will be 2*X+1 for every byte of the mantissa, except for the last byte which will be 2*X+0. The mantissa must be the minimum number of bytes necessary to represent the value; trailing *X==0* digits are omitted. This means that the mantissa will never contain a byte with the value 0x00. The function could be divided into 3 steps: # Confirm the sign (Negative or not) # Normalise the abs({*}val{*}), transformed to *(M * 100^E)* # Encode *M* by peeling off centimal digit and *X*{panel} At the step 2, we normalise abs(*val*) and determine the exponent *E*. The current implementation is : {code:java} while (abs.compareTo(E32) >= 0 && e <= 350) { abs = abs.movePointLeft(32); e +=16; } while (abs.compareTo(E8) >= 0 && e <= 350) { abs = abs.movePointLeft(8); e+= 4; } while (abs.compareTo(BigDecimal.ONE) >= 0 && e <= 350) { abs = abs.movePointLeft(2); e++; } {code} Which just move the point of abs(*val*), (which is in form yyyy.zzzz, where y & z are digits, e.g. 1000.0001) from right to left step by step, until abs(val) < 1. We can find that e is the half of point moved length. So that we could save the above three loops and calculate the moved length and e directly. My implementation: {code:java} // This is the number of digits of the Integer part of abs(val) when val > 10 int integerDigits = abs.precision() - abs.scale(); // If length is odd, from the last loop above, we actually moved one more step forward. int lengthToMoveLeft = integerDigits % 2 == 0 ? integerDigits : integerDigits + 1; e = lengthToMoveLeft / 2; // The edge condition. if (e > 350) { e = 351; lengthToMoveLeft = 702; } abs = abs.movePointLeft(lengthToMoveLeft); {code} In this case, we only move the point once. The time complexity is O(1). Same idea to the method of encodeNumericSmall. > Optimize determine E step in OrderedBytes > ----------------------------------------- > > Key: HBASE-26566 > URL: https://issues.apache.org/jira/browse/HBASE-26566 > Project: HBase > Issue Type: Task > Components: Performance > Reporter: Yutong Xiao > Assignee: Yutong Xiao > Priority: Major > > Found current estimate E step in OrderedBytes is to search step by step in > loops. We can directly calculate the length to move the point and let the > time complexity become to O(1). > From the comments of the method encodeNumericLarge: > {panel:title=encodeNumericLarge} > Encode the large magnitude floating point number *val* using the key > encoding. The caller guarantees that *val* will be > finite and abs({*}val{*}) >= 1.0. > A floating point value is encoded as an integer exponent *E* and a mantissa > {*}M{*}. The original value is equal to {*}(M * 100^E){*}. *E* is set to the > smallest value possible without making *M* greater than or equal to 1.0. > Each centimal digit of the mantissa is stored in a byte. If the value of the > centimal digit is *X* (hence X>=0 and X<=99) then the byte value will be > 2*X+1 for every byte of the mantissa, except for the last byte which will be > 2*X+0. The mantissa must be the minimum number of bytes necessary to > represent the value; trailing *X==0* digits are omitted. This means that the > mantissa will never contain a byte with the > value 0x00. > The function could be divided into 4 steps: > # Confirm the sign (Negative or not) > # Normalise the abs({*}val{*}), transformed to *(M * 100^E)* > # Encode *M* by peeling off centimal digit and > # Encode *X*{panel} > At the step 2, we normalise abs(*val*) and determine the exponent *E*. > The current implementation is : > {code:java} > while (abs.compareTo(E32) >= 0 && e <= 350) { abs = > abs.movePointLeft(32); e +=16; } > while (abs.compareTo(E8) >= 0 && e <= 350) { abs = abs.movePointLeft(8); > e+= 4; } > while (abs.compareTo(BigDecimal.ONE) >= 0 && e <= 350) { abs = > abs.movePointLeft(2); e++; } > {code} > Which just move the point of abs(*val*), (which is in form yyyy.zzzz, where y > & z are digits, e.g. 1000.0001) from right to left step by step, until > abs(val) < 1. We can find that e is the half of point moved length. So that > we could save the above three loops and calculate the moved length and e > directly. > My implementation: > {code:java} > // This is the number of digits of the Integer part of abs(val) when val > > 10 > int integerDigits = abs.precision() - abs.scale(); > // If length is odd, from the last loop above, we actually moved one more > step forward. > int lengthToMoveLeft = integerDigits % 2 == 0 ? integerDigits : > integerDigits + 1; > e = lengthToMoveLeft / 2; > // The edge condition. > if (e > 350) { > e = 351; > lengthToMoveLeft = 702; > } > abs = abs.movePointLeft(lengthToMoveLeft); > {code} > In this case, we only move the point once. The time complexity is O(1). > Same idea to the method of encodeNumericSmall. -- This message was sent by Atlassian Jira (v8.20.1#820001)