Speed up tcmalloc by allowing more inlining.

third_party/tcmalloc/chromium/src/free_list.h

 // Copyright (c) 2011, Google Inc.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
@@ skipping 24 matching lines @@
 // linked lists.  It also contains macros to tell the SizeMap class
 // how much space a node in the freelist needs so that SizeMap can
 // create large enough size classes.
 
 #ifndef TCMALLOC_FREE_LIST_H_
 #define TCMALLOC_FREE_LIST_H_
 
 #include <stddef.h>
 #include "internal_logging.h"
 #include "linked_list.h"
+#include "system-alloc.h"
 
 // Remove to enable singly linked lists (the default for open source tcmalloc).
 #define TCMALLOC_USE_DOUBLYLINKED_FREELIST
 
 namespace tcmalloc {
 
 #if defined(TCMALLOC_USE_DOUBLYLINKED_FREELIST)
 
 // size class information for common.h.
 static const bool kSupportsDoublyLinkedList = true;
 
-void *FL_Next(void *t);
-void FL_Init(void *t);
-void FL_Push(void **list, void *element);
-void *FL_Pop(void **list);
 void FL_PopRange(void **head, int n, void **start, void **end);
 void FL_PushRange(void **head, void *start, void *end);
 size_t FL_Size(void *head);
 
+template <typename T> inline void FL_EqualityCheck(const T& v0,
+                                                   const T& v1,
+                                                   const char* file,
+                                                   int line) {
+  if (v0 != v1) Log(kCrash, file, line, "Memory corruption detected.");

[jar (doing other things), 2013/03/14 00:05:09]

Is code optimized (by default) for the true case?  If so, you may as well:
if (v0 == v1) return;

[gpike, 2013/03/14 00:58:37]

I looked at the generated code and it seems fine. Also, as you say, the CPU's
branch predictor will generally do the right thing.

+}
+
+inline void EnsureNonLoop(void* node, void* next) {
+  // We only have time to do minimal checking.  We don't traverse the list, but
+  // only look for an immediate loop (cycle back to ourself).
+  if (node != next) return;
+  Log(kCrash, __FILE__, __LINE__, "Circular loop in list detected: ", next);
+}
+
+inline void* MaskPtr(void* p) {
+  // Maximize ASLR entropy and guarantee the result is an invalid address.
+  const uintptr_t mask = ~(reinterpret_cast<uintptr_t>(TCMalloc_SystemAlloc)
+                           >> 13);
+  return reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(p) ^ mask);
+}
+
+inline void* UnmaskPtr(void* p) {
+  return MaskPtr(p);
+}
+
+// Returns value of the |previous| pointer w/out running a sanity
+// check.
+inline void *FL_Previous_No_Check(void *t) {
+  return UnmaskPtr(reinterpret_cast<void**>(t)[1]);
+}
+
+// Returns value of the |next| pointer w/out running a sanity check.
+inline void *FL_Next_No_Check(void *t) {
+  return UnmaskPtr(reinterpret_cast<void**>(t)[0]);
+}
+
+inline void *FL_Previous(void *t) {
+  void *previous = FL_Previous_No_Check(t);
+  if (previous) {
+    FL_EqualityCheck(FL_Next_No_Check(previous), t, __FILE__, __LINE__);
+  }
+  return previous;
+}
+
+inline void FL_SetPrevious(void *t, void *n) {
+  EnsureNonLoop(t, n);
+  reinterpret_cast<void**>(t)[1] = MaskPtr(n);
+}
+
+inline void FL_SetNext(void *t, void *n) {
+  EnsureNonLoop(t, n);
+  reinterpret_cast<void**>(t)[0] = MaskPtr(n);
+}
+
+inline void *FL_Next(void *t) {
+  void *next = FL_Next_No_Check(t);
+  if (next) {
+    FL_EqualityCheck(FL_Previous_No_Check(next), t, __FILE__, __LINE__);
+  }
+  return next;
+}
+
+// Pops the top element off the linked list whose first element is at
+// |*list|, and updates |*list| to point to the next element in the
+// list.  Returns the address of the element that was removed from the
+// linked list.  |list| must not be NULL.
+inline void *FL_Pop(void **list) {
+  void *result = *list;
+  ASSERT(FL_Previous_No_Check(result) == NULL);
+  *list = FL_Next(result);
+  if (*list != NULL) {
+    FL_SetPrevious(*list, NULL);
+  }
+  return result;
+}
+
+// Makes the element at |t| a singleton doubly linked list.
+inline void FL_Init(void *t) {
+  FL_SetPrevious(t, NULL);
+  FL_SetNext(t, NULL);
+}
+
+// Pushes element to a linked list whose first element is at
+// |*list|. When this call returns, |list| will point to the new head
+// of the linked list.
+inline void FL_Push(void **list, void *element) {
+  void *old = *list;
+  if (old == NULL) { // Builds singleton list.

[jar (doing other things), 2013/03/14 00:05:09]

In most cases, I'd expect that our lists are non-null... and again, if compilers
optimize for the true cases, then we should swap this as well.

A profile would probably show what is going on (in the non-inlined case).

[gpike, 2013/03/14 00:58:37]

Within the next few days I want to look at this function again, because we
"know" that element is non-NULL here, so I think we can safely change
FL_SetPrevious(element, NULL) to "ASSERT(element != NULL);
FL_SetPreviousNoCheck(element, NULL);" Although perhaps the compiler already
does that. Anyway, at that point I'll check on the point you raise.

+    FL_Init(element);
+  } else {
+    ASSERT(FL_Previous_No_Check(old) == NULL);
+    FL_SetNext(element, old);
+    FL_SetPrevious(old, element);
+    FL_SetPrevious(element, NULL);
+  }
+  *list = element;
+}
+
 #else // TCMALLOC_USE_DOUBLYLINKED_FREELIST not defined
 static const bool kSupportsDoublyLinkedList = false;
 
 inline void *FL_Next(void *t) {
   return SLL_Next(t);
 }
 
 inline void FL_Init(void *t) {
   SLL_SetNext(t, NULL);
 }
@@ skipping 24 matching lines @@
 
 inline size_t FL_Size(void *head) {
   return SLL_Size(head);
 }
 
 #endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST
 
 } // namespace tcmalloc
 
 #endif // TCMALLOC_FREE_LIST_H_