parse: use dynamically sized hashtable for temporaries v1 PROPOSED

Michael Forney: 2
 parse: use dynamically sized hashtable for temporaries
 parse: use dynamically sized hashtable for temporaries

 2 files changed, 20 insertions(+), 12 deletions(-)

Michael Forney <mforney@mforney.org> wrote:

[PATCH] parse: use dynamically sized hashtable for temporaries Export this patch

This significantly improves parsing performance for massive functions
with a huge number of temporaries. Parsing the 86MiB IL produced

Quentin Carbonneaux <quentin@c9x.me>

4 months ago

Thanks a lot, I merged your patch in master.

Next

by cproc during zig bootstrap drops from 17m15s to 2.5s (over 400x
speedup).

Quentin Carbonneaux <quentin@c9x.me>

4 months ago

Is there a place where I can read more about this line of work?

The speedup is much smaller for IL produced from normal non-autogenerated
C code. Parsing the sqlite3 amalgamation drops from 0.40s to 0.33s.
---
I reused the TMask constant for the initial size of the hashtable,
but perhaps now it should have a different name?

 parse.c | 30 +++++++++++++++++++-----------
 1 file changed, 19 insertions(+), 11 deletions(-)

diff --git a/parse.c b/parse.c
index a909b7d..0154ca4 100644
--- a/parse.c
+++ b/parse.c
@@ -152,7 +152,8 @@ static struct {
 static int lnum;
 
 static Fn *curf;
-static int tmph[TMask+1];
+static int *tmph;
+static int tmphcap;
 static Phi **plink;
 static Blk *curb;
 static Blk **blink;
@@ -384,19 +385,26 @@ expect(int t)
 static Ref
 tmpref(char *v)
 {
-	int t, *h;
-
-	h = &tmph[hash(v) & TMask];
-	t = *h;
-	if (t) {
+	int t, i;
+
+	if (tmphcap/2 <= curf->ntmp-Tmp0) {
+		free(tmph);
+		tmphcap = tmphcap ? tmphcap*2 : TMask+1;
+		tmph = emalloc(tmphcap * sizeof *tmph);
+		for (t=Tmp0; t<curf->ntmp; t++) {
+			i = hash(curf->tmp[t].name) & (tmphcap-1);
+			for (; tmph[i]; i=(i+1) & (tmphcap-1))
+				;
+			tmph[i] = t;
+		}
+	}
+	for (i=hash(v) & (tmphcap-1); tmph[i]; i=(i+1) & (tmphcap-1)) {
+		t = tmph[i];
 		if (strcmp(curf->tmp[t].name, v) == 0)
 			return TMP(t);
-		for (t=curf->ntmp-1; t>=Tmp0; t--)
-			if (strcmp(curf->tmp[t].name, v) == 0)
-				return TMP(t);
 	}
 	t = curf->ntmp;
-	*h = t;
+	tmph[i] = t;
 	newtmp(0, Kx, curf);
 	strcpy(curf->tmp[t].name, v);
 	return TMP(t);
@@ -926,7 +934,7 @@ parsefn(Lnk *lnk)
 		b->dlink = 0; /* was trashed by findblk() */
 	for (i=0; i<BMask+1; ++i)
 		blkh[i] = 0;
-	memset(tmph, 0, sizeof tmph);
+	memset(tmph, 0, tmphcap * sizeof *tmph);
 	typecheck(curf);
 	return curf;
 }
-- 
2.44.0

Re: [PATCH] parse: use dynamically sized hashtable for temporaries Export this patch

Quentin Carbonneaux <quentin@c9x.me> wrote:
> > during zig bootstrap drops from 17m15s to 2.5s (over 400x
> > speedup).
> 
> Is there a place where I can read more about this line of work?

I just tried it since andrewrk mentioned it in #musl.

To try yourself, you can clone the zig repository, then

	cproc -o bootstrap bootstrap.c
	CC=cproc ./bootstrap

I also needed a small patch to prevent the generated C from loading
an uninitialized variably in a dead code path (slot %.174 is read
but never stored to).

It seems that everything is able to compile except for one function
`f17`, which gives

	rega.c: dying: cannot have more moves than registers

I haven't yet tried to minimize the function yet.

Michael Forney <mforney@mforney.org>

4 months ago

The result after creduce+ddmin is attached.

diff --git a/stage1/wasm2c.c b/stage1/wasm2c.c
index 10c0a0c3de..942ac40e85 100644
--- a/stage1/wasm2c.c
+++ b/stage1/wasm2c.c
@@ -552,7 +552,7 @@ int main(int argc, char **argv) {
                 FuncGen_indent(&fg, out);
                 (void)FuncGen_localDeclare(&fg, out,
                                            func_type->result->types[result_i]);
-                fputs(";\n", out);
+                fputs(" = 0;\n", out);
             }
             FuncGen_blockBegin(&fg, out, WasmOpcode_block, funcs[func_i].type_idx);
             while (!FuncGen_done(&fg)) {

Michael Forney <mforney@mforney.org>

4 months ago

Michael Forney <mforney@mforney.org> wrote: