Speed up IdAllocator.

gpu/command_buffer/common/id_allocator.h

 // Copyright (c) 2009 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // This file contains the definition of the IdAllocator class.
 
 #ifndef GPU_COMMAND_BUFFER_CLIENT_ID_ALLOCATOR_H_
 #define GPU_COMMAND_BUFFER_CLIENT_ID_ALLOCATOR_H_
 
 #include <set>
@@ skipping 24 matching lines @@
   bool MarkAsUsed(ResourceId id);
 
   // Frees a resource ID.
   void FreeID(ResourceId id);
 
   // Checks whether or not a resource ID is in use.
   bool InUse(ResourceId id) const;
 
  private:
   // TODO(gman): This would work much better with ranges or a hash table.
   typedef std::set<ResourceId> ResourceIdSet;

[greggman, 2011/05/26 16:25:29]

If were doing this for speed, how about changing this to a hash_set?

Note: you'll have to copy hash_set from base into gpu/common/ as anything in
used in gpu/client can not depend on base.

 
-  ResourceId FindFirstFree() const;
+  // The highest ID on the used list.
+  ResourceId LastUsedId() const;
+
+  // Lowest ID that isn't on the used list. This is slow, use as a last resort.
+  ResourceId FindFirstUnusedId() const;
 
   ResourceIdSet used_ids_;
+  ResourceIdSet free_ids_;
 
   DISALLOW_COPY_AND_ASSIGN(IdAllocator);
 };
 
 }  // namespace gpu
 
 #endif  // GPU_COMMAND_BUFFER_CLIENT_ID_ALLOCATOR_H_