Speed up IdAllocator.

gpu/command_buffer/common/id_allocator.cc

Index: gpu/command_buffer/common/id_allocator.cc
===================================================================
--- gpu/command_buffer/common/id_allocator.cc	(revision 86796)
+++ gpu/command_buffer/common/id_allocator.cc	(working copy)
@@ -14,33 +14,66 @@
 IdAllocator::~IdAllocator() {}
 
 ResourceId IdAllocator::AllocateID() {
-  ResourceId id = FindFirstFree();
+  ResourceId id;
+  ResourceIdSet::iterator iter = free_ids_.begin();
+  if (iter != free_ids_.end()) {
+    id = *iter;
+  } else {
+    id = LastUsedId() + 1;
+    if (!id) {
+      // We wrapped around to 0.
+      id = FindFirstUnusedId();
+    }
+  }
   MarkAsUsed(id);
   return id;
 }
 
 ResourceId IdAllocator::AllocateIDAtOrAbove(ResourceId desired_id) {
-  GPU_DCHECK_LT(static_cast<ResourceId>(used_ids_.size()),
-            static_cast<ResourceId>(-1));
-  for (; InUse(desired_id); ++desired_id) {}
-  MarkAsUsed(desired_id);
-  return desired_id;
+  ResourceId id;
+  ResourceIdSet::iterator iter = free_ids_.lower_bound(desired_id);
+  if (iter != free_ids_.end()) {
+    id = *iter;
+  } else if (LastUsedId() < desired_id) {
+    id = desired_id;
+  } else {
+    id = LastUsedId() + 1;
+    if (!id) {
+      // We wrapped around to 0.
+      id = FindFirstUnusedId();
+    }
+  }
+  MarkAsUsed(id);
+  return id;
 }
 
 bool IdAllocator::MarkAsUsed(ResourceId id) {
+  GPU_DCHECK(id);
+  free_ids_.erase(id);
   std::pair<ResourceIdSet::iterator, bool> result = used_ids_.insert(id);
   return result.second;
 }
 
 void IdAllocator::FreeID(ResourceId id) {
+  GPU_DCHECK(id);
   used_ids_.erase(id);
+  std::pair<ResourceIdSet::iterator, bool> result = free_ids_.insert(id);
+  GPU_DCHECK(result.second);
 }
 
 bool IdAllocator::InUse(ResourceId id) const {
   return id == kInvalidResource || used_ids_.find(id) != used_ids_.end();
 }
 
-ResourceId IdAllocator::FindFirstFree() const {
+ResourceId IdAllocator::LastUsedId() const {
+  if (used_ids_.empty()) {
+    return 0u;
+  } else {
+    return *used_ids_.rbegin();
+  }
+}
+
+ResourceId IdAllocator::FindFirstUnusedId() const {
   ResourceId id = 1;
   for (ResourceIdSet::const_iterator it = used_ids_.begin();
        it != used_ids_.end(); ++it) {