RFR: 6356745: (coll) Add PriorityQueue(Collection, Comparator) [v2]

[Stuart Marks]

On Tue, 19 Dec 2023 21:14:40 GMT, Valeh Hajiyev <duke at openjdk.org> wrote:

>> You should update the GitHub PR title to `6356745: (coll) Add PriorityQueue(Collection, Comparator)` to match the JBS issue title.
>> 
>> In addition, you will need a [CSR](https://wiki.openjdk.org/display/csr) as the bot tells you. Its prompt is like:
>> 
>> Summary
>> A concise description of the proposed change. The description should be one to two sentences long and written to be reusable in documents aggregating changes for a release.
>> 
>> Problem
>> A brief description of the problem, optionally including the motivation for developing a solution.
>> 
>> Solution
>> An overview of the solution. Alternative solutions may be discussed; links to rationale documents or review threads welcome to provide additional background to reviewers.
>> 
>> Specification
>> The detailed changes. Acceptable normative formats include inline patches, attached webrevs, and attached specdiffs. The names of attached files are recommended to include a bug id. References to external webservers, such as http://cr.openjdk.java.net/, can be provided as informative supplements for the convenience of reviewers, but must be accompanied by a normative form of the specification directly associated with the CSR issue to satisfy archival purposes.
>> 
>> 
>> I can create one for you, and here's my proposed CSR content:
>> 
>> Summary
>> Add a new constructor to PriorityQueue that takes a Collection and a Comparator.
>> 
>> Problem
>> Creating a PriorityQueue with an existing Collection and a custom Comparator is inefficient; it can use heapify which is `O(N)` in time complexity, but it currently has to be done via `addAll`, which has `O(N log N)` time complexity.
>> 
>> Solution
>> Add a new constructor `PriorityQueue(Collection, Comparator)` to explicitly allow the heapify process when a custom comparator is given. This constructor would be in pair with `PriorityQueue(Collection)`, as all other PriorityQueue constructors come in natural-order and comparator pairs (`()` and `(Comparator)`, `(int)` and `(int, Comparator)` ones)
>> 
>> An alternative solution would be to override `addAll(Collection)` to call `initFromCollection` when the PriorityQueue is empty. This would have the same effect as the new constructor and is applicable to all empty PriorityQueues, but doesn't solve the parity issue mentioned above.
>> 
>> Specification
>>     --- a/src/java.base/share/classes/java/util/PriorityQueue.java
>>     +++ b/src/java.base/share/classes/java/util/PriorityQueue.java
>>     @@ -209,6 +209,25 @@ else if (c instanc...
>
> @liach thanks for the help. I updated the PR title, also your proposed CSR content looks good to me. would you mind creating it with your proposed content?

@valeh

Hello, thanks for contributing this change. I can sponsor it.

Changes to the JDK such as this one require tests to be included. You can see some PriorityQueue tests in test/jdk/java/util/PriorityQueue. However, it looks like these are tests for specific features and bugfixes. A comprehensive set of tests resides in test/jdk/java/util/concurrent/tck/PriorityQueueTest.java. It might be best to add a test case for the new constructor there.

In addition, changes such as this will require a release note. I've added the `release-note=yes` label to the bug report to indicate this. The release note process is documented in the Developer's Guide here:

https://openjdk.org/guide/#release-notes

@liach 

Thanks for starting the CSR draft. It looks straightforward enough so far; a couple quick comments. 1) It's not necessary to include the implementation in the CSR, just the specification (or specification changes or diffs) and the method signature. 2) You might want to wait until the spec wording settles down before creating the CSR, otherwise you'll have to keep them in sync continually.

--

In passing, I note this Stack Overflow answer in response to a question about the lack of a PriorityQueue(Collection, Comparator) constructor:

https://stackoverflow.com/questions/66170496/java-priority-queue-build-heap-process-time-complexity/66174529#66174529

In the discussion of this bug report, I think we believe that constructing a PQ with the new constructor should be faster than constructing one with a Comparator and then calling addAll(), but this SO answer seems to indicate that this new constructor isn't necessary. I'm kind of skeptical of this, though. It would be good to have some confirmation that the new constructor indeed provides a performance improvement. Note however that benchmarking can easily turn into a distraction and a time sink, so I don't think a benchmark is required for this change. However, if somebody wants to try something out, please do so. If suitable, a benchmark could be added somewhere in the test/micro hierarchy (possibly as part of a different PR).

Finally, please note that with the holiday season, I'm planning to take several days away from work, so I might not respond quickly, but I eventually will.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/17045#issuecomment-1863858667