Optimize anchorset and flex tree traversal #22717
Conversation
github-actions
bot
added
area: dds
| * @param index - index being looked for. | ||
| * @returns child with the requested parentIndex, or undefined. | ||
| */ | ||
| function binaryFind(sorted: readonly PathNode[], index: number): PathNode | undefined { |
There was a problem hiding this comment.
does this function really not exist anywhere else in our codebase??
There was a problem hiding this comment.
(a parameterized binary search, I mean...obiously there are pathnode specifics in here)
There was a problem hiding this comment.
I started with a more generic binary search which returned the index, but this was so dominated by small data sizes (0 and 1 are the common array sizes here) that it had a lot of overhead (forces an extra array lookup, key extraction or comparison callback, JS lacks a 3 way compare operator so thats annoying etc). I did find another binary search implementation, but it was not exposed in a generically useful way either.
I have added a comment about this.
| * Gets a child if it exists. | ||
| * Does NOT add a ref. | ||
| */ | ||
| tryGetChild(key: FieldKey, index: number): AnchorNode | undefined; |
There was a problem hiding this comment.
it's a bit odd that child (which isn't named getChild?) returns an UpPath, and tryGetChild returns an AnchorNode. perhaps some naming cleanup could be done here for clarity?
There was a problem hiding this comment.
I think this makes sense (though I'm biased as I wrote it). child, as a noun named thing, has to be low cost and without side-effects, so it returns the a path to the child, which is the child if there is already an AnchorNode for it. It could be renamed to getChild, but in my opinion thats more verbose, and less informative, since it loses some of the low-cost connotation when adding get.
tryGetChild is the 'try' version of that, but try needs a verb form, so we have tryGet, which returns the child AnchorNode if it exists, without forcing one to exist.
We then have getOrCreateChild, which unconditionally returns an AnchorNode.
While I think that all makes since, you are right its a bit inconsistent due to the "get" being force on the "try" version for mostly grammatical reasons. Perhaps childIfAnchored would be a better name for it as it keeps the noun structure? I have done that rename.
⯅ @fluid-example/bundle-size-tests: +1.24 KB
Baseline commit: a9c881f |
## Description Optimizations based on a profile of BubbleBench. This resulted in about 5% more bubbles (80 vs 76). Given this application's read costs scale with bubbles squared (for the collision logic), contains writes, and most reads are leaf values which are not impacted by this, this seems like a pretty good win. Some real apps could probably show significantly larger gains if they are less leaf heavy or less write heavy.
Description
Optimizations based on a profile of BubbleBench.
This resulted in about 5% more bubbles (80 vs 76).
Given this application's read costs scale with bubbles squared (for the collision logic), contains writes, and most reads are leaf values which are not impacted by this, this seems like a pretty good win. Some real apps could probably show significantly larger gains if they are less leaf heavy or less write heavy.
Reviewer Guidance
The review process is outlined on this wiki page.