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>
author: Denys Vlasenko <vda.linux@googlemail.com> 2018-12-15 00:39:17 +0100
committer: Denys Vlasenko <vda.linux@googlemail.com> 2018-12-15 00:49:16 +0100
commit: 7db384338a803fc74a0e8eb62e9369e10a49ffdb (patch)
tree: 3ffc6b10de2c8f9d24b5e72042fe659cfc35c86d
parent: f10f17f8d3ee77c469fc57634a458e8a45aeb681 (diff)
download: busybox-w32-7db384338a803fc74a0e8eb62e9369e10a49ffdb.tar.gz
busybox-w32-7db384338a803fc74a0e8eb62e9369e10a49ffdb.tar.bz2
busybox-w32-7db384338a803fc74a0e8eb62e9369e10a49ffdb.zip
1 files changed, 23 insertions, 20 deletions
diff --git a/miscutils/bc.c b/miscutils/bc.c
index 4024a08df..2feaf7bf3 100644
--- a/miscutils/bc.c
+++ b/miscutils/bc.c
@@ -574,8 +574,9 @@ typedef struct BcLex {
 #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 @@ typedef struct BcLex {
 #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 @@ typedef struct BcParse {
        size_t nbraces;
        bool auto_part;
 } BcParse;
 typedef struct BcProgram {
@@ -3558,7 +3554,7 @@ static void bc_parse_reset(BcParse *p)
        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_reset(BcParse *p)
 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 @@ static void bc_parse_create(BcParse *p, size_t func)
        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 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
 {
        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 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
                        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 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
                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 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
        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 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
                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 BC_STATUS zbc_parse_endBody(BcParse *p)
 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 @@ err:
 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 @@ static BC_STATUS zbc_parse_stmt(BcParse *p)
                        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 @@ static BC_STATUS zbc_parse_stmt(BcParse *p)
                        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 @@ static BC_STATUS zbc_parse_parse(BcParse *p)
        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))
author	Denys Vlasenko <vda.linux@googlemail.com>	2018-12-15 00:39:17 +0100
committer	Denys Vlasenko <vda.linux@googlemail.com>	2018-12-15 00:49:16 +0100
commit	7db384338a803fc74a0e8eb62e9369e10a49ffdb (patch)
tree	3ffc6b10de2c8f9d24b5e72042fe659cfc35c86d
parent	f10f17f8d3ee77c469fc57634a458e8a45aeb681 (diff)
download	busybox-w32-7db384338a803fc74a0e8eb62e9369e10a49ffdb.tar.gz busybox-w32-7db384338a803fc74a0e8eb62e9369e10a49ffdb.tar.bz2 busybox-w32-7db384338a803fc74a0e8eb62e9369e10a49ffdb.zip

diff --git a/miscutils/bc.c b/miscutils/bc.c index 4024a08df..2feaf7bf3 100644 --- a/miscutils/bc.c +++ b/miscutils/bc.c
@@ -574,8 +574,9 @@ typedef struct BcLex {
574	#define BC_PARSE_NOREAD (1 << 3)	574	#define BC_PARSE_NOREAD (1 << 3)
575	#define BC_PARSE_ARRAY (1 << 4)	575	#define BC_PARSE_ARRAY (1 << 4)
576		576
577	#define BC_PARSE_TOP_FLAG_PTR(parse) ((uint8_t *) bc_vec_top(&(parse)->flags))	577	#define BC_PARSE_TOP_FLAG_PTR(parse) ((parse)->bf_top)
578	#define BC_PARSE_TOP_FLAG(parse) (*(BC_PARSE_TOP_FLAG_PTR(parse)))	578	#define BC_PARSE_TOP_FLAG(parse) (*(BC_PARSE_TOP_FLAG_PTR(parse)))
		579	#define BC_PARSE_FLAG_STACK_EMPTY(p) ((p)->bf_top == (p)->bf_base)
579		580
580	#define BC_PARSE_FLAG_FUNC_INNER (1 << 0)	581	#define BC_PARSE_FLAG_FUNC_INNER (1 << 0)
581	#define BC_PARSE_FLAG_FUNC (1 << 1)	582	#define BC_PARSE_FLAG_FUNC (1 << 1)
@@ -598,15 +599,11 @@ typedef struct BcLex {
598	#define BC_PARSE_ELSE(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_ELSE)	599	#define BC_PARSE_ELSE(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_ELSE)
599	#define BC_PARSE_IF_END(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_IF_END)	600	#define BC_PARSE_IF_END(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_IF_END)
600		601
601	struct BcParse;
602
603	struct BcProgram;
604
605	typedef struct BcParse {	602	typedef struct BcParse {
606
607	BcLex l;	603	BcLex l;
608		604
609	BcVec flags;	605	uint8_t *bf_base;
		606	uint8_t *bf_top;
610		607
611	BcVec exits;	608	BcVec exits;
612	BcVec conds;	609	BcVec conds;
@@ -618,7 +615,6 @@ typedef struct BcParse {
618		615
619	size_t nbraces;	616	size_t nbraces;
620	bool auto_part;	617	bool auto_part;
621
622	} BcParse;	618	} BcParse;
623		619
624	typedef struct BcProgram {	620	typedef struct BcProgram {
@@ -3558,7 +3554,7 @@ static void bc_parse_reset(BcParse *p)
3558	p->l.t.t = BC_LEX_EOF;	3554	p->l.t.t = BC_LEX_EOF;
3559	p->auto_part = (p->nbraces = 0);	3555	p->auto_part = (p->nbraces = 0);
3560		3556
3561	bc_vec_npop(&p->flags, p->flags.len - 1);	3557	p->bf_top = p->bf_base; // pop all flags
3562	bc_vec_pop_all(&p->exits);	3558	bc_vec_pop_all(&p->exits);
3563	bc_vec_pop_all(&p->conds);	3559	bc_vec_pop_all(&p->conds);
3564	bc_vec_pop_all(&p->ops);	3560	bc_vec_pop_all(&p->ops);
@@ -3568,7 +3564,7 @@ static void bc_parse_reset(BcParse *p)
3568		3564
3569	static void bc_parse_free(BcParse *p)	3565	static void bc_parse_free(BcParse *p)
3570	{	3566	{
3571	bc_vec_free(&p->flags);	3567	free(p->bf_base);
3572	bc_vec_free(&p->exits);	3568	bc_vec_free(&p->exits);
3573	bc_vec_free(&p->conds);	3569	bc_vec_free(&p->conds);
3574	bc_vec_free(&p->ops);	3570	bc_vec_free(&p->ops);
@@ -3580,10 +3576,9 @@ static void bc_parse_create(BcParse *p, size_t func)
3580	memset(p, 0, sizeof(BcParse));	3576	memset(p, 0, sizeof(BcParse));
3581		3577
3582	bc_lex_init(&p->l);	3578	bc_lex_init(&p->l);
3583	bc_vec_init(&p->flags, sizeof(uint8_t), NULL);	3579	p->bf_top = p->bf_base = xzalloc(1);
3584	bc_vec_init(&p->exits, sizeof(BcInstPtr), NULL);	3580	bc_vec_init(&p->exits, sizeof(BcInstPtr), NULL);
3585	bc_vec_init(&p->conds, sizeof(size_t), NULL);	3581	bc_vec_init(&p->conds, sizeof(size_t), NULL);
3586	bc_vec_pushZeroByte(&p->flags);
3587	bc_vec_init(&p->ops, sizeof(BcLexType), NULL);	3582	bc_vec_init(&p->ops, sizeof(BcLexType), NULL);
3588		3583
3589	// p->auto_part = p->nbraces = 0; - already is	3584	// p->auto_part = p->nbraces = 0; - already is
@@ -4050,7 +4045,7 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
4050	{	4045	{
4051	BcStatus s = BC_STATUS_SUCCESS;	4046	BcStatus s = BC_STATUS_SUCCESS;
4052		4047
4053	if (p->flags.len <= 1)	4048	if (BC_PARSE_FLAG_STACK_EMPTY(p))
4054	RETURN_STATUS(bc_error_bad_token());	4049	RETURN_STATUS(bc_error_bad_token());
4055		4050
4056	if (BC_PARSE_IF(p)) {	4051	if (BC_PARSE_IF(p)) {
@@ -4061,7 +4056,7 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
4061	if (s) RETURN_STATUS(s);	4056	if (s) RETURN_STATUS(s);
4062	}	4057	}
4063		4058
4064	bc_vec_pop(&p->flags);	4059	p->bf_top--;
4065		4060
4066	flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);	4061	flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
4067	dbg_lex("%s:%d setting BC_PARSE_FLAG_IF_END bit", __func__, __LINE__);	4062	dbg_lex("%s:%d setting BC_PARSE_FLAG_IF_END bit", __func__, __LINE__);
@@ -4074,7 +4069,7 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
4074	BcInstPtr *ip;	4069	BcInstPtr *ip;
4075	size_t *label;	4070	size_t *label;
4076		4071
4077	bc_vec_pop(&p->flags);	4072	p->bf_top--;
4078		4073
4079	ip = bc_vec_top(&p->exits);	4074	ip = bc_vec_top(&p->exits);
4080	label = bc_vec_item(&p->func->labels, ip->idx);	4075	label = bc_vec_item(&p->func->labels, ip->idx);
@@ -4085,7 +4080,7 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
4085	else if (BC_PARSE_FUNC_INNER(p)) {	4080	else if (BC_PARSE_FUNC_INNER(p)) {
4086	bc_parse_push(p, BC_INST_RET0);	4081	bc_parse_push(p, BC_INST_RET0);
4087	bc_parse_updateFunc(p, BC_PROG_MAIN);	4082	bc_parse_updateFunc(p, BC_PROG_MAIN);
4088	bc_vec_pop(&p->flags);	4083	p->bf_top--;
4089	}	4084	}
4090	else {	4085	else {
4091	BcInstPtr *ip = bc_vec_top(&p->exits);	4086	BcInstPtr *ip = bc_vec_top(&p->exits);
@@ -4097,7 +4092,7 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
4097	label = bc_vec_item(&p->func->labels, ip->idx);	4092	label = bc_vec_item(&p->func->labels, ip->idx);
4098	*label = p->func->code.len;	4093	*label = p->func->code.len;
4099		4094
4100	bc_vec_pop(&p->flags);	4095	p->bf_top--;
4101	bc_vec_pop(&p->exits);	4096	bc_vec_pop(&p->exits);
4102	bc_vec_pop(&p->conds);	4097	bc_vec_pop(&p->conds);
4103	}	4098	}
@@ -4110,10 +4105,15 @@ static BC_STATUS zbc_parse_endBody(BcParse *p)
4110		4105
4111	static void bc_parse_startBody(BcParse *p, uint8_t flags)	4106	static void bc_parse_startBody(BcParse *p, uint8_t flags)
4112	{	4107	{
		4108	size_t size;
4113	uint8_t *flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);	4109	uint8_t *flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
4114	flags \|= (*flag_ptr & (BC_PARSE_FLAG_FUNC \| BC_PARSE_FLAG_LOOP));	4110	flags \|= (*flag_ptr & (BC_PARSE_FLAG_FUNC \| BC_PARSE_FLAG_LOOP));
4115	flags \|= BC_PARSE_FLAG_BODY;	4111	flags \|= BC_PARSE_FLAG_BODY;
4116	bc_vec_push(&p->flags, &flags);	4112
		4113	size = p->bf_top - p->bf_base;
		4114	p->bf_base = xrealloc(p->bf_base, size + 2);
		4115	p->bf_top = p->bf_base + size + 1;
		4116	*p->bf_top = flags;
4117	}	4117	}
4118		4118
4119	static void bc_parse_noElse(BcParse *p)	4119	static void bc_parse_noElse(BcParse *p)
@@ -4492,7 +4492,7 @@ err:
4492	static BC_STATUS zbc_parse_body(BcParse *p, bool brace)	4492	static BC_STATUS zbc_parse_body(BcParse *p, bool brace)
4493	{	4493	{
4494	BcStatus s = BC_STATUS_SUCCESS;	4494	BcStatus s = BC_STATUS_SUCCESS;
4495	uint8_t *flag_ptr = bc_vec_top(&p->flags);	4495	uint8_t *flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
4496		4496
4497	dbg_lex_enter("%s:%d entered", __func__, __LINE__);	4497	dbg_lex_enter("%s:%d entered", __func__, __LINE__);
4498	*flag_ptr &= ~(BC_PARSE_FLAG_BODY);	4498	*flag_ptr &= ~(BC_PARSE_FLAG_BODY);
@@ -4535,10 +4535,12 @@ static BC_STATUS zbc_parse_stmt(BcParse *p)
4535	RETURN_STATUS(zbc_lex_next(&p->l));	4535	RETURN_STATUS(zbc_lex_next(&p->l));
4536		4536
4537	case BC_LEX_KEY_ELSE:	4537	case BC_LEX_KEY_ELSE:
		4538	dbg_lex("%s:%d BC_LEX_KEY_ELSE:", __func__, __LINE__);
4538	p->auto_part = false;	4539	p->auto_part = false;
4539	break;	4540	break;
4540		4541
4541	case BC_LEX_LBRACE:	4542	case BC_LEX_LBRACE:
		4543	dbg_lex("%s:%d BC_LEX_LBRACE:", __func__, __LINE__);
4542	if (!BC_PARSE_BODY(p)) RETURN_STATUS(bc_error_bad_token());	4544	if (!BC_PARSE_BODY(p)) RETURN_STATUS(bc_error_bad_token());
4543	++p->nbraces;	4545	++p->nbraces;
4544	s = zbc_lex_next(&p->l);	4546	s = zbc_lex_next(&p->l);
@@ -4547,6 +4549,7 @@ static BC_STATUS zbc_parse_stmt(BcParse *p)
4547	RETURN_STATUS(zbc_parse_body(p, true));	4549	RETURN_STATUS(zbc_parse_body(p, true));
4548		4550
4549	case BC_LEX_KEY_AUTO:	4551	case BC_LEX_KEY_AUTO:
		4552	dbg_lex("%s:%d BC_LEX_KEY_AUTO:", __func__, __LINE__);
4550	RETURN_STATUS(zbc_parse_auto(p));	4553	RETURN_STATUS(zbc_parse_auto(p));
4551		4554
4552	default:	4555	default:
@@ -4660,7 +4663,7 @@ static BC_STATUS zbc_parse_parse(BcParse *p)
4660		4663
4661	dbg_lex_enter("%s:%d entered", __func__, __LINE__);	4664	dbg_lex_enter("%s:%d entered", __func__, __LINE__);
4662	if (p->l.t.t == BC_LEX_EOF)	4665	if (p->l.t.t == BC_LEX_EOF)
4663	s = p->flags.len > 0 ? bc_error("block end could not be found") : bc_error("end of file");	4666	s = BC_PARSE_FLAG_STACK_EMPTY(p) ? bc_error("end of file") : bc_error("block end could not be found");
4664	else if (p->l.t.t == BC_LEX_KEY_DEFINE) {	4667	else if (p->l.t.t == BC_LEX_KEY_DEFINE) {
4665	dbg_lex("%s:%d p->l.t.t:BC_LEX_KEY_DEFINE", __func__, __LINE__);	4668	dbg_lex("%s:%d p->l.t.t:BC_LEX_KEY_DEFINE", __func__, __LINE__);
4666	if (!BC_PARSE_CAN_EXEC(p))	4669	if (!BC_PARSE_CAN_EXEC(p))