[perl #16278] [PATCH] Quicker pointer checking for stack walking

[via RT]

# New Ticket Created by  Jason Gloudon 
# Please include the string:  [perl #16278]
# in the subject line of all future correspondence about this issue. 
# <URL: http://rt.perl.org/rt2/Ticket/Display.html?id=16278 >



This patch modifies the stack walking code to create a prefix mask for doing a
fast approximate range check of candidate pointers. On a 500 generation
life.pasm run I get about a 12 percent speedup on an intel gcc -O3 build.  

-- 
Jason


-- attachment  1 ------------------------------------------------------
url: http://rt.perl.org/rt2/attach/34215/27953/d879a9/dod.diff


Index: dod.c
===================================================================
RCS file: /cvs/public/parrot/dod.c,v
retrieving revision 1.13
diff -u -r1.13 dod.c
--- dod.c       17 Aug 2002 01:11:08 -0000      1.13
+++ dod.c       18 Aug 2002 02:35:25 -0000
@@ -1,7 +1,7 @@
 /* dod.c 
  *  Copyright: (When this is determined...it will go here)
  *  CVS Info
- *     $Id: dod.c,v 1.13 2002/08/17 01:11:08 sfink Exp $
+ *     $Id: dod.c,v 1.12 2002/08/14 00:10:48 grunblatt Exp $
  *  Overview:
  *     Handles dead object destruction of the various headers
  *  Data Structure and Algorithms:
@@ -329,11 +329,32 @@
 }
 
 #ifndef PLATFORM_STACK_WALK
+
+/* Find a mask covering the longest common bit-prefix of val1 and val2 */
+static size_t
+find_common_mask(size_t val1, size_t val2){
+    int i, count;
+    int bound = sizeof(size_t) * 8;
+
+    for(i = 0; i < bound; i++){
+        if(val1 == val2){
+                return ~(size_t)0 << i;
+        }
+        val1 >>= 1;
+        val2 >>= 1;
+    }
+
+    internal_exception(INTERP_ERROR,
+                       "Unexpected condition in find_common_prefix()!\n");
+    return 0;
+}
+
 PMC*
 trace_system_stack(struct Parrot_Interp *interpreter, PMC *last)
 {
     size_t lo_var_ptr = (size_t)interpreter->lo_var_ptr;
     size_t hi_var_ptr = (size_t)&lo_var_ptr;
+    size_t prefix;
     ptrdiff_t cur_var_ptr;
     ptrdiff_t direction = (hi_var_ptr > lo_var_ptr) ? 1 : -1;
 
@@ -342,6 +363,12 @@
     size_t pmc_min = get_min_pmc_address(interpreter);
     size_t pmc_max = get_max_pmc_address(interpreter);
 
+    size_t mask = find_common_mask(buffer_min < pmc_min ? buffer_min: pmc_min,
+                buffer_max > pmc_max ? buffer_max : pmc_max);
+
+    /* Get the expected prefix */
+    prefix = mask & buffer_min;
+
     if (!lo_var_ptr)
         return last;
     
@@ -350,10 +377,14 @@
          cur_var_ptr = (size_t)( (ptrdiff_t)cur_var_ptr + direction * 
PARROT_PTR_ALIGNMENT )
          ) {
         size_t ptr = *(size_t *)cur_var_ptr;
-        if (pmc_min <= ptr && ptr < pmc_max && is_pmc_ptr(interpreter,(void *)ptr)) {
-            last = mark_used((PMC *)ptr, last);
-        } else if (buffer_min <= ptr && ptr < buffer_max && 
is_buffer_ptr(interpreter,(void *)ptr)) {
-            buffer_lives((Buffer *)ptr);
+
+        /* Do a quick approximate range check by bit-masking */
+        if((ptr & mask) == prefix){
+            if (pmc_min < ptr && ptr < pmc_max && is_pmc_ptr(interpreter,(void 
+*)ptr)) {
+                last = mark_used((PMC *)ptr, last);
+            } else if (buffer_min < ptr && ptr < buffer_max && 
+is_buffer_ptr(interpreter,(void *)ptr)) {
+                buffer_lives((Buffer *)ptr);
+            }
         }
     }
     return last;
Index: include/parrot/dod.h
===================================================================
RCS file: /cvs/public/parrot/include/parrot/dod.h,v
retrieving revision 1.1
diff -u -r1.1 dod.h
--- include/parrot/dod.h        18 Jul 2002 04:32:53 -0000      1.1
+++ include/parrot/dod.h        18 Aug 2002 02:35:25 -0000
@@ -20,6 +20,8 @@
 void Parrot_do_dod_run(struct Parrot_Interp *);
 PMC *trace_system_stack(struct Parrot_Interp *, PMC *);
 
+static size_t find_common_mask(size_t val1, size_t val2);
+
 /* Functions needed for custom DOD routines */
 
 PMC * mark_used(PMC *used_pmc, PMC *current_end_of_list);