refactor(watch deep): use bfs instead of dfs #13433
Conversation
WalkthroughThe Changes
Poem
✨ Finishing Touches
Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. 🪧 TipsChatThere are 3 ways to chat with CodeRabbit:
SupportNeed help? Create a ticket on our support page for assistance with any issues or questions. Note: Be mindful of the bot's finite context window. It's strongly recommended to break down tasks such as reading entire modules into smaller chunks. For a focused discussion, use review comments to chat about specific files and their changes, instead of using the PR comments. CodeRabbit Commands (Invoked using PR comments)
Other keywords and placeholders
CodeRabbit Configuration File (
|
There was a problem hiding this comment.
Actionable comments posted: 0
🧹 Nitpick comments (1)
packages/reactivity/src/watch.ts (1)
346-348: Consider performance implications ofqueue.shift().Using
queue.shift()for dequeuing has O(n) time complexity in JavaScript arrays. For deeply nested objects with many siblings at each level, this could impact performance significantly.Consider using a more efficient queue implementation:
- const queue: Array<[any, number]> = [] + const queue: Array<[any, number]> = [] + let queueIndex = 0 // ... initialization code ... - while (queue.length > 0) { - const [currentValue, currentDepth] = queue.shift()! + while (queueIndex < queue.length) { + const [currentValue, currentDepth] = queue[queueIndex++]This eliminates the O(n) shift operation while maintaining the same FIFO behavior.
📜 Review details
Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro
📒 Files selected for processing (1)
packages/reactivity/src/watch.ts(1 hunks)
⏰ Context from checks skipped due to timeout of 90000ms (3)
- GitHub Check: Redirect rules
- GitHub Check: Header rules
- GitHub Check: Pages changed
🔇 Additional comments (5)
packages/reactivity/src/watch.ts (5)
336-344: LGTM: Solid initialization and early return logic.The initialization correctly handles the
seenparameter for backward compatibility and implements proper early returns for non-traversable values.
361-366: LGTM: Proper cycle detection implementation.The seen set check correctly prevents infinite loops with circular references, and adding to the seen set at the right time maintains the same semantics as the original recursive implementation.
372-391: Excellent comprehensive child enumeration logic.The implementation correctly handles all supported object types (refs, arrays, sets, maps, plain objects) and properly includes enumerable symbol properties. The depth propagation logic is sound.
331-395: Successful refactoring that achieves the stated objectives.This BFS implementation effectively addresses the original concerns:
- ✅ Eliminates stack overflow risk for deeply nested objects
- ✅ Maintains identical traversal semantics
- ✅ Preserves function signature for backward compatibility
- ✅ Includes clear, documented logic flow
The refactoring successfully transforms a recursive DFS approach into an iterative BFS approach while maintaining all the original functionality. The only minor consideration is the
queue.shift()performance, but this is acceptable for typical use cases.
352-358:✅ Verification successful
Verify depth handling correctness for edge cases.
The depth check logic appears correct, but let's ensure it handles the edge case where
currentDepth === 0properly.
🏁 Script executed:
#!/bin/bash # Description: Verify that the traverse function is used correctly in the codebase and check for any existing tests # Expected: Find usages and tests that validate depth behavior # Search for traverse function usage rg -A 5 'traverse\(' --type ts # Look for existing tests fd -e spec.ts -e test.ts | xargs rg -l 'traverse'Length of output: 2078
🏁 Script executed:
#!/bin/bash # Show traverse implementation context rg -C 20 -n "export function traverse" packages/reactivity/src/watch.ts # Show usages of traverse with explicit depth rg -C 10 -n "traverse(source" packages/reactivity/src/watch.tsLength of output: 1429
🏁 Script executed:
#!/bin/bash # Extract the full traverse function for detailed review sed -n '331,430p' packages/reactivity/src/watch.tsLength of output: 2046
Depth checks for zero-depth cases are correctly handled
The early‐return
if (depth <= 0 …) return valueensures that callingtraverse(obj, 0)skips all property reads, and the in‐loop guardif (currentDepth <= 0 …) continueprevents exploring children once their depth counter hits zero. No changes needed here.
| @@ -333,35 +333,63 @@ export function traverse( | |||
| depth: number = Infinity, | |||
| seen?: Set<unknown>, | |||
There was a problem hiding this comment.
It seems that seen is no longer needed here.
| queue.push([value, depth]) | ||
|
|
||
| while (queue.length > 0) { | ||
| const [currentValue, currentDepth] = queue.shift()! |
There was a problem hiding this comment.
The time complexity of queue.shift() is O(n), so it can be optimized by tracking the index manually:
const queue: Array<[any, number]> = []
let queueIndex = 0
const [currentValue, currentDepth] = queue[queueIndex++]|
see https://github.com/vuejs/core/blob/main/.github/contributing.md
Thanks for your contribution. Could you provide a benchmark? |
| const activeSeen = seen || new Set() | ||
| const queue: Array<[any, number]> = [] |
There was a problem hiding this comment.
Shouldn't they be declared after the check line 338?
Currently they use memory even if they don't have any use
Also it could be nice to directly add value and depth when declaring for performance
There was a problem hiding this comment.
yes , you are right。 I will move these two lines to the bottom
|
I know the Playground isn't a particularly reliable way to do benchmarks, but from a quick bit of experimenting it looks like this PR may have a significantly adverse affect on performance: Maybe that can be improved with further tweaks, but I suspect the data structures required to implement a BFS may place limits on how fast it can be. |
|
Thank you for your reply. I tried these two demos. What you said is right. I investigated the reason because the Array.shift method was constantly used in my code. This is a waste of performance. I modified it and tested it. The performances of the two were about the same. So I think the improvement in performance brought by this pr is not obvious. |
Thank you for your reply. After the benchmark test. The performance before and after the modification is almost the same, and it belongs to extreme scenarios. So I think the improvement in performance brought by this pr is not obvious. |
|
see benchmark
|
|
@jsy-0526 Please push your latest changes to the PR so we can see them. |
hi, I have refactored the deep implementation logic of the watch api in reactivity. Previously, deep matching was carried out using the dfs method. But this will have the following problems.
Summary by CodeRabbit