Optimising `find_var` / `find_arg` performance

[andrjohns]

I've got a large JS program which qjs takes ~1.5 seconds just to parse/load. If I profile the evaluation using gprof, then it shows that over a third of the time is spent in find_var alone:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 36.65      1.84     1.84   275818     0.00     0.00  find_var
 12.75      2.48     0.64   212052     0.00     0.00  JS_CallInternal
 11.55      3.06     0.58   100362     0.00     0.00  get_var_ref
...

Given that every timefind_var is called it iterates through all variables in the scope until finding the target variable, it looks like this is causing a lot of repeated iteration over the same variables when fd->var_count is large (15951 in my case):

static int find_var(JSContext *ctx, JSFunctionDef *fd, JSAtom name)
{
    int i;
    for(i = fd->var_count; i-- > 0;) {
        if (fd->vars[i].var_name == name && fd->vars[i].scope_level == 0)
            return i;
    }
    return find_arg(ctx, fd, name);
}

Could this be replaced with a lookup/hashtable or similar in the JSFunctionDef object? Or is there a simpler alternative?

[chqrlie]

@andrjohns: Interesting use case. Do you have 15951 local variables in scope? How many nested scopes? Any closures involved too? Are these var or let / const definitions?
We never envisioned this simple loop to be an issue, but indeed some sort of hashing would help... The javascript scoping rules make this cumbersome, but I can try and investigate some ideas.
Could you possibly share this file for me to benchmark lookup alternatives?

[andrjohns]

Thanks! It's a bit of a behemoth file, but you can get it from here: https://github.com/stan-dev/stanc3/releases/download/nightly/stanc.js

As context, it's a transpiler for the Stan Language, converting the Stan language to C++. The transpiler itself is written in OCaml, but R doesn't support compiling OCaml in packages, so we instead have to compile the OCaml to JavaScript (using js_of_ocaml) for use in R

[andrjohns]

That's the minified file, let me know if the original/verbose would be more useful instead!

[chqrlie]

That's the minified file, let me know if the original/verbose would be more useful instead!

@andrjohns Indeed a more verbose version would be useful :)

[andrjohns]

That's the minified file, let me know if the original/verbose would be more useful instead!

@andrjohns Indeed a more verbose version would be useful :)

Of course, here you go: stanc-debug.js.txt

(Using .txt for github upload restrictions)

[bnoordhuis]

This is really just me thinking out aloud but...

We never envisioned this simple loop to be an issue, but indeed some sort of hashing would help

...what could maybe also work is a small 4-8 entries LRU¹ cache that's searched first. find_var does a lot of repeated work for the source file @andrjohns provided.

¹ Or a LFSR that randomly discards entries. Probably similar asymptotic performance, possibly better mechanical performance.

[bnoordhuis]

I implemented my LRU cache idea in #668 but it gives only a modest speedup (20% off resolve_scope_var, 10% off overall running time)

I'll see if turning fd->vars into a hash table helps.

[bnoordhuis]

#672 - hashing does make a dramatic difference: 70% off total running time.