diff -up ./array.c.orig ./array.c --- ./array.c.orig 2016-08-24 15:31:55.000000000 -0400 +++ ./array.c 2017-04-08 11:51:21.838405785 -0400 @@ -1348,12 +1348,22 @@ assoc_list(NODE *symbol, const char *sor list = symbol->alist(symbol, & akind); assoc_kind = (assoc_kind_t) akind.flags; /* symbol->alist can modify it */ - if (list == NULL || ! cmp_func || (assoc_kind & (AASC|ADESC)) != 0) - return list; /* empty list or unsorted, or list already sorted */ + /* check for empty list or unsorted, or list already sorted */ + if (list != NULL && cmp_func != NULL && (assoc_kind & (AASC|ADESC)) == 0) { + num_elems = assoc_length(symbol); - num_elems = assoc_length(symbol); + qsort(list, num_elems, elem_size * sizeof(NODE *), cmp_func); /* shazzam! */ - qsort(list, num_elems, elem_size * sizeof(NODE *), cmp_func); /* shazzam! */ + if (sort_ctxt == SORTED_IN && (assoc_kind & (AINDEX|AVALUE)) == (AINDEX|AVALUE)) { + /* relocate all index nodes to the first half of the list. */ + for (j = 1; j < num_elems; j++) + list[j] = list[2 * j]; + + /* give back extra memory */ + + erealloc(list, NODE **, num_elems * sizeof(NODE *), "assoc_list"); + } + } if (cmp_func == sort_user_func) { code = POP_CODE(); @@ -1362,15 +1372,5 @@ assoc_list(NODE *symbol, const char *sor bcfree(code); /* Op_func_call */ } - if (sort_ctxt == SORTED_IN && (assoc_kind & (AINDEX|AVALUE)) == (AINDEX|AVALUE)) { - /* relocate all index nodes to the first half of the list. */ - for (j = 1; j < num_elems; j++) - list[j] = list[2 * j]; - - /* give back extra memory */ - - erealloc(list, NODE **, num_elems * sizeof(NODE *), "assoc_list"); - } - return list; } diff -up ./awk.h.orig ./awk.h --- ./awk.h.orig 2016-08-24 15:31:55.000000000 -0400 +++ ./awk.h 2017-04-08 11:51:21.838405785 -0400 @@ -747,6 +747,7 @@ typedef struct exp_instruction { } x; short source_line; + short pool_size; // memory management in symbol.c OPCODE opcode; } INSTRUCTION; @@ -993,9 +994,19 @@ typedef struct srcfile { int lasttok; } SRCFILE; +// structure for INSTRUCTION pool, needed mainly for debugger +typedef struct instruction_pool { +#define MAX_INSTRUCTION_ALLOC 3 // we don't call bcalloc with more than this + struct instruction_mem_pool { + struct instruction_block *block_list; + INSTRUCTION *free_space; // free location in active block + INSTRUCTION *free_list; + } pool[MAX_INSTRUCTION_ALLOC]; +} INSTRUCTION_POOL; + /* structure for execution context */ typedef struct context { - INSTRUCTION pools; + INSTRUCTION_POOL pools; NODE symbols; INSTRUCTION rule_list; SRCFILE srcfiles; diff -up ./symbol.c.orig ./symbol.c --- ./symbol.c.orig 2016-08-24 15:31:55.000000000 -0400 +++ ./symbol.c 2017-04-08 11:56:10.799440016 -0400 @@ -37,7 +37,7 @@ static NODE *symbol_list; static void (*install_func)(NODE *) = NULL; static NODE *make_symbol(const char *name, NODETYPE type); static NODE *install(const char *name, NODE *parm, NODETYPE type); -static void free_bcpool(INSTRUCTION *pl); +static void free_bcpool(INSTRUCTION_POOL *pl); static AWK_CONTEXT *curr_ctxt = NULL; static int ctxt_level; @@ -693,22 +693,31 @@ check_param_names(void) return result; } -#define pool_size d.dl -#define freei x.xi -static INSTRUCTION *pool_list; +static INSTRUCTION_POOL *pools; -/* INSTR_CHUNK must be > largest code size (3) */ -#define INSTR_CHUNK 127 +/* + * For best performance, the INSTR_CHUNK value should be divisible by all + * possible sizes, i.e. 1 through MAX_INSTRUCTION_ALLOC. Otherwise, there + * will be wasted space at the end of the block. + */ +#define INSTR_CHUNK (2*3*21) + +struct instruction_block { + struct instruction_block *next; + INSTRUCTION i[INSTR_CHUNK]; +}; /* bcfree --- deallocate instruction */ void bcfree(INSTRUCTION *cp) { + assert(cp->pool_size >= 1 && cp->pool_size <= MAX_INSTRUCTION_ALLOC); + cp->opcode = 0; - cp->nexti = pool_list->freei; - pool_list->freei = cp; -} + cp->nexti = pools->pool[cp->pool_size - 1].free_list; + pools->pool[cp->pool_size - 1].free_list = cp; +} /* bcalloc --- allocate a new instruction */ @@ -716,38 +725,28 @@ INSTRUCTION * bcalloc(OPCODE op, int size, int srcline) { INSTRUCTION *cp; + struct instruction_mem_pool *pool; - if (size > 1) { - /* wide instructions Op_rule, Op_func_call .. */ - emalloc(cp, INSTRUCTION *, (size + 1) * sizeof(INSTRUCTION), "bcalloc"); - cp->pool_size = size; - cp->nexti = pool_list->nexti; - pool_list->nexti = cp++; - } else { - INSTRUCTION *pool; + assert(size >= 1 && size <= MAX_INSTRUCTION_ALLOC); + pool = &pools->pool[size - 1]; - pool = pool_list->freei; - if (pool == NULL) { - INSTRUCTION *last; - emalloc(cp, INSTRUCTION *, (INSTR_CHUNK + 1) * sizeof(INSTRUCTION), "bcalloc"); - - cp->pool_size = INSTR_CHUNK; - cp->nexti = pool_list->nexti; - pool_list->nexti = cp; - pool = ++cp; - last = &pool[INSTR_CHUNK - 1]; - for (; cp <= last; cp++) { - cp->opcode = 0; - cp->nexti = cp + 1; - } - --cp; - cp->nexti = NULL; - } - cp = pool; - pool_list->freei = cp->nexti; + if (pool->free_list != NULL) { + cp = pool->free_list; + pool->free_list = cp->nexti; + } else if (pool->free_space && pool->free_space + size <= & pool->block_list->i[INSTR_CHUNK]) { + cp = pool->free_space; + pool->free_space += size; + } else { + struct instruction_block *block; + emalloc(block, struct instruction_block *, sizeof(struct instruction_block), "bcalloc"); + block->next = pool->block_list; + pool->block_list = block; + cp = &block->i[0]; + pool->free_space = &block->i[size]; } memset(cp, 0, size * sizeof(INSTRUCTION)); + cp->pool_size = size; cp->opcode = op; cp->source_line = srcline; return cp; @@ -773,7 +772,7 @@ new_context() static void set_context(AWK_CONTEXT *ctxt) { - pool_list = & ctxt->pools; + pools = & ctxt->pools; symbol_list = & ctxt->symbols; srcfiles = & ctxt->srcfiles; rule_list = & ctxt->rule_list; @@ -910,27 +909,36 @@ free_bc_internal(INSTRUCTION *cp) } } -/* free_bcpool --- free list of instruction memory pools */ +/* free_bc_mempool --- free a single pool */ static void -free_bcpool(INSTRUCTION *pl) +free_bc_mempool(struct instruction_mem_pool *pool, int size) { - INSTRUCTION *pool, *tmp; + int first = 1; + struct instruction_block *block, *next; - for (pool = pl->nexti; pool != NULL; pool = tmp) { - INSTRUCTION *cp, *last; - long psiz; - psiz = pool->pool_size; - if (psiz == INSTR_CHUNK) - last = pool + psiz; - else - last = pool + 1; - for (cp = pool + 1; cp <= last ; cp++) { + for (block = pool->block_list; block; block = next) { + INSTRUCTION *cp, *end; + + end = (first ? pool->free_space : & block->i[INSTR_CHUNK]); + for (cp = & block->i[0]; cp + size <= end; cp += size) { if (cp->opcode != 0) free_bc_internal(cp); } - tmp = pool->nexti; - efree(pool); + next = block->next; + efree(block); + first = 0; } - memset(pl, 0, sizeof(INSTRUCTION)); +} + + +/* free_bcpool --- free list of instruction memory pools */ + +static void +free_bcpool(INSTRUCTION_POOL *pl) +{ + int i; + + for (i = 0; i < MAX_INSTRUCTION_ALLOC; i++) + free_bc_mempool(& pl->pool[i], i + 1); }