Hean-Chhinling opened a new pull request, #7278: URL: https://github.com/apache/hadoop/pull/7278
### Description of PR This PR addresses the TimSort contract violation issue in the `PriorityQueueComparator` class, which was identified when sorting queue with resource (0, 0) and queue resource(any number, any number). The comparator previously failed to maintain transitivity of TimSort, leading to `java.lang.IllegalArgumentException: Comparison method violates its general contract!` during sorting. **Root Cause** The issue occurred due to inconsistent comparison logic that violated the transitivity rules required by TimSort. Specifically, at the following code lines the AND condition that only compare the resources if both queues' resources are not none. However, when one of the queue resource is `none or (0, 0)` and the other queue resource is `not none` it skips this condition and go to compare based on the `absoluteCapacity` and when both of the queues' `absoluteCapacity` are the same, it leads to both queues equal each other even though their resources are different. For more detail example of how this behaviour break the TimSort algorithm please see this attachment. [ExampleZeroQueueResourceProblem](https://issues.apache.org/jira/secure/attachment/13073555/ExampleZeroQueueResourceproblem.pdf ) ``` if (!minEffRes1.equals(Resources.none()) && !minEffRes2.equals( Resources.none())) { return minEffRes2.compareTo(minEffRes1); } float abs1 = q1Sort.absoluteCapacity; float abs2 = q2Sort.absoluteCapacity; return Float.compare(abs2, abs1); ``` **Solution** Instead of checking if both queues' resource are not none. We should only check if _one of the queue's resource is not none_. This way to avoid skipping the queue resource comparison when we have one queue resource is not none and the other one is none. Specifically, change from AND condition to OR condition at the following codes: ` if (!minEffRes1.equals(Resources.none()) || !minEffRes2.equals( Resources.none())) { return minEffRes2.compareTo(minEffRes1); } ` **Testing** - Added a unit test `testPriorityQueueComparatorClassDoesNotViolateTimSortContract` to verify that sorting no longer throws `java.lang.IllegalArgumentException: Comparison method violates its general contract!`. - The test includes setting resource instance (0, 0) and resource(any number, any number) then shuffle the repeated queues that were created and then sort in using the `PriorityQueueComparator` class. It also mock the necessary elements, for example, `priority` `label`, `absoluteUsedCapacity`, `usedCapacity` and `absoluteCapacity`. These elements can be of any number. **Impact** - Resolves the `TimSort` violation, ensuring stable and predictable sorting for `PriorityQueueComparator` class. - No functional impact on other areas of the codebase. ### For code changes: - [X] Does the title or this PR starts with the corresponding JIRA issue id (e.g. 'HADOOP-17799. Your PR title ...')? - [ ] Object storage: have the integration tests been executed and the endpoint declared according to the connector-specific documentation? - [ ] If adding new dependencies to the code, are these dependencies licensed in a way that is compatible for inclusion under [ASF 2.0](http://www.apache.org/legal/resolved.html#category-a)? - [ ] If applicable, have you updated the `LICENSE`, `LICENSE-binary`, `NOTICE-binary` files? -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
