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

Application: maintain sorted state of requests instead of sorting

    XMLWordPrintableJSON

Details

    Description

      YUNIKORN-1719 improved the performance of scheduling by avoiding request sorting if it not necessary.

      But the current logic can be further improved. When we create pods which belong to the same application, we can assume that in the overwhelming majority of cases, the following will be true:

      • their createTime will be the same or later than those which already exist
      • the piority will be the same

      That is, when an ask comes in, we just have to append it to the end of the slice, we don't have to maintain a balanced, sorted tree, let alone sort it.

      Even if we constantly have to insert pods with increasing priority, maintaining a sorted order is an O( n) operation in the worst case, not O(n log n) due to shifting elements.

      Attachments

        Issue Links

          Activity

            People

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

              Dates

                Created:
                Updated:
                Resolved: