Avoid scanning huge freelists for large enough free blocks.

runtime/vm/freelist.cc

Index: runtime/vm/freelist.cc
diff --git a/runtime/vm/freelist.cc b/runtime/vm/freelist.cc
index cdb83fab43fb7350c2a0b11577aec82c2ef9fc1a..d8b7dd616d03b0aea33c868920f341f847ee5c4c 100644
--- a/runtime/vm/freelist.cc
+++ b/runtime/vm/freelist.cc
@@ -51,7 +51,8 @@ intptr_t FreeListElement::HeaderSizeFor(intptr_t size) {
 }
 
 
-FreeList::FreeList() : mutex_(new Mutex()) {
+FreeList::FreeList()
+    : mutex_(new Mutex()), freelist_health_(kMaxFreelistHealth) {
   Reset();
 }
 
@@ -111,6 +112,8 @@ uword FreeList::TryAllocateLocked(intptr_t size, bool is_protected) {
 
   FreeListElement* previous = NULL;
   FreeListElement* current = free_lists_[kNumLists];
+  // We are willing to search the freelist further for a big block.
+  intptr_t tries_left = freelist_health_ + (size >> kWordSizeLog2);

[kustermann, 2017/05/10 21:39:40]

Maybe add a more elaborate comment explaining what this does, something like:

"""
For each successful free-list search we:
  * increase the search budget by #allocated-words
  * decrease the search budget by #free-list-entries-traversed
which guarantees us to not waste more than around 1 search step per word of
allocation

Furthermore, to guarantee reasonable allocation latency we limit the number of
searches to be at most kMaxFreelistHealth.

After falling back to allocating a new page, we reset the search budget.
"""

   while (current != NULL) {
     if (current->Size() >= size) {
       // Found an element large enough to hold the requested size. Dequeue,
@@ -159,7 +162,11 @@ uword FreeList::TryAllocateLocked(intptr_t size, bool is_protected) {
         }
       }
       SplitElementAfterAndEnqueue(current, size, is_protected);
+      freelist_health_ = Utils::Minimum(tries_left, kMaxFreelistHealth);

[kustermann, 2017/05/10 21:39:40]

The Utils::Minimum is only for reducing allocation latency, right?

We would still get the guarantee to not waste more than 1 free list search per
allocated word if we just set:

freelist_health_ = tries_left;

       return reinterpret_cast<uword>(current);
+    } else if (tries_left-- < 0) {
+      freelist_health_ = kMaxFreelistHealth;
+      return 0;  // Trigger allocation of new page.
     }
     previous = current;
     current = current->next();
@@ -382,6 +389,8 @@ FreeListElement* FreeList::TryAllocateLargeLocked(intptr_t minimum_size) {
   FreeListElement* previous = NULL;
   FreeListElement* current = free_lists_[kNumLists];
   // TODO(koda): Find largest.
+  // We are willing to search the freelist further for a big block.
+  intptr_t tries_left = freelist_health_ + (minimum_size >> kWordSizeLog2);
   while (current != NULL) {
     FreeListElement* next = current->next();
     if (current->Size() >= minimum_size) {
@@ -390,7 +399,11 @@ FreeListElement* FreeList::TryAllocateLargeLocked(intptr_t minimum_size) {
       } else {
         previous->set_next(next);
       }
+      freelist_health_ = Utils::Minimum(tries_left, kMaxFreelistHealth);
       return current;
+    } else if (tries_left-- < 0) {
+      freelist_health_ = kMaxFreelistHealth;
+      return 0;  // Trigger allocation of new page.
     }
     previous = current;
     current = next;