LUCENE-8598: Improve field updates packed values#521
Conversation
| import org.apache.lucene.util.NullInfoStream; | ||
| import org.apache.lucene.util.TestUtil; | ||
|
|
||
| public class Benchmark { |
There was a problem hiding this comment.
NOTE: I included this benchmark in the initial version to show what I benchmarked
jpountz
left a comment
There was a problem hiding this comment.
It's interesting that you found out that most of the time is spent with packed ints when sorting, likely because of swaps: the sorting impl that is being used (InPlaceMergeSorter) is the impl that performs the higher number of swaps due to the constraint to run in-place. Maybe we should look into spending a bit more memory on sorting to avoid having so many swaps, eg. with TimSorter (see ArrayTimSorter for an example).
| values = new PagedGrowableWriter(1, PAGE_SIZE, 1, PackedInts.FAST); | ||
| assert minValue <= maxValue : "minValue must be <= maxValue [" + minValue + " > " + maxValue + "]"; | ||
| long max = maxValue - minValue; | ||
| if (max < 0) { // pretty large range - fall back to growable writer |
There was a problem hiding this comment.
It feels a bit weird to optimize when using 64 bits per value but not 63, or 62? Not sure if you are aware but PackedInts.unsignedBitsRequired can help avoid special-casing when max-min overflows.
| this.minValue = 0; | ||
| } else { | ||
| int bitsPerValue = PackedInts.bitsRequired(max); | ||
| values = new PagedMutable(1, PAGE_SIZE, bitsPerValue, PackedInts.DEFAULT); |
There was a problem hiding this comment.
since we are sorting in the end, all pages will likely have the same number of bits per value in the end anyway, should we move to PackedInts.getMutable instead?
There was a problem hiding this comment.
not sure we can since we don't know how many values we actually have?
regarding TimSorter, it looks pretty complex and I wonder how well it would work with the subclasses and what needs to be implemented. Maybe we can explore this in a separate change? |
jpountz
left a comment
There was a problem hiding this comment.
Right it adds complexity. Happy to look into this in a follow-up. LGTM
7b82abf to
d5c62e7
Compare
lucene/CHANGES.txt
Outdated
| based datastructures. (Simon Willnauer, Mike McCandless, Shai Erera, Adrien Grant) | ||
|
|
||
| * LUCENE-8598: Moved to the default accepted overhead ratio for packet ints in DocValuesFieldUpdats | ||
| yields an up-to 4x performance improvement when applying doc values updates. (Simon Willnauer, Adrien Grant) |
DocValuesFieldUpdats are using compact settings for packet ints that causes dramatic slowdowns when the updates are finished and sorted. Moving to the default accepted overhead ratio yields up to 4x improvements in applying updates. This change also improves the packing of numeric values since we know the value range in advance and can choose a different packing scheme in such a case. Overall this change yields a good performance improvement since 99% of the times of applying DV field updates are spend in the sort method which essentially makes applying the updates 4x faster.
d5c62e7 to
0650f99
Compare
DocValuesFieldUpdats are using compact settings for packet ints that causes
dramatic slowdowns when the updates are finished and sorted. Moving to the default
accepted overhead ratio yields up to 4x improvements in applying updates. This change
also improves the packing of numeric values since we know the value range in advance and
can choose a different packing scheme in such a case.
Overall this change yields a good performance improvement since 99% of the times of applying
DV field updates are spend in the sort method which essentially makes applying the updates
4x faster.