[jira] [Resolved] (YUNIKORN-1719) Improve the performance of Application.sortRequests()

["Craig Condit (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/YUNIKORN-1719?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Craig Condit resolved YUNIKORN-1719.
------------------------------------
     Fix Version/s: 1.3.0
    Target Version: 1.3.0
        Resolution: Fixed

Merged to master.

> Improve the performance of Application.sortRequests()
> -----------------------------------------------------
>
>                 Key: YUNIKORN-1719
>                 URL: https://issues.apache.org/jira/browse/YUNIKORN-1719
>             Project: Apache YuniKorn
>          Issue Type: Sub-task
>            Reporter: Peter Bacsko
>            Assignee: Peter Bacsko
>            Priority: Major
>              Labels: pull-request-available
>             Fix For: 1.3.0
>
>
> Too much time can be spent in {{{}Application.sortRequests(){}}}. There are various ways to solve this problem.
> Two competing approaches:
> # Store requests in a sorted data structures ({{btree.BTree}} from Google)
> # Only sort if a new request is added. If pendingAskRepeat becomes 0, simply skip it.
> Based on benchmarks, #2 is much simpler and even faster than the BTree based solution, even for 100,000 requests (that is, we go through the whole slice and only process asks where pendingAskRepeat > 0).
> {noformat}
> BenchmarkBtree_SmallItemCount
> BenchmarkBtree_SmallItemCount-6                    	 2143888	       553.1 ns/op	      80 B/op	       4 allocs/op
> BenchmarkIteration_DontRemovePendingAskRepeat0
> BenchmarkIteration_DontRemovePendingAskRepeat0-6   	 5071994	       253.9 ns/op	       0 B/op	       0 allocs/op
> BenchmarkIteration_AlwaysSort
> BenchmarkIteration_AlwaysSort-6                    	    3002	    395433 ns/op	     304 B/op	       7 allocs/op
> {noformat}
> {{BenchmarkBtree_SmallItemCount}} walks a btree with 10 elements.
> {{BenchmarkIteration_DontRemovePendingAskRepeat0}} goes through a slice of 100,000 elements but only 10 of them are interesting to us.
> {{BenchmarkIteration_AlwaysSort}} is what we have now.
> If we factor in adding requests / re-sorts, it's still better to sort.



--
This message was sent by Atlassian Jira
(v8.20.10#820010)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@yunikorn.apache.org
For additional commands, e-mail: dev-help@yunikorn.apache.org