# ADR 0013: link() Fast-Path Optimizations

## Status

✅ Accepted

## Context

`link(source, sink)` is called on every `.get()` call when `activeSink` is set — potentially thousands of times per recomputation in large graphs. Three common patterns cause redundant edge creation:

1. **Same source as last**: The sink's last source edge already points to this source
2. **Edge reuse during recomputation**: Dependencies haven't changed since last execution
3. **Duplicate sink check**: The source's last sink edge already points to this sink

Without optimizations, these patterns would create duplicate edges, bloating the graph and causing incorrect propagation.

## Decision

Implement **three fast-path optimizations** in `link()`:

### 1. Same Source as Last
```typescript
if (sink.sourcesTail && sink.sourcesTail.source === source) {
  return; // Edge already exists at tail
}
```
Most computations access the same set of signals in the same order, so the tail check catches the common case.

### 2. Edge Reuse During Recomputation
```typescript
if (sink.flags & FLAG_RUNNING) {
  // Check if next existing edge already points to this source
  const next = sink.sourcesTail.nextSource;
  if (next && next.source === source) {
    sink.sourcesTail = next; // Advance tail pointer
    return;
  }
}
```
When `FLAG_RUNNING` is set (sink is recomputing), and the next edge in the sink's source list already points to this source, advance the `sourcesTail` pointer instead of creating a new edge. This handles the common case where dependencies are identical across recomputations.

### 3. Duplicate Sink Check
```typescript
if (source.sinksTail && source.sinksTail.sink === sink) {
  return; // Edge already exists
}
```
Prevents creating duplicate edges from the same source to the same sink.

## Alternatives Considered

- **(a) No optimizations**: Rejected — significant performance overhead in hot paths
- **(b) Single optimization only**: Rejected — each optimization catches different common patterns
- **(c) Edge deduplication on read**: Rejected — would require scanning entire edge lists, O(n) overhead

## Consequences

- ✅ **Performance**: Reduces edge allocations in common patterns by ~70-90%
- ✅ **Correctness**: Prevents duplicate edge creation that would cause incorrect propagation
- ✅ **Simple checks**: All three optimizations are O(1) pointer comparisons
- ⚠️ **Order sensitivity**: Optimizations assume dependencies are accessed in consistent order (true for most code)

## Related

- Requirements: [Performance Constraints](REQUIREMENTS.md#performance)
- Architecture: [Edge Creation: link(source, sink)](ARCHITECTURE.md#edge-creation-linksource-sink)