Skip to content

[WIP] Rewrite DeltaBundler cycle collection as a separate pass#820

Closed
motiz88 wants to merge 1 commit into
react:mainfrom
motiz88:export-D36403390
Closed

[WIP] Rewrite DeltaBundler cycle collection as a separate pass#820
motiz88 wants to merge 1 commit into
react:mainfrom
motiz88:export-D36403390

Conversation

@motiz88

@motiz88 motiz88 commented May 16, 2022

Copy link
Copy Markdown
Contributor

See also: microsoft/rnx-kit#1514

Rewrites traverseDependencies (the core algorithm of DeltaBundler) to run in two distinct phases:

  1. Module transformation + dependency discovery/diffing.
  2. Garbage collection.

Modules that are trivially unreachable (inverse dependency count decreases to zero) are deleted during (1); the rest ( = unreachable modules in dependency cycles) are deleted during (2).

By collecting cycles in a separate pass instead of kicking off nested traversals during the dependency diffing pass, the algorithm becomes easier to reason about, and we gain the ability to optionally skip GC (in future work) because all the GC state is stored in the graph (and not on the traversal stack).

The garbage collection code is adapted from the Synchronous Cycle Collection algorithm described in:

David F. Bacon and V. T. Rajan. 2001. Concurrent Cycle Collection in Reference Counted Systems. In Proceedings of the 15th European Conference on Object-Oriented Programming (ECOOP '01). Springer-Verlag, Berlin, Heidelberg, 207–235.


As part of this rewrite we also make the handling of async imports under experimentalImportBundleSupport: true more sound and tested, at least as far as traverseDependencies goes. Several of the new tests under "lazy traversal of async imports" were failing before this diff. Note that there a few remaining problems with this experimental feature, which will need to be fixed in separate work:

  1. The HMR protocol does not sync changes to importBundleNames between the client and server, so any newly added async dependencies in a Fast Refresh'd module will (still) break at runtime.
  2. A module's out-edges are keyed on the unresolved dependency paths only, so a parallel async+sync pair of dependencies from A --> B will result in either an async or sync edge being recorded, depending on their order in the dependencies array. This will need fixing in both DeltaBundler and collectDependencies.

Differential Revision: D36403390

@facebook-github-bot facebook-github-bot added CLA Signed This label is managed by the Facebook bot. Authors need to sign the CLA before a PR can be reviewed. fb-exported labels May 16, 2022
@facebook-github-bot

Copy link
Copy Markdown
Contributor

This pull request was exported from Phabricator. Differential Revision: D36403390

@motiz88 motiz88 changed the title Rewrite DeltaBundler cycle collection as a separate pass [WIP] Rewrite DeltaBundler cycle collection as a separate pass May 16, 2022
Summary:
Pull Request resolved: react#820

See also: microsoft/rnx-kit#1514

Rewrites traverseDependencies (the core algorithm of DeltaBundler) to run in two distinct phases:

1. Module transformation + dependency discovery/diffing.
2. Garbage collection.

Modules that are trivially unreachable (inverse dependency count decreases to zero) are deleted during (1); the rest ( = unreachable modules in dependency cycles) are deleted during (2).

By collecting cycles in a separate pass instead of kicking off nested traversals during the dependency diffing pass, the algorithm becomes easier to reason about, and we gain the ability to optionally skip GC (in future work) because all the GC state is stored in the graph (and not on the traversal stack).

The garbage collection code is adapted from the Synchronous Cycle Collection algorithm described in:

> David F. Bacon and V. T. Rajan. 2001. Concurrent Cycle Collection in Reference Counted Systems. In Proceedings of the 15th European Conference on Object-Oriented Programming (ECOOP '01). Springer-Verlag, Berlin, Heidelberg, 207–235.

 ---

As part of this rewrite we also make the handling of async imports under `experimentalImportBundleSupport: true` more sound and tested, at least as far as `traverseDependencies` goes. Several of the new tests under "lazy traversal of async imports" were failing before this diff. Note that there a few remaining problems with this experimental feature, which will need to be fixed in separate work:

1. The HMR protocol does not sync changes to `importBundleNames` between the client and server, so any newly added async dependencies in a Fast Refresh'd module will (still) break at runtime.
2. A module's out-edges are keyed on the unresolved dependency paths only, so a parallel async+sync pair of dependencies from A --> B will result in either an async or sync edge being recorded, depending on their order in the dependencies array. This will need fixing in both DeltaBundler and `collectDependencies`.

Differential Revision: D36403390

fbshipit-source-id: f56241d0c4c038b6c780cb58ca4d50e1bb0ff1fb
@motiz88 motiz88 force-pushed the export-D36403390 branch from bdf6d4c to 82d507a Compare May 24, 2022 04:13
@facebook-github-bot

Copy link
Copy Markdown
Contributor

This pull request was exported from Phabricator. Differential Revision: D36403390

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

CLA Signed This label is managed by the Facebook bot. Authors need to sign the CLA before a PR can be reviewed. fb-exported

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants