Optimization of tree structure flattening

Optimization of Tree Structure Flattening

In Vue 3's reactivity system, the flattening optimization of tree structures is a key design. This optimization significantly improves performance by converting nested dependency relationships into a flat structure. The core idea lies in reducing the overhead caused by recursion while maintaining the accuracy of dependency tracking.

Issues with Tree Structures in Reactivity Systems

In Vue 2's implementation, dependency collection is organized as a tree structure. Each reactive object creates a corresponding Dep instance, forming parent-child relationships:

// Vue2-style dependency tree
parent: {
  deps: [child1, child2],
  subs: [watcherA]
}
child1: {
  deps: [grandChild],
  subs: [watcherB]
}

This structure leads to:

1. High performance cost due to deep recursive traversal
2. Complex dependency relationship maintenance
3. Linear increase in memory usage with nesting depth

Principles of Flattening Design

Vue 3 introduces an optimization that flattens the tree structure, using a global targetMap to store all dependency relationships:

// Vue 3's flattened storage structure
const targetMap = new WeakMap()
targetMap.set(target, {
  key1: new Set(effect1, effect2),
  key2: new Set(effect3)
})

Key implementation features:

1. Uses WeakMap as the root container, with keys as raw objects
2. Each property corresponds to a Set storing related effects
3. Completely eliminates explicit parent-child dependency relationships

Implementation Details Analysis

In packages/reactivity/src/effect.ts, the key code is as follows:

// Dependency tracking entry
export function track(target: object, type: TrackOpTypes, key: unknown) {
  let depsMap = targetMap.get(target)
  if (!depsMap) {
    targetMap.set(target, (depsMap = new Map()))
  }
  let dep = depsMap.get(key)
  if (!dep) {
    depsMap.set(key, (dep = new Set()))
  }
  dep.add(activeEffect)
}

This design offers three significant advantages:

1. Reduces query time complexity from O(n) to O(1)
2. More stable memory usage, unaffected by nesting depth
3. Higher GC efficiency, with WeakMap automatically handling object cleanup

Synergy with Virtual DOM Optimization

The flattening design also synergizes with the optimization strategies of the virtual DOM. During the patching process:

// Component update flow
function patchComponent(n1, n2) {
  const instance = n2.component = n1.component
  // Flattened props comparison
  if (hasPropsChanged(instance.props, n2.props)) {
    updateComponent(instance)
  }
}

The comparison algorithm directly retrieves changes from the flat structure without recursively comparing the entire props tree.

Performance Comparison Tests

Benchmark tests comparing the performance differences between the two structures:

Handling Special Scenarios

For circular reference scenarios, Vue 3 uses ReactiveFlags markers:

export const enum ReactiveFlags {
  SKIP = '__v_skip',
  IS_REACTIVE = '__v_isReactive',
  RAW = '__v_raw'
}

function createReactiveObject(target) {
  if (target[ReactiveFlags.IS_REACTIVE]) {
    return target
  }
  // ...other processing
}

This mechanism ensures that even with circular references, infinite recursion is avoided.

Comparison with React

React's latest context implementation also adopts similar optimizations:

// React Context implementation
const contextMap = new WeakMap()
function readContext(Context) {
  const dependencies = contextMap.get(Context)
  return dependencies.current
}

However, Vue 3's unique aspects include:

1. Granularity down to the property level
2. Automatic dependency collection
3. Deep integration with the rendering system

Developer Tools Integration

The flattened structure also optimizes devtools display. In packages/reactivity/src/debug.ts:

export function debugTarget(target) {
  const depsMap = targetMap.get(target)
  return Array.from(depsMap?.entries() || [])
    .flatMap(([key, deps]) => 
      Array.from(deps).map(dep => ({ key, effect: dep }))
}

This transformation allows complex dependency relationships to be displayed as a flat list.

Compile-Time Optimization Coordination

The template compiler also generates optimized code:

// Before compilation
<template>
  <div>{{ user.info.name }}</div>
</template>

// After compilation
function render() {
  return _ctx.user.info.name
}
// After optimization
function render() {
  // Direct binding to the final property
  return _cache[0] || (_cache[0] = _ctx.user.info.name)
}

Memory Management Strategy

The use of WeakMap enables intelligent memory reclamation:

// Example of reactive object cleanup
let obj = reactive({ foo: 'bar' })
const handle = effect(() => {
  console.log(obj.foo)
})
// When obj=null, the corresponding entry in targetMap is automatically cleared

This mechanism is particularly suitable for large single-page applications.

Special Optimization for Array Handling

For array operations, Vue 3 implements dual optimizations:

const arrayInstrumentations = {
  includes() { /*...*/ },
  indexOf() { /*...*/ },
  push() {
    // Flattened tracking
    track(this, 'push')
    return Array.prototype.push.apply(this, arguments)
  }
}

Extended Impact on Reactive APIs

This design influences the entire Composition API implementation:

function useFeature() {
  const state = reactive({ x: 0 })
  // Each composition function is an independent flat unit
  return {
    state,
    increment: () => state.x++
  }
}

TypeScript Type System Adaptation

Type definitions also reflect this flattening:

interface TargetMap {
  get(target: object): Map<any, Set<ReactiveEffect>> | undefined
  set(target: object, depsMap: Map<any, Set<ReactiveEffect>>): void
}

Server-Side Rendering Optimization

In SSR environments, the flattened structure reduces serialization costs:

// State extraction during server-side rendering
export function serializeState(instance) {
  return Array.from(targetMap.get(instance.proxy) || [])
    .map(([key]) => [key, instance.proxy[key]])
}

Custom Renderer Support

Custom renderers can leverage the same reactivity system:

function createRenderer(options) {
  return {
    createApp: createAppAPI((...args) => {
      // Shared targetMap structure
      const effect = new ReactiveEffect(...)
    })
  }
}

Reactive Debugging Tools

Debugging utility functions are provided in development mode:

import { debugTarget } from 'vue'

const obj = reactive({ foo: 'bar' })
effect(() => console.log(obj.foo))

// View all dependencies
console.log(debugTarget(obj))
// Output: [{ key: 'foo', effect: [...] }]