kc3-lang/angle/src/libANGLE/HandleAllocator.cpp

• Show log

  Commit

• Hash : df4d9667
  Author :
  Date : 2023-12-13T18:28:53
  

  Revert "Optimize HandleAllocator for fast ID churning."
  
  This reverts commit b25ffe5a9775cc912a304c8552dd9c097a93420a.
  
  Reason for revert: b/316162914
  
  Original change's description:
  > Optimize HandleAllocator for fast ID churning.
  >
  > Instead of calculating ranges of IDs and the overhead with updating
  > them every allocation/release, store a released ID list in a small
  > FastVector.
  >
  > Optimize the allocate path for the "good case" of no reserved IDs so
  > that it either pops the last released ID or incriments a next value and
  > returns it. Release has a similar cost of just a push_back when there
  > are no reserved IDs.
  >
  > This adds a small fixed memory cost due to the FastVector and a dynamic
  > memory cost of mReleasedList having up to N elements where N is the
  > maxmimum total handles allocated at one time.
  >
  > Bug: angleproject:8434
  > Change-Id: I7c5aa126b5303c105cd2464d0d0933b922cc2b8f
  > Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/5101509
  > Reviewed-by: Charlie Lao <cclao@google.com>
  > Commit-Queue: Shahbaz Youssefi <syoussefi@chromium.org>
  
  Bug: angleproject:8434
  Change-Id: Ide43d787b6942cc6b622e3b5d938bfbbbf3b3ebb
  No-Presubmit: true
  No-Tree-Checks: true
  No-Try: true
  Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/5120277
  Commit-Queue: Shahbaz Youssefi <syoussefi@chromium.org>
  Reviewed-by: Shahbaz Youssefi <syoussefi@chromium.org>
  Bot-Commit: Rubber Stamper <rubber-stamper@appspot.gserviceaccount.com>
  

Download

• src/libANGLE/HandleAllocator.cpp

• //
  // Copyright 2002 The ANGLE Project Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  //
  
  // HandleAllocator.cpp: Implements the gl::HandleAllocator class, which is used
  // to allocate GL handles.
  
  #include "libANGLE/HandleAllocator.h"
  
  #include <algorithm>
  #include <functional>
  #include <limits>
  
  #include "common/debug.h"
  
  namespace gl
  {
  
  struct HandleAllocator::HandleRangeComparator
  {
      bool operator()(const HandleRange &range, GLuint handle) const { return (range.end < handle); }
  };
  
  HandleAllocator::HandleAllocator()
      : mBaseValue(1),
        mNextValue(1),
        mMaxValue(std::numeric_limits<GLuint>::max()),
        mLoggingEnabled(false)
  {
      mUnallocatedList.push_back(HandleRange(1, mMaxValue));
  }
  
  HandleAllocator::HandleAllocator(GLuint maximumHandleValue)
      : mBaseValue(1), mNextValue(1), mMaxValue(maximumHandleValue), mLoggingEnabled(false)
  {
      mUnallocatedList.push_back(HandleRange(1, mMaxValue));
  }
  
  HandleAllocator::~HandleAllocator() {}
  
  void HandleAllocator::setBaseHandle(GLuint value)
  {
      ASSERT(mBaseValue == mNextValue);
      mBaseValue = value;
      mNextValue = value;
  }
  
  GLuint HandleAllocator::allocate()
  {
      ASSERT(!mUnallocatedList.empty() || !mReleasedList.empty());
  
      // Allocate from released list, logarithmic time for pop_heap.
      if (!mReleasedList.empty())
      {
          std::pop_heap(mReleasedList.begin(), mReleasedList.end(), std::greater<GLuint>());
          GLuint reusedHandle = mReleasedList.back();
          mReleasedList.pop_back();
  
          if (mLoggingEnabled)
          {
              WARN() << "HandleAllocator::allocate reusing " << reusedHandle << std::endl;
          }
  
          return reusedHandle;
      }
  
      // Allocate from unallocated list, constant time.
      auto listIt = mUnallocatedList.begin();
  
      GLuint freeListHandle = listIt->begin;
      ASSERT(freeListHandle > 0);
  
      if (listIt->begin == listIt->end)
      {
          mUnallocatedList.erase(listIt);
      }
      else
      {
          listIt->begin++;
      }
  
      if (mLoggingEnabled)
      {
          WARN() << "HandleAllocator::allocate allocating " << freeListHandle << std::endl;
      }
  
      return freeListHandle;
  }
  
  void HandleAllocator::release(GLuint handle)
  {
      if (mLoggingEnabled)
      {
          WARN() << "HandleAllocator::release releasing " << handle << std::endl;
      }
  
      // Try consolidating the ranges first.
      for (HandleRange &handleRange : mUnallocatedList)
      {
          if (handleRange.begin - 1 == handle)
          {
              handleRange.begin--;
              return;
          }
  
          if (handleRange.end == handle - 1)
          {
              handleRange.end++;
              return;
          }
      }
  
      // Add to released list, logarithmic time for push_heap.
      mReleasedList.push_back(handle);
      std::push_heap(mReleasedList.begin(), mReleasedList.end(), std::greater<GLuint>());
  }
  
  void HandleAllocator::reserve(GLuint handle)
  {
      if (mLoggingEnabled)
      {
          WARN() << "HandleAllocator::reserve reserving " << handle << std::endl;
      }
  
      // Clear from released list -- might be a slow operation.
      if (!mReleasedList.empty())
      {
          auto releasedIt = std::find(mReleasedList.begin(), mReleasedList.end(), handle);
          if (releasedIt != mReleasedList.end())
          {
              mReleasedList.erase(releasedIt);
              std::make_heap(mReleasedList.begin(), mReleasedList.end(), std::greater<GLuint>());
              return;
          }
      }
  
      // Not in released list, reserve in the unallocated list.
      auto boundIt = std::lower_bound(mUnallocatedList.begin(), mUnallocatedList.end(), handle,
                                      HandleRangeComparator());
  
      ASSERT(boundIt != mUnallocatedList.end());
  
      GLuint begin = boundIt->begin;
      GLuint end   = boundIt->end;
  
      if (handle == begin || handle == end)
      {
          if (begin == end)
          {
              mUnallocatedList.erase(boundIt);
          }
          else if (handle == begin)
          {
              boundIt->begin++;
          }
          else
          {
              ASSERT(handle == end);
              boundIt->end--;
          }
          return;
      }
  
      ASSERT(begin < handle && handle < end);
  
      // need to split the range
      auto placementIt = mUnallocatedList.erase(boundIt);
      placementIt      = mUnallocatedList.insert(placementIt, HandleRange(handle + 1, end));
      mUnallocatedList.insert(placementIt, HandleRange(begin, handle - 1));
  }
  
  void HandleAllocator::reset()
  {
      mUnallocatedList.clear();
      mUnallocatedList.push_back(HandleRange(1, mMaxValue));
      mReleasedList.clear();
      mBaseValue = 1;
      mNextValue = 1;
  }
  
  bool HandleAllocator::anyHandleAvailableForAllocation() const
  {
      return !mUnallocatedList.empty() || !mReleasedList.empty();
  }
  
  void HandleAllocator::enableLogging(bool enabled)
  {
      mLoggingEnabled = enabled;
  }
  
  }  // namespace gl
  

Download