You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2022/03/27 02:03:42 UTC
[GitHub] [lucene] BaurzhanSakhariev opened a new pull request #770: Add PriorityQueue constructor accepting array as argument
BaurzhanSakhariev opened a new pull request #770:
URL: https://github.com/apache/lucene/pull/770
Hi!
This PR doesn't have a link to a Jira Issue as according to contribution guidelines I can either create a patch and attach it to an issue on Jira or open a pull request - let me know if I misunderstood things and have to create a Jira issue anyway.
# Description
`PriorityQueue` class doesn't have a constructor accepting array/collection and I created one for the cases, when heap elements are known in advance to save some time on queue creation: `O(N)` ([heapify](https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap)) vs `Nlog(N)` (calling add() in loop).
# Solution
JDK `PriorityQueue` has a constructor, accepting Collection and it internally uses `heapify` - this PR is basically adaptation of this method (index is not 0 but 1 based and no need to check comparator presence).
# Tests
I added a test creating a queue filled by random elements with the new method and checking its validity. Also added a potential usage (just took randomly first usage of `add`) and it didn't cause any failures.
Tried to run benchmarks using https://github.com/mikemccand/luceneutil but
got an error
```
src/python/competition.py", line 302
raise ValueError(f'mode must be "cpu" or "heap" but got: {mode}')
```
may I ask is there any detailed guide on running Lucene benchmarks?
# Checklist
Please review the following and check all that apply:
- [x] I have reviewed the guidelines for [How to Contribute](https://wiki.apache.org/lucene/HowToContribute) and my code conforms to the standards described there to the best of my ability.
- [ ] I have created a Jira issue and added the issue ID to my pull request title.
- [x] I have given Lucene maintainers [access](https://help.github.com/en/articles/allowing-changes-to-a-pull-request-branch-created-from-a-fork) to contribute to my PR branch. (optional but recommended)
- [x] I have developed this patch against the `main` branch.
- [x] I have run `./gradlew check`.
- [x] I have added tests for my changes.
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r836886681
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
Pulled out random and added comparison with JDK `PriorityQueue` as implementations are same and internal states are comparable, thanks!
Wanted to compare with Lucene` PriorityQueue` built by calling `add` in loop: their internal states were different but both were valid as one can build many valid heaps from the same array (for example, 1,2,3, 1 is root and children: 2/3 or 3/2) - didn't add case with `checkValidity` as it's already tested in other tests.
Not sure how compare with `Set `- internally they are different, the only similarity is that removing top element `size` times gets sorted array - but in case of Set it's already tested API, in case of Lucene PQ - validity is tested and other stuff is also tested/works given that current PQ implementation works fine with valid internal array.
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r837475991
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
removed. I was going to say that `heapify` must be same regardless of the vendor as it's defined algorithm - but then realized that JDK already differs (no index shift, 0-based) 😄
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r836886681
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
I added comparison with JDK `PriorityQueue` as implementations are same and internal states are comparable.
Wanted to compare with Lucene` PriorityQueue` built by calling `add` in loop: their internal states were different but both were valid as one can build many valid heaps from the same array (for example, 1,2,3, 1 is root and children: 2/3 or 3/2) - didn't add case with `checkValidity` as it's already tested in other tests.
Not sure how compare with `Set `- internally they are different, the only similarity is that removing top element `size` times gets sorted array - but in case of Set it's already tested API, in case of Lucene PQ - validity is tested and other stuff is also tested given that current PQ implementation works fine for heaps with valid internal array.
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838240191
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
> Looks good to me, thank you! Let's wait for checks to pass. Please add CHANGES.txt entry under the corresponding version (main or 9x, if you'd like this backported).
Thanks a lot for reviewing!
Added a CHANGES entry (without Jira issue as there is no one) to Lucene 9.2.0 under Improvements sections (since there is only one usage and there are more add-in-loop usages - so another PR with changing those could be Optimization).
I wanted to run a benchmark (saw nice tables with baseline comparison in other PR-s but couldn't do the same,
found out https://github.com/mikemccand/luceneutil but had some issues with running it. Probably not necessary anyway as I haven't replaced all other potential usages.
I don't think I can create issues in JIRA, but if there will be any to apply this method where possible I can address it (at least partially as it's probably big change).
Thanks again for the quick feedback!
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on pull request #770: Add PriorityQueue constructor accepting array as argument
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on pull request #770:
URL: https://github.com/apache/lucene/pull/770#issuecomment-1080022115
Fair point, I changed it to `addAll`. Also added a case to add into partially filled queue - just realized that you probably meant this use case and I misunderstood 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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838245085
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check it.
UPD: OK, assertion diff is in line ending - I started this PR on another machine, which is currently broken and switched to the windows machine with CRLF - it affected checksum change (fails on Windows machine because I have CRLF in _all_ files) and apparently tests - I think should be fine as I checked `testForceUCase` in debugger and it didn't even enter new method
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check it.
UPD: OK, assertion diff is in line ending - I started this PR on another machine, which is currently broken and switched to the windows machine with CRLF - it affected checksum change (fails on Windows machine because I have CRLF in _all_ files) and apparently tests - I think should be fine as I checked `testForceUCase` in debugger and it didn't even enter new method
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on pull request #770: Add PriorityQueue constructor accepting array as argument
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on pull request #770:
URL: https://github.com/apache/lucene/pull/770#issuecomment-1079892023
> Maybe add a method called addAll(Collection) which would be smart enough to detect when it can use this accelerated addition instead of element-by-element addition? I'm not sure an additional constructor is needed here.
Good point with `Collection`, thanks. No need to convert list to array if we don't use it directly anyway (because of 1-index shift) - can rather copy from collection.
It's always possible to build a heap if elements are provided and comparable - in JDK they check what kind of collection is provided and take comparator from it - but here we have `lessThan`. My understanding is that user decides whether it's possible to use faster addition - one of use cases when `add()` are not interrupted by `pop()` or any other structure changing operations, i.e when we build first and only then do something.
I added a constructor as other option would be to use existing ones and then do smth like `addAll(items)` - but I wanted to avoid usage of default constructor, filling it with sentinel null objects. But I actually found an issue in my constructor - need to add `maxSize >= ArrayUtil.MAX_ARRAY_LENGTH` check there, thanks!
Would it it be fine if I keep the constructor but adjust it to copy directly from `Collection` and add a size check?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-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
[GitHub] [lucene] dweiss commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
dweiss commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r836748820
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
Wouldn't it be good to cross-check against some other implementation of a PQ (or even a set) and make sure the elements held in both are the same? I'd also pull out random() outside any loop - this call is costly (the returned Random is cheap).
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838245085
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check it.
UPD: OK, assertion diff is in line ending - I started this PR on another machine, which is currently broken and switched to the windows machine with CRLF - it affected checksum change (fails on Windows machine) and apparently tests - I think should be fine as I checked `testForceUCase` in debugger and it didn't even enter new method
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r836886681
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
I added comparison with JDK `PriorityQueue` as implementations are same and internal states are comparable.
Wanted to compare with Lucene` PriorityQueue` built by calling `add` in loop: their internal states were different but both were valid as one can build many valid heaps from the same array (for example, 1,2,3, 1 is root and children: 2/3 or 3/2) - didn't add case with `checkValidity` as it's already tested in other tests.
Not sure how compare with `Set `- internally they are different, the only similarity is that removing top element `size` times gets sorted array - but in case of Set it's already tested API, in case of Lucene PQ - validity is tested and other stuff is also tested/works given that current PQ implementation works fine with valid internal array.
--
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
[GitHub] [lucene] dweiss commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
dweiss commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838264080
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
> fails on Windows machine because I have CRLF in all files
Don't do this, it's a nightmare. git checkout as-is and commit as-is (this can be configured in git for windows).
--
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
[GitHub] [lucene] dweiss commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
dweiss commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r837084866
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
Ah, sorry for not being clearer before - all I meant is to check whether the elements added are actually stored in the PQ (nothing was lost) and that they're in the right order when the PQ is drained. This is effectively equal to what you wrote but instead of comparing arrays, you'd need to drain the PQ (element ordering) and then compare against a (sorted) list of reference elements that you expect the PQ to hold. These two should be equal. I agree that comparing heap element-by-element may be too strict as the implementations may be different (but correct).
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838240191
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
> Looks good to me, thank you! Let's wait for checks to pass. Please add CHANGES.txt entry under the corresponding version (main or 9x, if you'd like this backported).
Thanks a lot for reviewing!
Added a CHANGES entry (without Jira issue as there is no one) to Lucene 9.2.0 under Improvements sections (there is only one usage and there are more add-in-loop usages - so another PR with changing those could be Optimization).
I wanted to run a benchmark (saw nice tables with baseline comparison in other PR-s but couldn't do the same,
found out https://github.com/mikemccand/luceneutil but had some issues with running it. Probably not necessary anyway as I haven't replaced all other potential usages.
I don't think I can create issues in JIRA, but if there will be any to apply this method where possible I can address it (at least partially as it's probably big change).
Thanks again for the quick feedback!
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838245085
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some failing - probably there is some flakiness, need to check it
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check 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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r837310904
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
done. I didn't remove internal array comparison with jdkQueue - if it's comparable probably good to have extra reassurance?
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838245085
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check it.
UPD: OK, assertion diff is in line ending - I started this PR on another machine where all checks and tests succeeded, which is currently unusable and switched to the Windows machine with CRLF line endings - it affected checksum change (fails on Windows machine because I have CRLF in _all_ files) and apparently some tests - I think should be fine as I checked `testForceUCase` in debugger and it didn't even enter the new method - I think it's just a local 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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838245085
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check it.
UPD: OK, assertion diff is in line ending - I started this PR on another machine where all checks and tests succeeded, which is currently unusable and switched to the Windows machine with CRLF line endings - it affected checksum change (fails on Windows machine because I have CRLF in _all_ files) and apparently some tests - I think should be fine as I checked `testForceUCase` in debugger and it didn't even enter the new method
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r837475991
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
removed. I was going to say that `heapify` must be same regardless of the vendor as it's defined algorithm - but then realized that JDK already differs (no index shift, 0-based and unit test used to specifically take care about 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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838245085
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check it.
UPD: OK, assertion diff is in line ending - I started this PR on another machine, which is currently broken and switched to the Windows machine with CRLF line endings - it affected checksum change (fails on Windows machine because I have CRLF in _all_ files) and apparently some tests - I think should be fine as I checked `testForceUCase` in debugger and it didn't even enter the new method
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838341280
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
looks like there are more things to make it work on windows (gradlew.bat check complains to the lack of perl) - I would rather hold on while I get another machine working - probably it's just local issue but would be better to run all checks.
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r837310904
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
done. I also kept internal array comparison with jdkQueue - if it's comparable probably good to have extra reassurance?
--
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
[GitHub] [lucene] dweiss commented on pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
dweiss commented on pull request #770:
URL: https://github.com/apache/lucene/pull/770#issuecomment-1083411399
I've added a proper issue number (https://issues.apache.org/jira/browse/LUCENE-10494) and tweaked minor details of the implementation (exception types thrown in addAll and add were different). I think it's good to go.
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838245085
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check it.
UPD: OK, assertion diff is in line ending - I started this PR on another machine, which is currently unusable and switched to the Windows machine with CRLF line endings - it affected checksum change (fails on Windows machine because I have CRLF in _all_ files) and apparently some tests - I think should be fine as I checked `testForceUCase` in debugger and it didn't even enter the new method
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838245085
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check it.
UPD: OK, assertion diff is in line ending - I started this PR on another machine, which is currently broken and switched to the Windows machine with CRLF line endings - it affected checksum change (fails on Windows machine because I have CRLF in _all_ files) and apparently tests - I think should be fine as I checked `testForceUCase` in debugger and it didn't even enter new method
--
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
[GitHub] [lucene] dweiss commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
dweiss commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838137561
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
+
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> oneByOne = new ArrayList<>();
+ List<Integer> bulkAdded = new ArrayList<>();
+ Random random = random();
+ for (int i = 0; i < 10; i++) {
+ bulkAdded.add(random.nextInt());
+
+ int x = random.nextInt();
+ pq.add(x);
+ oneByOne.add(x);
+ }
+
+ pq.addAll(bulkAdded);
+ pq.checkValidity();
+
+ oneByOne.addAll(bulkAdded); // Gather all "reference" data.
+ assertOrderedWhenDrained(pq, oneByOne);
+ }
+
+ public void testAddAllDontFitIntoQueue() {
Review comment:
```suggestion
public void testAddAllDoesNotFitIntoQueue() {
```
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
I think you'll have to run 'gradlew tidy' to clean up formatting 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
[GitHub] [lucene] dweiss commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
dweiss commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r837354373
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
I'd remove it. JDKs can change over time and (in theory) can be implemented by different vendors - I wouldn't tie the test to a particular reference implementation.
--
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
[GitHub] [lucene] dweiss commented on pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
dweiss commented on pull request #770:
URL: https://github.com/apache/lucene/pull/770#issuecomment-1083420937
Thank you!
--
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
[GitHub] [lucene] dweiss commented on pull request #770: Add PriorityQueue constructor accepting array as argument
Posted by GitBox <gi...@apache.org>.
dweiss commented on pull request #770:
URL: https://github.com/apache/lucene/pull/770#issuecomment-1079987498
> I wanted to avoid usage of default constructor, filling it with sentinel null objects
In all honesty, this is probably not something you can ever, ever notice when you compare the cost of building the heap with clearing a chunk of memory. And it makes the API simpler in my opinion. But sure, you can keep the constructor.
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r836886681
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +163,43 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random().nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+ pq.checkValidity();
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < 10; i++) {
+ list.add(random().nextInt());
+ pq.add(random().nextInt());
+ }
+ pq.addAll(list);
+ pq.checkValidity();
Review comment:
Pulled out random and added comparison with JDK `PriorityQueue` as implementations are same (when adding into empty queue) and internal states are comparable, thanks!
Wanted to compare with Lucene` PriorityQueue` built by calling `add` in loop: their internal states were different but both were valid as one can build many valid heaps from the same array (for example, 1,2,3, 1 is root and children: 2/3 or 3/2) - didn't add case with `checkValidity` as it's already tested in other tests.
Not sure how compare with `Set `- internally they are different, the only similarity is that removing top element `size` times gets sorted array - but in case of Set it's already tested API, in case of Lucene PQ - validity is tested and other stuff is also tested/works given that current PQ implementation works fine with valid internal array.
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838341280
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
looks like there are more things to make it work on windows (gradlew.bat check complains to the lack of perl) - I would rather hold on while I get another machine working - probably it's just local issue but would be better to run all checks.
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on pull request #770:
URL: https://github.com/apache/lucene/pull/770#issuecomment-1083556811
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
[GitHub] [lucene] dweiss merged pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
dweiss merged pull request #770:
URL: https://github.com/apache/lucene/pull/770
--
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
[GitHub] [lucene] BaurzhanSakhariev commented on a change in pull request #770: Implement method to bulk add all collection elements to a PriorityQueue
Posted by GitBox <gi...@apache.org>.
BaurzhanSakhariev commented on a change in pull request #770:
URL: https://github.com/apache/lucene/pull/770#discussion_r838245085
##########
File path: lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
##########
@@ -163,6 +164,57 @@ public void testInsertWithOverflow() {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
Review comment:
Hm, tests passed locally, now some are failing - probably there is some flakiness, need to check it.
UPD: OK, assertion diff is in line ending - I started this PR on another machine, which is currently broken and switched to the Windows machine with CRLF line endings - it affected checksum change (fails on Windows machine because I have CRLF in _all_ files) and apparently some tests - I think should be fine as I checked `testForceUCase` in debugger and it didn't even enter new method
--
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