You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@yunikorn.apache.org by "Dale Richardson (Jira)" <ji...@apache.org> on 2026/08/08 00:51:00 UTC
[jira] [Updated] (YUNIKORN-3352) Replace the O(n) ask-priority rescan with a pending histogram
[ https://issues.apache.org/jira/browse/YUNIKORN-3352?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Dale Richardson updated YUNIKORN-3352:
--------------------------------------
Description:
{{Application.updateAskMaxPriority}} iterates the whole {{sa.requests}} map to recompute the highest priority among asks that are not yet allocated. It is called from {{allocateAsk}} on every allocation whose priority is at or above the current maximum, and again from {{removeAsksInternal}} on ask removal. Each call is O(number of asks), so scheduling N asks costs O(N^2), and the cost grows as an application gets larger.
It cannot stop early, because pending and allocated asks share one map — it has to test {{IsAllocated()}} on every entry, and that takes a read lock each time. In a CPU profile of master the function is {*}55% of {{Application.tryAllocate}}{*}, split 56% map iteration, 22% {{{}IsAllocated{}}}, 15% {{{}GetPriority{}}}.
Replace it with a per-priority histogram of pending asks ({{{}pendingPriorities map[int32]int{}}}), maintained incrementally as asks enter and leave the pending set, so {{askMaxPriority}} is available in O(1). {{updateAskMaxPriority}} is deleted.
was:
{{Application.updateAskMaxPriority}} iterates the whole {{sa.requests}} map to recompute the highest priority among asks that are not yet allocated. It is called from {{allocateAsk}} on every allocation whose priority is at or above the current maximum, and again from {{removeAsksInternal}} on ask removal. Each call is O(number of asks), so scheduling N asks costs O(N^2), and the cost grows as an application gets larger.
It cannot stop early, because pending and allocated asks share one map — it has to test
{{IsAllocated()}} on every entry, and that takes a read lock each time. In a CPU profile of master the function is {*}55% of {{Application.tryAllocate}}{*}, split 56% map iteration, 22% {{{}IsAllocated{}}}, 15% {{{}GetPriority{}}}.
Replace it with a per-priority histogram of pending asks ({{{}pendingPriorities map[int32]int{}}}), maintained incrementally as asks enter and leave the pending set, so {{askMaxPriority}} is available in O(1). {{updateAskMaxPriority}} is deleted.
> Replace the O(n) ask-priority rescan with a pending histogram
> -------------------------------------------------------------
>
> Key: YUNIKORN-3352
> URL: https://issues.apache.org/jira/browse/YUNIKORN-3352
> Project: Apache YuniKorn
> Issue Type: Sub-task
> Components: core - scheduler
> Reporter: Dale Richardson
> Assignee: Dale Richardson
> Priority: Major
>
> {{Application.updateAskMaxPriority}} iterates the whole {{sa.requests}} map to recompute the highest priority among asks that are not yet allocated. It is called from {{allocateAsk}} on every allocation whose priority is at or above the current maximum, and again from {{removeAsksInternal}} on ask removal. Each call is O(number of asks), so scheduling N asks costs O(N^2), and the cost grows as an application gets larger.
> It cannot stop early, because pending and allocated asks share one map — it has to test {{IsAllocated()}} on every entry, and that takes a read lock each time. In a CPU profile of master the function is {*}55% of {{Application.tryAllocate}}{*}, split 56% map iteration, 22% {{{}IsAllocated{}}}, 15% {{{}GetPriority{}}}.
> Replace it with a per-priority histogram of pending asks ({{{}pendingPriorities map[int32]int{}}}), maintained incrementally as asks enter and leave the pending set, so {{askMaxPriority}} is available in O(1). {{updateAskMaxPriority}} is deleted.
--
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