central_freelist: fetch objects as much as possible during each trial

It is better to reduce function call if possible. If we try to fetch
objects from one span as much as possible during each function call,
number of function call would be reduced and this would help performance.

2 files changed, 40 insertions, 31 deletions

diff --git a/src/central_freelist.cc b/src/central_freelist.cc
index e442a49..65e67bb 100644
--- a/src/central_freelist.cc
+++ b/src/central_freelist.cc
@@ -258,52 +258,61 @@ int CentralFreeList::RemoveRange(void **start, void **end, int N) {
   }
 
   int result = 0;
-  void* head = NULL;
-  void* tail = NULL;
+  *start = NULL;
+  *end = NULL;
   // TODO: Prefetch multiple TCEntries?
-  tail = FetchFromSpansSafe();
-  if (tail != NULL) {
-    SLL_SetNext(tail, NULL);
-    head = tail;
-    result = 1;
+  result = FetchFromOneSpansSafe(N, start, end);
+  if (result != 0) {
     while (result < N) {
-      void *t = FetchFromSpans();
-      if (!t) break;
-      SLL_Push(&head, t);
-      result++;
+      int n;
+      void* head = NULL;
+      void* tail = NULL;
+      n = FetchFromOneSpans(N - result, &head, &tail);
+      if (!n) break;
+      result += n;
+      SLL_PushRange(start, head, tail);
     }
   }
   lock_.Unlock();
-  *start = head;
-  *end = tail;
   return result;
 }
 
 
-void* CentralFreeList::FetchFromSpansSafe() {
-  void *t = FetchFromSpans();
-  if (!t) {
+int CentralFreeList::FetchFromOneSpansSafe(int N, void **start, void **end) {
+  int result = FetchFromOneSpans(N, start, end);
+  if (!result) {
     Populate();
-    t = FetchFromSpans();
+    result = FetchFromOneSpans(N, start, end);
   }
-  return t;
+  return result;
 }
 
-void* CentralFreeList::FetchFromSpans() {
-  if (tcmalloc::DLL_IsEmpty(&nonempty_)) return NULL;
+int CentralFreeList::FetchFromOneSpans(int N, void **start, void **end) {
+  if (tcmalloc::DLL_IsEmpty(&nonempty_)) return 0;
   Span* span = nonempty_.next;
 
   ASSERT(span->objects != NULL);
-  span->refcount++;
-  void* result = span->objects;
-  span->objects = *(reinterpret_cast<void**>(result));
-  if (span->objects == NULL) {
-    // Move to empty list
-    tcmalloc::DLL_Remove(span);
-    tcmalloc::DLL_Prepend(&empty_, span);
-    Event(span, 'E', 0);
+
+  int result = 0;
+  *end = span->objects;
+  while (result < N) {
+    void *t;
+
+    t = span->objects;
+    span->objects = *(reinterpret_cast<void**>(t));
+    SLL_Push(start, t);
+    result++;
+    if (span->objects == NULL) {
+      // Move to empty list
+      tcmalloc::DLL_Remove(span);
+      tcmalloc::DLL_Prepend(&empty_, span);
+      Event(span, 'E', 0);
+      break;
+    }
   }
-  counter_--;
+  span->refcount += result;
+  counter_ -= result;
+  SLL_SetNext(*end, NULL);
   return result;
 }
 
diff --git a/src/central_freelist.h b/src/central_freelist.h
index 0b6afb6..4148680 100644
--- a/src/central_freelist.h
+++ b/src/central_freelist.h
@@ -114,13 +114,13 @@ class CentralFreeList {
   // REQUIRES: lock_ is held
   // Remove object from cache and return.
   // Return NULL if no free entries in cache.
-  void* FetchFromSpans() EXCLUSIVE_LOCKS_REQUIRED(lock_);
+  int FetchFromOneSpans(int N, void **start, void **end) EXCLUSIVE_LOCKS_REQUIRED(lock_);
 
   // REQUIRES: lock_ is held
   // Remove object from cache and return.  Fetches
   // from pageheap if cache is empty.  Only returns
   // NULL on allocation failure.
-  void* FetchFromSpansSafe() EXCLUSIVE_LOCKS_REQUIRED(lock_);
+  int FetchFromOneSpansSafe(int N, void **start, void **end) EXCLUSIVE_LOCKS_REQUIRED(lock_);
 
   // REQUIRES: lock_ is held
   // Release a linked list of objects to spans.