bc: rewrite "block flag stack" using simple realloc'ed byte array
Each access to current top flag took a function call + fetch of three data items
+ multiplication and some additions + and then following the resulting pointer.
After the change, it is: fetch pointer value + one byte access via this pointer.
function old new delta
bc_parse_startBody 45 49 +4
bc_parse_free 46 47 +1
zbc_parse_auto 188 185 -3
bc_parse_push 14 11 -3
bc_vm_run 398 394 -4
zbc_vm_process 63 58 -5
zdc_parse_expr 638 632 -6
zbc_parse_body 101 95 -6
bc_parse_addFunc 31 25 -6
bc_parse_noElse 56 48 -8
zcommon_parse 341 331 -10
zbc_parse_else 134 123 -11
bc_parse_create 124 108 -16
zbc_parse_text_init 123 104 -19
zbc_parse_endBody 292 252 -40
zbc_parse_stmt 1479 1420 -59
------------------------------------------------------------------------------
(add/remove: 0/0 grow/shrink: 2/14 up/down: 5/-196) Total: -191 bytes
text data bss dec hex filename
979880 485 7296 987661 f120d busybox_old
979689 485 7296 987470 f114e busybox_unstripped
Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
diff --git a/miscutils/bc.c b/miscutils/bc.c
index 4024a08..2feaf7b 100644
--- a/miscutils/bc.c
+++ b/miscutils/bc.c
@@ -574,8 +574,9 @@
#define BC_PARSE_NOREAD (1 << 3)
#define BC_PARSE_ARRAY (1 << 4)
-#define BC_PARSE_TOP_FLAG_PTR(parse) ((uint8_t *) bc_vec_top(&(parse)->flags))
+#define BC_PARSE_TOP_FLAG_PTR(parse) ((parse)->bf_top)
#define BC_PARSE_TOP_FLAG(parse) (*(BC_PARSE_TOP_FLAG_PTR(parse)))
+#define BC_PARSE_FLAG_STACK_EMPTY(p) ((p)->bf_top == (p)->bf_base)
#define BC_PARSE_FLAG_FUNC_INNER (1 << 0)
#define BC_PARSE_FLAG_FUNC (1 << 1)
@@ -598,15 +599,11 @@
#define BC_PARSE_ELSE(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_ELSE)
#define BC_PARSE_IF_END(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_IF_END)
-struct BcParse;
-
-struct BcProgram;
-
typedef struct BcParse {
-
BcLex l;
- BcVec flags;
+ uint8_t *bf_base;
+ uint8_t *bf_top;
BcVec exits;
BcVec conds;
@@ -618,7 +615,6 @@
size_t nbraces;
bool auto_part;
-
} BcParse;
typedef struct BcProgram {
@@ -3558,7 +3554,7 @@
p->l.t.t = BC_LEX_EOF;
p->auto_part = (p->nbraces = 0);
- bc_vec_npop(&p->flags, p->flags.len - 1);
+ p->bf_top = p->bf_base; // pop all flags
bc_vec_pop_all(&p->exits);
bc_vec_pop_all(&p->conds);
bc_vec_pop_all(&p->ops);
@@ -3568,7 +3564,7 @@
static void bc_parse_free(BcParse *p)
{
- bc_vec_free(&p->flags);
+ free(p->bf_base);
bc_vec_free(&p->exits);
bc_vec_free(&p->conds);
bc_vec_free(&p->ops);
@@ -3580,10 +3576,9 @@
memset(p, 0, sizeof(BcParse));
bc_lex_init(&p->l);
- bc_vec_init(&p->flags, sizeof(uint8_t), NULL);
+ p->bf_top = p->bf_base = xzalloc(1);
bc_vec_init(&p->exits, sizeof(BcInstPtr), NULL);
bc_vec_init(&p->conds, sizeof(size_t), NULL);
- bc_vec_pushZeroByte(&p->flags);
bc_vec_init(&p->ops, sizeof(BcLexType), NULL);
// p->auto_part = p->nbraces = 0; - already is
@@ -4050,7 +4045,7 @@
{
BcStatus s = BC_STATUS_SUCCESS;
- if (p->flags.len <= 1)
+ if (BC_PARSE_FLAG_STACK_EMPTY(p))
RETURN_STATUS(bc_error_bad_token());
if (BC_PARSE_IF(p)) {
@@ -4061,7 +4056,7 @@
if (s) RETURN_STATUS(s);
}
- bc_vec_pop(&p->flags);
+ p->bf_top--;
flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
dbg_lex("%s:%d setting BC_PARSE_FLAG_IF_END bit", __func__, __LINE__);
@@ -4074,7 +4069,7 @@
BcInstPtr *ip;
size_t *label;
- bc_vec_pop(&p->flags);
+ p->bf_top--;
ip = bc_vec_top(&p->exits);
label = bc_vec_item(&p->func->labels, ip->idx);
@@ -4085,7 +4080,7 @@
else if (BC_PARSE_FUNC_INNER(p)) {
bc_parse_push(p, BC_INST_RET0);
bc_parse_updateFunc(p, BC_PROG_MAIN);
- bc_vec_pop(&p->flags);
+ p->bf_top--;
}
else {
BcInstPtr *ip = bc_vec_top(&p->exits);
@@ -4097,7 +4092,7 @@
label = bc_vec_item(&p->func->labels, ip->idx);
*label = p->func->code.len;
- bc_vec_pop(&p->flags);
+ p->bf_top--;
bc_vec_pop(&p->exits);
bc_vec_pop(&p->conds);
}
@@ -4110,10 +4105,15 @@
static void bc_parse_startBody(BcParse *p, uint8_t flags)
{
+ size_t size;
uint8_t *flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
flags |= (*flag_ptr & (BC_PARSE_FLAG_FUNC | BC_PARSE_FLAG_LOOP));
flags |= BC_PARSE_FLAG_BODY;
- bc_vec_push(&p->flags, &flags);
+
+ size = p->bf_top - p->bf_base;
+ p->bf_base = xrealloc(p->bf_base, size + 2);
+ p->bf_top = p->bf_base + size + 1;
+ *p->bf_top = flags;
}
static void bc_parse_noElse(BcParse *p)
@@ -4492,7 +4492,7 @@
static BC_STATUS zbc_parse_body(BcParse *p, bool brace)
{
BcStatus s = BC_STATUS_SUCCESS;
- uint8_t *flag_ptr = bc_vec_top(&p->flags);
+ uint8_t *flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
dbg_lex_enter("%s:%d entered", __func__, __LINE__);
*flag_ptr &= ~(BC_PARSE_FLAG_BODY);
@@ -4535,10 +4535,12 @@
RETURN_STATUS(zbc_lex_next(&p->l));
case BC_LEX_KEY_ELSE:
+ dbg_lex("%s:%d BC_LEX_KEY_ELSE:", __func__, __LINE__);
p->auto_part = false;
break;
case BC_LEX_LBRACE:
+ dbg_lex("%s:%d BC_LEX_LBRACE:", __func__, __LINE__);
if (!BC_PARSE_BODY(p)) RETURN_STATUS(bc_error_bad_token());
++p->nbraces;
s = zbc_lex_next(&p->l);
@@ -4547,6 +4549,7 @@
RETURN_STATUS(zbc_parse_body(p, true));
case BC_LEX_KEY_AUTO:
+ dbg_lex("%s:%d BC_LEX_KEY_AUTO:", __func__, __LINE__);
RETURN_STATUS(zbc_parse_auto(p));
default:
@@ -4660,7 +4663,7 @@
dbg_lex_enter("%s:%d entered", __func__, __LINE__);
if (p->l.t.t == BC_LEX_EOF)
- s = p->flags.len > 0 ? bc_error("block end could not be found") : bc_error("end of file");
+ s = BC_PARSE_FLAG_STACK_EMPTY(p) ? bc_error("end of file") : bc_error("block end could not be found");
else if (p->l.t.t == BC_LEX_KEY_DEFINE) {
dbg_lex("%s:%d p->l.t.t:BC_LEX_KEY_DEFINE", __func__, __LINE__);
if (!BC_PARSE_CAN_EXEC(p))