matz	2008-03-03 17:27:43 +0900 (Mon, 03 Mar 2008)

  New Revision: 15674

  Modified files:
    trunk/ChangeLog
    trunk/gc.c

  Log:
    * gc.c (add_heap): sort heaps array in ascending order to use
      binary search.
    
    * gc.c (is_pointer_to_heap): use binary search to identify object
      in heaps.  works better when number of heap segments grow big.

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/ChangeLog?r1=15674&r2=15673&diff_format=u
  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/gc.c?r1=15674&r2=15673&diff_format=u

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 15673)
+++ ChangeLog	(revision 15674)
@@ -1,3 +1,11 @@
+Mon Mar  3 17:25:45 2008  Yukihiro Matsumoto  <matz@r...>
+
+	* gc.c (add_heap): sort heaps array in ascending order to use
+	  binary search.
+
+	* gc.c (is_pointer_to_heap): use binary search to identify object
+	  in heaps.  works better when number of heap segments grow big.
+
 Mon Mar  3 17:15:09 2008  Yukihiro Matsumoto  <matz@r...>
 
 	* re.c (rb_reg_regsub): remove too strict encoding check.
Index: gc.c
===================================================================
--- gc.c	(revision 15673)
+++ gc.c	(revision 15674)
@@ -17,6 +17,7 @@
 #include "ruby/node.h"
 #include "ruby/re.h"
 #include "ruby/io.h"
+#include "ruby/util.h"
 #include "vm_core.h"
 #include "gc.h"
 #include <stdio.h>
@@ -412,6 +413,14 @@
     }
 }
 
+static int
+heap_cmp(const void *ap, const void *bp, void *dummy)
+{
+    const struct heaps_slot *a = ap, *b = bp;
+
+    return a->membase - b->membase;
+}
+
 static void
 add_heap(void)
 {
@@ -465,7 +474,9 @@
 	freelist = p;
 	p++;
     }
+    ruby_qsort(heaps, heaps_used, sizeof(struct heaps_slot), heap_cmp, 0);
 }
+
 #define RANY(o) ((RVALUE*)(o))
 
 static VALUE
@@ -720,17 +731,26 @@
 is_pointer_to_heap(void *ptr)
 {
     register RVALUE *p = RANY(ptr);
-    register RVALUE *heap_org;
-    register long i;
+    register struct heaps_slot *heap;
+    register long hi, lo, mid;
 
     if (p < lomem || p > himem) return Qfalse;
     if ((VALUE)p % sizeof(RVALUE) != 0) return Qfalse;
 
-    /* check if p looks like a pointer */
-    for (i=0; i < heaps_used; i++) {
-	heap_org = heaps[i].slot;
-	if (heap_org <= p && p < heap_org + heaps[i].limit)
-	    return Qtrue;
+    /* check if p looks like a pointer using bsearch*/
+    lo = 0;
+    hi = heaps_used;
+    while (lo < hi) {
+	mid = (lo + hi) / 2;
+	heap = &heaps[mid];
+	if (heap->slot <= p) {
+	    if (p < heap->slot + heap->limit)
+		return Qtrue;
+	    lo = mid + 1;
+	}
+	else {
+	    hi = mid;
+	}
     }
     return Qfalse;
 }

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/