Dale Richardson created YUNIKORN-3352:
-----------------------------------------
Summary: 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
{{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: [email protected]
For additional commands, e-mail: [email protected]
