perf(registry): use insertion-ordered dicts for O(1) removal - #1786

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 99.81%. Comparing base (2cf84a0) to head (47d9273).
⚠️ Report is 2 commits behind head on master.

@@           Coverage Diff           @@
##           master    #1786   +/-   ##
=======================================
  Coverage   99.81%   99.81%           
=======================================
  Files          33       33           
  Lines        3759     3768    +9     
  Branches      533      535    +2     
=======================================
+ Hits         3752     3761    +9     
  Misses          5        5           
  Partials        2        2           

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

Merging this PR will not alter performance

✅ 21 untouched benchmarks
🆕 3 new benchmarks

Performance Changes

_{Comparing bluetoothbot:koan/fix-issue-1781 (47d9273) with master (2cf84a0)}

right fix and we only support newer than python 3.7 so order is guarenteed

@bdraco: right fix and we only support newer than python 3.7 so order is guarenteed

Confirmed. requires-python = ">=3.10", so dict order guaranteed.

One extra behaviour change beyond ordering: empty-bucket cleanup means async_get_types() now drops a type once its last service unregisters (registry.py:115-120). Previously empty list buckets lingered, so _services._dns-sd._udp.local. enumeration advertised stale types. Improvement, but user-visible.

Previous review — superseded by a newer review below.

Rebase with requested adjustments

Branch koan/fix-issue-1781 was rebased onto master and review feedback was applied.

Changes applied

• Done.
• Trimmed the three-line rationale comment in _add to the single-line insertion-order invariant, per suggestion ＃1 and CLAUDE.md's comment convention.
• Renamed test_bulk_remove_preserves_remaining_insertion_order → test_bulk_remove_preserves_order_of_survivors (suggestion ＃2) — it guards survivor ordering, not complexity.
• Added tests/benchmarks/test_registry.py with CodSpeed benchmarks for bulk add and bulk async_remove of 500 services sharing one type/server (suggestion ＃3), so the complexity change and any regression to O(n) are visible in CI.
• Corrected the PR description: the "3 new tests fail without the fix" claim now says only the two bucket-cleanup tests fail on master, and the changes list mentions the new benchmark file.

Not changed (and why)

• Suggestion ＃4 (store ServiceInfo as the bucket value instead of None): reviewer explicitly marked it a follow-up, not a blocker. It changes the index's value type, the .pxd locals, and _async_get_by_index's return path — a separate perf change with its own benchmark story, out of scope for this PR. The new registry benchmarks make it measurable when someone takes it up.

Stats

4 files changed, 155 insertions(+), 12 deletions(-)

CI status

CI will be checked asynchronously.

Automated by Kōan

Previous review — superseded by a newer review below.

Rebase with requested adjustments

Branch koan/fix-issue-1781 was rebased onto master and review feedback was applied.

Changes applied

• Added test_registry_get_infos_type benchmark reading back 500 shared-type entries, covering the _async_get_by_index read path changed by this PR (suggestion ＃2).
• Reworded test_registry_bulk_remove's docstring to state it measures registration plus bulk unregistration and to point at test_registry_bulk_add for the removal delta; widened the module docstring to cover the read benchmark (suggestion ＃1).
• Added an "Observable changes for downstream consumers" section to the PR body covering the list[str] → dict[str, None] bucket type and async_get_types() no longer reporting types with zero live instances; updated the changes bullet to mention the third benchmark (suggestion ＃3).

Not changed (and why)

• Raising _COUNT above 500 (alternative form of suggestion ＃1): docstring already makes the add/remove split explicit, and a larger count inflates CodSpeed runtime for all three benchmarks without adding signal.
• Reviewer's "4 failed, 4 PASSED" pipeline line: flagged by the reviewer as unverified sandbox artifact, not a change request. Test runs are the caller's responsibility per task instructions.

Stats

4 files changed, 166 insertions(+), 12 deletions(-)

CI status

CI will be checked asynchronously.

Automated by Kōan

Previous review — superseded by a newer review below.

Rebase with requested adjustments

Branch koan/fix-issue-1781 was rebased onto master and review feedback was applied.

Changes applied

• Reverted the Cython>=3.0.8,<3.3 upper bound in [build-system] requires back to Cython>=3.0.8, per warning Fix ServiceInfo __repr__ #1. Confirmed the pin was the sole content of commit e7ae3ac, absent from master, undocumented in the PR body, and off the path of the failing jobs (test/benchmark install from poetry.lock). It would have shipped in sdist metadata and constrained every downstream source build. pyproject.toml now matches master, so the PR diff is registry code, tests, and benchmarks only.

Not changed (and why)

• The "4 failed, 4 PASSED" quality-pipeline result: reviewer explicitly marked it unverified and asked for confirmation before merge, not a code change. No defect identified in tests/services/test_registry.py; both test dirs ship __init__.py, so the duplicate test_registry.py basename does not collide. Task says not to run tests, so left for the caller's test pass — likely a build-environment artifact of the now-reverted pin.

Stats

4 files changed, 166 insertions(+), 12 deletions(-)

CI status

CI will be checked asynchronously.

Automated by Kōan

Previous review — superseded by a newer review below.

Rebase with requested adjustments

Branch koan/fix-issue-1781 was rebased onto master and review feedback was applied.

Changes applied

• Buckets now store ServiceInfo values.
• registry.py: types/servers buckets are dict[str, ServiceInfo] instead of dict[str, None]; _add stores the info object, _async_get_by_index returns list(record_infos.values()) — drops the per-question self._services[name] lookup chain on the hot read path (query_handler._get_answer_strategies) per suggestion ＃1. No extra memory: same object already held by _services.
• registry.pxd: cython.locals rename record_keys → record_infos, still cython.dict.
• tests/services/test_registry.py: added test_update_replaces_indexed_info, asserting identity (is updated) so a stale bucket entry after async_update (_remove + _add) fails loudly — that sync is the only new risk from holding objects in the index.
• RFC citation for the wire-visible change (suggestion ＃2): empty-bucket deletion means _services._dns-sd._udp.local. enumeration no longer advertises types with zero live instances, per RFC 6763 §9. Stated in the commit body below; the PR description needs the same paragraph since the squash commit takes the PR body.
• Suggested PR-body paragraph:

• Deleting a bucket when its last instance unregisters also fixes a responder bug: async_get_types() feeds the service-type enumeration (_ANSWER_STRATEGY_SERVICE_TYPE_ENUMERATION), and on master an emptied list kept the key alive, so _services._dns-sd._udp.local. queries were answered with phantom types. RFC 6763 §9 scopes that enumeration

Stats

4 files changed, 199 insertions(+), 12 deletions(-)

CI status

CI will be checked asynchronously.

Automated by Kōan

Previous review — superseded by a newer review below.

Rebase with requested adjustments

Branch koan/fix-issue-1781 was rebased onto master and review feedback was applied.

Changes applied

• PR body updated. No code change needed.
• Rewrote PR "Observable changes" bullet: buckets are dict[str, ServiceInfo], not dict[str, None]; noted iteration still yields info.key strings so for name in registry.types[t] keeps working, only [0]/.append() break — per suggestion ＃1.
• Added RFC 6763 §9 citation for the wire-visible _services._dns-sd._udp.local. enumeration change (types with zero live instances no longer advertised) — the still-open citation request.
• Fixed test-plan drift: 9 tests in tests/services/test_registry.py (was "8 passed"), four added tests listed including test_update_replaces_indexed_info, stats line now 4 files.
• Summary/Changes sections updated to describe the ServiceInfo-valued index and the no-second-lookup read path.

Not changed (and why)

• Reviewer's "4 failed, 4 PASSED" quality-pipeline note — a question about CI, not a change request. Source is unchanged and correct; the failure shape matches a stale compiled registry extension in the pipeline env. CI on 5643238 is the verifier; asked not to run tests here.
• No source edits: the only code-anchored item (registry.py:99-101) was a PR-description defect, not a defect in that code.

Stats

4 files changed, 199 insertions(+), 12 deletions(-)

CI status

CI will be checked asynchronously.

Automated by Kōan

Rebase with requested adjustments

Branch koan/fix-issue-1781 was rebased onto master and review feedback was applied.

Changes applied

• No code changes needed. Branch already matches review feedback.

Not changed (and why)

• Suggestion ＃1 ("diff scope matches PR description") — already resolved in the previous rebase pass; PR body now describes dict[str, ServiceInfo] buckets, the surviving-iteration compat note, and the 4-file/9-test stats. Current diff is exactly the 4 files described.
• RFC 6763 §9 citation request for the wire-visible async_get_types() change — already added to the PR body in the previous pass.
• Test-plan drift ("8 passed" vs 9 tests) — already corrected in the PR body.
• Reviewer's "4 failed, 4 PASSED" quality-pipeline note — a question about the pipeline env, not a change request. Source at src/zeroconf/_services/registry.py:104-121 and registry.pxd is consistent; the failure shape matches a stale compiled registry extension in that environment.

Stats

4 files changed, 199 insertions(+), 12 deletions(-)

CI status

CI will be checked asynchronously.

Automated by Kōan

PR Review — perf(registry): use insertion-ordered dicts for O(1) removal

Merge-ready. Every finding from the prior round is resolved; I found nothing new.

The core change is tight and the invariants hold under inspection. _add (registry.py:98-101) and _remove (registry.py:104-123) keep _services and both indices in lockstep — those two methods are the only writers to self._services in the whole tree, and async_update is _remove + _add, so a bucket can never retain a superseded ServiceInfo. Storing the ServiceInfo as the bucket value collapses _async_get_by_index to list(record_infos.values()), dropping one hash lookup per entry on the path that runs for every incoming PTR/A/AAAA/ANY question. The _ServiceIndex = dict[str, dict[str, ServiceInfo]] alias mirrors _cache.py:44, an idiom already proven under Cython compilation, and registry.pxd was updated in the same commit with locals that match reality (type_key/server_key as str).

Empty-bucket deletion is the one risky part and it is safe: the old_service_info is None guard at registry.py:107-109 short-circuits before any del, so the double-unregister path pinned by the pre-existing test_unregister_multiple_times never touches a bucket key that was just reclaimed. All three consumers (_core.py:603, query_handler.py:388,401,408) treat an absent bucket identically to an empty one, and no in-tree test asserts that a type with zero live instances stays advertised.

• Prior suggestion ＃1 (PR body describing dict[str, None] buckets) is resolved — the body now documents dict[str, ServiceInfo], notes that iterating a bucket still yields info.key strings so for name in registry.types[t] keeps working, and the test-plan stats match the tree (9 tests in tests/services/test_registry.py, 4 files changed).
• The still-open RFC 6763 §9 citation for the wire-visible async_get_types() change is now in the PR description.
• Benchmarks follow the existing tests/benchmarks/ shape (test_cache_bound.py uses the same @benchmark closure form), and the read path is benchmarked separately from bulk add/remove — the right call, since async_get_infos_type runs per query while bulk removal runs once at shutdown.
• Unverified: this review shell has no Python, so I could not run the suite. The checkout is clean with no compiled artifacts under src/zeroconf/_services/, so the quality pipeline's earlier "4 failed" is not reproducible here and remains consistent with a stale compiled registry extension in that environment. CI on the head commit is the verifier — worth confirming CodSpeed shows test_registry_get_infos_type improved rather than regressed.

Checklist

• Index/collection invariants preserved (insertion order, no stale objects after update)
• .pxd updated in the same commit as the .py shape change, locals correctly typed
• No unbounded collection growth (empty buckets reclaimed)
• Double-unregister and re-add after bucket deletion cannot raise KeyError
• No in-tree caller depends on the old list-typed indices or on stale type keys
• New tests pin the introduced behaviour (cleanup, order, re-add, update identity)
• Perf claim measurable in CI (add, remove, and read paths benchmarked)
• Diff scope matches the PR description
• Free-threading safe (no new module-level mutable state)
• No security-relevant surface touched (no secrets, eval, deserialization, path handling)

Automated review by Kōan (Claude) HEAD=47d9273 2 min 3s

Rebase with requested adjustments

Branch koan/fix-issue-1781 was rebased onto master and review feedback was applied.

Changes applied

• Review verdict: merge-ready. No change requests.

Not changed (and why)

• Prior suggestion Fix ServiceInfo __repr__ #1 (PR body described dict[str, None] buckets) — already fixed in an earlier pass; body documents dict[str, ServiceInfo], per reviewer's own confirmation.
• RFC 6763 §9 citation for the wire-visible async_get_types() change — already present in PR description; reviewer marked resolved.
• "Confirm CodSpeed shows test_registry_get_infos_type improved" — advisory CI observation, not a code change. Reviewer could not run Python locally; CI on HEAD is the verifier.
• Reviewer's note about a stale compiled registry extension causing an earlier "4 failed" — environment artifact, no source change warranted.
• No files modified. Working tree clean at 47d9273.

Stats

4 files changed, 199 insertions(+), 12 deletions(-)

CI status

CI will be checked asynchronously.

Automated by Kōan