Speed up IdAllocator.

Speed up IdAllocator.

I noticed while debugging that FindFirstFree() was iterating
through all existing IDs, so it's O(n^2). This CL makes most
operations constant time by adding an explicit freelist (but
we need to fall back to a linear search in the worst case).

This will increase memory usage slightly, but only by as much
as the maximum number of IDs that were in use at any one time.
We won't get "garbage IDs" building up over time.

MarkAsUsed and FreeID both do an erase/insert pair. The erase
could be optimised out (as we've already done the lookup by
this point) but I figured it was clearer and simpler this way.

TEST=Existing
Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=87026

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

Just curious but did this actually show up on a profile?  It seems like you'd
have to be doing an awful lot of object creations per frame for this to matter
and any OpenGL app that is creating objects per frame is probably doing
something wrong.

http://codereview.chromium.org/7077006/diff/8/gpu/command_buffer/common/id_al...
File gpu/command_buffer/common/id_allocator.h (right):

http://codereview.chromium.org/7077006/diff/8/gpu/command_buffer/common/id_al...
gpu/command_buffer/common/id_allocator.h:45: typedef std::set<ResourceId>
ResourceIdSet;
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.

[lain Merrick, 2011-05-26 16:35:12]

On 2011/05/26 16:25:29, greggman wrote:
> Just curious but did this actually show up on a profile?  It seems like you'd
> have to be doing an awful lot of object creations per frame for this to matter
> and any OpenGL app that is creating objects per frame is probably doing
> something wrong.

Nope, it didn't, it just stuck out when I was stepping through the code.

I'm looking into accelerated compositing, rather than something like WebGL or
canvas where Javascript is in control, if that makes a difference. Some
degenerate pages can allocate a ton of textures (mainly because WebKit's
compositor is a bit naive).

>
http://codereview.chromium.org/7077006/diff/8/gpu/command_buffer/common/id_al...
> File gpu/command_buffer/common/id_allocator.h (right):
> 
>
http://codereview.chromium.org/7077006/diff/8/gpu/command_buffer/common/id_al...
> gpu/command_buffer/common/id_allocator.h:45: typedef std::set<ResourceId>
> ResourceIdSet;
> If were doing this for speed, how about changing this to a hash_set?

Hmm, I guess I could try that. Going from O(log n) to O(1) doesn't seem as big a
win as going from O(n^2) in the first place. And does hash_set have ordered
iteration?

I suspect it wouldn't make a difference (but you could say that about this CL
already...)

Sounds like I should go and do some profiling.

[lain Merrick, 2011-05-26 16:37:55]

On 2011/05/26 16:35:12, Iain Merrick wrote:
> Hmm, I guess I could try that. Going from O(log n) to O(1) doesn't seem as big
a
> win as going from O(n^2) in the first place.

Bleh, I'm being imprecise, sorry. For n operations, we're O(n^2), O(n log n) and
O(n) respectively for the linear scan, set and hash_set.

[greggman, 2011-05-26 17:07:19]

Ok, well, LGTM. We can do the hash_set thing later I guess.

[lain Merrick, 2011-05-26 17:08:44]

On 2011/05/26 17:07:19, greggman wrote:
> Ok, well, LGTM. We can do the hash_set thing later I guess.

Thanks! I'll do the profiling anyway, because you made me paranoid. :)

[M-A Ruel, 2011-05-26 18:06:46]

When you send try jobs with this change, it kills the try slaves, even with
clobber build! Examples:

http://build.chromium.org/p/tryserver.chromium/builders/win/builds/33786
http://build.chromium.org/p/tryserver.chromium/builders/win/builds/33780
http://build.chromium.org/p/tryserver.chromium/builders/win/builds/33771

I'll clean the mess manually but please stop sending try jobs.

[lain Merrick, 2011-05-26 18:07:32]

On 2011/05/26 18:06:46, Marc-Antoine Ruel wrote:
> When you send try jobs with this change, it kills the try slaves, even with
> clobber build! Examples:
> 
> http://build.chromium.org/p/tryserver.chromium/builders/win/builds/33786
> http://build.chromium.org/p/tryserver.chromium/builders/win/builds/33780
> http://build.chromium.org/p/tryserver.chromium/builders/win/builds/33771
> 
> I'll clean the mess manually but please stop sending try jobs.

Yikes, sorry. Thanks for the warning.

[M-A Ruel, 2011-05-26 18:22:31]

Ignore this, it's unrelated to your change. Something else is breaking the
slaves.

[lain Merrick, 2011-05-27 15:45:12]

Having done some profiling, with an admittedly artificial test involving lots of
texture churn, FindFirstFree is indeed a hotspot in this class. I's pretty
insignificant in the grand scheme of things, but I'll go ahead and submit. Now
that I've got profiling set up I can look for some bigger targets.