# pre-0001: cache_policies.py Inputs.exclude list O(N×M) membership in task cache hot path

**Severity:** HIGH
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test in hot loop)
**Speedup:** ~Mx at M=50 exclude keys (verified by unit test)
**Target:** Prefect (PrefectHQ/prefect)
**Files:**
- `src/prefect/cache_policies.py:364` — `Inputs.exclude: list[str]` field definition
- `src/prefect/cache_policies.py:380-381` — `compute_key()`: list membership inside task input loop

## Description

`Inputs.compute_key()` is called on every cached task invocation to compute the
cache key from task inputs. It filters out excluded keys using a plain list:

```python
# cache_policies.py:364
exclude: list[str] = field(default_factory=lambda: [])

# cache_policies.py:373-383
def compute_key(self, task_ctx, inputs, flow_parameters, **kwargs):
    hashed_inputs = {}
    exclude = self.exclude or []       # plain list
    for key, val in inputs.items():   # O(N) outer loop over task inputs
        if key not in exclude:         # O(M) linear scan — O(N×M) total
            ...
    return hash_objects(hashed_inputs)
```

With N task input parameters and M excluded keys, `compute_key()` performs O(N×M)
comparisons per task invocation. For workflows with many task inputs (N=100) and
many exclusions (M=50), this is 5,000 comparisons per cache key computation instead
of 100.

`compute_key()` is on the direct invocation hot path for every cached task call —
not a setup-time cost. This degrades throughput for high-throughput cached task
workflows.

The `Inputs` class is also used via `CachePolicy.__sub__` and `__add__`, which
compose `exclude` lists via concatenation (`self.exclude + [other]`), meaning
exclusion lists can grow with each policy composition.

## Root Cause

`exclude` is typed as `list[str]` (line 364) and stored as a list. Converting to
a `frozenset[str]` at `compute_key()` entry time (or at construction time) gives
O(1) average membership test per key with no semantic change, since exclusion is
order-independent.

## Patch

See `patch/pre-0001-cache-policies-exclude-list.patch`

## Complexity Before

`key not in exclude` (list): **O(M)**
Total per `compute_key()` call: **O(N×M)**

## Complexity After

`key not in exclude_set` (frozenset): **O(1)** average
Total per `compute_key()` call: **O(N)**

## Reproduction

```
cd defects/prefect/unit && javac -d . PrefectTest.java && java -ea unit.PrefectTest
```
