From c3a4d7721f0f5d082336b8cc9c9d765ad2f7d17e Mon Sep 17 00:00:00 2001 From: Keith Packard Date: Fri, 18 Nov 2016 22:41:46 -0800 Subject: [PATCH] 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 --- src/lisp/ao_lisp.h | 5 +++- src/lisp/ao_lisp_frame.c | 51 ++++++++++++++++++++++++++++++--------- src/lisp/ao_lisp_lambda.c | 9 +++---- src/lisp/ao_lisp_mem.c | 4 ++- 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 -- 2.30.2