search

endojs / endo

Endo is a distributed secure JavaScript sandbox, based on SES
Apache License 2.0
804 stars 71 forks source link

For performance, compactOrdered decodePassable should minimize reparsing #1747

Open gibson042 opened 1 year ago

gibson042 commented 1 year ago

_Extracted from https://github.com/endojs/endo/pull/1594#discussion_r1285296392_

What is the Problem Being Solved?

The depth-aware array-decoding function introduced in #1594 is aware of each leaf node in a deep structure, but decoding is a recursive operation with string input. This means that nested arrays are fully traversed and comprehended, but that information is discarded in the calls that ultimately deserialize their constituent elements.

Description of the Design

The function should instead be provided with an ephemeral cache shared across the call stack of an outermost call to decodePassable, such that the outermost decodeArray function can populate it and reentrant calls can return from it rather than iterating over an already-visited slice of the input string.

Security Considerations

None in particular.

Scaling Considerations

This is only worth pursuing if it actually improves performance, specifically time complexity without an undue degradation of space complexity.

Test Plan

Per the above, we should perform some kind of benchmarking.

Upgrade Considerations

None; this will be a functionality-preserving optimization.

erights commented 6 months ago

@gibson042 , does this also apply to compactOrdered? If not, I suggest closing as won't fix. If so, I suggest renaming.