Merge tcmalloc r111 (perftools v. 1.8) with the chromium/ branch.

third_party/tcmalloc/chromium/src/common.cc

 // Copyright (c) 2008, 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 36 matching lines @@
       n = x;
       log += shift;
     }
   }
   ASSERT(n == 1);
   return log;
 }
 
 int AlignmentForSize(size_t size) {
   int alignment = kAlignment;
-  if (size >= 2048) {
-    // Cap alignment at 256 for large sizes.
-    alignment = 256;
+  if (size > kMaxSize) {
+    // Cap alignment at kPageSize for large sizes.
+    alignment = kPageSize;
   } else if (size >= 128) {
     // Space wasted due to alignment is at most 1/8, i.e., 12.5%.
     alignment = (1 << LgFloor(size)) / 8;
   } else if (size >= 16) {
     // We need an alignment of at least 16 bytes to satisfy
     // requirements for some SSE types.
     alignment = 16;
   }
+  // Maximum alignment allowed is page size alignment.
+  if (alignment > kPageSize) {
+    alignment = kPageSize;
+  }
   CHECK_CONDITION(size < 16 || alignment >= 16);
   CHECK_CONDITION((alignment & (alignment - 1)) == 0);
   return alignment;
 }
 
 int SizeMap::NumMoveSize(size_t size) {
   if (size == 0) return 0;
   // Use approx 64k transfers between thread and central caches.
   int num = static_cast<int>(64.0 * 1024.0 / size);
   if (num < 2) num = 2;
@@ skipping 20 matching lines @@
     CRASH("Invalid class index %d for size 0\n", ClassIndex(0));
   }
   if (ClassIndex(kMaxSize) >= sizeof(class_array_)) {
     CRASH("Invalid class index %d for kMaxSize\n", ClassIndex(kMaxSize));
   }
 
   // Compute the size classes we want to use
   int sc = 1;   // Next size class to assign
   int alignment = kAlignment;
   CHECK_CONDITION(kAlignment <= 16);
-  int last_lg = -1;
   for (size_t size = kAlignment; size <= kMaxSize; size += alignment) {
-    int lg = LgFloor(size);
-    if (lg > last_lg) {
-      // Increase alignment every so often to reduce number of size classes.
-      alignment = AlignmentForSize(size);
-      last_lg = lg;
-    }
+    alignment = AlignmentForSize(size);
     CHECK_CONDITION((size % alignment) == 0);
 
-    // Allocate enough pages so leftover is less than 1/8 of total.
-    // This bounds wasted space to at most 12.5%.
-    size_t psize = kPageSize;
-    while ((psize % size) > (psize >> 3)) {
+    int blocks_to_move = NumMoveSize(size) / 4;
+    size_t psize = 0;
+    do {
       psize += kPageSize;
-    }
+      // Allocate enough pages so leftover is less than 1/8 of total.
+      // This bounds wasted space to at most 12.5%.
+      while ((psize % size) > (psize >> 3)) {
+        psize += kPageSize;
+      }
+      // Continue to add pages until there are at least as many objects in

[jar (doing other things), 2011/07/31 08:19:39]

I'm not clear on the justification for doing this.
Yes, it will help when we do the *first* allocation (and we had nothing). 
However, when we have some left-over in the central cache, but not enough to
satisfy a request from a thread, this will seemingly lead to over-allocation (so
as to avoid a second call??).  I'd like to better understand the motivation.

<sigh>... but glancing at the code in line 116, perhaps this is actually 1/4th
of the amount we typically move... which would be sensible.  I need to look at
the definition and use of NumMoveSize().

+      // the span as are needed when moving objects from the central
+      // freelists and spans to the thread caches.
+    } while ((psize / size) < (blocks_to_move));
     const size_t my_pages = psize >> kPageShift;
 
     if (sc > 1 && my_pages == class_to_pages_[sc-1]) {
       // See if we can merge this into the previous class without
       // increasing the fragmentation of the previous class.
       const size_t my_objects = (my_pages << kPageShift) / size;
       const size_t prev_objects = (class_to_pages_[sc-1] << kPageShift)
                                   / class_to_size_[sc-1];
       if (my_objects == prev_objects) {
         // Adjust last class to include this size
@@ skipping 74 matching lines @@
   return result;
 }
 
 uint64_t metadata_system_bytes() { return metadata_system_bytes_; }
 
 void increment_metadata_system_bytes(size_t bytes) {
   metadata_system_bytes_ += bytes;
 }
 
 }  // namespace tcmalloc