You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "vsop-479 (via GitHub)" <gi...@apache.org> on 2026/03/14 03:19:10 UTC
[PR] Add PriorityQueue#addNoShift, and use it in DisjunctionMaxBulkScorer's constructor. [lucene]
vsop-479 opened a new pull request, #15823:
URL: https://github.com/apache/lucene/pull/15823
(no comment)
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2992876874
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +176,36 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link Function} to transform element.
+ * This method should be preferred over calling {@link #addAll(Collection)}, when the type of
+ * param elements is different from the type of this {@link PriorityQueue}, since it doesn't
+ * require the caller to do the conversion at the call site.
+ */
+ public <S> void addAll(Collection<S> elements, Function<S, T> elementTransformer) {
Review Comment:
> We'll hit the same AIOOB exception anyway in the for-each loop that's populating the array
Indeed. That is what `PriorityQueue#add` do (when caller iterate their elements to call ). So i removed the validation and implmented `public void addAll(Iterable<T> elements)`.
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4108360594
I implemented it with `Iterables/Iterators` (they only have transform function for now).
Please take a look when you get a chance @dweiss, @gsmiller .
I like the design of `Iterables/Iterators`. But, there are some notes i think we may care in Guava's `Iterables`:
> Java 8+ users: several common uses for this class are now more comprehensively addressed by the new Stream library. Read the method documentation below for comparisons. This class is not being deprecated, but we gently encourage you to migrate to streams.
Note on `Iterables#transform`:
> Stream equivalent: Stream.map.
So, I test it with `Stream`, it works too. The code with stream likes:
````
elements.stream().map(elementTransformer).forEach(e -> {
this.heap[size + 1] = e;
this.size++;
});
````
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4167969105
I had a similar issue with changing an Exception type for the caller checks #15877, but I decided then: It's not an issue, because nobody is allowed the method from externally so the thrown exception won't matter, because there is no way to recover from that issue.
Here it is similar: If you hit an exception the difference is now that heap is sane afterwards, before it was not sane. So it is better afterwards. Anybody who tried to cleanup from it in the past would have made the heap sane, but doing that twice is not an issue.
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4132445056
So, -1 to add all this collection code that already has native support in jdk.
--
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] Add PriorityQueue#addNoShift, and use it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2934590460
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -189,6 +189,18 @@ public final T add(T element) {
return heap[1];
}
+ /**
+ * Adds an Object to a PriorityQueue without upHeap. Note: only use it when all elements have a
+ * same value.
+ */
+ public final void addNoShift(T element) {
+ // TODO: Check element equalsTo lastElement, if we can get the comparator.
Review Comment:
Typo/grammar in the new TODO comment: "equalsTo" should be "equal to".
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -189,6 +189,18 @@ public final T add(T element) {
return heap[1];
}
+ /**
+ * Adds an Object to a PriorityQueue without upHeap. Note: only use it when all elements have a
+ * same value.
+ */
+ public final void addNoShift(T element) {
Review Comment:
New API addNoShift is not covered by tests. Since lucene/core already has util-level tests in TestPriorityQueue, please add a focused test that builds a queue via addNoShift under its intended precondition (all elements compare equal), then mutates one element and calls updateTop()/pop() to verify heap behavior remains correct.
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -189,6 +189,18 @@ public final T add(T element) {
return heap[1];
}
+ /**
+ * Adds an Object to a PriorityQueue without upHeap. Note: only use it when all elements have a
Review Comment:
Grammar in the new Javadoc: "a same value" should be "the same value".
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -189,6 +189,18 @@ public final T add(T element) {
return heap[1];
}
+ /**
+ * Adds an Object to a PriorityQueue without upHeap. Note: only use it when all elements have a
+ * same value.
+ */
+ public final void addNoShift(T element) {
+ // TODO: Check element equalsTo lastElement, if we can get the comparator.
+
+ int index = size + 1;
Review Comment:
addNoShift currently bypasses heap restoration without any guardrails, so an accidental misuse can corrupt the heap and lead to incorrect top()/pop() results later. Since PriorityQueue already has access to lessThan, please either enforce/validate the precondition (at least via an assert that the new element is not less than its parent / compares equal to existing elements) or make this API less error-prone (e.g., restrict visibility if possible). Also, consider removing the TODO by implementing the check directly.
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -189,6 +189,18 @@ public final T add(T element) {
return heap[1];
}
+ /**
+ * Adds an Object to a PriorityQueue without upHeap. Note: only use it when all elements have a
+ * same value.
Review Comment:
The Javadoc precondition for addNoShift is ambiguous ("all elements have the same value"—is that by comparator/lessThan ordering, by equals, or by some key?). Since violating the heap invariant can silently break top()/pop(), please reword the contract in terms of ordering (e.g., element must not compare less than its parent / must compare equal to existing elements) and consider documenting that callers must maintain the heap property.
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2968626065
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
> Not use a 3rd party library directly (we don't want that dependency in core).
Thanks for explicit that.
> create our own implementation of Iterable that applies the transformation internally.
OK, I will try this approach.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4142383523
This is how it's used in the disj scorer, so only allow to initialize. Latter calling addAll would lead to trouble.
So basically a factory method like: produce a PQ with that size and take the elements from that stream.
AddAll should not be allowed when heap is already populated because code may misuse it and fail suddenly.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3010979109
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +177,38 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Adds all elements of the stream into the queue. This method should be preferred over calling
+ * {@link #add(Object)} in loop if all elements are known in advance as it builds queue faster.
+ *
+ * <p>If one needs to map or filter element in the iteration of elements in this method, call this
+ * method with elements wrapped by {@link Stream#map(Function)} or {@link
+ * Stream#filter(Predicate)}, etc. In these cases, this method should be preferred over calling
+ * {@link #addAll(Collection)}.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown. Which may result in parts of elements added into the
+ * queue, but the heap is still stay in correct state. In this case, if caller wants to readd or
+ * {@link #updateTop(Object)} with remaining elements, it should use a new stream, and use {@link
+ * Stream#skip(long)} to skip consumed elements with the delta size of queue.
+ */
+ public void addAll(Stream<T> elements) {
+ // Heap with size S always takes first S elements of the array,
+ // and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
+ try {
+ elements.forEachOrdered(
+ element -> {
+ this.heap[size + 1] = element;
+ this.size++;
Review Comment:
> No doubt I likely have a misunderstanding here :). I don't often leverage streams to be honest.
>
> If I'm understanding, your point here is that `forEachOrdered` is going to guarantee sequential invocation. Is that correct? I took a look at the [documentation](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/stream/Stream.html#forEachOrdered(java.util.function.Consumer))[1] and it seems to highlight this point as well.
Yes that what I am after. The difference betwen forEach() and forEachOrdered is just the order. Because of the defined order (oteratoion order of the stream), you can repeat the operation after an exception, stepping over the already processed ones (using skipping as mentioned in the docs here).
> Apologies for the confusion. I should have looked at this documentation first.
No problem. Parallel streams often make people think they need to prevent this, but it is only an issue if non-terminal operations change the stream. E.g., if the map() method's lambda would change the collection. Foreach is a terminal operation, you can be sure it is running in order with happens-before.
> [1] "Performing the action for one element [**happens-before**](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/package-summary.html#MemoryVisibility) performing the action for subsequent elements"
Thanks for that documentation hint, this makes sure for-each is sequential and itsself is not parallelized. In fact, `forEach()`, `forEachOrdered()` or `iterator()` disables parallelization on the stream anyways, therefor features like `collect()` or `reduce()` are much better when you have a parallel stream.
Foreach converts the stream to a for-each loop. Alternatively, we could also call `iterator()` on the stream and consume the iterator like this:
```java
Iterable<T> it = () -> stream.iterator();
for (T element : it) {
this.heap[size + 1] = element;
this.size++;
}
```
Of course that's not really better readable.
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4090745436
> I used an variant: add an ElementSupplier to avoid duplicate loop.
Oh, that works too. That's a creative way to avoid the comparison check on initialization :)
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3010575641
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +177,38 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Adds all elements of the stream into the queue. This method should be preferred over calling
+ * {@link #add(Object)} in loop if all elements are known in advance as it builds queue faster.
+ *
+ * <p>If one needs to map or filter element in the iteration of elements in this method, call this
+ * method with elements wrapped by {@link Stream#map(Function)} or {@link
+ * Stream#filter(Predicate)}, etc. In these cases, this method should be preferred over calling
+ * {@link #addAll(Collection)}.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown. Which may result in parts of elements added into the
+ * queue, but the heap is still stay in correct state. In this case, if caller wants to readd or
+ * {@link #updateTop(Object)} with remaining elements, it should use a new stream, and use {@link
+ * Stream#skip(long)} to skip consumed elements with the delta size of queue.
+ */
+ public void addAll(Stream<T> elements) {
+ // Heap with size S always takes first S elements of the array,
+ // and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
+ try {
+ elements.forEachOrdered(
+ element -> {
+ this.heap[size + 1] = element;
+ this.size++;
Review Comment:
Final note: streams are "declarative", that's the key takeaway.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4151899252
> Oh, I also noticed you're targeting 11.0 to release this. Is there any reason not to target 10.5 instead?
> I figured out that add() also throws AIOOBE. Maybe we should keep the exception; I would remove the catch block and only keep the finally intact.
I moved the change entity to 10.5.0, and removed the catch block.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3001448473
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +177,43 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Adds all elements of the stream into the queue. This method should be preferred over calling
+ * {@link #add(Object)} in loop if all elements are known in advance as it builds queue faster.
+ *
+ * <p>If one needs to map or filter element in the iteration of elements in this method, call this
+ * method with elements wrapped by {@link Stream#map(Function)} or {@link
+ * Stream#filter(Predicate)}, etc. In these cases, this method should be preferred over calling
+ * {@link #addAll(Collection)}.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown. Which may result in parts of elements added into the
Review Comment:
minor: Let's also mention that the heap invariant will always be maintained, even on this error case?
##########
lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java:
##########
@@ -159,6 +160,40 @@ public void testInsertWithOverflow() {
assertThat(pq.top(), equalTo(2));
}
+ public void testAddAllWithStream() {
+ PriorityQueue<Integer> pq = new IntegerQueue(6);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ pq.addAll(elements.stream().map(String::hashCode));
+ assertEquals("a".hashCode(), pq.top().intValue());
+ }
+
+ public void testAddAllWithStreamNotFitIntoQueue() {
+ PriorityQueue<Integer> pq = new IntegerQueue(5);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ assertThrows(
+ "Cannot add 6 elements to a queue with remaining capacity: 5",
+ ArrayIndexOutOfBoundsException.class,
+ () -> pq.addAll(elements.stream().map(String::hashCode)));
+ // Partly added.
+ assertEquals(5, pq.size());
Review Comment:
Can we also put some asserts in here to validate the created PriorityQueue maintains the heap invariant (essentially test the fact that you're doing heapify in the finally block correctly in case someone in the future tries to change that)?
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4139672698
Thanks @gsmiller, @uschindler !
I think this one is close, Please take a look when you get a chance!
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4146805817
> This is how it's used in the disj scorer, so only allow to initialize. Later calling addAll would lead to trouble.
So basically a factory method like: produce a PQ with that size and take the elements from that stream.
AddAll should not be allowed when heap is already populated because code may misuse it and fail suddenly.
> @uschindler - I don't completely follow your comment about addAll only working on a newly-constructed/empty heap. Can you elaborate a bit? I believe both of the addAll methods (existing and this proposed one) should work correctly on a heap that already contains some elements, but I might be missing something? Or maybe I'm misunderstanding your point? Oh wait, after re-reading, maybe you're describing a different option that would appropriately size a new heap for a provided stream? One that would handle the overflow case by essentially allocating a bigger PQ?
I am trying to understand this too :)
--
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] Add PriorityQueue#addNoShift, and use it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4087411993
Thanks for your reply @gsmiller !
> but it doesn't seem particularly expensive?
No, it doesn't.
> Maybe we could leverage #addAll from the DisjunctionMaxBulkScorer ctor?
I will try.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4142353273
I agree. Ideally the code should be like: do the fast addall until you hit exception. Once you hit it in foreach call, clean up the heap with down heap and then add the remaining elements "the slow" way.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3004101825
##########
lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java:
##########
@@ -159,6 +160,40 @@ public void testInsertWithOverflow() {
assertThat(pq.top(), equalTo(2));
}
+ public void testAddAllWithStream() {
+ PriorityQueue<Integer> pq = new IntegerQueue(6);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ pq.addAll(elements.stream().map(String::hashCode));
+ assertEquals("a".hashCode(), pq.top().intValue());
+ }
+
+ public void testAddAllWithStreamNotFitIntoQueue() {
+ PriorityQueue<Integer> pq = new IntegerQueue(5);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ assertThrows(
+ "Cannot add 6 elements to a queue with remaining capacity: 5",
+ ArrayIndexOutOfBoundsException.class,
+ () -> pq.addAll(elements.stream().map(String::hashCode)));
+ // Partly added.
+ assertEquals(5, pq.size());
Review Comment:
I added `TestPriorityQueue#assertHeap`, please take a look when you get a chance.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4146766919
> Oh, I also noticed you're targeting 11.0 to release this. Is there any reason not to target 10.5 instead?
I will move it to 10.5. To be honest, I am not sure where it should be.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3010979109
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +177,38 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Adds all elements of the stream into the queue. This method should be preferred over calling
+ * {@link #add(Object)} in loop if all elements are known in advance as it builds queue faster.
+ *
+ * <p>If one needs to map or filter element in the iteration of elements in this method, call this
+ * method with elements wrapped by {@link Stream#map(Function)} or {@link
+ * Stream#filter(Predicate)}, etc. In these cases, this method should be preferred over calling
+ * {@link #addAll(Collection)}.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown. Which may result in parts of elements added into the
+ * queue, but the heap is still stay in correct state. In this case, if caller wants to readd or
+ * {@link #updateTop(Object)} with remaining elements, it should use a new stream, and use {@link
+ * Stream#skip(long)} to skip consumed elements with the delta size of queue.
+ */
+ public void addAll(Stream<T> elements) {
+ // Heap with size S always takes first S elements of the array,
+ // and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
+ try {
+ elements.forEachOrdered(
+ element -> {
+ this.heap[size + 1] = element;
+ this.size++;
Review Comment:
> No doubt I likely have a misunderstanding here :). I don't often leverage streams to be honest.
>
> If I'm understanding, your point here is that `forEachOrdered` is going to guarantee sequential invocation. Is that correct? I took a look at the [documentation](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/stream/Stream.html#forEachOrdered(java.util.function.Consumer))[1] and it seems to highlight this point as well.
Yes that what I am after. The difference betwen forEach() and forEachOrdered is just the order. Because of the defined order (oteratoion order of the stream), you can repeat the operation after an exception, stepping over the already processed ones (using skipping as mentioned in the docs here).
> Apologies for the confusion. I should have looked at this documentation first.
No problem. Parallel streams often make people think they need to prevent this, but it is only an issue if non-terminal operations change the stream. E.g., if the map() method's lambda would change the collection. Foreach is a terminal operation, you can be sure it is running in order with happens-before.
> [1] "Performing the action for one element [**happens-before**](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/package-summary.html#MemoryVisibility) performing the action for subsequent elements"
Thanks for that documentation hint, this makes sure for-each is sequential and itsself is not parallelized. In fact, `forEach()`, `forEachOrdered()` or `iterator()` disables parallelization on the stream anyways, therefor features like `collect()` or `reduce()` are much better when you have a parallel stream.
Foreach converts the stream to a for-each loop. Alternatively, we could also call `iterator()` on the stream and consume the iterator like this:
```java
for (T element : (Iterable<T>)stream::iterator) {
this.heap[size + 1] = element;
this.size++;
}
```
Of course that's not really better readable.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3016709865
##########
lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java:
##########
@@ -159,6 +160,57 @@ public void testInsertWithOverflow() {
assertThat(pq.top(), equalTo(2));
}
+ public void testAddAllWithStream() {
+ PriorityQueue<Integer> pq = new IntegerQueue(6);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ pq.addAll(elements.stream().map(String::hashCode));
+ assertEquals("a".hashCode(), pq.top().intValue());
+ }
+
+ public void testAddAllWithStreamNotFitIntoQueue() {
+ PriorityQueue<Integer> pq = new IntegerQueue(10);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ assertThrows(
+ "Cannot add 11 elements to a queue with remaining capacity: 10",
+ ArrayIndexOutOfBoundsException.class,
+ () -> pq.addAll(elements.stream().map(String::hashCode)));
+ // Partly added.
+ assertEquals(10, pq.size());
+ assertHeap(pq);
Review Comment:
Yeah, totally fine by me either way :) Thanks!
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4132656807
I just want to avoid all that all this untested crazy code dealing with Spliterators just to filter something in an iterator.
One hint: when you only have an iterable, not a collection you may get a stream with: `StreamSupport.stream(iterable.spliterator(), false);`
That said, I'd stay with Collection. Iterable is to generic. Collections have a size so preallocation works better.
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4132497795
Hi @uschindler , you prefer approach like this?
> So, I test it with Stream, it works too. The code with stream likes:
// Use stream to transform and iterate.
elements.stream().map(elementTransformer).forEach(e -> {
this.heap[size + 1] = e;
this.size++;
});
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2986836998
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +176,36 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link Function} to transform element.
+ * This method should be preferred over calling {@link #addAll(Collection)}, when the type of
+ * param elements is different from the type of this {@link PriorityQueue}, since it doesn't
+ * require the caller to do the conversion at the call site.
+ */
+ public <S> void addAll(Collection<S> elements, Function<S, T> elementTransformer) {
Review Comment:
> The goal is that PriorityQueue doesn't need to know anything about the translation logic. That all gets encapsulated behind the Iterator that is setup by the calling code. WDYT?
+1. There is a minor issue with `public void addAll(Iterable<T> elements)`, the original `addAll` validate the size with `Collection#size` firstly. If we want keep this validation, maybe the caller need input the size of elements? like this:`public void addAll(Iterable<T> elements, int size)`?
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3000489998
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -193,15 +193,24 @@ public void addAll(Collection<T> elements) {
public void addAll(Stream<T> elements) {
// Heap with size S always takes first S elements of the array,
// and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
- elements.forEach(
- element -> {
- this.heap[size + 1] = element;
- this.size++;
- });
-
- // The loop goes down to 1 as heap is 1-based not 0-based.
- for (int i = (size >>> 1); i >= 1; i--) {
- downHeap(i);
+ final int remainingSize = maxSize - this.size;
+ try {
+ elements.forEach(
+ element -> {
+ this.heap[size + 1] = element;
+ this.size++;
+ });
+
+ } catch (
+ @SuppressWarnings("unused")
+ ArrayIndexOutOfBoundsException e) {
Review Comment:
You can use "_" as name for the variable in main branch. then there are no warnings. so suppress not needed. While backporting you need the code with suppress.
Another suggestion: Maybe better use a generic `IndexOutOfBoundsException` to describe the message.
I like it that you still clean up the heap after a failed addition.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3010733646
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +177,38 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Adds all elements of the stream into the queue. This method should be preferred over calling
+ * {@link #add(Object)} in loop if all elements are known in advance as it builds queue faster.
+ *
+ * <p>If one needs to map or filter element in the iteration of elements in this method, call this
+ * method with elements wrapped by {@link Stream#map(Function)} or {@link
+ * Stream#filter(Predicate)}, etc. In these cases, this method should be preferred over calling
+ * {@link #addAll(Collection)}.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown. Which may result in parts of elements added into the
+ * queue, but the heap is still stay in correct state. In this case, if caller wants to readd or
+ * {@link #updateTop(Object)} with remaining elements, it should use a new stream, and use {@link
+ * Stream#skip(long)} to skip consumed elements with the delta size of queue.
+ */
+ public void addAll(Stream<T> elements) {
+ // Heap with size S always takes first S elements of the array,
+ // and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
+ try {
+ elements.forEachOrdered(
+ element -> {
+ this.heap[size + 1] = element;
+ this.size++;
Review Comment:
No doubt I likely have a misunderstanding here :). I don't often leverage streams to be honest.
If I'm understanding, your point here is that `forEachOrdered` is going to guarantee sequential invocation. Is that correct? I took a look at the [documentation](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/stream/Stream.html#forEachOrdered(java.util.function.Consumer))[1] and it seems to highlight this point as well.
Apologies for the confusion. I should have looked at this documentation first.
[1] "Performing the action for one element [**happens-before**](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/package-summary.html#MemoryVisibility) performing the action for subsequent elements"
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4150082268
Hi,
Sorry. Add is also without overflow. So naming is fine.
In that case it's fine. Ignore my previous comment.
You can also revert the exception change. It's consistent with add.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller merged PR #15823:
URL: https://github.com/apache/lucene/pull/15823
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4155783319
This looks mostly good to me, thanks!
I left an earlier comment regarding consistency differences between this new addAll method and the existing addAll(Collection) method that I'd like to resolve (let's either, (a) decide the inconsistency is OK, (b) change the current addAll(Collection) behavior, or (c) open a follow-up issue to address it). The inconsistent behavior relates to how we handle an "overflow" case where more elements are provided than PQ capacity:
- Current addAll(Collection) method: Detects the issue up-front and will not add any elements to the PQ.
- New addAll(Stream) method: Because it cannot detect the issue up-front, it partially completes the operation by adding elements until capacity.
I'd propose: Modify the current addAll(Collection) method to be consistent with the newly added addAll(Stream) method (this is the only option for consistency). (I think it's OK to do this in a follow-up issue if we want to separate the changes).
I recognize this is fairly nitpicky, but I think it's helpful to maintain as much consistency as we can here. WDYT?
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4149959326
> > This is how it's used in the disj scorer, so only allow to initialize. Later calling addAll would lead to trouble.
> > So basically a factory method like: produce a PQ with that size and take the elements from that stream.
> > AddAll should not be allowed when heap is already populated because code may misuse it and fail suddenly.
>
> > @uschindler - I don't completely follow your comment about addAll only working on a newly-constructed/empty heap. Can you elaborate a bit? I believe both of the addAll methods (existing and this proposed one) should work correctly on a heap that already contains some elements, but I might be missing something? Or maybe I'm misunderstanding your point? Oh wait, after re-reading, maybe you're describing a different option that would appropriately size a new heap for a provided stream? One that would handle the overflow case by essentially allocating a bigger PQ?
>
> I am trying to understand this too :)
Ok let me explain this: The problem is that addAll() does not use the same contract like add(). Normally PQs in Lucene are always used with overflow - and this is also how it differs from the JDK provided one. So I'd expect that addAll works identical to a repeated call to add, just faster.
Actually here the addAll call is not using the important overflowing that add uses. And therefor it is completely useless for the "normal" PQ usage like in TopcDocs scoring or similar. addAll in its current form is only useful to the end user if you know how many items are already in the queue and that size is large enough to hold all added elements. Therefor the only use case I see for it when you create an empty PQ with appropiate size and ad all elements to it. If you already have some elements in it and call addAll() it behaves not as expected.
So my proposal was to use the current addAll not as a public method, but more allow to create a new PQ prepopulated with the given elements. So my proposal was to add a separate factory method that returns a new PQ with the elemnts given as stream and not offer to use addAll later, unless it is fixed to handle overflow.
So in conclusion there are 3 options to solve this:
- keep the current method but clearly renam eit to addAllNoOverflow(), documenting that it adds all elements from the stream., but fails once the queue is full.
- don't expose addAll at all on the PQ instance and only add a factory method using the stream to populate a newly created instance with initial elements
- fix addAll() to behave like repeated add with overflow. I have some code written down already that calls uses a conventional loop with `stream.iterator()`, adds all elements until it hits AIOOBE. Once the AIOObE was hit, it rebalances the heap and adds the remaining elements with add().
Is this now understandable what my problem is? PQ is a central and important public class in Lucene and it should not have methods that are similarily named but behave differently.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3013257318
##########
lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java:
##########
@@ -159,6 +160,57 @@ public void testInsertWithOverflow() {
assertThat(pq.top(), equalTo(2));
}
+ public void testAddAllWithStream() {
+ PriorityQueue<Integer> pq = new IntegerQueue(6);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ pq.addAll(elements.stream().map(String::hashCode));
+ assertEquals("a".hashCode(), pq.top().intValue());
+ }
+
+ public void testAddAllWithStreamNotFitIntoQueue() {
+ PriorityQueue<Integer> pq = new IntegerQueue(10);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ assertThrows(
+ "Cannot add 11 elements to a queue with remaining capacity: 10",
+ ArrayIndexOutOfBoundsException.class,
+ () -> pq.addAll(elements.stream().map(String::hashCode)));
+ // Partly added.
+ assertEquals(10, pq.size());
+ assertHeap(pq);
Review Comment:
> but you could also pop elements off the heap in a loop and assert the ordered nature of what comes out. It's nice that you avoid mutating the heap here with your check
Yes, pop and assert the order came to my mind firstly. And in order to avoid mutate the heap, I picked this apporach.
> but since it's the last thing we're doing in a unit test, it might be simpler to just pop stuff off the heap and check rather than writing custom heap traversal logic?
But, you are right.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4163577617
Thanks for making the two addAll methods consistent (and for the other minor revisions)! I'll go ahead and merge this since I don't see any other outstanding feedback. Thanks again!
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4133840468
> > Java 8+ users: several common uses for this class are now more comprehensively addressed by the new Stream library. Read the method documentation below for comparisons. This class is not being deprecated, but we gently encourage you to migrate to streams.
>
> OK, Stream is also encouraged by Guava.
>
> So we can add a method `#addAll(Collection<S> elements, Function<S, T> elementTransformer)` and use `elements.stream().map(elementTransformer)` to filter in it, or `#addAll(Stream<T> stream)` and let the caller to filter or not but need removing the size validation.
>
> > we don't know size before so allocation may be harder and ineffective.
>
> I am a bit confused about why the size of elements affects PQ's allocation, Is the PQ not allcated according to its `maxSize`?
For PQ, no - it has a fixed size, so the typical forEach is enough. Sorry, I mixed it up. But wasn't also DisjunctionScorer involved here that has lists internally that need to be precalculated. Anyways, PQ is the deal here.
Anyways, if the size is not required to optimize any allocation then lets go with the above ideas!
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2994248963
##########
lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxBulkScorer.java:
##########
@@ -53,9 +54,7 @@ private static class BulkScorerAndNext {
}
this.scorers =
PriorityQueue.usingComparator(scorers.size(), Comparator.comparingInt(b -> b.next));
- for (BulkScorer scorer : scorers) {
- this.scorers.add(new BulkScorerAndNext(scorer));
- }
+ this.scorers.addAll(Iterables.transform(scorers, BulkScorerAndNext::new));
Review Comment:
this would need the new API, understood.
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4135359827
> Anyways, if the size is not required to optimize any allocation then lets go with the above ideas!
I'll also add my +1 to not adding all the new iteration-related code. My personal preference would be for the new addAll method to take a Stream as input instead of directly accepting a filtering function. Let the caller create the stream with filtering logic (or whatever they need) then just consume the stream in addAll.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "dweiss (via GitHub)" <gi...@apache.org>.
dweiss commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4142291290
I would go for an exception. If there is a limit needed somewhere, it should be added in the calling code. An internal .limit call is most likely going to obscure a problem elsewhere.
Streams may be infinite - that's why they don't expose their size. Like Uwe said, their spliterators may have "sized" characteristics but in general there is no way to acquire size from a stream (the name is accurate here).
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2968342388
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
I suspect the idea here would be:
1. Not use a 3rd party library directly (we don't want that dependency in core)
2. Have an addAll method that simply takes a `java.lang.Iterable` as a single input but create our own implementation of `Iterable` that applies the transformation internally. Much like what Guava's `Iterables#transform` method does. This is probably something we'd put in core (maybe in o.a.l.util)? We could probably deprecate the current addAll method that takes a Collection in favor of this new API as well.
This approach makes a lot of sense to me, and I don't think it would be too much work to do. (Hopefully I'm understanding the suggestion correctly).
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "dweiss (via GitHub)" <gi...@apache.org>.
dweiss commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2961711962
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
Wouldn't it be more natural for addAll to accept Iterable<X>, followed by an utility method Iterables.transforming(Iterable<Y>, Function<Y,X>). Many libraries do this kind of view thing - we can't reuse them but it should be trivial to implement. Just a thought.
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2964513111
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
> Many libraries do this kind of view thing - we can't reuse them but it should be trivial to implement.
If we prefer this way(I think current committed way is ok too:), do you mean we should implement lucene's `Iterables`, `Iterators`, etc. Ranther than use these libraries directly?
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4163865407
Oh and @vsop-479, just to respond to your earlier comment ("I will move it to 10.5. To be honest, I am not sure where it should be."), I would generally release a change in the next minor version unless it _has_ to wait for the next major version because of something like a backwards compatibility issue. There more here if you're interested: https://cwiki.apache.org/confluence/display/LUCENE/BackwardsCompatibility
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4166952932
> Oh and @vsop-479, just to respond to your earlier comment ("I will move it to 10.5. To be honest, I am not sure where it should be."), I would generally release a change in the next minor version unless it has to wait for the next major version because of something like a backwards compatibility issue. There more here if you're interested: https://cwiki.apache.org/confluence/display/LUCENE/BackwardsCompatibility
Thanks, it is helpful to me. And thanks everyone for the review!
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3010445924
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +177,38 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Adds all elements of the stream into the queue. This method should be preferred over calling
+ * {@link #add(Object)} in loop if all elements are known in advance as it builds queue faster.
+ *
+ * <p>If one needs to map or filter element in the iteration of elements in this method, call this
+ * method with elements wrapped by {@link Stream#map(Function)} or {@link
+ * Stream#filter(Predicate)}, etc. In these cases, this method should be preferred over calling
+ * {@link #addAll(Collection)}.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown. Which may result in parts of elements added into the
+ * queue, but the heap is still stay in correct state. In this case, if caller wants to readd or
+ * {@link #updateTop(Object)} with remaining elements, it should use a new stream, and use {@link
+ * Stream#skip(long)} to skip consumed elements with the delta size of queue.
+ */
+ public void addAll(Stream<T> elements) {
+ // Heap with size S always takes first S elements of the array,
+ // and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
+ try {
+ elements.forEachOrdered(
+ element -> {
+ this.heap[size + 1] = element;
+ this.size++;
Review Comment:
Thanks for using `forEachOrdered` here to be more technically correct. This does make me wonder if we have a potential concurrency bug lurking though. If the caller passes a parallel stream implementation, I think we have a currency bug in how we read-then-update `this.size` right? I'm not a stream expert, so maybe not? But I think so? If so, let's add javadoc? Or maybe we chain a call to `#sequential`, like `elements.sequential().forEachOrdered`?
##########
lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java:
##########
@@ -159,6 +160,57 @@ public void testInsertWithOverflow() {
assertThat(pq.top(), equalTo(2));
}
+ public void testAddAllWithStream() {
+ PriorityQueue<Integer> pq = new IntegerQueue(6);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ pq.addAll(elements.stream().map(String::hashCode));
+ assertEquals("a".hashCode(), pq.top().intValue());
+ }
+
+ public void testAddAllWithStreamNotFitIntoQueue() {
+ PriorityQueue<Integer> pq = new IntegerQueue(10);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ assertThrows(
+ "Cannot add 11 elements to a queue with remaining capacity: 10",
+ ArrayIndexOutOfBoundsException.class,
+ () -> pq.addAll(elements.stream().map(String::hashCode)));
+ // Partly added.
+ assertEquals(10, pq.size());
+ assertHeap(pq);
+ }
+
+ private void assertHeap(PriorityQueue<Integer> pq) {
+ // TODO: Maybe change getHeapArray return type T[].
+ Object[] heapArray = pq.getHeapArray();
+ // The loop goes down to 1 as heap is 1-based not 0-based.
+ for (int i = (heapArray.length >>> 1); i >= 1; i--) {
+ int left = i << 1;
+ int right = left + 1;
+ if (right < heapArray.length) {
+ assert (Integer) heapArray[i] <= (Integer) heapArray[right];
Review Comment:
nit: This test will silently not work if asserts are disabled in the jvm. Let's use the idiomatic juint assert methods instead. I'd have this assertHeap method return a boolean then use assertTrue from the calling method.
##########
lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java:
##########
@@ -159,6 +160,57 @@ public void testInsertWithOverflow() {
assertThat(pq.top(), equalTo(2));
}
+ public void testAddAllWithStream() {
+ PriorityQueue<Integer> pq = new IntegerQueue(6);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ pq.addAll(elements.stream().map(String::hashCode));
+ assertEquals("a".hashCode(), pq.top().intValue());
+ }
+
+ public void testAddAllWithStreamNotFitIntoQueue() {
+ PriorityQueue<Integer> pq = new IntegerQueue(10);
+ List<String> elements = new ArrayList<>();
+ for (String s : Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k")) {
+ if (random().nextBoolean()) {
+ elements.addFirst(s);
+ } else {
+ elements.addLast(s);
+ }
+ }
+
+ assertThrows(
+ "Cannot add 11 elements to a queue with remaining capacity: 10",
+ ArrayIndexOutOfBoundsException.class,
+ () -> pq.addAll(elements.stream().map(String::hashCode)));
+ // Partly added.
+ assertEquals(10, pq.size());
+ assertHeap(pq);
Review Comment:
This approach works, but you could also pop elements off the heap in a loop and assert the ordered nature of what comes out. It's nice that you avoid mutating the heap here with your check, but since it's the last thing we're doing in a unit test, it might be simpler to just pop stuff off the heap and check rather than writing custom heap traversal logic? I don't have strong opinions I suppose. Take-it-or-leave it :)
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4150556349
That's not working with streams. If it works it is an implementation detail and could break with different types of streams.
After the exception the stream is by definition no longer useable. I have to lookup the spec. The correct reuse case would be if addAll would return the number of added entries.
Then one could redo the add with a new stream using `stream.skip(return value)`. In that case it should not throw exception. It is all not easy to decide. For now I think the current impl is fine if we add enough documentation.
I figured out that `add()` also throws AIOOBE. Maybe we should keep the exception; I would remove the catch block and only keep the `finally` intact.
Uwe
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4150567300
Quote from stream Java docs:
> A stream should be operated on (invoking an intermediate or terminal stream operation) only once. This rules out, for example, "forked" streams, where the same source feeds two or more pipelines, or multiple traversals of the same stream. A stream implementation may throw IllegalStateException if it detects that the stream is being reused. However, since some stream operations may return their receiver rather than a new stream object, it may not be possible to detect reuse in all cases.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3008266256
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +177,38 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Adds all elements of the stream into the queue. This method should be preferred over calling
+ * {@link #add(Object)} in loop if all elements are known in advance as it builds queue faster.
+ *
+ * <p>If one needs to map or filter element in the iteration of elements in this method, call this
+ * method with elements wrapped by {@link Stream#map(Function)} or {@link
+ * Stream#filter(Predicate)}, etc. In these cases, this method should be preferred over calling
+ * {@link #addAll(Collection)}.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown. Which may result in parts of elements added into the
+ * queue, but the heap is still stay in correct state. In this case, if caller wants to readd or
+ * {@link #updateTop(Object)} with remaining elements, it should use a new stream, and use {@link
+ * Stream#skip(long)} to skip consumed elements with the delta size of queue.
+ */
+ public void addAll(Stream<T> elements) {
+ // Heap with size S always takes first S elements of the array,
+ // and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
+ try {
+ elements.forEach(
Review Comment:
Nitpick: Better to use `forEachOrdered()`. This makes practically no difference unless stream is parallel, but we should be correct here. Especially when we have the `skip(long)` mentioned in the javadcos.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4143128954
Thanks for the iteration! I also like where this change has evolved.
@uschindler - I don't completely follow your comment about addAll only working on a newly-constructed/empty heap. Can you elaborate a bit? I believe both of the addAll methods (existing and this proposed one) should work correctly on a heap that already contains some elements, but I might be missing something? Or maybe I'm misunderstanding your point? Oh wait, after re-reading, maybe you're describing a different option that would appropriately size a new heap for a provided stream? One that would handle the overflow case by essentially allocating a bigger PQ?
One thing that jumps out to me: The Stream-based and Collection-based addAll methods are inconsistent with how they handle the overflow/error case. The existing, Collection-based implementation won't add anything if it would overflow the PQ (so the PQ instance stayed unchanged on an invalid call). The Stream-based version best-effort adds until it discovers an overflow, then ensures the heap invariant with the finally block. This behavior makes sense to me for the Stream-based version—it's essentially all we can do since we don't know the size up-front. But it makes me wonder if we should change the Collection-based version to be consistent, and add what's possible, maintain the heap invariant, then throw.
Oh, and +1 to the try/catch paradigm vs. using #limit and silently failing to add everything.
Thanks again!
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3010523742
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +177,38 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Adds all elements of the stream into the queue. This method should be preferred over calling
+ * {@link #add(Object)} in loop if all elements are known in advance as it builds queue faster.
+ *
+ * <p>If one needs to map or filter element in the iteration of elements in this method, call this
+ * method with elements wrapped by {@link Stream#map(Function)} or {@link
+ * Stream#filter(Predicate)}, etc. In these cases, this method should be preferred over calling
+ * {@link #addAll(Collection)}.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown. Which may result in parts of elements added into the
+ * queue, but the heap is still stay in correct state. In this case, if caller wants to readd or
+ * {@link #updateTop(Object)} with remaining elements, it should use a new stream, and use {@link
+ * Stream#skip(long)} to skip consumed elements with the delta size of queue.
+ */
+ public void addAll(Stream<T> elements) {
+ // Heap with size S always takes first S elements of the array,
+ // and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
+ try {
+ elements.forEachOrdered(
+ element -> {
+ this.heap[size + 1] = element;
+ this.size++;
Review Comment:
No there is no concurrency bug lurking here. There is no need to call "sequential". I think you have a misunderstanding here.
The stream itsself will never call the final thing in a concurrent way. The implementantion is only required to call the final forEach in correct order, it will never be async, so the above code here is semantically corrcet.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4168635670
> I think there is a bit of backwards compatibility issue because the already existing Collection based version now behaves a bit different on exception.
Oh, I missed this.
> Here it is similar: If you hit an exception the difference is now that heap is sane afterwards, before it was not sane. So it is better afterwards. Anybody who tried to cleanup from it in the past would have made the heap sane, but doing that twice is not an issue.
+1.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4141188984
> To prevent an ArrayIndexOutOfBounds we could also apply a .limit(remaining) to the stream
> Alternatively maybe add a test for the new method to verify heap keeps intact when adding too many elements.
Current implementation will throw an `ArrayIndexOutOfBoundsException` when elements's size exceeds, and tested by `TestPriorityQueue#testAddAllWithStreamNotFitIntoQueue`.
> Maybe add a try/catch around the stream consumer to transform the exception to something more meaningful with a good error message.
The original error message is `Index $maxsize out of bounds for length $maxsize`.
Since we can't get size from stream (right?), how about `no remaining capacity, but $(maxSize - size) elements were added into the queue`?
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4172440920
@uschindler do you know what our policy generally is on `@lucene.internal` tagged classes w.r.t. backwards compatibility? My understanding was that we can be a little more flexibility within reason on these tagged classes. Either way, I still think we should bring this to 10.5 personally.
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2964463209
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
I use Guava's `Iterables` implemented it, it works too (transform in iterating). Here is the code(haven't committed):
````
public <S> void addAll(
Collection<S> elements, com.google.common.base.Function<S, T> elementConverter) {
if (this.size + elements.size() > this.maxSize) {
throw new ArrayIndexOutOfBoundsException(
"Cannot add "
+ elements.size()
+ " elements to a queue with remaining capacity: "
+ (maxSize - size));
}
Iterable<T> transform = Iterables.transform(elements, elementConverter);
// Heap with size S always takes first S elements of the array,
// and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
for (T element : transform) {
this.heap[size + 1] = element;
this.size++;
}
// The loop goes down to 1 as heap is 1-based not 0-based.
for (int i = (size >>> 1); i >= 1; i--) {
downHeap(i);
}
}
````
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2988354176
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +176,36 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link Function} to transform element.
+ * This method should be preferred over calling {@link #addAll(Collection)}, when the type of
+ * param elements is different from the type of this {@link PriorityQueue}, since it doesn't
+ * require the caller to do the conversion at the call site.
+ */
+ public <S> void addAll(Collection<S> elements, Function<S, T> elementTransformer) {
Review Comment:
I wonder how important that validation is. It's an exceptional case (the caller really shouldn't be overflowing their PQ capacity). We'll hit the same AIOOB exception anyway in the for-each loop that's populating the array, so the outcome is really the same if you overflow the capacity, so I'm not sure that early check adds a ton of value. It's nice to do up-front, but I don't think I'd design the API around it. So I guess I don't think it's a problem to remove this up-front sizing check, but maybe you're considering something I'm not? Do you think it's critical? Thanks again for iterating!
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4132439091
Hi,
I don't think we should add those self made Spliterators and all this internal collection wrapper stuff.
What I generally do when I want a filtered Iterator: get a stream from the collection/it's able (for iterables there's a trick to get it, but I'd prefer a collection instead of Iterables). The use all stream filtering or mapping and finally wrap the thing into an iterator.
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4132615538
Yes, or instead of foreach call iterator()
--
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] Add PriorityQueue#addNoShift, and use it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4083870463
I'm a bit uncomfortable with adding a "no shift" API to PQ. It has potential to be pretty trappy. Is there a better way to get at what you're trying to do? Maybe we could leverage `#addAll` from the DisjunctionMaxBulkScorer ctor? I get that we don't need the downHeap operation if everything is actually equal, but it doesn't seem particularly expensive?
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2963757966
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
Sure, it makes sense.
--
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] Add PriorityQueue#addNoShift, and use it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4087999594
> Maybe we could leverage #addAll from the DisjunctionMaxBulkScorer ctor?
I used an variant: add an `ElementSupplier` avoid duplicate loop.
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2960834947
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
Can you add test coverage for this method?
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
Review Comment:
Maybe we could be more explicit in the documentation that the value of this version of addAll is for cases where you need to convert between element types since it doesn't require the caller to do the conversion at the call site?
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
What if we just use `Function<S, T>` as the type of `elementSupplier` here so we don't need another interface definition?
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2964077508
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
Review Comment:
I added more documentation, not sure it is explicit enough.
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
Added.
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2964463209
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +179,32 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link ElementSupplier} to convert origin
+ * element to target element. This is useful when source elements does not fit target elements.
+ */
+ public <S> void addAll(Collection<S> elements, ElementSupplier<T, S> elementSupplier) {
Review Comment:
I use Guava's `Iterables` implemented it, it works too (transform in iterating). Here is the code(uncommitted):
````
public <S> void addAll(
Collection<S> elements, com.google.common.base.Function<S, T> elementConverter) {
if (this.size + elements.size() > this.maxSize) {
throw new ArrayIndexOutOfBoundsException(
"Cannot add "
+ elements.size()
+ " elements to a queue with remaining capacity: "
+ (maxSize - size));
}
Iterable<T> transform = Iterables.transform(elements, elementConverter);
// Heap with size S always takes first S elements of the array,
// and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
for (T element : transform) {
this.heap[size + 1] = element;
this.size++;
}
// The loop goes down to 1 as heap is 1-based not 0-based.
for (int i = (size >>> 1); i >= 1; i--) {
downHeap(i);
}
}
````
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4132805889
For PQ we can also add a much simpler method: `#addAll(Stream<T> stream)` without any filter function. Then it is up to the caller to provide the stream and map/filter whatever it likes to do it. Documentation needs to say that this `addAll` method consumes the stream fully.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4140584400
Looks good. To prevent an ArrayIndexOutOfBounds we could also apply a `.limit(remaining)` to the stream passed to `addAll` and possibly change the Java docs to state that at most something like `maxSize - size` are consumed from stream.
Alternatively maybe add a test for the new method to verify heap keeps intact when adding too many elements. Maybe add a try/catch around the stream consumer to transform the exception to something more meaningful with a good error message.
I will have a close look later.
--
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] Implement Iterables#transform function and change the input type of elements in PriorityQueue#addAll from Collection to Iterable. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4133149036
> Java 8+ users: several common uses for this class are now more comprehensively addressed by the new Stream library. Read the method documentation below for comparisons. This class is not being deprecated, but we gently encourage you to migrate to streams.
OK, Stream is also encouraged by Guava.
So we can add a method `#addAll(Collection<S> elements, Function<S, T> elementTransformer)` and use `elements.stream().map(elementTransformer)` to filter in it, or `#addAll(Stream<T> stream)` and let the caller to filter or not but need removing the size validation.
> we don't know size before so allocation may be harder and ineffective.
I am a bit confused about why the size of elements affects PQ's allocation, does not PQ allcated according to its `maxSize`?
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4143136638
Oh, I also noticed you're targeting 11.0 to release this. Is there any reason not to target 10.5 instead?
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4142003259
> > To prevent an ArrayIndexOutOfBounds we could also apply a .limit(remaining) to the stream
>
> > Alternatively maybe add a test for the new method to verify heap keeps intact when adding too many elements.
>
> Current implementation will throw an `ArrayIndexOutOfBoundsException` when elements's size exceeds, and tested by `TestPriorityQueue#testAddAllWithStreamNotFitIntoQueue`.
>
> > Maybe add a try/catch around the stream consumer to transform the exception to something more meaningful with a good error message.
>
> The original error message is `Index $maxsize out of bounds for length $maxsize`. Since we can't get size from stream (right?), how about `no remaining capacity, but $(maxSize - size) elements were added into the queue`?
Yes stream does not know its size (like iterator). Internally it may know, but you can't get it.
Therefor we have 2 possibilities:
- try/catch the exception and - I like it - fix the heap in a finally to not leave it in a broken state.
- limit the stream from beginning using `stream.limit()` in the implementation (so never try to add more elements from stream that could overflow the PQ) - but then we get no exception and it silently discards more elements on stream.
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "vsop-479 (via GitHub)" <gi...@apache.org>.
vsop-479 commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4150165859
I think there is a difference between add and addAll, with add the caller can use the element to compare to PQ’s top and maybe pop the top and reAdd the element after got an AIOOBE(maybe the normal usage is judge wether the queue is full firstly?), but if we want addAll behave the same after AIOOBE, we need keep remaining elements in the stream, so the caller can add them intersect(maybe stream already works like this? I will verify it)
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r3010979109
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +177,38 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Adds all elements of the stream into the queue. This method should be preferred over calling
+ * {@link #add(Object)} in loop if all elements are known in advance as it builds queue faster.
+ *
+ * <p>If one needs to map or filter element in the iteration of elements in this method, call this
+ * method with elements wrapped by {@link Stream#map(Function)} or {@link
+ * Stream#filter(Predicate)}, etc. In these cases, this method should be preferred over calling
+ * {@link #addAll(Collection)}.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown. Which may result in parts of elements added into the
+ * queue, but the heap is still stay in correct state. In this case, if caller wants to readd or
+ * {@link #updateTop(Object)} with remaining elements, it should use a new stream, and use {@link
+ * Stream#skip(long)} to skip consumed elements with the delta size of queue.
+ */
+ public void addAll(Stream<T> elements) {
+ // Heap with size S always takes first S elements of the array,
+ // and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
+ try {
+ elements.forEachOrdered(
+ element -> {
+ this.heap[size + 1] = element;
+ this.size++;
Review Comment:
> No doubt I likely have a misunderstanding here :). I don't often leverage streams to be honest.
>
> If I'm understanding, your point here is that `forEachOrdered` is going to guarantee sequential invocation. Is that correct? I took a look at the [documentation](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/stream/Stream.html#forEachOrdered(java.util.function.Consumer))[1] and it seems to highlight this point as well.
Yes that what I am after. The difference betwen forEach() and forEachOrdered is just the order. Because of the defined order (oteratoion order of the stream), you can repeat the operation after an exception, stepping over the already processed ones (using skipping as mentioned in the docs here).
> Apologies for the confusion. I should have looked at this documentation first.
No problem. Parallel streams often make people think they need to prevent this, but it is only an issue if non-terminal operations change the stream. E.g., if the map() method's lambda would change the collection. Foreach is a terminal operation, you can be sure it is running in order with happens-before.
> [1] "Performing the action for one element [**happens-before**](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/package-summary.html#MemoryVisibility) performing the action for subsequent elements"
Thanks for that documentation hint, this makes sure for-each is sequential and itsself is not parallelized. In fact, `forEach()`, `forEachOrdered() or iterator() disables parallelization on the stream anyways, therefor features like `` collect()` or `reduce()` are much better when you have a parallel stream.
Foreach converts the stream to a for-each loop. Alternatively, we could also call `iterator()` on the stream and consume the iterator like this:
```java
Iterable<T> it = () -> stream.iterator();
for (T element : it) {
this.heap[size + 1] = element;
this.size++;
}
```
Of course that's not really better readable.
--
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] Implement method to convert and add all collection elements to a PriorityQueue, and leverage it in DisjunctionMaxBulkScorer's constructor. [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #15823:
URL: https://github.com/apache/lucene/pull/15823#discussion_r2985032890
##########
lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java:
##########
@@ -174,6 +176,36 @@ public void addAll(Collection<T> elements) {
}
}
+ /**
+ * Similar to {@link #addAll(Collection)}, but supply an {@link Function} to transform element.
+ * This method should be preferred over calling {@link #addAll(Collection)}, when the type of
+ * param elements is different from the type of this {@link PriorityQueue}, since it doesn't
+ * require the caller to do the conversion at the call site.
+ */
+ public <S> void addAll(Collection<S> elements, Function<S, T> elementTransformer) {
Review Comment:
So I think the proposed idea is a little different actually. The idea would be for this method signature to simply be:
`public void addAll(Iterable<T> elements)`.
Then, from your calling code in DisjunctionMaxBulkScorer, you'd call like this:
`this.scorers.addAll(Iterables.transform(scorers, BulkScorerAndNext::new));`
The goal is that PriorityQueue doesn't need to know anything about the translation logic. That all gets encapsulated behind the Iterator that is setup by the calling code. WDYT?
--
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] Implement method to add all stream elements into a PriorityQueue. [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #15823:
URL: https://github.com/apache/lucene/pull/15823#issuecomment-4167953920
I think there is a bit of backwards compatibility issue because the already existing Collection based version now behaves a bit different on exception. But I don't know if this is really an issue (does anybody adds element with a collection to an already full PQ)?
--
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