You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@yunikorn.apache.org by "Peter Bacsko (Jira)" <ji...@apache.org> on 2023/06/04 08:29:00 UTC
[jira] [Updated] (YUNIKORN-1783) Application: maintain sorted state of requests instead of sorting
[ 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: issues-unsubscribe@yunikorn.apache.org
For additional commands, e-mail: issues-help@yunikorn.apache.org