Index: runtime/vm/freelist.cc |
diff --git a/runtime/vm/freelist.cc b/runtime/vm/freelist.cc |
index cdb83fab43fb7350c2a0b11577aec82c2ef9fc1a..e4a880e8113cb0f354f7a6b0a1d75f9f4d24ea96 100644 |
--- a/runtime/vm/freelist.cc |
+++ b/runtime/vm/freelist.cc |
@@ -51,7 +51,9 @@ intptr_t FreeListElement::HeaderSizeFor(intptr_t size) { |
} |
-FreeList::FreeList() : mutex_(new Mutex()) { |
+FreeList::FreeList() |
+ : mutex_(new Mutex()), |
+ freelist_search_budget_(kInitialFreeListSearchBudget) { |
Reset(); |
} |
@@ -111,6 +113,16 @@ 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. |
+ // 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 |
+ // |
+ // If we run out of search budget we fall back to allocating a new page and |
+ // reset the search budget. |
+ intptr_t tries_left = freelist_search_budget_ + (size >> kWordSizeLog2); |
while (current != NULL) { |
if (current->Size() >= size) { |
// Found an element large enough to hold the requested size. Dequeue, |
@@ -159,7 +171,12 @@ uword FreeList::TryAllocateLocked(intptr_t size, bool is_protected) { |
} |
} |
SplitElementAfterAndEnqueue(current, size, is_protected); |
+ freelist_search_budget_ = |
+ Utils::Minimum(tries_left, kInitialFreeListSearchBudget); |
return reinterpret_cast<uword>(current); |
+ } else if (tries_left-- < 0) { |
+ freelist_search_budget_ = kInitialFreeListSearchBudget; |
+ return 0; // Trigger allocation of new page. |
} |
previous = current; |
current = current->next(); |
@@ -382,6 +399,9 @@ 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_search_budget_ + (minimum_size >> kWordSizeLog2); |
while (current != NULL) { |
FreeListElement* next = current->next(); |
if (current->Size() >= minimum_size) { |
@@ -390,7 +410,12 @@ FreeListElement* FreeList::TryAllocateLargeLocked(intptr_t minimum_size) { |
} else { |
previous->set_next(next); |
} |
+ freelist_search_budget_ = |
+ Utils::Minimum(tries_left, kInitialFreeListSearchBudget); |
return current; |
+ } else if (tries_left-- < 0) { |
+ freelist_search_budget_ = kInitialFreeListSearchBudget; |
+ return 0; // Trigger allocation of new page. |
} |
previous = current; |
current = next; |