rustdoc sidebar duplicate-anchor de-duplication appears to be quadratic #158174

cat > rustdoc_sidebar_deref_repro.py <<'PY'
#!/usr/bin/env python3
import os
import shutil
import subprocess
import time
from pathlib import Path

N = int(os.environ.get("N", "1600"))
RUSTDOC = os.environ.get("RUSTDOC", "rustdoc")


def write_deref_chain(path: Path) -> None:
    with path.open("w", encoding="ascii") as f:
        f.write("pub struct S0;\n")
        for i in range(1, N + 1):
            f.write(f"pub struct S{i};\n")
        for i in range(1, N + 1):
            f.write(f"impl S{i} {{ pub fn foo(&self) {{}} }}\n")
        for i in range(N):
            j = i + 1
            f.write(
                f"impl std::ops::Deref for S{i} {{ "
                f"type Target = S{j}; "
                f"fn deref(&self) -> &S{j} {{ static V: S{j} = S{j}; &V }} "
                "}\n"
            )


src = Path(f"sidebar_deref_{N}.rs")
write_deref_chain(src)
out = Path(f"rustdoc_sidebar_{N}")
if out.exists():
    shutil.rmtree(out)

start = time.perf_counter()
subprocess.run([RUSTDOC, str(src), "--crate-name", "sidebarpoc", "-o", str(out)], check=True)
seconds = time.perf_counter() - start
print(f"deref_depth={N} elapsed={seconds:.3f}s source={src.stat().st_size}")
PY

RUSTDOC=/path/to/rustdoc N=1600 python3 rustdoc_sidebar_deref_repro.py