Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Improve performance of structuredClone #50320

Closed
JMTK opened this issue Oct 21, 2023 · 11 comments
Closed

Improve performance of structuredClone #50320

JMTK opened this issue Oct 21, 2023 · 11 comments
Labels
feature request Issues that request new features to be added to Node.js. stale

Comments

@JMTK
Copy link

JMTK commented Oct 21, 2023 •
edited
Loading

What is the problem this feature will solve?

structuredClone performance is quite slow compared to alternative object copying(while those also have their downsides in some capacity, the performance loss is worth polyfilling at the moment).

I also noticed in the source code there's already a TODO about performance and it would also have WebStreams ReadableStream

There was another discussion here which I thought was insightful #34355 (comment)

Consider code like the following:

var x = { "userId": "134374683951759360", "guild": "86908735326281728", "status": "online", "activities": [{ "name": "Twitch", "type": 1, "url": "https://www.twitch.tv/craggle25", "details": "Weekend dirt naps with @mart0k and Cat. Hunt Showdown", "state": "Hunt: Showdown", "applicationId": null, "timestamps": null, "party": null, "assets": { "largeText": null, "smallText": null, "largeImage": "twitch:craggle25", "smallImage": null }, "flags": 0, "emoji": null, "buttons": [], "createdTimestamp": 1697880668811 }], "clientStatus": { "desktop": "online" } };

function isArr(x) {
    return Array.isArray(x);
}
function isObject(x) {
    return typeof x === 'object';
}

function shallowClone(obj) {
    let clone = {};
    for (let key in obj) {
        let r = obj[key];
        let isArray = isArr(r);
        if (!isArray && isObject(r)) {
            continue;
        }
        if (isArray) {
            clone[key] = [];
            for (let i = 0; i < r.length; i  ) {
                clone[key][i] = shallowClone(r[i]);
            }
        }
        else {
            clone[key] = r;
        }
    }
    return clone;
}

// pulled this from https://github.com/nodejs/node/issues/34355#issuecomment-658394617
function deepClone(o) {
    if (typeof o !== "object") {
      return o
    }
    if (!o) {
      return o
    }

    // https://jsperf.com/deep-copy-vs-json-stringify-json-parse/25
    if (Array.isArray(o)) {
      const newO = []
      for (let i = 0; i < o.length; i  = 1) {
        const val = !o[i] || typeof o[i] !== "object" ? o[i] : deepClone(o[i])
        newO[i] = val === undefined ? null : val
      }
      return newO
    }

    const newO = {}
    for (const i of Object.keys(o)) {
      const val = !o[i] || typeof o[i] !== "object" ? o[i] : deepClone(o[i])
      if (val === undefined) {
        continue
      }
      newO[i] = val
    }
    return newO
  }


let iterations = [100, 10000, 1000000, 10000000];
function profile(name, func) {
    for (let iterationCount of iterations) {
        let n = name   " at "   iterationCount   " iterations";
        console.time(n);
        for (let i = 0; i < iterationCount; i  ) {
            func();
        }
        console.timeEnd(n);
    }
    console.log("");
}


profile('StructuredClone', () => {
    structuredClone(x);
});

profile('ParseStringify', () => {
    JSON.parse(JSON.stringify(x))
});

profile('ShallowClone1', () => {
    shallowClone(x);
});

profile('DeepClone', () => {
    deepClone(x);
});

The output gives me:

StructuredClone at 100 iterations: 5.935ms
StructuredClone at 10000 iterations: 131.071ms
StructuredClone at 1000000 iterations: 9.968s
StructuredClone at 10000000 iterations: 1:45.852 (m:ss.mmm)

ParseStringify at 100 iterations: 1.362ms
ParseStringify at 10000 iterations: 87.677ms
ParseStringify at 1000000 iterations: 8.104s
ParseStringify at 10000000 iterations: 1:33.020 (m:ss.mmm)

ShallowClone1 at 100 iterations: 0.589ms
ShallowClone1 at 10000 iterations: 18.628ms
ShallowClone1 at 1000000 iterations: 739.982ms
ShallowClone1 at 10000000 iterations: 6.942s

DeepClone at 100 iterations: 1.079ms
DeepClone at 10000 iterations: 46.382ms
DeepClone at 1000000 iterations: 2.914s
DeepClone at 10000000 iterations: 26.039s

What is the feature you are proposing to solve the problem?

Increase throughput on structuredClone calls

What alternatives have you considered?

Polyfilling my own object clone methods
@JMTK JMTK added the feature request Issues that request new features to be added to Node.js. label Oct 21, 2023
@bnoordhuis
Copy link
Member

Your report isn't actionable unless you have concrete improvement suggestions. "Increase throughput" isn't.

In case you're unaware: structuredClone is implemented in terms of V8's value serializer/deserializer API, i.e., the meat of the work is done inside V8, not node.

@benjamingr
Copy link
Member

@nodejs/performance we could consider a fast path for certain types of values if that's an interesting use case.

@bnoordhuis
Copy link
Member

I really doubt that once you handle all the edge cases it's going to be significantly faster than what V8 already does.

For example, OP's deepClone function doesn't handle arrays with non-element properties correctly, to say nothing of recursive data structures.

@benjamingr
Copy link
Member

@bnoordhuis not going through an extra MessageChannel might be a good start https://github.com/nodejs/node/blob/main/lib/internal/structured_clone.js but even so - I wouldn't assume V8's implementation is particularly fast, that they optimized it a lot or that it's too difficult to beat (in a spec compliant manner obviously), I may be wrong.

@bnoordhuis
Copy link
Member

Oh sure, no disagreement from me there, but OP's suggestion is to shortcut the algorithm and I don't think that's going to be a fruitful endeavor. Adding cycle detection alone probably wipes out much of the performance advantage, never mind everything else.

(I recently wrote a golang library that speaks V8's serde protocol so this is all sparking fresh on my mind.)

@Qard
Copy link
Member

Qard commented Oct 22, 2023

I would expect more often than not the input is going to be a complex object, not a primitive which a fast path could be added for. I don't think there's much we can do here beyond pulling out the clone algorithm so you don't need to construct a the MessageChannel to pass through it, and then start looking at what can be done in V8.

One could possibly inform the V8 optimizer with shape information to compute ahead if other code passed in a shape known to not have pitfalls like circular references and skip the checks. That would be a complicated effort though. I'm happy to mentor anyone wanting to take it on when I can, just be prepared for it to take several weeks or even months. 😅

@joyeecheung
Copy link
Member

joyeecheung commented Oct 22, 2023 •
edited
Loading

I wrote up a simplified implementation of structuredClone in native and it improves the performance a bit:

                                                    confidence improvement accuracy (*)   (**)  (***)
misc/structured-clone.js n=10000 type='arraybuffer'        ***      5.93 %       ±1.64% ±2.18% ±2.84%
misc/structured-clone.js n=10000 type='object'             ***      7.83 %       ±1.89% ±2.53% ±3.32%
misc/structured-clone.js n=10000 type='string'             ***     43.98 %       ±1.90% ±2.53% ±3.29%

Would be even better if we just don't use ports. But baby steps. That would also allow us to support structuredClone in customized snapshots (I am fairly certain that there was an issue for this - cannot find it though - or someone asked me about this).

@joyeecheung joyeecheung mentioned this issue Oct 22, 2023
Merged
@JMTK
Copy link
Author

JMTK commented Oct 25, 2023

Thanks for getting that change in so quickly @joyeecheung. Do you think this issue should be closed and a separate one should be reopened for future work?

@joyeecheung
Copy link
Member

joyeecheung commented Oct 26, 2023 •
edited
Loading

With the snippet in the OP I got this:

StructuredClone at 100 iterations: 0.804ms
StructuredClone at 10000 iterations: 56.326ms
StructuredClone at 1000000 iterations: 5.372s
StructuredClone at 10000000 iterations: 52.784s

ParseStringify at 100 iterations: 0.617ms
ParseStringify at 10000 iterations: 41.563ms
ParseStringify at 1000000 iterations: 4.063s
ParseStringify at 10000000 iterations: 41.037s

ShallowClone1 at 100 iterations: 0.434ms
ShallowClone1 at 10000 iterations: 6.873ms
ShallowClone1 at 1000000 iterations: 409.999ms
ShallowClone1 at 10000000 iterations: 4.105s

DeepClone at 100 iterations: 0.618ms
DeepClone at 10000 iterations: 16.654ms
DeepClone at 1000000 iterations: 1.308s
DeepClone at 10000000 iterations: 13.063s

So I think there are still work to be done to make structured clone more performant. One is #50330 (comment) and another is using fast APIs when there's no transfer list. But I think even with those there's still a lot for structured clone to catch up with other alternatives.

@github-actions GitHub Actions
Copy link
Contributor

There has been no activity on this feature request for 5 months. To help maintain relevant open issues, please add the never-stale Mark issue so that it is never considered stale label or close this issue if it should be closed. If not, the issue will be automatically closed 6 months after the last non-automated comment.
For more information on how the project manages feature requests, please consult the feature request management document.

@github-actions github-actions bot added the stale label Apr 23, 2024
@github-actions GitHub Actions
Copy link
Contributor

There has been no activity on this feature request and it is being closed. If you feel closing this issue is not the right thing to do, please leave a comment.

For more information on how the project manages feature requests, please consult the feature request management document.

@github-actions github-actions bot closed this as not planned Won't fix, can't repro, duplicate, stale May 23, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
feature request Issues that request new features to be added to Node.js. stale
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@Qard @bnoordhuis @JMTK @benjamingr @joyeecheung