[GitHub] [yunikorn-core] pbacsko commented on pull request #567: [YUNIKORN-1717] cache sortedQueues

["pbacsko (via GitHub)" <gi...@apache.org>]

pbacsko commented on PR #567:
URL: https://github.com/apache/yunikorn-core/pull/567#issuecomment-1591269504

   AFAIK this solution won't give too much speedup. It will eliminate sorting when no allocation occurs, however, all allocation will invalidate the cache. We want to optimize for the busy case, so I don't expect to see earth shattering results.
   
   Two things we can do:
   1. Store child queues in a BTree/Red-black tree and update it every time an allocation/pending resource changes. This is more complicated.
   2. We can check if an allocation changes the ordering with respect to other queues in the hierarchy. For example, our Queue is Q(n) and we did a sorting in the previous scheduling cycle:
   
   `Q(n-1) < Q(n) < Q(n+1)`
   
   We have to check if `Q(n-1) < Q(n)` and `Q(n) < Q(n+1)` still holds. If it does, then there's no need to sort, otherwise we invalidate the cached result. 
   
   But the thing is, eliminating request and application sorting (I have some local changes related to this) already gives a substantial performance boost. So we might as well just ignore it. We don't usually have thousands of queues. Performing quicksort (actually it's insertion sort if "n" less than 12) on 20-30 queues is not something which kills performance.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: reviews-unsubscribe@yunikorn.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org