You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "original-brownbear (via GitHub)" <gi...@apache.org> on 2024/10/20 02:44:41 UTC
[PR] Speedup OrderIntervalsSource some more [lucene]
original-brownbear opened a new pull request, #13937:
URL: https://github.com/apache/lucene/pull/13937
Follow-up to #13871, getting another speedup from relatively trivial changes:
* avoid redundant `end()` call by directly storing the end value for sub-iterator that we don't use for anything else
* also save most `get(...)` calls for this sub-iterator
* avoid redundant `start()` call by grabbing `start()` directly from `nextInterval`
* replace `getFirst()` with `get(0)`, it looks nice but has needless overhead in my testing (not sure why, but profiling clearly shows it to be slower, maybe just a result of having `get()`'s code hot in the cache with a higher likelihood or something esoteric like that)
* avoid using an iterator for loop for a random access list, this is probably the biggest win in this PR
wikimedium results:
```
TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff p-value
BrowseMonthTaxoFacets 12.36 (29.8%) 11.55 (35.5%) -6.5% ( -55% - 83%) 0.440
IntNRQ 82.82 (9.6%) 83.04 (10.6%) 0.3% ( -18% - 22%) 0.919
HighTermTitleBDVSort 19.91 (8.5%) 19.99 (9.0%) 0.4% ( -15% - 19%) 0.857
BrowseDayOfYearTaxoFacets 5.21 (7.2%) 5.26 (11.5%) 0.9% ( -16% - 21%) 0.706
BrowseDateTaxoFacets 5.13 (7.4%) 5.18 (11.4%) 0.9% ( -16% - 21%) 0.701
OrNotHighLow 1350.70 (3.7%) 1363.76 (5.2%) 1.0% ( -7% - 10%) 0.404
OrNotHighMed 413.84 (5.0%) 418.36 (4.5%) 1.1% ( -7% - 11%) 0.373
BrowseRandomLabelTaxoFacets 4.43 (10.0%) 4.48 (11.0%) 1.1% ( -18% - 24%) 0.678
OrHighNotHigh 328.80 (5.0%) 332.94 (5.3%) 1.3% ( -8% - 12%) 0.346
MedTerm 1080.94 (4.9%) 1094.66 (4.6%) 1.3% ( -7% - 11%) 0.300
BrowseDateSSDVFacets 1.26 (8.2%) 1.28 (10.3%) 1.4% ( -15% - 21%) 0.567
MedSloppyPhrase 141.62 (4.2%) 143.96 (6.4%) 1.7% ( -8% - 12%) 0.235
Fuzzy1 123.51 (3.0%) 125.62 (3.1%) 1.7% ( -4% - 8%) 0.032
BrowseRandomLabelSSDVFacets 3.38 (5.1%) 3.44 (7.6%) 1.8% ( -10% - 15%) 0.281
BrowseDayOfYearSSDVFacets 4.59 (6.1%) 4.67 (6.4%) 1.9% ( -10% - 15%) 0.252
OrHighLow 844.21 (2.2%) 859.99 (2.4%) 1.9% ( -2% - 6%) 0.002
Fuzzy2 86.55 (2.6%) 88.26 (2.4%) 2.0% ( -2% - 7%) 0.002
LowTerm 1125.43 (4.2%) 1147.90 (4.5%) 2.0% ( -6% - 11%) 0.078
OrHighNotMed 529.41 (5.2%) 540.19 (4.9%) 2.0% ( -7% - 12%) 0.120
LowPhrase 57.41 (4.0%) 58.59 (2.5%) 2.1% ( -4% - 8%) 0.016
HighPhrase 117.91 (6.3%) 120.40 (5.6%) 2.1% ( -9% - 15%) 0.172
LowSloppyPhrase 79.27 (2.6%) 80.97 (2.8%) 2.1% ( -3% - 7%) 0.002
PKLookup 242.22 (1.6%) 247.50 (1.8%) 2.2% ( -1% - 5%) 0.000
AndHighMed 263.71 (3.2%) 269.83 (3.5%) 2.3% ( -4% - 9%) 0.007
HighTerm 724.28 (6.9%) 741.28 (4.6%) 2.3% ( -8% - 14%) 0.121
OrHighNotLow 428.22 (7.1%) 438.49 (7.5%) 2.4% ( -11% - 18%) 0.203
TermDTSort 192.28 (3.0%) 197.11 (4.7%) 2.5% ( -5% - 10%) 0.013
LowSpanNear 43.25 (3.0%) 44.37 (3.9%) 2.6% ( -4% - 9%) 0.004
Respell 50.44 (1.4%) 51.74 (1.8%) 2.6% ( 0% - 5%) 0.000
HighTermMonthSort 1543.51 (6.2%) 1584.42 (5.2%) 2.7% ( -8% - 14%) 0.073
Prefix3 1238.14 (4.3%) 1271.37 (5.3%) 2.7% ( -6% - 12%) 0.032
AndHighLow 1325.79 (4.2%) 1363.49 (5.2%) 2.8% ( -6% - 12%) 0.019
MedTermDayTaxoFacets 19.45 (3.0%) 20.00 (3.5%) 2.9% ( -3% - 9%) 0.001
HighSloppyPhrase 61.26 (4.2%) 63.04 (5.8%) 2.9% ( -6% - 13%) 0.026
AndHighMedDayTaxoFacets 21.27 (3.4%) 21.90 (4.6%) 3.0% ( -4% - 11%) 0.004
OrNotHighHigh 498.28 (5.9%) 513.21 (6.5%) 3.0% ( -8% - 16%) 0.063
MedSpanNear 128.18 (2.1%) 132.10 (2.0%) 3.1% ( 0% - 7%) 0.000
OrHighMedDayTaxoFacets 9.39 (3.5%) 9.68 (5.4%) 3.1% ( -5% - 12%) 0.009
HighTermTitleSort 77.60 (3.5%) 80.02 (3.2%) 3.1% ( -3% - 10%) 0.000
MedPhrase 64.87 (8.0%) 67.14 (8.3%) 3.5% ( -11% - 21%) 0.097
Wildcard 86.60 (3.8%) 89.64 (3.9%) 3.5% ( -4% - 11%) 0.000
OrHighHigh 92.02 (8.6%) 95.53 (9.0%) 3.8% ( -12% - 23%) 0.091
BrowseMonthSSDVFacets 4.58 (7.1%) 4.75 (14.8%) 3.8% ( -16% - 27%) 0.202
AndHighHigh 85.41 (3.6%) 88.71 (5.7%) 3.9% ( -5% - 13%) 0.002
OrHighMed 105.71 (6.5%) 110.08 (7.7%) 4.1% ( -9% - 19%) 0.024
AndHighHighDayTaxoFacets 13.38 (4.4%) 13.99 (6.8%) 4.5% ( -6% - 16%) 0.002
HighTermDayOfYearSort 371.69 (7.1%) 389.79 (7.4%) 4.9% ( -8% - 20%) 0.009
HighSpanNear 32.24 (5.6%) 33.99 (2.8%) 5.4% ( -2% - 14%) 0.000
MedIntervalsOrdered 32.46 (5.1%) 34.66 (6.6%) 6.8% ( -4% - 19%) 0.000
LowIntervalsOrdered 179.96 (4.2%) 193.33 (5.9%) 7.4% ( -2% - 18%) 0.000
HighIntervalsOrdered 30.10 (6.7%) 32.89 (8.2%) 9.2% ( -5% - 25%) 0.000
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speedup OrderIntervalsSource some more [lucene]
Posted by "original-brownbear (via GitHub)" <gi...@apache.org>.
original-brownbear commented on code in PR #13937:
URL: https://github.com/apache/lucene/pull/13937#discussion_r1807578084
##########
lucene/queries/src/java/org/apache/lucene/queries/intervals/OrderedIntervalsSource.java:
##########
@@ -127,29 +127,31 @@ public int nextInterval() throws IOException {
final var subIterators = this.subIterators;
int currentIndex = i;
while (true) {
+ int prevEnd = subIterators.get(currentIndex - 1).end();
while (true) {
- var prev = subIterators.get(currentIndex - 1);
- if (prev.end() >= lastStart) {
+ if (prevEnd >= lastStart) {
i = currentIndex;
return start;
}
if (currentIndex == subIterators.size()) {
break;
}
final IntervalIterator current = subIterators.get(currentIndex);
- if (minimizing && (current.start() > prev.end())) {
+ if (minimizing && (current.start() > prevEnd)) {
break;
}
+ int currentStart;
do {
if (current.end() >= lastStart
- || current.nextInterval() == IntervalIterator.NO_MORE_INTERVALS) {
+ || (currentStart = current.nextInterval()) == IntervalIterator.NO_MORE_INTERVALS) {
i = currentIndex;
return start;
}
- } while (current.start() <= prev.end());
+ } while (currentStart <= prevEnd);
currentIndex++;
+ prevEnd = current.end();
}
- var first = subIterators.getFirst();
+ var first = subIterators.get(0);
Review Comment:
I tried some more tricks here around just getting `first` once at the beginning of the loop (and similar optimisations that tried to exploit loop invariants) but to no avail (in fact those resulted in slow-downs). Seems the compiler eventually does not like having too many local variables around.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speedup OrderIntervalsSource some more [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #13937:
URL: https://github.com/apache/lucene/pull/13937#discussion_r1808166752
##########
lucene/queries/src/java/org/apache/lucene/queries/intervals/OrderedIntervalsSource.java:
##########
@@ -161,8 +163,8 @@ public int nextInterval() throws IOException {
final int end = last.end();
this.end = end;
int slop = end - start + 1;
- for (IntervalIterator subIterator : subIterators) {
- slop -= subIterator.width();
+ for (int j = 0; j < subIterators.size(); j++) {
Review Comment:
Can you add a small code comment, so that someone doesn't change it back to a for..in loop in the future?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speedup OrderIntervalsSource some more [lucene]
Posted by "original-brownbear (via GitHub)" <gi...@apache.org>.
original-brownbear commented on code in PR #13937:
URL: https://github.com/apache/lucene/pull/13937#discussion_r1808845516
##########
lucene/queries/src/java/org/apache/lucene/queries/intervals/OrderedIntervalsSource.java:
##########
@@ -161,8 +163,8 @@ public int nextInterval() throws IOException {
final int end = last.end();
this.end = end;
int slop = end - start + 1;
- for (IntervalIterator subIterator : subIterators) {
- slop -= subIterator.width();
+ for (int j = 0; j < subIterators.size(); j++) {
Review Comment:
Done :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speedup OrderIntervalsSource some more [lucene]
Posted by "original-brownbear (via GitHub)" <gi...@apache.org>.
original-brownbear commented on PR #13937:
URL: https://github.com/apache/lucene/pull/13937#issuecomment-2426878304
Thanks Adrien!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speedup OrderIntervalsSource some more [lucene]
Posted by "original-brownbear (via GitHub)" <gi...@apache.org>.
original-brownbear merged PR #13937:
URL: https://github.com/apache/lucene/pull/13937
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Speedup OrderIntervalsSource some more [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13937:
URL: https://github.com/apache/lucene/pull/13937#issuecomment-2429119642
There is indeed a small speedup to intervals with a low p-value. https://benchmarks.mikemccandless.com/IntervalsOrdered.html I pushed an annotation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org