# UNDF: UNDF-2026-000000593
# v8-0004: KnownMapsMerger::IntersectWithKnownNodeAspects std::find O(P×R) → O(P+R) merge

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | HIGH |
| Component   | `src/maglev/maglev-known-node-aspects.h:852` |
| Function    | `KnownMapsMerger::IntersectWithKnownNodeAspects` |
| Hot path    | Every `CheckMaps` node during Maglev compile — once per polymorphic call site per function |
| Status      | PATCHED (unit test PASS) |

## Defect

`KnownMapsMerger::IntersectWithKnownNodeAspects` intersects the `requested_maps_` set
against the maps known at a predecessor node. For each of P requested maps it calls
`std::find` over R already-seen maps — an O(P×R) inner product:

```cpp
// maglev-known-node-aspects.h:852
for (compiler::MapRef map : requested_maps_) {          // P maps
    if (std::find(known_maps.begin(),                   // O(R) linear scan
                  known_maps.end(), map) != known_maps.end()) {
        maps_found.push_back(map);
    }
}
```

The V8 team left an explicit acknowledgement in the same file:

```cpp
// TODO(v8:7700): Make intersection non-quadratic.
```

With P=8 requested maps and R=50 predecessor maps at a hot polymorphic call site:
**400 comparisons per node**, repeated for every `CheckMaps` node in every compiled
function. Maglev compiles frequently (OSR, tiered) — this appears on every warm-up.

## Fix

Convert `requested_maps_` from a `ZoneVector<MapRef>` to a sorted `ZoneRefSet<Map>`
(already used elsewhere in Maglev). Intersection becomes a sorted merge — O(P+R):

```cpp
// Replace inner std::find with set membership:
ZoneRefSet<Map> requested_set(requested_maps_.begin(), requested_maps_.end(), zone);

for (compiler::MapRef map : known_maps) {           // R maps, one pass
    if (requested_set.contains(map)) {              // O(log P) binary search
        maps_found.push_back(map);
    }
}
```

Or sort both sides once and merge in O(P+R) total.

Speedup: ~40× at P=8, R=50 (400 → 10 effective comparisons).
