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

bluetoothbot · bluetoothbot · commit a4e0bdc65362 · 2026-05-26T17:20:54.000Z
ServiceRegistry's per-type and per-server indices were stored as
list[str], so each list.remove(...) call in _remove was an O(n)
linear scan. Bulk async_remove of N services sharing a type or
server therefore degraded to O(N**2) &mdash; visible at shutdown for
deployments with many entries under one _type._tcp.local.

Switch the value type to dict[str, None], which preserves insertion
order (so async_get_infos_type / async_get_infos_server still return
entries in registration order) while giving O(1) add and remove.

Also delete empty buckets once their last entry is removed so that
long-lived Zeroconf instances with churning type / server names
don't leak dict keys.
diff --git a/src/zeroconf/_services/registry.pxd b/src/zeroconf/_services/registry.pxd
@@ -12,15 +12,19 @@ cdef class ServiceRegistry:
     cdef public bint has_entries
 
     @cython.locals(
-        record_list=cython.list,
+        record_keys=cython.dict,
     )
     cdef cython.list _async_get_by_index(self, cython.dict records, str key)
 
     cdef _add(self, ServiceInfo info)
 
     @cython.locals(
         info=ServiceInfo,
-        old_service_info=ServiceInfo
+        old_service_info=ServiceInfo,
+        type_bucket=cython.dict,
+        server_bucket=cython.dict,
+        type_key=str,
+        server_key=str,
     )
     cdef _remove(self, cython.list infos)
 
diff --git a/src/zeroconf/_services/registry.py b/src/zeroconf/_services/registry.py
@@ -42,8 +42,8 @@ def __init__(
     ) -> None:
         """Create the ServiceRegistry class."""
         self._services: dict[str, ServiceInfo] = {}
-        self.types: dict[str, list] = {}
-        self.servers: dict[str, list] = {}
+        self.types: dict[str, dict[str, None]] = {}
+        self.servers: dict[str, dict[str, None]] = {}
         self.has_entries: bool = False
 
     def async_add(self, info: ServiceInfo) -> None:
@@ -79,12 +79,12 @@ def async_get_infos_server(self, server: str) -> list[ServiceInfo]:
         """Return all ServiceInfo matching server."""
         return self._async_get_by_index(self.servers, server)
 
-    def _async_get_by_index(self, records: dict[str, list], key: _str) -> list[ServiceInfo]:
+    def _async_get_by_index(self, records: dict[str, dict[str, None]], key: _str) -> list[ServiceInfo]:
         """Return all ServiceInfo matching the index."""
-        record_list = records.get(key)
-        if record_list is None:
+        record_keys = records.get(key)
+        if record_keys is None:
             return []
-        return [self._services[name] for name in record_list]
+        return [self._services[name] for name in record_keys]
 
     def _add(self, info: ServiceInfo) -> None:
         """Add a new service under the lock."""
@@ -94,8 +94,11 @@ def _add(self, info: ServiceInfo) -> None:
 
         info.async_clear_cache()
         self._services[info.key] = info
-        self.types.setdefault(info.type.lower(), []).append(info.key)
-        self.servers.setdefault(info.server_key, []).append(info.key)
+        # dict[str, None] gives O(1) add/remove while preserving insertion order
+        # so async_get_infos_type / async_get_infos_server return entries in the
+        # order they were registered.
+        self.types.setdefault(info.type.lower(), {})[info.key] = None
+        self.servers.setdefault(info.server_key, {})[info.key] = None
         self.has_entries = True
 
     def _remove(self, infos: list[ServiceInfo]) -> None:
@@ -105,8 +108,16 @@ def _remove(self, infos: list[ServiceInfo]) -> None:
             if old_service_info is None:
                 continue
             assert old_service_info.server_key is not None
-            self.types[old_service_info.type.lower()].remove(info.key)
-            self.servers[old_service_info.server_key].remove(info.key)
+            type_key = old_service_info.type.lower()
+            server_key = old_service_info.server_key
+            type_bucket = self.types[type_key]
+            del type_bucket[info.key]
+            if not type_bucket:
+                del self.types[type_key]
+            server_bucket = self.servers[server_key]
+            del server_bucket[info.key]
+            if not server_bucket:
+                del self.servers[server_key]
             del self._services[info.key]
 
         self.has_entries = bool(self._services)
