Favor free list allocation to bump pointer allocation.

Favor free list allocation to bump pointer allocation.

This change improves the utilization of the smallest size classes on
benchmarks performing old space allocations including Splay, Box2D,
and Dart2JSCompileAll.

Initial measurements showed that free list allocation was slightly
slower than bump pointer allocation.  Profiling identified that free
list allocation spent most of its time searching for a matching size
class.  To eliminate this overhead, a bitmap index has been added
resulting in no appreciable difference in running time between either
method.

Committed: https://code.google.com/p/dart/source/detail?r=9773

[siva, 2012-07-19 19:38:23]

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.cc
File runtime/vm/freelist.cc (right):

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.cc#newcode163
runtime/vm/freelist.cc:163: intptr_t size = length * kObjectAlignment;
Shouldn't this be length * i * kObjectAlignment;

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.cc#newcode166
runtime/vm/freelist.cc:166: }
Would it also make sense to print the indexes that have no free elements i.e
free_lists[i] == NULL.

Also would be helpful if you printed the size alongside Index 
Index(size) so that we don't have to do the math everytime

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.h
File runtime/vm/freelist.h (right):

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.h#newcode8
runtime/vm/freelist.h:8: #include <bitset>
The compiler uses our BitVector class for all these kinds of bitmap needs.
This comes back to the generic question do we use our home brewed data
structures or the stl ones.

[cshapiro, 2012-07-19 22:34:29]

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.cc
File runtime/vm/freelist.cc (right):

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.cc#newcode163
runtime/vm/freelist.cc:163: intptr_t size = length * kObjectAlignment;
I think so.  Done.

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.cc#newcode166
runtime/vm/freelist.cc:166: }
Printing out the empty free list elements is pretty noisy for what I needed. 
Maybe that will be useful in the future, but for the time being it is just
clutter.  I think this report can be made more useful having some other ways of
aggregating the information and I intend to improve it.

As for the free list index versus size issue, I have changed the first column to
report the size in bytes rather than the (size / kObjectAlignment).

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.h
File runtime/vm/freelist.h (right):

http://codereview.chromium.org/10807031/diff/1/runtime/vm/freelist.h#newcode8
runtime/vm/freelist.h:8: #include <bitset>
With regard to our off-line discussion, this is a distinct type whose behavior
is sufficiently different from BitVector to justify its existence.

[siva, 2012-07-20 01:28:37]

lgtm