Changeset 3840 in CLRX


Ignore:
Timestamp:
Feb 23, 2018, 4:24:01 PM (16 months ago)
Author:
matszpk
Message:

CLRadeonExtender: SimpleCache?: Optimize updating sortedEntries after increasing element usage. Sort only by usage.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • CLRadeonExtender/trunk/amdasm/AsmRegAlloc.cpp

    r3839 r3840  
    459459   
    460460    typedef typename std::unordered_map<K, Entry>::iterator EntryMapIt;
    461     // sorted entries - sorted by weight
     461    // sorted entries - sorted by usage
    462462    std::vector<EntryMapIt> sortedEntries;
    463463    std::unordered_map<K, Entry> entryMap;
     
    465465    void updateInSortedEntries(EntryMapIt it)
    466466    {
    467         size_t i;
    468         for (i = it->second.sortedPos; i > 0 &&
    469              // sort by usage or if equal by weight in reverse order
    470              (sortedEntries[i-1]->second.usage < it->second.usage ||
    471               (sortedEntries[i-1]->second.usage == it->second.usage &&
    472                sortedEntries[i-1]->second.value.weight() < it->second.value.weight()));
    473               i--)
    474         {
    475             sortedEntries[i-1]->second.sortedPos++;
    476             std::swap(sortedEntries[i-1], sortedEntries[i]);
    477         }
    478         it->second.sortedPos = i;
     467        // update after increasing usage, just swap entries if needed
     468        auto fit = std::upper_bound(sortedEntries.begin(),
     469            sortedEntries.begin()+it->second.sortedPos, it,
     470            [](EntryMapIt it1, EntryMapIt it2)
     471            { return it1->second.usage > it2->second.usage; });
     472        if (fit != sortedEntries.begin()+it->second.sortedPos)
     473        {
     474            const size_t curPos = it->second.sortedPos;
     475            std::swap((*fit)->second.sortedPos, it->second.sortedPos);
     476            std::swap(*fit, sortedEntries[curPos]);
     477        }
    479478    }
    480479   
     
    483482        it->second.sortedPos = sortedEntries.size();
    484483        sortedEntries.push_back(it);
    485         updateInSortedEntries(it);
    486484    }
    487485   
Note: See TracChangeset for help on using the changeset viewer.