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 != -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 33 matching lines @@
   intptr_t index = size / kObjectAlignment;
   if (index >= kNumLists) {
     index = kNumLists;
   }
   return index;
 }
 
 
 void FreeList::EnqueueElement(FreeListElement* element, intptr_t index) {
   FreeListElement* next = free_lists_[index];
-  if (next == NULL) {
+  if (next == NULL && index != kNumLists) {
     free_map_.Set(index, true);
   }
   element->set_next(next);
   free_lists_[index] = element;
 }
 
 
 FreeListElement* FreeList::DequeueElement(intptr_t index) {
   FreeListElement* result = free_lists_[index];
   FreeListElement* next = result->next();
-  if (next == NULL) {
+  if (next == NULL && index != kNumLists) {
     free_map_.Set(index, false);
   }
   free_lists_[index] = next;
   return result;
 }
 
 
 intptr_t FreeList::Length(int index) const {
   ASSERT(index >= 0);
   ASSERT(index < kNumLists);
@@ skipping 34 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