You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "kaivalnp (via GitHub)" <gi...@apache.org> on 2025/10/08 04:44:23 UTC
[PR] Speed up NumericUtils#{subtract,add} [lucene]
kaivalnp opened a new pull request, #15303:
URL: https://github.com/apache/lucene/pull/15303
### Description
[`NumericUtils#subtract`](https://github.com/apache/lucene/blob/5249ab91f4b9198ffb01bddefb9b1148f3d23b6a/lucene/core/src/java/org/apache/lucene/util/NumericUtils.java#L94) and [`NumericUtils#add`](https://github.com/apache/lucene/blob/5249ab91f4b9198ffb01bddefb9b1148f3d23b6a/lucene/core/src/java/org/apache/lucene/util/NumericUtils.java#L117) perform their respective operations on two byte arrays (treating them as large unsigned numbers) and store the result in another byte array.
These are performed byte-by-byte, can we speed them up by operating on integers?
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15303:
URL: https://github.com/apache/lucene/pull/15303#issuecomment-3379565851
I'm not 100% sure on what's considered a "normal" `size` for these functions -- please let me know and I can re-run these benchmarks!
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15303:
URL: https://github.com/apache/lucene/pull/15303#issuecomment-3498183822
Thanks @gsmiller, I didn't know which benchmark would capture the impact of this change most suitably -- please let me know if you have suggestions.
I've added a `CHANGES.txt` entry under 10.4 for now..
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #15303:
URL: https://github.com/apache/lucene/pull/15303#issuecomment-3379550069
This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15303:
URL: https://github.com/apache/lucene/pull/15303#issuecomment-3529735874
LGTM, thanks @kaivalnp! I'm not aware of a luceneutil benchmark that would capture this well. Maybe there is one, but I'm not sure? I'd be comfortable moving forward with this change though based on the jmh benchmark results. I'll go ahead and merge.
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on code in PR #15303:
URL: https://github.com/apache/lucene/pull/15303#discussion_r2427154740
##########
lucene/core/src/java/org/apache/lucene/util/NumericUtils.java:
##########
@@ -94,17 +94,35 @@ public static int sortableFloatBits(int bits) {
public static void subtract(int bytesPerDim, int dim, byte[] a, byte[] b, byte[] result) {
int start = dim * bytesPerDim;
int end = start + bytesPerDim;
+
int borrow = 0;
- for (int i = end - 1; i >= start; i--) {
- int diff = (a[i] & 0xff) - (b[i] & 0xff) - borrow;
+ int i;
+
+ int limit = start + (bytesPerDim & ~3);
+ for (i = end - 1; i >= limit; i--) {
+ int diff = Byte.toUnsignedInt(a[i]) - Byte.toUnsignedInt(b[i]) - borrow;
if (diff < 0) {
- diff += 256;
borrow = 1;
} else {
borrow = 0;
}
result[i - start] = (byte) diff;
}
+
+ for (i -= 3; i >= start; i -= 4) {
+ int aInt = (int) BitUtil.VH_BE_INT.get(a, i);
+ int bInt = (int) BitUtil.VH_BE_INT.get(b, i);
+
+ long diff = Integer.toUnsignedLong(aInt) - Integer.toUnsignedLong(bInt) - borrow;
+ if (diff < 0) {
+ borrow = 1;
+ } else {
+ borrow = 0;
+ }
+
+ BitUtil.VH_BE_INT.set(result, i - start, (int) diff);
Review Comment:
[`BitUtil.VH_BE_INT`](https://github.com/apache/lucene/blob/e3184cbe47a7bf429bd2be06d48f56687fcc05c6/lucene/core/src/java/org/apache/lucene/util/BitUtil.java#L155-L163) will need to be un-deprecated if we go ahead with this?
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15303:
URL: https://github.com/apache/lucene/pull/15303#issuecomment-3458076922
@jainankitk I chose integer because these are unsigned numbers, and Java does not have an "unsigned long" equivalent (but "unsigned integer" can be represented and added / subtracted in an intermediate long).
For SIMD, it's tricky because every operation is dependent on the output of the previous operation (carry / borrow) -- so while we can add / subtract (say) 8 integers at the same time, I don't know if the carry logic can be meaningfully parallelized
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15303:
URL: https://github.com/apache/lucene/pull/15303#issuecomment-3379551543
JMH benchmarks show \~75% speedup in individual operations:
```
Benchmark (size) Mode Cnt Score Error Units
NumericUtilsBenchmark.add 1 thrpt 15 444.595 ± 9.706 ops/us
NumericUtilsBenchmark.add 128 thrpt 15 10.058 ± 0.158 ops/us
NumericUtilsBenchmark.add 207 thrpt 15 6.283 ± 0.054 ops/us
NumericUtilsBenchmark.add 256 thrpt 15 5.075 ± 0.039 ops/us
NumericUtilsBenchmark.add 300 thrpt 15 4.345 ± 0.025 ops/us
NumericUtilsBenchmark.add 512 thrpt 15 2.559 ± 0.016 ops/us
NumericUtilsBenchmark.add 702 thrpt 15 1.870 ± 0.008 ops/us
NumericUtilsBenchmark.add 1024 thrpt 15 1.282 ± 0.005 ops/us
NumericUtilsBenchmark.addNew 1 thrpt 15 424.607 ± 4.942 ops/us
NumericUtilsBenchmark.addNew 128 thrpt 15 17.099 ± 0.013 ops/us
NumericUtilsBenchmark.addNew 207 thrpt 15 10.607 ± 0.003 ops/us
NumericUtilsBenchmark.addNew 256 thrpt 15 8.880 ± 0.003 ops/us
NumericUtilsBenchmark.addNew 300 thrpt 15 7.617 ± 0.002 ops/us
NumericUtilsBenchmark.addNew 512 thrpt 15 4.528 ± 0.001 ops/us
NumericUtilsBenchmark.addNew 702 thrpt 15 3.289 ± 0.001 ops/us
NumericUtilsBenchmark.addNew 1024 thrpt 15 2.287 ± 0.001 ops/us
NumericUtilsBenchmark.subtract 1 thrpt 15 436.634 ± 5.048 ops/us
NumericUtilsBenchmark.subtract 128 thrpt 15 9.791 ± 0.155 ops/us
NumericUtilsBenchmark.subtract 207 thrpt 15 5.995 ± 0.119 ops/us
NumericUtilsBenchmark.subtract 256 thrpt 15 4.892 ± 0.097 ops/us
NumericUtilsBenchmark.subtract 300 thrpt 15 4.136 ± 0.067 ops/us
NumericUtilsBenchmark.subtract 512 thrpt 15 2.424 ± 0.035 ops/us
NumericUtilsBenchmark.subtract 702 thrpt 15 1.744 ± 0.018 ops/us
NumericUtilsBenchmark.subtract 1024 thrpt 15 1.187 ± 0.015 ops/us
NumericUtilsBenchmark.subtractNew 1 thrpt 15 408.084 ± 23.214 ops/us
NumericUtilsBenchmark.subtractNew 128 thrpt 15 17.513 ± 0.009 ops/us
NumericUtilsBenchmark.subtractNew 207 thrpt 15 10.732 ± 0.050 ops/us
NumericUtilsBenchmark.subtractNew 256 thrpt 15 9.003 ± 0.002 ops/us
NumericUtilsBenchmark.subtractNew 300 thrpt 15 7.816 ± 0.022 ops/us
NumericUtilsBenchmark.subtractNew 512 thrpt 15 4.563 ± 0.004 ops/us
NumericUtilsBenchmark.subtractNew 702 thrpt 15 3.339 ± 0.001 ops/us
NumericUtilsBenchmark.subtractNew 1024 thrpt 15 2.296 ± 0.005 ops/us
```
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15303:
URL: https://github.com/apache/lucene/pull/15303#issuecomment-3493743233
I like this change.
With respect to the `deprecated` notice, it looks like these big endian var handles were added back in 2021 (#308) in a deprecated state. It seems OK to me to leverage it here for this use (we could always change this if we wanted to actually remove these BE var handles).
In terms of impact, it looks like the only meaningful usage is of `subtract` from `BKDWriter`. So I wouldn't expect much performance impact (at least not in the query-centric benchmarking... and probably not really in a noticeable way while indexing)? Still seems like a nice, contained change.
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller merged PR #15303:
URL: https://github.com/apache/lucene/pull/15303
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15303:
URL: https://github.com/apache/lucene/pull/15303#issuecomment-3533049129
Thanks @gsmiller !
--
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] Speed up NumericUtils#{subtract,add} [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15303:
URL: https://github.com/apache/lucene/pull/15303#issuecomment-3382643472
I ran the `wikimedium10m` benchmark:
```
TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff p-value
BrowseDayOfYearTaxoFacets 23.92 (45.2%) 20.73 (39.1%) -13.3% ( -67% - 129%) 0.319
BrowseDateTaxoFacets 23.47 (44.9%) 20.35 (38.8%) -13.3% ( -66% - 127%) 0.317
BrowseRandomLabelTaxoFacets 17.96 (37.8%) 15.98 (33.2%) -11.0% ( -59% - 96%) 0.329
LowIntervalsOrdered 342.80 (4.4%) 320.95 (11.8%) -6.4% ( -21% - 10%) 0.024
IntSet 906.42 (16.4%) 866.41 (18.1%) -4.4% ( -33% - 36%) 0.419
LowSloppyPhrase 365.89 (5.2%) 352.39 (10.7%) -3.7% ( -18% - 12%) 0.166
OrNotHighMed 727.67 (15.2%) 704.54 (21.4%) -3.2% ( -34% - 39%) 0.588
OrHighMed 824.34 (18.4%) 804.45 (19.3%) -2.4% ( -33% - 43%) 0.685
MedIntervalsOrdered 265.83 (6.6%) 260.54 (11.8%) -2.0% ( -19% - 17%) 0.510
MedSloppyPhrase 59.58 (3.7%) 58.42 (5.3%) -1.9% ( -10% - 7%) 0.178
HighSloppyPhrase 149.76 (4.1%) 147.03 (6.0%) -1.8% ( -11% - 8%) 0.261
MedPhrase 577.97 (11.0%) 568.92 (16.0%) -1.6% ( -25% - 28%) 0.718
HighTerm 1278.65 (8.3%) 1260.42 (10.6%) -1.4% ( -18% - 18%) 0.635
BrowseMonthSSDVFacets 17.49 (14.5%) 17.25 (14.9%) -1.4% ( -26% - 32%) 0.765
OrHighHigh 550.67 (16.3%) 544.30 (15.5%) -1.2% ( -28% - 36%) 0.819
OrHighLow 1108.06 (12.4%) 1095.72 (13.4%) -1.1% ( -23% - 28%) 0.785
LowPhrase 857.44 (19.7%) 848.38 (16.3%) -1.1% ( -30% - 43%) 0.853
OrNotHighHigh 321.02 (10.0%) 317.87 (8.9%) -1.0% ( -18% - 19%) 0.744
OrHighMedDayTaxoFacets 42.98 (5.4%) 42.61 (5.1%) -0.9% ( -10% - 10%) 0.605
LowSpanNear 70.50 (3.3%) 69.91 (5.0%) -0.8% ( -8% - 7%) 0.536
HighTermTitleSort 148.21 (12.5%) 147.07 (13.5%) -0.8% ( -23% - 28%) 0.851
MedTerm 1565.66 (13.1%) 1553.75 (10.6%) -0.8% ( -21% - 26%) 0.840
Fuzzy1 106.20 (6.7%) 105.42 (7.3%) -0.7% ( -13% - 14%) 0.742
OrHighNotHigh 496.93 (9.9%) 493.40 (12.0%) -0.7% ( -20% - 23%) 0.839
TermDTSort 507.80 (15.3%) 504.79 (19.5%) -0.6% ( -30% - 40%) 0.915
AndHighHighDayTaxoFacets 39.90 (5.0%) 39.66 (5.1%) -0.6% ( -10% - 10%) 0.715
Prefix3 830.78 (16.8%) 825.93 (20.4%) -0.6% ( -32% - 44%) 0.921
MedSpanNear 368.33 (9.1%) 366.31 (11.3%) -0.5% ( -19% - 21%) 0.865
HighIntervalsOrdered 91.56 (7.4%) 91.08 (8.9%) -0.5% ( -15% - 17%) 0.839
OrNotHighLow 1362.93 (16.0%) 1360.42 (16.7%) -0.2% ( -28% - 38%) 0.972
PKLookup 220.59 (4.0%) 220.39 (4.7%) -0.1% ( -8% - 8%) 0.948
BrowseDateSSDVFacets 3.00 (6.2%) 3.00 (6.1%) 0.0% ( -11% - 13%) 0.994
BrowseRandomLabelSSDVFacets 12.38 (8.5%) 12.39 (8.7%) 0.0% ( -15% - 18%) 0.990
HighSpanNear 81.94 (4.3%) 82.02 (3.1%) 0.1% ( -6% - 7%) 0.936
MedTermDayTaxoFacets 95.21 (4.9%) 95.52 (5.2%) 0.3% ( -9% - 10%) 0.837
OrHighNotMed 738.20 (13.8%) 740.84 (12.3%) 0.4% ( -22% - 30%) 0.931
range 3799.69 (6.8%) 3813.77 (8.5%) 0.4% ( -13% - 16%) 0.879
Respell 77.74 (3.0%) 78.04 (3.3%) 0.4% ( -5% - 6%) 0.697
BrowseMonthTaxoFacets 36.52 (2.0%) 36.66 (1.6%) 0.4% ( -3% - 4%) 0.495
HighTermMonthSort 1295.20 (13.2%) 1301.64 (16.6%) 0.5% ( -25% - 34%) 0.916
AndHighMedDayTaxoFacets 183.09 (9.5%) 184.07 (10.1%) 0.5% ( -17% - 22%) 0.863
HighPhrase 170.33 (12.9%) 171.68 (15.9%) 0.8% ( -24% - 33%) 0.863
Fuzzy2 68.46 (9.4%) 69.09 (7.3%) 0.9% ( -14% - 19%) 0.728
OrHighNotLow 1036.13 (16.5%) 1048.35 (17.2%) 1.2% ( -27% - 41%) 0.825
AndHighLow 1342.36 (13.7%) 1366.95 (14.1%) 1.8% ( -22% - 34%) 0.677
LowTerm 1804.40 (12.2%) 1842.15 (15.9%) 2.1% ( -23% - 34%) 0.641
AndHighMed 876.53 (25.8%) 894.96 (23.3%) 2.1% ( -37% - 69%) 0.787
AndHighHigh 524.59 (24.5%) 537.07 (21.4%) 2.4% ( -34% - 63%) 0.744
BrowseDayOfYearSSDVFacets 15.85 (7.2%) 16.26 (11.3%) 2.6% ( -14% - 22%) 0.394
Wildcard 686.64 (20.0%) 705.26 (19.2%) 2.7% ( -30% - 52%) 0.662
HighTermTitleBDVSort 91.71 (6.1%) 94.50 (5.6%) 3.0% ( -8% - 15%) 0.099
IntNRQ 616.93 (21.5%) 659.96 (13.9%) 7.0% ( -23% - 53%) 0.223
HighTermDayOfYearSort 485.02 (24.7%) 525.05 (18.6%) 8.3% ( -28% - 68%) 0.233
```
--
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