Favor free list allocation to bump pointer allocation.

runtime/vm/freelist.cc

Index: runtime/vm/freelist.cc
diff --git a/runtime/vm/freelist.cc b/runtime/vm/freelist.cc
index 959607e94eef99183345725f3aba5ea20348b8b1..8944aa15480597721ebdacba96afcbe0a5352404 100644
--- a/runtime/vm/freelist.cc
+++ b/runtime/vm/freelist.cc
@@ -49,14 +49,14 @@ FreeList::~FreeList() {
 
 uword FreeList::TryAllocate(intptr_t size) {
   int index = IndexForSize(size);
-  if ((index != kNumLists) && (free_lists_[index] != NULL)) {
+  if ((index != kNumLists) && free_map_[index]) {
     return reinterpret_cast<uword>(DequeueElement(index));
   }
 
   if (index < kNumLists) {
     index++;
     while (index < kNumLists) {
-      if (free_lists_[index] != NULL) {
+      if (free_map_[index]) {
         // Dequeue an element from the list, split and enqueue the remainder in
         // the appropriate list.
         FreeListElement* element = DequeueElement(index);
@@ -96,11 +96,13 @@ void FreeList::Free(uword addr, intptr_t size) {
 
 
 void FreeList::Reset() {
+  free_map_.reset();
   for (int i = 0; i < (kNumLists + 1); i++) {
     free_lists_[i] = NULL;
   }
 }
 
+
 intptr_t FreeList::IndexForSize(intptr_t size) {
   ASSERT(size >= kObjectAlignment);
   ASSERT(Utils::IsAligned(size, kObjectAlignment));
@@ -114,18 +116,60 @@ intptr_t FreeList::IndexForSize(intptr_t size) {
 
 
 void FreeList::EnqueueElement(FreeListElement* element, intptr_t index) {
-  element->set_next(free_lists_[index]);
+  FreeListElement* next = free_lists_[index];
+  if (next == NULL) {
+    free_map_[index] = true;
+  }
+  element->set_next(next);
   free_lists_[index] = element;
 }
 
 
 FreeListElement* FreeList::DequeueElement(intptr_t index) {
   FreeListElement* result = free_lists_[index];
-  free_lists_[index] = result->next();
+  FreeListElement* next = result->next();
+  if (next == NULL) {
+    free_map_[index] = false;
+  }
+  free_lists_[index] = next;
   return result;
 }
 
 
+intptr_t FreeList::Length(int index) const {
+  ASSERT(index >= 0);
+  ASSERT(index < kNumLists);
+  intptr_t result = 0;
+  FreeListElement* element = free_lists_[index];
+  while (element != NULL) {
+    ++result;
+    element = element->next();
+  }
+  return result;
+}
+
+
+void FreeList::Print() const {
+  OS::Print("%*s %*s %*s\n", 10, "Index", 10, "Length", 10, "Size");
+  OS::Print("--------------------------------\n");
+  int total_index = 0;
+  int total_length = 0;
+  int total_size = 0;
+  for (int i = 0; i < kNumLists; ++i) {
+    if (free_lists_[i] != NULL) {
+      total_index += 1;
+      intptr_t length = Length(i);
+      total_length += length;
+      intptr_t size = length * kObjectAlignment;

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

Shouldn't this be length * i * kObjectAlignment;

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

I think so.  Done.

+      total_size += size;
+      OS::Print("%*d %*d %*d\n", 10, i, 10, length, 10, size);
+    }

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

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

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

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).

+  }
+  OS::Print("--------------------------------\n");
+  OS::Print("%*d %*d %*d\n", 10, total_index, 10, total_length, 10, total_size);
+}
+
+
 void FreeList::SplitElementAfterAndEnqueue(FreeListElement* element,
                                            intptr_t size) {
   intptr_t remainder_size = element->Size() - size;