[
https://issues.apache.org/jira/browse/HBASE-26566?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Yutong Xiao updated HBASE-26566:
--------------------------------
Attachment: JmhBenchmark.java
> 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
> Attachments: Benchmark.log, JmhBenchmark.java
>
>
> 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.
> In the loop body, the increment of e is always the half of steps the point
> moved to left. (step=32, deltaE=16), (step=8, deltaE=4), (step=2, deltaE=1)
> As e starts from 0, the value of e must be the half of the total moved steps
> at last.
> 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 of the Integer part 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)
