Improve the performance of bit set searches with a compiler intrinsic.

runtime/vm/freelist.cc

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/freelist.h"
 
 #include "vm/bit_set.h"
 #include "vm/object.h"
 #include "vm/raw_object.h"
 
@@ skipping 36 matching lines @@
   // Nothing to release.
 }
 
 
 uword FreeList::TryAllocate(intptr_t size) {
   int index = IndexForSize(size);
   if ((index != kNumLists) && free_map_.Test(index)) {
     return reinterpret_cast<uword>(DequeueElement(index));
   }
 
-  if (index < kNumLists) {
-    index++;
-    while (index < kNumLists) {
-      if (free_map_.Test(index)) {
-        // Dequeue an element from the list, split and enqueue the remainder in
-        // the appropriate list.
-        FreeListElement* element = DequeueElement(index);
-        SplitElementAfterAndEnqueue(element, size);
-        return reinterpret_cast<uword>(element);
-      }
-      index++;
+  if ((index + 1) < kNumLists) {
+    intptr_t next_index = free_map_.Next(index + 1);
+    if (next_index == kNumLists) {
+      next_index = -1;
+    }

[siva, 2012/07/24 01:07:43]

per offline discussion this check could go away if you set up the freelist bit
set to be just 128 long.

+    if (next_index != -1) {
+      // Dequeue an element from the list, split and enqueue the remainder in
+      // the appropriate list.
+      FreeListElement* element = DequeueElement(next_index);
+      SplitElementAfterAndEnqueue(element, size);
+      return reinterpret_cast<uword>(element);
     }
   }
 
   FreeListElement* previous = NULL;
   FreeListElement* current = free_lists_[kNumLists];
   while (current != NULL) {
     if (current->Size() >= size) {
       // Found an element large enough to hold the requested size. Dequeue,
       // split and enqueue the remainder.
       if (previous == NULL) {
@@ skipping 99 matching lines @@
   intptr_t remainder_size = element->Size() - size;
   if (remainder_size == 0) return;
 
   element = FreeListElement::AsElement(reinterpret_cast<uword>(element) + size,
                                        remainder_size);
   intptr_t remainder_index = IndexForSize(remainder_size);
   EnqueueElement(element, remainder_index);
 }
 
 }  // namespace dart