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>

4 files changed, 50 insertions, 19 deletions

diff --git a/src/lisp/ao_lisp.h b/src/lisp/ao_lisp.h
index af6ff8bb..1f7c85e1 100644
--- 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 17fa141a..05f6d253 100644
--- 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 b164cd66..526863c5 100644
--- 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 e8907cf6..1f09ede8 100644
--- 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