use 2-level page map for 48-bit addresses

48 bits is size of x86-64 and arm64 address spaces. So using 2 levels
map for them is slightly faster. We keep 3 levels for small-but-slow
configuration, since 2 levels consume a bit more memory.

This is partial port of Google-internal commit by Sanjay
Ghemawat (same idea, different implementation).

2 files changed, 22 insertions, 8 deletions

diff --git a/src/page_heap.h b/src/page_heap.h
index 195c79a..990d292 100644
--- a/src/page_heap.h
+++ b/src/page_heap.h
@@ -86,6 +86,19 @@ template <int BITS> class MapSelector {
   typedef PackedCache<BITS-kPageShift, uint64_t> CacheType;
 };
 
+#ifndef TCMALLOC_SMALL_BUT_SLOW
+// x86-64 and arm64 are using 48 bits of address space. So we can use
+// just two level map, but since initial ram consumption of this mode
+// is a bit on the higher side, we opt-out of it in
+// TCMALLOC_SMALL_BUT_SLOW mode.
+template <> class MapSelector<48> {
+ public:
+  typedef TCMalloc_PageMap2<48-kPageShift> Type;
+  typedef PackedCache<48-kPageShift, uint64_t> CacheType;
+};
+
+#endif // TCMALLOC_SMALL_BUT_SLOW
+
 // A two-level map for 32-bit machines
 template <> class MapSelector<32> {
  public:
diff --git a/src/pagemap.h b/src/pagemap.h
index dd94423..a072a0f 100644
--- a/src/pagemap.h
+++ b/src/pagemap.h
@@ -119,19 +119,18 @@ class TCMalloc_PageMap1 {
 template <int BITS>
 class TCMalloc_PageMap2 {
  private:
-  // Put 32 entries in the root and (2^BITS)/32 entries in each leaf.
-  static const int ROOT_BITS = 5;
-  static const int ROOT_LENGTH = 1 << ROOT_BITS;
-
-  static const int LEAF_BITS = BITS - ROOT_BITS;
+  static const int LEAF_BITS = (BITS + 1) / 2;
   static const int LEAF_LENGTH = 1 << LEAF_BITS;
 
+  static const int ROOT_BITS = BITS - LEAF_BITS;
+  static const int ROOT_LENGTH = 1 << ROOT_BITS;
+
   // Leaf node
   struct Leaf {
     void* values[LEAF_LENGTH];
   };
 
-  Leaf* root_[ROOT_LENGTH];             // Pointers to 32 child nodes
+  Leaf* root_[ROOT_LENGTH];             // Pointers to child nodes
   void* (*allocator_)(size_t);          // Memory allocator
 
  public:
@@ -182,11 +181,13 @@ class TCMalloc_PageMap2 {
 
   void PreallocateMoreMemory() {
     // Allocate enough to keep track of all possible pages
-    Ensure(0, 1 << BITS);
+    if (BITS < 20) {
+      Ensure(0, Number(1) << BITS);
+    }
   }
 
   void* Next(Number k) const {
-    while (k < (1 << BITS)) {
+    while (k < (Number(1) << BITS)) {
       const Number i1 = k >> LEAF_BITS;
       Leaf* leaf = root_[i1];
       if (leaf != NULL) {