Uploaded image for project: 'Apache YuniKorn'
  1. Apache YuniKorn
  2. YUNIKORN-1715 Yunikorn performance improvements
  3. YUNIKORN-1719

Improve the performance of Application.sortRequests()

    XMLWordPrintableJSON

Details

    • Sub-task
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 1.3.0
    • None

    Description

      Too much time can be spent in Application.sortRequests(). There are various ways to solve this problem.

      Two competing approaches:

      1. Store requests in a sorted data structures (btree.BTree from Google)
      2. 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).

      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
      

      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.

      Attachments

        Activity

          People

            pbacsko Peter Bacsko
            pbacsko Peter Bacsko
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: