Speed up freelist by using intrinsics to find last set bit.

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 <map>
 
 #include "vm/bit_set.h"
 #include "vm/lockers.h"
@@ skipping 213 matching lines @@
   }
   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 && index != kNumLists) {
-    free_map_.Set(index, false);
     intptr_t size = index << kObjectAlignmentLog2;
     if (size == last_free_small_size_) {
-      // Note: Last() returns -1 if none are set; avoid shift of negative.
-      last_free_small_size_ = free_map_.Last() * kObjectAlignment;
-      // TODO(koda): Consider adding BitSet::Previous(i).
+      // Note: This is -1 * kObjectAlignment if no other small sizes remain.
+      last_free_small_size_ =
+          free_map_.ClearLastAndFindPrevious(index) * kObjectAlignment;
+    } else {
+      free_map_.Set(index, false);
     }
   }
   free_lists_[index] = next;
   return result;
 }
 
 
 intptr_t FreeList::LengthLocked(int index) const {
   DEBUG_ASSERT(mutex_->Owner() == Isolate::Current());
   ASSERT(index >= 0);
@@ skipping 143 matching lines @@
     if (next_index != -1) {
       FreeListElement* element = DequeueElement(next_index);
       SplitElementAfterAndEnqueue(element, size, false);
       return reinterpret_cast<uword>(element);
     }
   }
   return 0;
 }
 
 }  // namespace dart