From b802e8fe709f22ad56f8a43bc9675c114c2fc21f Mon Sep 17 00:00:00 2001
From: Leandro Lucarella <llucax@gmail.com>
Date: Sun, 1 Aug 2010 15:09:14 -0300
Subject: [PATCH 1/1] Minimize the use of findPool()

findPool() is one of the most used functions in the GC, usually taking 15%
of the GC time. This patch minimizes it use by converting the functions
findBase() and findSize() to Pool methods, avoiding calling findPool()
twice (in most cases, when calling findBase() or findSize() we already
know the pool).
---
 rt/gc/cdgc/gc.d | 131 ++++++++++++++++++------------------------------
 1 file changed, 50 insertions(+), 81 deletions(-)

diff --git a/rt/gc/cdgc/gc.d b/rt/gc/cdgc/gc.d
index 2282ada..b8008f1 100644
--- a/rt/gc/cdgc/gc.d
+++ b/rt/gc/cdgc/gc.d
@@ -288,81 +288,6 @@ Pool *findPool(void *p)
 }
 
 
-/**
- * Find base address of block containing pointer p.
- * Returns null if not a gc'd pointer
- */
-void* findBase(void *p)
-{
-    Pool *pool;
-
-    pool = findPool(p);
-    if (pool)
-    {
-        size_t offset = cast(size_t)(p - pool.baseAddr);
-        size_t pn = offset / PAGESIZE;
-        Bins   bin = cast(Bins)pool.pagetable[pn];
-
-        // Adjust bit to be at start of allocated memory block
-        if (bin <= B_PAGE)
-        {
-            return pool.baseAddr + (offset & notbinsize[bin]);
-        }
-        else if (bin == B_PAGEPLUS)
-        {
-            do
-            {
-                --pn, offset -= PAGESIZE;
-            } while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
-
-            return pool.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
-        }
-        else
-        {
-            // we are in a B_FREE page
-            return null;
-        }
-    }
-    return null;
-}
-
-
-/**
- * Find size of pointer p.
- * Returns 0 if not a gc'd pointer
- */
-size_t findSize(void *p)
-{
-    Pool*  pool;
-    size_t size = 0;
-
-    pool = findPool(p);
-    if (pool)
-    {
-        size_t pagenum;
-        Bins   bin;
-
-        pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
-        bin = cast(Bins)pool.pagetable[pagenum];
-        size = binsize[bin];
-        if (bin == B_PAGE)
-        {
-            ubyte* pt;
-            size_t i;
-
-            pt = &pool.pagetable[0];
-            for (i = pagenum + 1; i < pool.npages; i++)
-            {
-                if (pt[i] != B_PAGEPLUS)
-                    break;
-            }
-            size = (i - pagenum) * PAGESIZE;
-        }
-    }
-    return size;
-}
-
-
 /**
  * Determine the base address of the block containing p.  If p is not a gc
  * allocated pointer, return null.
@@ -1442,8 +1367,8 @@ private void *realloc(void *p, size_t size, uint attrs,
         else
             attrs = getAttr(pool, bit_i);
 
-        void* blk_base_addr = findBase(p);
-        size_t blk_size = findSize(p);
+        void* blk_base_addr = pool.findBase(p);
+        size_t blk_size = pool.findSize(p);
         bool has_pm = has_pointermap(attrs);
         size_t pm_bitmask_size = 0;
         if (has_pm) {
@@ -1572,8 +1497,8 @@ body
     auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
     uint attrs = getAttr(pool, bit_i);
 
-    void* blk_base_addr = findBase(p);
-    size_t blk_size = findSize(p);
+    void* blk_base_addr = pool.findBase(p);
+    size_t blk_size = pool.findSize(p);
     bool has_pm = has_pointermap(attrs);
     size_t* pm_bitmask = null;
     size_t pm_bitmask_size = 0;
@@ -1699,7 +1624,7 @@ private size_t sizeOf(void *p)
     auto biti = cast(size_t)(p - pool.baseAddr) / 16;
     uint attrs = getAttr(pool, biti);
 
-    size_t size = findSize(p);
+    size_t size = pool.findSize(p);
     size_t pm_bitmask_size = 0;
     if (has_pointermap(attrs))
         pm_bitmask_size = size_t.sizeof;
@@ -2063,6 +1988,47 @@ struct Pool
     }
 
 
+    /**
+     * Find base address of block containing pointer p.
+     * Returns null if the pointer doesn't belong to this pool
+     */
+    void* findBase(void *p)
+    {
+        size_t offset = cast(size_t)(p - this.baseAddr);
+        size_t pagenum = offset / PAGESIZE;
+        Bins bin = cast(Bins)this.pagetable[pagenum];
+        // Adjust bit to be at start of allocated memory block
+        if (bin <= B_PAGE)
+            return this.baseAddr + (offset & notbinsize[bin]);
+        if (bin == B_PAGEPLUS) {
+            do {
+                --pagenum, offset -= PAGESIZE;
+            } while (cast(Bins)this.pagetable[pagenum] == B_PAGEPLUS);
+            return this.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
+        }
+        // we are in a B_FREE page
+        return null;
+    }
+
+
+    /**
+     * Find size of pointer p.
+     * Returns 0 if p doesn't belong to this pool if if it's block size is less
+     * than a PAGE.
+     */
+    size_t findSize(void *p)
+    {
+        size_t pagenum = cast(size_t)(p - this.baseAddr) / PAGESIZE;
+        Bins bin = cast(Bins)this.pagetable[pagenum];
+        if (bin != B_PAGE)
+            return binsize[bin];
+        for (size_t i = pagenum + 1; i < this.npages; i++)
+            if (this.pagetable[i] != B_PAGEPLUS)
+                return (i - pagenum) * PAGESIZE;
+        return (this.npages - pagenum) * PAGESIZE;
+    }
+
+
     /**
      * Used for sorting pools
      */
@@ -2333,7 +2299,10 @@ void* gc_addrOf(void* p)
         return null;
     return locked!(void*, () {
         assert (Invariant()); scope (exit) assert (Invariant());
-        return findBase(p);
+        Pool* pool = findPool(p);
+        if (pool is null)
+            return null;
+        return pool.findBase(p);
     })();
 }
 
-- 
2.43.0