jpountz commented on code in PR #875:
URL: https://github.com/apache/lucene/pull/875#discussion_r869429459
##########
lucene/core/src/java/org/apache/lucene/index/OrdinalMap.java:
##########
@@ -48,10 +49,69 @@ public class OrdinalMap implements Accountable {
// need it
// TODO: use more efficient packed ints structures?
+ /**
+ * Copy the first 8 bytes of the given term as a comparable unsigned long.
In case the term has
+ * less than 8 bytes, missing bytes will be replaced with zeroes. Note that
two terms that produce
+ * the same long could still be different due to the fact that missing bytes
are replaced with
+ * zeroes, e.g. {@code [1, 0]} and {@code [1]} get mapped to the same long.
+ */
+ static long prefix8ToComparableUnsignedLong(BytesRef term) {
+ // Use Big Endian so that longs are comparable
+ if (term.length >= Long.BYTES) {
+ return (long) BitUtil.VH_BE_LONG.get(term.bytes, term.offset);
+ } else {
+ long l;
+ int offset;
+ if (term.length >= Integer.BYTES) {
+ l = (int) BitUtil.VH_BE_INT.get(term.bytes, term.offset);
+ offset = Integer.BYTES;
+ } else {
+ l = 0;
+ offset = 0;
+ }
+ while (offset < term.length) {
+ l = (l << 8) | Byte.toUnsignedLong(term.bytes[term.offset + offset]);
+ offset++;
+ }
+ l <<= (Long.BYTES - term.length) << 3;
+ return l;
+ }
+ }
+
+ private static int compare(BytesRef termA, long prefix8A, BytesRef termB,
long prefix8B) {
+ assert prefix8A == prefix8ToComparableUnsignedLong(termA);
Review Comment:
FWIW the observation that made me come up with this change is that in my
benchmark, `PriorityQueue` would spend lots of time reorganizing itself and
perform 7 `lessThan` comparisons for each `updateTop()` call on average. So if
there's anything I could pre-compute based on the values that could speed up
comparisons, then it could help speed up OrdinalMap construction. This is how I
came up with this long.
The computation of this long only needs to make different decisions
depending on the length of the input array or bound checks once, and then for 7
comparisons we can compare 8 bytes at once without any other consideration.
This helps amortize its computation time. On the other hand,
`Arrays#compareUnsigned` needs to check the length of both input arrays every
time to know how many bytes need to be compared, I'm guessing it also needs to
perform bound checks, and it probably also chooses different strategies
depending on how many bytes need to be compared.
Maybe `Arrays#compareUnsigned` has room for improvement, but I don't think
there's any improvement that can speed up `OrdinalMap` construction to a
similar level as this 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-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
