[
https://issues.apache.org/jira/browse/YUNIKORN-1783?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Peter Bacsko updated YUNIKORN-1783:
-----------------------------------
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.
was:
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.
> Application: maintain sorted state of requests instead of sorting
> -----------------------------------------------------------------
>
> Key: YUNIKORN-1783
> URL: https://issues.apache.org/jira/browse/YUNIKORN-1783
> Project: Apache YuniKorn
> Issue Type: Sub-task
> Components: core - scheduler
> Reporter: Peter Bacsko
> Assignee: Peter Bacsko
> Priority: Major
>
> 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.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
