Adding JsValues to Vec<JsValue> takes quadratic time with reference types enabled for first run.

[richardlett]

Describe the Bug

I wanted to try out reference types. In testing, it sped up my code, except on first run, where it is slowed it down dramatically. It appears to take quadratic time with respect to number of items added.

I've isolated it to adding items to a vec.

Addin 1.2 million JsValues to a vec, using reference types made the first run go from .2-.3 seconds (not using them) to ~150 seconds.

(the JsValue was always 1)

Subsequent runs after removing all items were faster than the first. (Only <0.7 seconds for 1.2 million)

Removing all items from first, and then re-adding 1 million items to a second object was also faster.

Steps to Reproduce

1. Install wasm-pack with reference type support using this branch (remember to switch branches) using cargo install while in the directory
2. Clone this minimal reproduction repo, `
3. run wasm-pack build --release --ref-types --target web to build
4. Create a static http server at root, using python3 -m http.server or similar, and open in firefox. After a while, in the console you will see
   

wasm-push is 1.2 million items to a vec. wasm-pop is removing them all. Wasm-pushpop does both.

Expected behavior:

Take linear time to add N items to a vec.

Actual behavior:

It seems to take quadratic time. Here's a table of time taken for first N items added vs a chart.

Sorry if this has already been reported.

[richardlett]

(Follow up to @Tarnadas from rustwasm/wasm-pack#888 (comment) , since this is not too relevant to that thread)

Thank you for your patience and the explanation. I ended with

    const m = new WebAssembly.Memory({ initial: 1000, maximum: 25000 });
    console.log(m.buffer);
    const { instance, module } = await load(await input, {  js: { mem: m }, ...imports });

I gather the load function takes care of returning the instance by calling either WebAssembly.instantiate(module, imports) or WebAssembly.instantiateStreaming(module, imports), depending on context.

Unfortunately, this does not seem like this has too much of an effect, no mater what the initial memory is set to. Out of curiosity,I also started timing the constructor. initiating the vec with capacity 1 million took generally around 0-1ms, when intial was 1 (~65 kb), but up to 5 ms when initial was 10000 (~650 Mb).

[richardlett]

It seems most of the time is spend resizing the externref_table. Hmmm.

edit: I think I figured it out. Working on a PR now.