[
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).
Current implementation in encodeNumericLarge:
{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}
We start with e == 0 and move the point to left with 2e each time. The time
complexity is O(\n).
>From the loop above we can see that for large decimal, we can just move the
>point to left until abs < BigDecimal.ONE.
This can be directly calculated and we can also directly calculated the e (just
the half of the steps).
In this case, we only need move the point once.
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).
Current implementation in encodeNumericLarge:
{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}
We start with e == 0 and move the point to left with 2e each time. The time
complexity is O(\n).
>From the loop above we can see that for large decimal, we can just move the
>point to left until abs < BigDecimal.ONE.
This can be directly calculated and we can also directly calculated the e (just
the half of the steps).
> 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).
> Current implementation in encodeNumericLarge:
> {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}
> We start with e == 0 and move the point to left with 2e each time. The time
> complexity is O(\n).
> From the loop above we can see that for large decimal, we can just move the
> point to left until abs < BigDecimal.ONE.
> This can be directly calculated and we can also directly calculated the e
> (just the half of the steps).
> In this case, we only need move the point once.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
