[LUCENE-7258] Tune DocIdSetBuilder allocation rate

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 6.1, 7.0
• Component/s: modules/spatial
• Lucene Fields: New
• Assignee: Unassigned
• Reporter: Jeff Wartes
• Created: 26/Apr/16 18:09
• Updated: 28/Aug/22 14:57
• Resolved: 23/May/16 07:29

Description

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.