You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Adrien Grand (JIRA)" <ji...@apache.org> on 2016/05/17 10:23:13 UTC
[jira] [Updated] (LUCENE-7258) Tune DocIdSetBuilder allocation rate
[ https://issues.apache.org/jira/browse/LUCENE-7258?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Adrien Grand updated LUCENE-7258:
---------------------------------
Attachment: LUCENE-7258-expanding.patch
Out of curiosity, I played with Solr's ExpandingIntArray approach that consists of accumulating buffers of exponentially increasing sizes. In the attached patch, the size of a new buffer is equal to the sum of the sizes of the buffers that have been allocated so far, so in terms of growth rate it is similar to a scaling factor of 2. Since we need to reserve space up-front, I added a protection that resizes the current array rather than adding a new one if it is less than 7/8 full, otherwise it could leave a non negligible amount of wasted space (eg. if you always call grow(remainingNumberOfSlotsInCurrentBuffer + 1) and then only call add() once).
Interestingly it performed significantly better than the current approach, so maybe we should switch to it?
||Benchmark||Poly 5||Box|
||scaling factor = 9/8 (like in master)|48.5|65.6|
||scaling factor = 5/4|49.2|67.6|
||scaling factor = 3/2|50.2|69.1|
||scaling factor = 2|50.8|69.6|
||ExpandingIntArray-style|51.6|71.0|
||MatchingPoints|51.8|71.7|
> Tune DocIdSetBuilder allocation rate
> ------------------------------------
>
> Key: LUCENE-7258
> URL: https://issues.apache.org/jira/browse/LUCENE-7258
> Project: Lucene - Core
> Issue Type: Improvement
> Components: modules/spatial
> Reporter: Jeff Wartes
> Attachments: LUCENE-7258-Tune-memory-allocation-rate-for-Intersec.patch, LUCENE-7258-Tune-memory-allocation-rate-for-Intersec.patch, LUCENE-7258-expanding.patch, allocation_plot.jpg
>
>
> LUCENE-7211 converted IntersectsPrefixTreeQuery to use DocIdSetBuilder, but didn't actually reduce garbage generation for my Solr index.
> Since something like 40% of my garbage (by space) is now attributed to DocIdSetBuilder.growBuffer, I charted a few different allocation strategies to see if I could tune things more.
> See here: http://i.imgur.com/7sXLAYv.jpg
> The jump-then-flatline at the right would be where DocIdSetBuilder gives up and allocates a FixedBitSet for a 100M-doc index. (The 1M-doc index curve/cutoff looked similar)
> Perhaps unsurprisingly, the 1/8th growth factor in ArrayUtil.oversize is terrible from an allocation standpoint if you're doing a lot of expansions, and is especially terrible when used to build a short-lived data structure like this one.
> By the time it goes with the FBS, it's allocated around twice as much memory for the buffer as it would have needed for just the FBS.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org