[YUNIKORN-1783] Application: maintain sorted state of requests instead of sorting

• Type: Sub-task
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.4.0
• Component/s: core - scheduler
• Labels: pull-request-available
• Assignee: Peter Bacsko
• Reporter: Peter Bacsko
• Created: 04/Jun/23 08:27
• Updated: 20/Nov/23 16:42
• Resolved: 06/Jun/23 15:09

Description

YUNIKORN-1719 improved the performance of scheduling by avoiding request sorting if it not necessary.

But the current logic can be further improved. When we create pods which belong to the same application, we can assume that in the overwhelming majority of cases, the following will be true:

• their createTime will be the same or later than those which already exist
• the piority will be the same

That is, when an ask comes in, we just have to append it to the end of the slice, we don't have to maintain a balanced, sorted tree, let alone sort it.

Even if we constantly have to insert pods with increasing priority, maintaining a sorted order is an O( n) operation in the worst case, not O(n log n) due to shifting elements.

Issue Links

• links to: GitHub Pull Request #560