[reconciler] Mark moved fibers with placement flag granularly and cache host sibling lookups during commit#33048

<!-- Thanks for submitting a pull request! We appreciate you spending the time to work on these changes. Please provide enough information so that others can review your pull request. The three fields below are mandatory. Before submitting a pull request, please make sure the following is done: 1. Fork [the repository](https://github.com/facebook/react) and create your branch from `main`. 2. Run `yarn` in the repository root. 3. If you've fixed a bug or added code that should be tested, add tests! 4. Ensure the test suite passes (`yarn test`). Tip: `yarn test --watch TestName` is helpful in development. 5. Run `yarn test --prod` to test in the production environment. It supports the same options as `yarn test`. 6. If you need a debugger, run `yarn test --debug --watch TestName`, open `chrome://inspect`, and press "Inspect". 7. Format your code with [prettier](https://github.com/prettier/prettier) (`yarn prettier`). 8. Make sure your code lints (`yarn lint`). Tip: `yarn linc` to only check changed files. 9. Run the [Flow](https://flowtype.org/) type checks (`yarn flow`). 10. If you haven't already, complete the CLA. Learn more about contributing: https://reactjs.org/docs/how-to-contribute.html --> ## Summary This PR includes 2 small optimizations: - **Render phase:** Mark updated moved fibers with `Placement` flag granularly by computing the longest increasing subsequence (LIS) of their old indices and finding out which fibers are not in LIS. - **Commit phase:** Cache host sibling lookups per parent to avoid repeated tree traversals on consecutive inserts. ### Results Here are the [js-framework-benchmark](https://github.com/krausest/js-framework-benchmark) results comparing `react-hooks-placement-opt` vs `react-hooks` built locally against the vanilla JS implementation. The lower score is better. This table shows significant benchmark score improvements in `swap rows` and `create many rows`. While I understand that these two metrics are edge cases and are specifically designed to stress the implementation, I still wanted to present my findings because the code changes turned out to be relatively minor. My main goal was to get familiar with some of the codebase while doing a fun project, however, if there is interest I am happy to get this over the finish line. <img width="313" alt="test-results" src="https://github.com/user-attachments/assets/573eac8e-66f8-4f63-97f5-49e992dfa269" /> <!-- Explain the **motivation** for making this change. What existing problem does the pull request solve? --> ### Motivation I was looking at `reconcileChildrenArray` function in react-reconciler and found something that made me curious. Suppose we have a list of nodes: ``` [A, B, C, D, E, F, G] ``` That got re-arranged in the following way: ``` [A, F (moved), B, C, D, E, G] ``` Ideally, only `F` should be marked as moved (Placement flag). However, the reconciler outputs this: ``` [A, F (moved), B (moved), C (moved), D (moved), E (moved), G] ``` Only `A` and `G` remain in place. I found this interesting and dug further because I had an assumption that React would try to derive the least amount of dom operations needed. It seemed to me as if there was a code complexity tradeoff being made and I was curious if there was a way to make it granular while maintaining runtime performance. This behavior comes from the `placeChild` helper: ```ts function placeChild( newFiber: Fiber, lastPlacedIndex: number, newIndex: number, ): number { ... const current = newFiber.alternate; if (current !== null) { const oldIndex = current.index; if (oldIndex < lastPlacedIndex) { // This is a move. newFiber.flags |= Placement | PlacementDEV; return lastPlacedIndex; } else { // This item can stay in place. return oldIndex; } ... } ``` The above results in more work in `commitPlacement`, where for every "placed" node it will look up the closest "non-placed" stable sibling with dom (in `getHostSibling`) and insert each node before it. In our example for each "placed" node (F, B, C, D, E) React will traverse the fiber tree to lookup `G` repeatedly and call `insertBefore` to place it before `G`. This is how this would look like in the browser when only one item is moved back:  The fact that `getHostSibling` was constantly looking up stable host nodes and had to go past pending inserts also led me to consider that it could be cached to prevent potential deep traversals that result in the same output. For example, if one was rendering a table and then populated the table rows, for each row in this table `getHostSibling` will be called and traverse the entire list of siblings in front but return `null` each time. ### Proposed improvements **Granular placement of updated fiber nodes** It's possible to derive the maximum number of updated nodes that can stay in place by looking at their indices in the old list and identifying which ones do not belong to the longest increasing subsequence when laid out in the new list order. An increasing subsequence of old indices in this case means those elements maintained their relative order. If we look again at the previous example: ``` [A, B, C, D, E, F, G] -> [A, F (moved), B, C, D, E, G] ``` And take the old indices (alternate indices) of all updated nodes in the previous list: ``` [0 (A), 5 (F), 1 (B), 2 (C), 3 (D), 4 (E), 6 (G)] ``` After we find the LIS it results in the following indices: ``` [0 (A), 1 (B), 2 (C), 3 (D), 4 (E), 6 (G)] ``` Indices not in LIS: ``` [5 (F)] - this node was moved ``` We can proceed to mark `F` with the Placement flag and all other updated nodes can remain in place. **Finding nodes not in LIS:** The LIS is computed using a greedy patience sort, conceptually it can be visualized like this: <img width="438" alt="Screenshot 2025-04-19 at 6 47 09 PM" src="https://github.com/user-attachments/assets/92ae2065-2387-4033-a90f-865146f6dbf5" /> Slide from [here](https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf). The time complexity is `O(n)` in the case of all numbers increasing or decreasing (the most common cases) and O(N log N) in the case of completely random reordering of all nodes in the list. The algorithm in this PR is modified to fit the exact use case of finding which entry is not in LIS. **Caching of `getHostSibling`** Let's say we have a list that originally did not have any rows and then rendered the following: ``` <List> <Row key='A' value='A'> <Row key='B' value='B'> <Row key='C' value='C'> <Row key='D' value='D'> <Row key='E' value='E'> <List> ``` When committing row placement the current implementation will: - Look at `A` and start searching for the next sibling that `A` can be placed before - Eventually traverse the entire list resulting in `null` (all nodes are new). If we maintain a cache per parent node (in this case `List`), we can keep track of the last node that was placed and what `stateNode` it was placed before. Then when processing `B` in `commitPlacement` we can: - Reference the cache by parent (`return`) - Find out that the last placed node was `A` and that it was placed before `null` (end of list). - We verify that `A` is our direct previous sibling, and skip doing the traversal because we know it would result in the same host sibling. ## How did you test this change? 1. Ran the existing test suite 3. Ran the `js-framework-benchmark` on the modified version of React without issues 4. Introduced a test to verify reordering still works as expected in both regular and iterator versions of `reconcileChildrenArray` 5. Added a test for a helper that computes what is not in LIS <!-- Demonstrate the code is solid. Example: The exact commands you ran and their output, screenshots / videos if the pull request changes the user interface. How exactly did you verify that your PR solves the issue you wanted to solve? If you leave this empty, your PR will very likely be closed. -->