Re: [PR] Remove patching for doc blocks. [lucene]
s1monw commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1862531327 I wanted to give my $0.02 on this. I am not convinced that a 2% change on a benchmark warrants a 6.2k SLoC addition to such an important codebase. I think the differences in terms of performance between FOR and PFOR vary a lot across benchmarks and are heavily dependent on what your index looks like, how big it is. I would even argue that the space savings PFOR was bringing in (about 5%) might make a bigger difference in terms of performance depending on the size of the index and your hardware. I don't wanna go that far and ask for a revert of this change but I think we need to look closer in the future if the rather questionable improvements warrant a change like this or if such a change should rather be an optional postings format rather than the default. -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1808258638 > > I ran a new luceneutil benchmark on Saturday with my commit [8ae598b](https://github.com/apache/lucene/commit/8ae598bae593e1faa4ff82a87f4cd45f120f1059) (using Lucene99PostingsFormat) as candidate and the commit's parent as baseline (using Lucene90PostingsFormat). > > Is this `wikimediumall` or `wikibigall`? Should have specified, it's `wikimediumall` -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
mikemccand commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1808208970 > I ran a new luceneutil benchmark on Saturday with my commit [8ae598b](https://github.com/apache/lucene/commit/8ae598bae593e1faa4ff82a87f4cd45f120f1059) (using Lucene99PostingsFormat) as candidate and the commit's parent as baseline (using Lucene90PostingsFormat). Is this `wikimediumall` or `wikibigall`? -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1807962044 I ran a new luceneutil benchmark on Saturday with my commit https://github.com/apache/lucene/commit/8ae598bae593e1faa4ff82a87f4cd45f120f1059 (using Lucene99PostingsFormat) as candidate and the commit's parent as baseline (using Lucene90PostingsFormat). Other benchmark variables for transparency: * Java 19 * Ec2 instance: `m5.12xlarge`. * Disabled JFR ``` TaskQPS baseline StdDevQPS my_modified_version StdDevPct diff p-value BrowseMonthTaxoFacets3.98 (6.7%)3.92 (2.3%) -1.7% ( -9% -7%) 0.286 BrowseDayOfYearSSDVFacets3.29 (1.6%)3.27 (1.1%) -0.7% ( -3% -2%) 0.126 BrowseDateSSDVFacets1.01 (4.8%)1.00 (5.6%) -0.6% ( -10% - 10%) 0.695 PKLookup 151.00 (2.5%) 150.26 (2.6%) -0.5% ( -5% -4%) 0.543 BrowseMonthSSDVFacets3.44 (1.6%)3.43 (1.5%) -0.5% ( -3% -2%) 0.321 LowTerm 345.74 (3.0%) 344.39 (3.1%) -0.4% ( -6% -5%) 0.689 Wildcard 142.48 (1.9%) 142.00 (1.8%) -0.3% ( -3% -3%) 0.569 Prefix3 1056.96 (4.0%) 1054.07 (3.2%) -0.3% ( -7% -7%) 0.812 BrowseRandomLabelSSDVFacets2.55 (7.2%)2.54 (7.2%) -0.1% ( -13% - 15%) 0.975 BrowseDayOfYearTaxoFacets3.96 (0.7%)3.96 (0.7%) -0.0% ( -1% -1%) 0.856 BrowseDateTaxoFacets3.94 (0.7%)3.94 (0.7%) -0.0% ( -1% -1%) 0.912 BrowseRandomLabelTaxoFacets3.41 (0.8%)3.41 (0.9%) -0.0% ( -1% -1%) 0.977 Fuzzy1 69.71 (0.9%) 69.74 (0.8%)0.0% ( -1% -1%) 0.902 OrHighNotHigh 205.50 (4.6%) 205.67 (5.3%)0.1% ( -9% - 10%) 0.958 Fuzzy2 58.39 (0.8%) 58.44 (0.6%)0.1% ( -1% -1%) 0.688 OrHighNotLow 265.57 (5.4%) 266.05 (5.9%)0.2% ( -10% - 12%) 0.921 HighIntervalsOrdered5.32 (4.5%)5.33 (4.1%)0.2% ( -8% -9%) 0.879 HighTermTitleBDVSort7.81 (3.1%)7.83 (2.7%)0.3% ( -5% -6%) 0.756 Respell 34.00 (1.3%) 34.10 (1.1%)0.3% ( -2% -2%) 0.451 MedTermDayTaxoFacets 16.00 (3.8%) 16.04 (3.8%)0.3% ( -7% -8%) 0.801 OrHighNotMed 255.88 (5.0%) 257.07 (5.2%)0.5% ( -9% - 11%) 0.774 AndHighHighDayTaxoFacets2.83 (3.5%)2.84 (3.4%)0.5% ( -6% -7%) 0.658 MedTerm 374.43 (4.9%) 376.51 (5.6%)0.6% ( -9% - 11%) 0.738 HighTerm 472.29 (4.8%) 474.92 (5.7%)0.6% ( -9% - 11%) 0.738 MedSpanNear5.01 (4.3%)5.04 (4.6%)0.6% ( -7% -9%) 0.690 HighTermMonthSort 2670.49 (4.1%) 2689.05 (3.1%)0.7% ( -6% -8%) 0.549 LowIntervalsOrdered6.65 (4.2%)6.70 (4.3%)0.7% ( -7% -9%) 0.584 OrHighHigh 22.54 (1.2%) 22.71 (2.4%)0.7% ( -2% -4%) 0.204 OrHighMedDayTaxoFacets1.58 (4.6%)1.59 (3.5%)0.8% ( -6% -9%) 0.523 IntNRQ 27.99 (2.4%) 28.25 (3.9%)0.9% ( -5% -7%) 0.371 OrNotHighHigh 244.47 (3.7%) 246.97 (4.5%)1.0% ( -6% -9%) 0.432 MedIntervalsOrdered3.14 (3.7%)3.18 (3.9%)1.0% ( -6% -9%) 0.391 OrHighMed 43.19 (1.3%) 43.65 (1.7%)1.1% ( -1% -4%) 0.025 HighSpanNear6.73 (2.7%)6.80 (3.3%)1.2% ( -4% -7%) 0.223 LowPhrase 255.75 (2.1%) 259.11 (2.0%)1.3% ( -2% -5%) 0.043 HighTermDayOfYearSort 253.38 (4.1%) 257.57 (2.2%)1.7% ( -4% -8%) 0.112 AndHighHigh 15.70 (1.1%) 15.98 (2.5%)1.8% ( -1% -5%) 0.004 MedPhrase 14.60 (2.4%) 14.89 (2.2%)1.9% ( -2% -6%) 0.009
Re: [PR] Remove patching for doc blocks. [lucene]
jpountz commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1807797987 Thanks both, I pushed an annotation, it should show up tomorrow. I hah high expectations based on preliminary results from https://github.com/apache/lucene/issues/12696#issue-1950239343 where `AndHighMed` had a reproducible 3-4% speedup, so I was expecting nightlies to show it too. @slow-J I'm curious if you had a chance to run benchmarks on this PR, did it also show a speedup? -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1806515360 I think that it's a little hard to tell with 1 datapoint due to noise, it seems to be trending upwards in the `BooleanQuery` graphs, but I agree that it's not obvious that there is a noticeable speedup... -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
gf2121 commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1805253760 FYI this great [view](https://home.apache.org/~mikemccand/lucenebench/2023.11.09.18.02.58.html) could be easier to see the impact of changes in single day for all tasks. It seems some count tasks get a bit happy with little p-value. -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
jpountz commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1805220170 [Nightly benchmarks](https://home.apache.org/~mikemccand/lucenebench/) just caught up this change, it's no obvious that there is a speedup. -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on code in PR #12741:
URL: https://github.com/apache/lucene/pull/12741#discussion_r1383744529
##
lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99PostingsFormat.java:
##
@@ -0,0 +1,518 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import org.apache.lucene.codecs.BlockTermState;
+import org.apache.lucene.codecs.CodecUtil;
+import org.apache.lucene.codecs.FieldsConsumer;
+import org.apache.lucene.codecs.FieldsProducer;
+import org.apache.lucene.codecs.MultiLevelSkipListWriter;
+import org.apache.lucene.codecs.PostingsFormat;
+import org.apache.lucene.codecs.PostingsReaderBase;
+import org.apache.lucene.codecs.PostingsWriterBase;
+import
org.apache.lucene.codecs.lucene90.blocktree.Lucene90BlockTreeTermsReader;
+import
org.apache.lucene.codecs.lucene90.blocktree.Lucene90BlockTreeTermsWriter;
+import org.apache.lucene.index.IndexOptions;
+import org.apache.lucene.index.SegmentReadState;
+import org.apache.lucene.index.SegmentWriteState;
+import org.apache.lucene.index.TermState;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.IOUtils;
+import org.apache.lucene.util.packed.PackedInts;
+
+/**
+ * Lucene 9.9 postings format, which encodes postings in packed integer blocks
for fast decode.
+ *
+ * Basic idea:
+ *
+ *
+ * Packed Blocks and VInt Blocks:
+ * In packed blocks, integers are encoded with the same bit width
({@link PackedInts packed
+ * format}): the block size (i.e. number of integers inside block) is
fixed (currently 128).
+ * Additionally blocks that are all the same value are encoded in an
optimized way.
+ * In VInt blocks, integers are encoded as {@link
DataOutput#writeVInt VInt}: the block
+ * size is variable.
+ * Block structure:
+ * When the postings are long enough, Lucene99PostingsFormat will try
to encode most
+ * integer data as a packed block.
+ * Take a term with 259 documents as an example, the first 256
document ids are encoded as
+ * two packed blocks, while the remaining 3 are encoded as one VInt
block.
+ * Different kinds of data are always encoded separately into
different packed blocks, but
+ * may possibly be interleaved into the same VInt block.
+ * This strategy is applied to pairs: document number,
frequency, position,
+ * payload length, position, offset start, offset length,
and position,
+ * payload length, offsetstart, offset length.
+ * Skipdata settings:
+ * The structure of skip table is quite similar to previous version
of Lucene. Skip
+ * interval is the same as block size, and each skip entry points to the
beginning of each
+ * block. However, for the first block, skip data is omitted.
+ * Positions, Payloads, and Offsets:
+ * A position is an integer indicating where the term occurs within
one document. A payload
+ * is a blob of metadata associated with current position. An offset is
a pair of integers
+ * indicating the tokenized start/end offsets for given term in current
position: it is
+ * essentially a specialized payload.
+ * When payloads and offsets are not omitted,
numPositions==numPayloads==numOffsets
+ * (assuming a null payload contributes one count). As mentioned in
block structure, it is
+ * possible to encode these three either combined or separately.
+ * In all cases, payloads and offsets are stored together. When
encoded as a packed block,
+ * position data is separated out as .pos, while payloads and offsets
are encoded in .pay
+ * (payload metadata will also be stored directly in .pay). When encoded
as VInt blocks, all
+ * these three are stored interleaved into the .pos (so is payload
metadata).
+ * With this strategy, the majority of payload and offset data will
be outside .pos file.
+ * So for queries that require only position data, running on a full
index with payloads and
+ * offsets, this reduces disk pre-fetches.
+ *
+ *
+ * Files and detailed format:
+ *
+ *
+ * .tim: Term Dictionary
+ * .tip: Term Index
+
Re: [PR] Remove patching for doc blocks. [lucene]
mikemccand commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1795532339 Thank you @slow-J! -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1795505918 Thanks Mike and all reviewers! -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
mikemccand merged PR #12741: URL: https://github.com/apache/lucene/pull/12741 -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
mikemccand commented on code in PR #12741:
URL: https://github.com/apache/lucene/pull/12741#discussion_r1383233272
##
lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99PostingsFormat.java:
##
@@ -0,0 +1,518 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import org.apache.lucene.codecs.BlockTermState;
+import org.apache.lucene.codecs.CodecUtil;
+import org.apache.lucene.codecs.FieldsConsumer;
+import org.apache.lucene.codecs.FieldsProducer;
+import org.apache.lucene.codecs.MultiLevelSkipListWriter;
+import org.apache.lucene.codecs.PostingsFormat;
+import org.apache.lucene.codecs.PostingsReaderBase;
+import org.apache.lucene.codecs.PostingsWriterBase;
+import
org.apache.lucene.codecs.lucene90.blocktree.Lucene90BlockTreeTermsReader;
+import
org.apache.lucene.codecs.lucene90.blocktree.Lucene90BlockTreeTermsWriter;
+import org.apache.lucene.index.IndexOptions;
+import org.apache.lucene.index.SegmentReadState;
+import org.apache.lucene.index.SegmentWriteState;
+import org.apache.lucene.index.TermState;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.IOUtils;
+import org.apache.lucene.util.packed.PackedInts;
+
+/**
+ * Lucene 9.9 postings format, which encodes postings in packed integer blocks
for fast decode.
+ *
+ * Basic idea:
+ *
+ *
+ * Packed Blocks and VInt Blocks:
+ * In packed blocks, integers are encoded with the same bit width
({@link PackedInts packed
+ * format}): the block size (i.e. number of integers inside block) is
fixed (currently 128).
+ * Additionally blocks that are all the same value are encoded in an
optimized way.
+ * In VInt blocks, integers are encoded as {@link
DataOutput#writeVInt VInt}: the block
+ * size is variable.
+ * Block structure:
+ * When the postings are long enough, Lucene99PostingsFormat will try
to encode most
+ * integer data as a packed block.
+ * Take a term with 259 documents as an example, the first 256
document ids are encoded as
+ * two packed blocks, while the remaining 3 are encoded as one VInt
block.
+ * Different kinds of data are always encoded separately into
different packed blocks, but
+ * may possibly be interleaved into the same VInt block.
+ * This strategy is applied to pairs: document number,
frequency, position,
+ * payload length, position, offset start, offset length,
and position,
+ * payload length, offsetstart, offset length.
+ * Skipdata settings:
+ * The structure of skip table is quite similar to previous version
of Lucene. Skip
+ * interval is the same as block size, and each skip entry points to the
beginning of each
+ * block. However, for the first block, skip data is omitted.
+ * Positions, Payloads, and Offsets:
+ * A position is an integer indicating where the term occurs within
one document. A payload
+ * is a blob of metadata associated with current position. An offset is
a pair of integers
+ * indicating the tokenized start/end offsets for given term in current
position: it is
+ * essentially a specialized payload.
+ * When payloads and offsets are not omitted,
numPositions==numPayloads==numOffsets
+ * (assuming a null payload contributes one count). As mentioned in
block structure, it is
+ * possible to encode these three either combined or separately.
+ * In all cases, payloads and offsets are stored together. When
encoded as a packed block,
+ * position data is separated out as .pos, while payloads and offsets
are encoded in .pay
+ * (payload metadata will also be stored directly in .pay). When encoded
as VInt blocks, all
+ * these three are stored interleaved into the .pos (so is payload
metadata).
+ * With this strategy, the majority of payload and offset data will
be outside .pos file.
+ * So for queries that require only position data, running on a full
index with payloads and
+ * offsets, this reduces disk pre-fetches.
+ *
+ *
+ * Files and detailed format:
+ *
+ *
+ * .tim: Term Dictionary
+ * .tip: Term
Re: [PR] Remove patching for doc blocks. [lucene]
jpountz commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1792586157 For reference, I'm interested in taking advantage of the fact we're changing the codec anyway to look into other smaller changes, like switching tail postings from vints to group-varint, or better alignign blocks and skip lists so that `BlockDocsEnum#advance` doesn't need to check whether if `docBufferUpto == BLOCK_SIZE` to decode a new block and could do it directly under the `target > nextSkipDoc` check. -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1790605861 Thanks @mikemccand and yes, the codec version bump is the majority of this change :D -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
mikemccand commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1790294665 Thanks for tackling this / persisting @slow-J, especially the glorious fun experience of having to "bump" the Codec version ;) A nice rite-of-passage in this Lucene world! -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1788786005 > Thanks @slow-J ! I left some minor comments about additional `90` -> `99` refactoring. Thanks @gf2121 , committed all the suggestions. -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
gf2121 commented on code in PR #12741: URL: https://github.com/apache/lucene/pull/12741#discussion_r1378509674 ## lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99PostingsFormat.java: ## @@ -0,0 +1,518 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.lucene.codecs.lucene99; + +import java.io.IOException; +import org.apache.lucene.codecs.BlockTermState; +import org.apache.lucene.codecs.CodecUtil; +import org.apache.lucene.codecs.FieldsConsumer; +import org.apache.lucene.codecs.FieldsProducer; +import org.apache.lucene.codecs.MultiLevelSkipListWriter; +import org.apache.lucene.codecs.PostingsFormat; +import org.apache.lucene.codecs.PostingsReaderBase; +import org.apache.lucene.codecs.PostingsWriterBase; +import org.apache.lucene.codecs.lucene90.blocktree.Lucene90BlockTreeTermsReader; +import org.apache.lucene.codecs.lucene90.blocktree.Lucene90BlockTreeTermsWriter; +import org.apache.lucene.index.IndexOptions; +import org.apache.lucene.index.SegmentReadState; +import org.apache.lucene.index.SegmentWriteState; +import org.apache.lucene.index.TermState; +import org.apache.lucene.store.DataOutput; +import org.apache.lucene.util.IOUtils; +import org.apache.lucene.util.packed.PackedInts; + +/** + * Lucene 5.0 postings format, which encodes postings in packed integer blocks for fast decode. Review Comment: ```suggestion * Lucene 9.9 postings format, which encodes postings in packed integer blocks for fast decode. ``` ## lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90PostingsFormat.java: ## @@ -38,6 +37,8 @@ /** * Lucene 5.0 postings format, which encodes postings in packed integer blocks for fast decode. Review Comment: ```suggestion * Lucene 9.0 postings format, which encodes postings in packed integer blocks for fast decode. ``` ## lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99SkipReader.java: ## @@ -0,0 +1,206 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.lucene.codecs.lucene99; + +import java.io.IOException; +import java.util.Arrays; +import org.apache.lucene.codecs.MultiLevelSkipListReader; +import org.apache.lucene.store.IndexInput; + +/** + * Implements the skip list reader for block postings format that stores positions and payloads. + * + * Although this skipper uses MultiLevelSkipListReader as an interface, its definition of skip + * position will be a little different. + * + * For example, when skipInterval = blockSize = 3, df = 2*skipInterval = 6, + * + * + * 0 1 2 3 4 5 + * d d d d d d(posting list) + * ^ ^(skip point in MultiLeveSkipWriter) + * ^(skip point in Lucene90SkipWriter) + * + * + * In this case, MultiLevelSkipListReader will use the last document as a skip point, while + * Lucene90SkipReader should assume no skip point will comes. + * + * If we use the interface directly in Lucene90SkipReader, it may silly try to read another skip + * data after the only skip point is loaded. + * + * To illustrate this, we can call skipTo(d[5]), since skip point d[3] has smaller docId, and + * numSkipped+blockSize== df, the MultiLevelSkipListReader will assume the skip list isn't exhausted + * yet, and try to load a non-existed skip point + * + * Therefore, we'll trim df before passing it to the interface. see trim(int) + */ +public class Lucene99SkipReader
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on code in PR #12741:
URL: https://github.com/apache/lucene/pull/12741#discussion_r1378259917
##
lucene/core/src/java/org/apache/lucene/codecs/lucene99/ForDeltaUtil.java:
##
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.packed.PackedInts;
+
+/** Utility class to encode/decode increasing sequences of 128 integers. */
+public class ForDeltaUtil {
+
+ // IDENTITY_PLUS_ONE[i] == i+1
+ private static final long[] IDENTITY_PLUS_ONE = new long[ForUtil.BLOCK_SIZE];
+
+ static {
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ IDENTITY_PLUS_ONE[i] = i + 1;
+}
+ }
+
+ private static void prefixSumOfOnes(long[] arr, long base) {
+System.arraycopy(IDENTITY_PLUS_ONE, 0, arr, 0, ForUtil.BLOCK_SIZE);
+// This loop gets auto-vectorized
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ arr[i] += base;
+}
+ }
+
+ private final ForUtil forUtil;
+
+ ForDeltaUtil(ForUtil forUtil) {
+this.forUtil = forUtil;
+ }
+
+ /**
+ * Encode deltas of a strictly monotonically increasing sequence of
integers. The provided {@code
+ * longs} are expected to be deltas between consecutive values.
+ */
+ void encodeDeltas(long[] longs, DataOutput out) throws IOException {
+if (longs[0] == 1 && PForUtil.allEqual(longs)) { // happens with very
dense postings
+ out.writeByte((byte) 0);
+} else {
+ long or = 0;
+ for (long l : longs) {
+or |= l;
+ }
+ assert or != 0;
+ final int bitsPerValue = PackedInts.bitsRequired(or);
+ out.writeByte((byte) bitsPerValue);
+ forUtil.encode(longs, bitsPerValue, out);
+}
+ }
+
+ /** Decode deltas, compute the prefix sum and add {@code base} to all
decoded longs. */
+ void decodeAndPrefixSum(DataInput in, long base, long[] longs) throws
IOException {
+final int bitsPerValue = Byte.toUnsignedInt(in.readByte());
+if (bitsPerValue == 0) {
+ prefixSumOfOnes(longs, base);
+} else {
+ forUtil.decodeAndPrefixSum(bitsPerValue, in, base, longs);
Review Comment:
I think its the convenience + otherwise we would have to duplicate about 650
lines of code from `ForUtil`. (all the decode1 -> decode24)
--
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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on code in PR #12741:
URL: https://github.com/apache/lucene/pull/12741#discussion_r1378259917
##
lucene/core/src/java/org/apache/lucene/codecs/lucene99/ForDeltaUtil.java:
##
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.packed.PackedInts;
+
+/** Utility class to encode/decode increasing sequences of 128 integers. */
+public class ForDeltaUtil {
+
+ // IDENTITY_PLUS_ONE[i] == i+1
+ private static final long[] IDENTITY_PLUS_ONE = new long[ForUtil.BLOCK_SIZE];
+
+ static {
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ IDENTITY_PLUS_ONE[i] = i + 1;
+}
+ }
+
+ private static void prefixSumOfOnes(long[] arr, long base) {
+System.arraycopy(IDENTITY_PLUS_ONE, 0, arr, 0, ForUtil.BLOCK_SIZE);
+// This loop gets auto-vectorized
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ arr[i] += base;
+}
+ }
+
+ private final ForUtil forUtil;
+
+ ForDeltaUtil(ForUtil forUtil) {
+this.forUtil = forUtil;
+ }
+
+ /**
+ * Encode deltas of a strictly monotonically increasing sequence of
integers. The provided {@code
+ * longs} are expected to be deltas between consecutive values.
+ */
+ void encodeDeltas(long[] longs, DataOutput out) throws IOException {
+if (longs[0] == 1 && PForUtil.allEqual(longs)) { // happens with very
dense postings
+ out.writeByte((byte) 0);
+} else {
+ long or = 0;
+ for (long l : longs) {
+or |= l;
+ }
+ assert or != 0;
+ final int bitsPerValue = PackedInts.bitsRequired(or);
+ out.writeByte((byte) bitsPerValue);
+ forUtil.encode(longs, bitsPerValue, out);
+}
+ }
+
+ /** Decode deltas, compute the prefix sum and add {@code base} to all
decoded longs. */
+ void decodeAndPrefixSum(DataInput in, long base, long[] longs) throws
IOException {
+final int bitsPerValue = Byte.toUnsignedInt(in.readByte());
+if (bitsPerValue == 0) {
+ prefixSumOfOnes(longs, base);
+} else {
+ forUtil.decodeAndPrefixSum(bitsPerValue, in, base, longs);
Review Comment:
I think its the convenience. Otherwise we would have to duplicate about 650
lines of code from `ForUtil`. (all the decode1 -> decode24)
--
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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on PR #12741: URL: https://github.com/apache/lucene/pull/12741#issuecomment-1787958483 Thanks for the suggestion, I added `Lucene90RWPostingsFormat` in latest commit and made `Lucene90PostingsFormat` read-only. -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on code in PR #12741:
URL: https://github.com/apache/lucene/pull/12741#discussion_r1378112509
##
lucene/core/src/java/org/apache/lucene/codecs/lucene99/PForUtil.java:
##
@@ -0,0 +1,558 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import java.util.Arrays;
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.LongHeap;
+import org.apache.lucene.util.packed.PackedInts;
+
+/** Utility class to encode sequences of 128 small positive integers. */
+final class PForUtil {
+
+ private static final int MAX_EXCEPTIONS = 7;
+ private static final int HALF_BLOCK_SIZE = ForUtil.BLOCK_SIZE / 2;
+
+ // IDENTITY_PLUS_ONE[i] == i + 1
+ private static final long[] IDENTITY_PLUS_ONE = new long[ForUtil.BLOCK_SIZE];
+
+ static {
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ IDENTITY_PLUS_ONE[i] = i + 1;
+}
+ }
+
+ static boolean allEqual(long[] l) {
+for (int i = 1; i < ForUtil.BLOCK_SIZE; ++i) {
+ if (l[i] != l[0]) {
+return false;
+ }
+}
+return true;
+ }
+
+ private final ForUtil forUtil;
+ // buffer for reading exception data; each exception uses two bytes (pos +
high-order bits of the
+ // exception)
+ private final byte[] exceptionBuff = new byte[MAX_EXCEPTIONS * 2];
+
+ PForUtil(ForUtil forUtil) {
+assert ForUtil.BLOCK_SIZE <= 256 : "blocksize must fit in one byte. got "
+ ForUtil.BLOCK_SIZE;
+this.forUtil = forUtil;
+ }
+
+ /** Encode 128 integers from {@code longs} into {@code out}. */
+ void encode(long[] longs, DataOutput out) throws IOException {
+// Determine the top MAX_EXCEPTIONS + 1 values
+final LongHeap top = new LongHeap(MAX_EXCEPTIONS + 1);
+for (int i = 0; i <= MAX_EXCEPTIONS; ++i) {
+ top.push(longs[i]);
+}
+long topValue = top.top();
+for (int i = MAX_EXCEPTIONS + 1; i < ForUtil.BLOCK_SIZE; ++i) {
+ if (longs[i] > topValue) {
+topValue = top.updateTop(longs[i]);
+ }
+}
+
+long max = 0L;
+for (int i = 1; i <= top.size(); ++i) {
+ max = Math.max(max, top.get(i));
+}
+
+final int maxBitsRequired = PackedInts.bitsRequired(max);
+// We store the patch on a byte, so we can't decrease the number of bits
required by more than 8
+final int patchedBitsRequired =
+Math.max(PackedInts.bitsRequired(topValue), maxBitsRequired - 8);
+int numExceptions = 0;
+final long maxUnpatchedValue = (1L << patchedBitsRequired) - 1;
+for (int i = 2; i <= top.size(); ++i) {
+ if (top.get(i) > maxUnpatchedValue) {
+numExceptions++;
+ }
+}
+final byte[] exceptions = new byte[numExceptions * 2];
+if (numExceptions > 0) {
+ int exceptionCount = 0;
+ for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+if (longs[i] > maxUnpatchedValue) {
+ exceptions[exceptionCount * 2] = (byte) i;
+ exceptions[exceptionCount * 2 + 1] = (byte) (longs[i] >>>
patchedBitsRequired);
+ longs[i] &= maxUnpatchedValue;
+ exceptionCount++;
+}
+ }
+ assert exceptionCount == numExceptions : exceptionCount + " " +
numExceptions;
+}
+
+if (allEqual(longs) && maxBitsRequired <= 8) {
+ for (int i = 0; i < numExceptions; ++i) {
+exceptions[2 * i + 1] =
+(byte) (Byte.toUnsignedLong(exceptions[2 * i + 1]) <<
patchedBitsRequired);
+ }
+ out.writeByte((byte) (numExceptions << 5));
+ out.writeVLong(longs[0]);
+} else {
+ final int token = (numExceptions << 5) | patchedBitsRequired;
+ out.writeByte((byte) token);
+ forUtil.encode(longs, patchedBitsRequired, out);
+}
+out.writeBytes(exceptions, exceptions.length);
+ }
+
+ /** Decode 128 integers into {@code ints}. */
+ void decode(DataInput in, long[] longs) throws IOException {
+final int token = Byte.toUnsignedInt(in.readByte());
+final int bitsPerValue = token & 0x1f;
+final int numExceptions = token >>> 5;
+if (bitsPerValue == 0) {
+ Arrays.fill(longs, 0, ForUtil.BLOCK_SIZE, in.readVLong());
+} else {
+
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on code in PR #12741:
URL: https://github.com/apache/lucene/pull/12741#discussion_r1378112295
##
lucene/core/src/java/org/apache/lucene/codecs/lucene99/ForDeltaUtil.java:
##
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.packed.PackedInts;
+
+/** Utility class to encode/decode increasing sequences of 128 integers. */
+public class ForDeltaUtil {
+
+ // IDENTITY_PLUS_ONE[i] == i+1
+ private static final long[] IDENTITY_PLUS_ONE = new long[ForUtil.BLOCK_SIZE];
+
+ static {
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ IDENTITY_PLUS_ONE[i] = i + 1;
+}
+ }
+
+ private static void prefixSumOfOnes(long[] arr, long base) {
+System.arraycopy(IDENTITY_PLUS_ONE, 0, arr, 0, ForUtil.BLOCK_SIZE);
+// This loop gets auto-vectorized
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ arr[i] += base;
+}
+ }
+
+ private final ForUtil forUtil;
+
+ ForDeltaUtil(ForUtil forUtil) {
+this.forUtil = forUtil;
+ }
+
+ /**
+ * Encode deltas of a strictly monotonically increasing sequence of
integers. The provided {@code
+ * longs} are expected to be deltas between consecutive values.
+ */
+ void encodeDeltas(long[] longs, DataOutput out) throws IOException {
+if (longs[0] == 1 && PForUtil.allEqual(longs)) { // happens with very
dense postings
+ out.writeByte((byte) 0);
+} else {
+ long or = 0;
+ for (long l : longs) {
+or |= l;
+ }
+ assert or != 0;
+ final int bitsPerValue = PackedInts.bitsRequired(or);
+ out.writeByte((byte) bitsPerValue);
+ forUtil.encode(longs, bitsPerValue, out);
+}
+ }
+
+ /** Decode deltas, compute the prefix sum and add {@code base} to all
decoded longs. */
+ void decodeAndPrefixSum(DataInput in, long base, long[] longs) throws
IOException {
+final int bitsPerValue = Byte.toUnsignedInt(in.readByte());
+if (bitsPerValue == 0) {
+ prefixSumOfOnes(longs, base);
+} else {
+ forUtil.decodeAndPrefixSum(bitsPerValue, in, base, longs);
+}
+ }
+
+ /** Skip a sequence of 128 longs. */
+ void skip(DataInput in) throws IOException {
Review Comment:
Thanks, removed in latest commit.
--
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
Re: [PR] Remove patching for doc blocks. [lucene]
slow-J commented on code in PR #12741: URL: https://github.com/apache/lucene/pull/12741#discussion_r1378112072 ## lucene/CHANGES.txt: ## @@ -104,6 +104,8 @@ Optimizations * GITHUB#12552: Make FSTPostingsFormat load FSTs off-heap. (Tony X) +* GITHUB#12696: Change Postings back to using FOR in Lucene99PostingsFormat. (Jakub Slowinski) Review Comment: Thanks, done in latest commit. -- 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
Re: [PR] Remove patching for doc blocks. [lucene]
jpountz commented on code in PR #12741:
URL: https://github.com/apache/lucene/pull/12741#discussion_r1377911285
##
lucene/core/src/java/org/apache/lucene/codecs/lucene99/ForDeltaUtil.java:
##
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.packed.PackedInts;
+
+/** Utility class to encode/decode increasing sequences of 128 integers. */
+public class ForDeltaUtil {
+
+ // IDENTITY_PLUS_ONE[i] == i+1
+ private static final long[] IDENTITY_PLUS_ONE = new long[ForUtil.BLOCK_SIZE];
+
+ static {
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ IDENTITY_PLUS_ONE[i] = i + 1;
+}
+ }
+
+ private static void prefixSumOfOnes(long[] arr, long base) {
+System.arraycopy(IDENTITY_PLUS_ONE, 0, arr, 0, ForUtil.BLOCK_SIZE);
+// This loop gets auto-vectorized
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ arr[i] += base;
+}
+ }
+
+ private final ForUtil forUtil;
+
+ ForDeltaUtil(ForUtil forUtil) {
+this.forUtil = forUtil;
+ }
+
+ /**
+ * Encode deltas of a strictly monotonically increasing sequence of
integers. The provided {@code
+ * longs} are expected to be deltas between consecutive values.
+ */
+ void encodeDeltas(long[] longs, DataOutput out) throws IOException {
+if (longs[0] == 1 && PForUtil.allEqual(longs)) { // happens with very
dense postings
+ out.writeByte((byte) 0);
+} else {
+ long or = 0;
+ for (long l : longs) {
+or |= l;
+ }
+ assert or != 0;
+ final int bitsPerValue = PackedInts.bitsRequired(or);
+ out.writeByte((byte) bitsPerValue);
+ forUtil.encode(longs, bitsPerValue, out);
+}
+ }
+
+ /** Decode deltas, compute the prefix sum and add {@code base} to all
decoded longs. */
+ void decodeAndPrefixSum(DataInput in, long base, long[] longs) throws
IOException {
+final int bitsPerValue = Byte.toUnsignedInt(in.readByte());
+if (bitsPerValue == 0) {
+ prefixSumOfOnes(longs, base);
+} else {
+ forUtil.decodeAndPrefixSum(bitsPerValue, in, base, longs);
+}
+ }
+
+ /** Skip a sequence of 128 longs. */
+ void skip(DataInput in) throws IOException {
Review Comment:
It looks like we don't need this method as it's only used for tests.
##
lucene/core/src/java/org/apache/lucene/codecs/lucene99/PForUtil.java:
##
@@ -0,0 +1,558 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import java.util.Arrays;
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.LongHeap;
+import org.apache.lucene.util.packed.PackedInts;
+
+/** Utility class to encode sequences of 128 small positive integers. */
+final class PForUtil {
+
+ private static final int MAX_EXCEPTIONS = 7;
+ private static final int HALF_BLOCK_SIZE = ForUtil.BLOCK_SIZE / 2;
+
+ // IDENTITY_PLUS_ONE[i] == i + 1
+ private static final long[] IDENTITY_PLUS_ONE = new long[ForUtil.BLOCK_SIZE];
+
+ static {
+for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ IDENTITY_PLUS_ONE[i] = i + 1;
+}
+ }
+
+ static boolean allEqual(long[] l) {
+for (int i = 1; i < ForUtil.BLOCK_SIZE; ++i) {
+ if (l[i] != l[0]) {
