federation icon indicating copy to clipboard operation
federation copied to clipboard

Use a `Set` for referencers

Open clenfest opened this issue 1 year ago • 4 comments

When working with elements with many referencers, addReferencer() became very hot.

If you have eg. 100 referencers, each one is added one by one, and each new addition iterates the entire existing referencers list. This could cause quadratic performance.

This changes the _referencers values to be JS Sets. This maintains the same order for algorithms that rely on order.

clenfest avatar Jun 28 '24 17:06 clenfest

⚠️ No Changeset found

Latest commit: c65b400f8733ba9f9790039dad9440e95551eee6

Merging this PR will not cause a version bump for any packages. If these changes should not result in a new version, you're good to go. If these changes should result in a version bump, you need to add a changeset.

This PR includes no changesets

When changesets are added to this PR, you'll see the packages that this PR includes changesets for and the associated semver types

Click here to learn what changesets are, and how to add one.

Click here if you're a maintainer who wants to add a changeset to this PR

changeset-bot[bot] avatar Jun 28 '24 17:06 changeset-bot[bot]

Deploy Preview for apollo-federation-docs canceled.

Name Link
Latest commit c65b400f8733ba9f9790039dad9440e95551eee6
Latest deploy log https://app.netlify.com/sites/apollo-federation-docs/deploys/667ef99c53902b0008bb729b

netlify[bot] avatar Jun 28 '24 17:06 netlify[bot]

This pull request is automatically built and testable in CodeSandbox.

To see build info of the built libraries, click here or the icon next to each commit SHA.

codesandbox-ci[bot] avatar Jun 28 '24 17:06 codesandbox-ci[bot]

It actually might be good to convert unionsWhereMember and allImplementations, too. I didn't do it because it's more work. But allImplementations in particular is used for the runtimeTypesIntersect check, which is currently O(n^2), and could be O(n) if allImplementations used a Set. But maybe do that when we have an example query where it is very hot?

goto-bus-stop avatar Jul 01 '24 07:07 goto-bus-stop