You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "ASF subversion and git services (Jira)" <ji...@apache.org> on 2021/05/14 07:34:00 UTC
[jira] [Commented] (LUCENE-9932) Performance improvement for BKD
index building
[ https://issues.apache.org/jira/browse/LUCENE-9932?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17344379#comment-17344379 ]
ASF subversion and git services commented on LUCENE-9932:
---------------------------------------------------------
Commit fd4b3c81d517e0cf9d804211b0785721cdfd1a6c in lucene's branch refs/heads/main from neoReMinD
[ https://gitbox.apache.org/repos/asf?p=lucene.git;h=fd4b3c8 ]
LUCENE-9932: Performance improvement for BKD index building (#91)
> Performance improvement for BKD index building
> ----------------------------------------------
>
> Key: LUCENE-9932
> URL: https://issues.apache.org/jira/browse/LUCENE-9932
> Project: Lucene - Core
> Issue Type: Improvement
> Components: core/index
> Affects Versions: 8.8.2
> Reporter: neoremind
> Priority: Critical
> Attachments: benchmark_data.png, flame-graph.png, refined-code-benchmark.png, refined-code-benchmark2.png
>
> Time Spent: 12h
> Remaining Estimate: 0h
>
> In BKD index building, the input bytes must be sorted before calling BKD writer related API. The sorting method leverages MSB Radix Sort algorithm, and the comparing method takes both the bytes itself and the DocId, but in real cases, DocIds are usually monotonically increasing. This could yield one possible performance enhancer. I found this enhancement when I dig into one performance issue in our system. Then I research on the possible solution.
> DocId is usually increased by one when building index in a thread-safe way, by assuming such condition, the comparing method can eliminate the unnecessary comparing input - DocId, only leave the bytes itself to compare. In order to do so, MSB radix sorting and its fallback sorting method must be *stable*, so that when elements are the same, the sorting method maintains its original order when added, which makes DocId still monotonically increasing. To make MSB Radix Sort stable, it needs a trivial update; to make fallback sort table, use merge sort instead of quick sort. Meanwhile, there should introduce a switch which is able to turn the stable option on or off.
> To validate how much performance could be gained. I make a benchmark taking down only the time elapsed in _MutablePointsReaderUtils.sort_ stage.
> *Test environment:*
> MacBook Pro (Retina, 15-inch, Mid 2015), 2.2 GHz Intel Core i7, 16 GB 1600 MHz DDR3
> *Java version:*
> java version "1.8.0_161"
> Java(TM) SE Runtime Environment (build 1.8.0_161-b12)
> Java HotSpot(TM) 64-Bit Server VM (build 25.161-b12, mixed mode)
> *Testcase:*
> bytesPerDim = [1, 2, 3, 4, 8, 16, 32]
> dim = 1
> doc num = 2,000,000
> warm up 5 time, run 10 times to calculate average time used.
> *Result:*
>
> ||bytesPerDim\scenario||disable sort doc id (PR branch)||enable sort doc id (master branch)||
> |1|30989.594 us|1151149.9 us|
> |2|313469.47 us|1115595.1 us|
> |3|844617.8 us|1465465.1 us|
> |4|1350946.8 us|1465465.1 us|
> |8|1344814.6 us|1458115.5 us|
> |16|1344516.6 us|1459849.6 us|
> |32|1386847.8 us|1583097.5 us|
> !benchmark_data.png|width=580,height=283!
> Result shows that, by disabling sort DocId, sorting runs 1.73x to 37x faster when there are many duplicate bytes (bytesPerDim = 1 or 2 or 3). When data cardinality is high (bytesPerDim >= 4, test cases will generate random bytes which are more scatter, not likely to be duplicate), the performance does not go backward, still a little better.
> In conclusion, in the end to end process for building BKD index, which relies on BKDWriter for some data types, performance could be better by ignoring DocId if they are already monotonically increasing.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org