Do a binary search in findPool()

[software/dgc/cdgc.git] / rt / gc / cdgc / gc.d

diff --git a/rt/gc/cdgc/gc.d b/rt/gc/cdgc/gc.d
index f2d2f6ef3469f2bc75703fdd788bc7f3370064f4..1df824cdaf38ff5a3baa911f7a9076250d60c285 100644 (file)
--- a/rt/gc/cdgc/gc.d
+++ b/rt/gc/cdgc/gc.d
@@ -264,26 +264,28 @@ bool Invariant()
  * Return null if not in a Pool.
  * Assume pools is sorted.
  */
-Pool *findPool(void *p)
+Pool* findPool(void* p)
 {
-    if (p >= gc.min_addr && p < gc.max_addr)
-    {
-        if (gc.pools.length == 1)
-        {
-            return gc.pools[0];
-        }
-
-        for (size_t i = 0; i < gc.pools.length; i++)
-        {
-            Pool* pool = gc.pools[i];
-            if (p < pool.topAddr)
-            {
-                if (pool.baseAddr <= p)
-                    return pool;
-                break;
-            }
-        }
+    if (p < gc.min_addr || p >= gc.max_addr)
+        return null;
+    if (gc.pools.length == 0)
+        return null;
+    if (gc.pools.length == 1)
+        return gc.pools[0];
+    /// The pooltable[] is sorted by address, so do a binary search
+    size_t low = 0;
+    size_t high = gc.pools.length - 1;
+    while (low <= high) {
+        size_t mid = (low + high) / 2;
+        auto pool = gc.pools[mid];
+        if (p < pool.baseAddr)
+            high = mid - 1;
+        else if (p >= pool.topAddr)
+            low = mid + 1;
+        else
+            return pool;
     }
+    // Not found
     return null;
 }
 
@@ -615,12 +617,25 @@ void mark(void *pbot, void *ptop, size_t* pm_bitmask)
 
     size_t type_size = pm_bitmask[0];
     size_t* pm_bits = pm_bitmask + 1;
+    bool has_type_info = type_size != 1 || pm_bits[0] != 1 || pm_bits[1] != 0;
 
     //printf("marking range: %p -> %p\n", pbot, ptop);
     for (; p1 + type_size <= p2; p1 += type_size) {
-        for (size_t n = 0; n < type_size; n++) {
+        size_t n = 0;
+        if (has_type_info) {
+            while (n < type_size && pm_bits[n / BITS_PER_WORD] == 0)
+                n += BITS_PER_WORD;
+            if (n < type_size && (pm_bits[n / BITS_PER_WORD] &
+                        ((1 << (BITS_PER_WORD / 2)) - 1)) == 0)
+                n += BITS_PER_WORD / 2;
+            else if (n < type_size && (pm_bits[n / BITS_PER_WORD] &
+                        ((1 << (BITS_PER_WORD / 4)) - 1)) == 0)
+                n += BITS_PER_WORD / 4;
+        }
+        for (; n < type_size; n++) {
             // scan bit set for this word
-            if (!(pm_bits[n / BITS_PER_WORD] & (1 << (n % BITS_PER_WORD))))
+            if (has_type_info &&
+                    !(pm_bits[n / BITS_PER_WORD] & (1 << (n % BITS_PER_WORD))))
                 continue;
 
             void* p = *(p1 + n);