altos/lisp: Sort frames by atom

Fortunately, the collector always retains the relative order between
addresses, so we can sort based on the atom address itself. This
reduces the time spent looking for names in larger (e.g. global)
frames.

Signed-off-by: Keith Packard <keithp@keithp.com>

diff --git a/src/lisp/ao_lisp.h b/src/lisp/ao_lisp.h
index af6ff8bbc149c37c95b6af45de11234e99fb722b..1f7c85e18a5f5201ad29dacaf6a9304045f1286c 100644 (file)
--- a/src/lisp/ao_lisp.h
+++ b/src/lisp/ao_lisp.h
@@ -621,7 +621,7 @@ ao_lisp_read_eval_print(void);
 /* frame */
 extern const struct ao_lisp_type ao_lisp_frame_type;
 
-#define AO_LISP_FRAME_FREE     4
+#define AO_LISP_FRAME_FREE     6
 
 extern struct ao_lisp_frame    *ao_lisp_frame_free_list[AO_LISP_FRAME_FREE];
 
@@ -637,6 +637,9 @@ ao_lisp_frame_new(int num);
 void
 ao_lisp_frame_free(struct ao_lisp_frame *frame);
 
+void
+ao_lisp_frame_bind(struct ao_lisp_frame *frame, int num, ao_poly atom, ao_poly val);
+
 int
 ao_lisp_frame_add(struct ao_lisp_frame **frame, ao_poly atom, ao_poly val);
 

diff --git a/src/lisp/ao_lisp_frame.c b/src/lisp/ao_lisp_frame.c
index 17fa141a00e014aec425b78303e3faded572241c..05f6d253ca23159fee0413c516e32cbbc9be0c8d 100644 (file)
--- a/src/lisp/ao_lisp_frame.c
+++ b/src/lisp/ao_lisp_frame.c
@@ -128,14 +128,32 @@ ao_lisp_frame_print(ao_poly p)
        printf("}");
 }
 
+static int
+ao_lisp_frame_find(struct ao_lisp_frame *frame, int top, ao_poly atom)
+{
+       int l = 0;
+       int r = top - 1;
+       while (l <= r) {
+               int m = (l + r) >> 1;
+               if (frame->vals[m].atom < atom)
+                       l = m + 1;
+               else
+                       r = m - 1;
+       }
+       return l;
+}
+
 ao_poly *
 ao_lisp_frame_ref(struct ao_lisp_frame *frame, ao_poly atom)
 {
-       int f;
-       for (f = 0; f < frame->num; f++)
-               if (frame->vals[f].atom == atom)
-                       return &frame->vals[f].val;
-       return NULL;
+       int l = ao_lisp_frame_find(frame, frame->num, atom);
+
+       if (l >= frame->num)
+               return NULL;
+
+       if (frame->vals[l].atom != atom)
+               return NULL;
+       return &frame->vals[l].val;
 }
 
 int
@@ -234,6 +252,18 @@ ao_lisp_frame_realloc(struct ao_lisp_frame **frame_ref, int new_num)
        return new;
 }
 
+void
+ao_lisp_frame_bind(struct ao_lisp_frame *frame, int num, ao_poly atom, ao_poly val)
+{
+       int l = ao_lisp_frame_find(frame, num, atom);
+
+       memmove(&frame->vals[l+1],
+               &frame->vals[l],
+               (num - l) * sizeof (struct ao_lisp_val));
+       frame->vals[l].atom = atom;
+       frame->vals[l].val = val;
+}
+
 int
 ao_lisp_frame_add(struct ao_lisp_frame **frame_ref, ao_poly atom, ao_poly val)
 {
@@ -251,14 +281,13 @@ ao_lisp_frame_add(struct ao_lisp_frame **frame_ref, ao_poly atom, ao_poly val)
                        f = 0;
                        frame = ao_lisp_frame_new(1);
                }
-               atom = ao_lisp_poly_fetch(0);
-               val = ao_lisp_poly_fetch(1);
                if (!frame)
                        return 0;
                *frame_ref = frame;
-               frame->vals[f].atom = atom;
-               ref = &frame->vals[f].val;
-       }
-       *ref = val;
+               atom = ao_lisp_poly_fetch(0);
+               val = ao_lisp_poly_fetch(1);
+               ao_lisp_frame_bind(frame, frame->num - 1, atom, val);
+       } else
+               *ref = val;
        return 1;
 }

diff --git a/src/lisp/ao_lisp_lambda.c b/src/lisp/ao_lisp_lambda.c
index b164cd66421056662fc72f301c6f81efe3bd8b11..526863c508e1187c24a3be251ecb5fcfba294998 100644 (file)
--- a/src/lisp/ao_lisp_lambda.c
+++ b/src/lisp/ao_lisp_lambda.c
@@ -166,8 +166,7 @@ ao_lisp_lambda_eval(void)
        case AO_LISP_FUNC_LAMBDA:
                for (f = 0; f < args_wanted; f++) {
                        DBGI("bind "); DBG_POLY(args->car); DBG(" = "); DBG_POLY(vals->car); DBG("\n");
-                       next_frame->vals[f].atom = args->car;
-                       next_frame->vals[f].val = vals->car;
+                       ao_lisp_frame_bind(next_frame, f, args->car, vals->car);
                        args = ao_lisp_poly_cons(args->cdr);
                        vals = ao_lisp_poly_cons(vals->cdr);
                }
@@ -180,14 +179,12 @@ ao_lisp_lambda_eval(void)
        case AO_LISP_FUNC_MACRO:
                for (f = 0; f < args_wanted - 1; f++) {
                        DBGI("bind "); DBG_POLY(args->car); DBG(" = "); DBG_POLY(vals->car); DBG("\n");
-                       next_frame->vals[f].atom = args->car;
-                       next_frame->vals[f].val = vals->car;
+                       ao_lisp_frame_bind(next_frame, f, args->car, vals->car);
                        args = ao_lisp_poly_cons(args->cdr);
                        vals = ao_lisp_poly_cons(vals->cdr);
                }
                DBGI("bind "); DBG_POLY(args->car); DBG(" = "); DBG_POLY(ao_lisp_cons_poly(vals)); DBG("\n");
-               next_frame->vals[f].atom = args->car;
-               next_frame->vals[f].val = ao_lisp_cons_poly(vals);
+               ao_lisp_frame_bind(next_frame, f, args->car, ao_lisp_cons_poly(vals));
                break;
        default:
                break;

diff --git a/src/lisp/ao_lisp_mem.c b/src/lisp/ao_lisp_mem.c
index e8907cf622ef0b7ca20805d1d67bcae4c1618f58..1f09ede826e749781a822f3b35a42b2986c22dad 100644 (file)
--- a/src/lisp/ao_lisp_mem.c
+++ b/src/lisp/ao_lisp_mem.c
@@ -218,9 +218,11 @@ static const void ** const ao_lisp_cache[] = {
        (const void **) &ao_lisp_frame_free_list[1],
        (const void **) &ao_lisp_frame_free_list[2],
        (const void **) &ao_lisp_frame_free_list[3],
+       (const void **) &ao_lisp_frame_free_list[4],
+       (const void **) &ao_lisp_frame_free_list[5],
 };
 
-#if AO_LISP_FRAME_FREE != 4
+#if AO_LISP_FRAME_FREE != 6
 #error Unexpected AO_LISP_FRAME_FREE value
 #endif