From 2c80fea1936ff956df127b43e65139afec3929a0 Mon Sep 17 00:00:00 2001 From: Keith Packard Date: Fri, 18 Nov 2016 22:52:53 -0800 Subject: [PATCH] altos/lisp: Share binary search for memory chunk between mark and move Save some text space. Signed-off-by: Keith Packard --- src/lisp/ao_lisp_mem.c | 109 +++++++++++++++++++---------------------- 1 file changed, 50 insertions(+), 59 deletions(-) diff --git a/src/lisp/ao_lisp_mem.c b/src/lisp/ao_lisp_mem.c index 1f09ede8..5bf6e1e4 100644 --- a/src/lisp/ao_lisp_mem.c +++ b/src/lisp/ao_lisp_mem.c @@ -36,6 +36,10 @@ uint8_t ao_lisp_pool[AO_LISP_POOL + AO_LISP_POOL_EXTRA] __attribute__((aligned(4 #endif +#ifndef DBG_MEM_STATS +#define DBG_MEM_STATS DBG_MEM +#endif + #if DBG_MEM int dbg_move_depth; int dbg_mem = DBG_MEM_START; @@ -283,8 +287,6 @@ static inline int limit(int offset) { return min(AO_LISP_POOL, max(offset, 0)); } -static int total_marked; - static void note_cons(uint16_t offset) { @@ -295,19 +297,14 @@ note_cons(uint16_t offset) static uint16_t chunk_low, chunk_high; static uint16_t chunk_first, chunk_last; -static int chunk_busy; -static void -note_chunk(uint16_t offset, uint16_t size) +static int +find_chunk(uint16_t offset) { int l, r; - - if (offset < chunk_low || chunk_high <= offset) - return; - /* Binary search for the location */ - l = 0; - r = chunk_busy - 1; + l = chunk_first; + r = chunk_last - 1; while (l <= r) { int m = (l + r) >> 1; if (ao_lisp_chunk[m].old_offset < offset) @@ -315,6 +312,19 @@ note_chunk(uint16_t offset, uint16_t size) else r = m - 1; } + return l; +} + +static void +note_chunk(uint16_t offset, uint16_t size) +{ + int l; + + if (offset < chunk_low || chunk_high <= offset) + return; + + l = find_chunk(offset); + /* * The correct location is always in 'l', with r = l-1 being * the entry before the right one @@ -326,12 +336,12 @@ note_chunk(uint16_t offset, uint16_t size) ao_lisp_abort(); /* Off the left side */ - if (l == 0 && chunk_busy && offset > ao_lisp_chunk[0].old_offset) + if (l == 0 && chunk_last && offset > ao_lisp_chunk[0].old_offset) ao_lisp_abort(); #endif /* Shuffle existing entries right */ - int end = min(AO_LISP_NCHUNK, chunk_busy + 1); + int end = min(AO_LISP_NCHUNK, chunk_last + 1); memmove(&ao_lisp_chunk[l+1], &ao_lisp_chunk[l], @@ -342,11 +352,11 @@ note_chunk(uint16_t offset, uint16_t size) ao_lisp_chunk[l].size = size; /* Increment the number of elements up to the size of the array */ - if (chunk_busy < AO_LISP_NCHUNK) - chunk_busy++; + if (chunk_last < AO_LISP_NCHUNK) + chunk_last++; /* Set the top address if the array is full */ - if (chunk_busy == AO_LISP_NCHUNK) + if (chunk_last == AO_LISP_NCHUNK) chunk_high = ao_lisp_chunk[AO_LISP_NCHUNK-1].old_offset + ao_lisp_chunk[AO_LISP_NCHUNK-1].size; } @@ -354,9 +364,9 @@ note_chunk(uint16_t offset, uint16_t size) static void reset_chunks(void) { - memset(ao_lisp_chunk, '\0', sizeof (ao_lisp_chunk)); chunk_high = ao_lisp_top; - chunk_busy = 0; + chunk_last = 0; + chunk_first = 0; } /* @@ -369,7 +379,6 @@ walk(int (*visit_addr)(const struct ao_lisp_type *type, void **addr), { int i; - total_marked = 0; ao_lisp_record_reset(); memset(ao_lisp_busy, '\0', sizeof (ao_lisp_busy)); memset(ao_lisp_cons_note, '\0', sizeof (ao_lisp_cons_note)); @@ -452,26 +461,26 @@ ao_lisp_poly_mark_ref(ao_poly *p, uint8_t do_note_cons) return ao_lisp_poly_mark(*p, do_note_cons); } +#if DBG_MEM_STATS int ao_lisp_collects[2]; int ao_lisp_freed[2]; int ao_lisp_loops[2]; +#endif int ao_lisp_last_top; int ao_lisp_collect(uint8_t style) { - int ret; int i; int top; +#if DBG_MEM_STATS int loops = 0; +#endif #if DBG_MEM - int marked; - int moved; struct ao_lisp_record *mark_record = NULL, *move_record = NULL; - MDBG_MOVE("collect %d\n", ao_lisp_collects); - marked = moved = 0; + MDBG_MOVE("collect %d\n", ao_lisp_collects[style]); #endif /* The first time through, we're doing a full collect */ @@ -487,27 +496,25 @@ ao_lisp_collect(uint8_t style) chunk_low = top = ao_lisp_last_top; } for (;;) { +#if DBG_MEM_STATS loops++; +#endif MDBG_MOVE("move chunks from %d to %d\n", chunk_low, top); /* Find the sizes of the first chunk of objects to move */ reset_chunks(); walk(ao_lisp_mark_ref, ao_lisp_poly_mark_ref); #if DBG_MEM - marked = total_marked; ao_lisp_record_free(mark_record); mark_record = ao_lisp_record_save(); if (mark_record && move_record) ao_lisp_record_compare("mark", move_record, mark_record); - - if (moved && moved != marked) - ao_lisp_abort(); #endif DUMP_BUSY(); /* Find the first moving object */ - for (i = 0; i < chunk_busy; i++) { + for (i = 0; i < chunk_last; i++) { uint16_t size = ao_lisp_chunk[i].size; #if DBG_MEM @@ -536,7 +543,7 @@ ao_lisp_collect(uint8_t style) chunk_low = ao_lisp_chunk[i].old_offset; /* Copy all of the objects */ - for (; i < chunk_busy; i++) { + for (; i < chunk_last; i++) { uint16_t size = ao_lisp_chunk[i].size; #if DBG_MEM @@ -557,8 +564,6 @@ ao_lisp_collect(uint8_t style) top += size; } - chunk_last = i; - if (chunk_first < chunk_last) { /* Relocate all references to the objects */ walk(ao_lisp_move, ao_lisp_poly_move); @@ -568,10 +573,6 @@ ao_lisp_collect(uint8_t style) move_record = ao_lisp_record_save(); if (mark_record && move_record) ao_lisp_record_compare("move", mark_record, move_record); - - moved = total_marked; - if (moved != marked) - ao_lisp_abort(); #endif } @@ -585,13 +586,12 @@ ao_lisp_collect(uint8_t style) chunk_low = chunk_high; } - /* Compute amount of memory freed */ - ret = ao_lisp_top - top; - +#if DBG_MEM_STATS /* Collect stats */ ++ao_lisp_collects[style]; - ao_lisp_freed[style] += ret; + ao_lisp_freed[style] += ao_lisp_top - top; ao_lisp_loops[style] += loops; +#endif ao_lisp_top = top; if (style == AO_LISP_COLLECT_FULL) @@ -600,7 +600,7 @@ ao_lisp_collect(uint8_t style) MDBG_DO(memset(ao_lisp_chunk, '\0', sizeof (ao_lisp_chunk)); walk(ao_lisp_mark_ref, ao_lisp_poly_mark_ref)); - return ret; + return AO_LISP_POOL - ao_lisp_top; } /* @@ -697,21 +697,13 @@ ao_lisp_poly_mark(ao_poly p, uint8_t do_note_cons) static uint16_t move_map(uint16_t offset) { - int l, r; + int l; if (offset < chunk_low || chunk_high <= offset) return offset; - /* Binary search for the location */ - l = chunk_first; - r = chunk_busy - 1; - while (l <= r) { - int m = (l + r) >> 1; - if (ao_lisp_chunk[m].old_offset < offset) - l = m + 1; - else - r = m - 1; - } + l = find_chunk(offset); + #if DBG_MEM if (ao_lisp_chunk[l].old_offset != offset) ao_lisp_abort(); @@ -832,13 +824,12 @@ ao_lisp_alloc(int size) MDBG_DO(++dbg_allocs); MDBG_DO(if (dbg_validate) ao_lisp_validate()); size = ao_lisp_size_round(size); - if (ao_lisp_top + size > AO_LISP_POOL) { - if (ao_lisp_collect(AO_LISP_COLLECT_INCREMENTAL) < size && - ao_lisp_collect(AO_LISP_COLLECT_FULL) < size) - { - ao_lisp_error(AO_LISP_OOM, "out of memory"); - return NULL; - } + if (AO_LISP_POOL - ao_lisp_top < size && + ao_lisp_collect(AO_LISP_COLLECT_INCREMENTAL) < size && + ao_lisp_collect(AO_LISP_COLLECT_FULL) < size) + { + ao_lisp_error(AO_LISP_OOM, "out of memory"); + return NULL; } addr = ao_lisp_pool + ao_lisp_top; ao_lisp_top += size; -- 2.30.2