java-topology/docs/tickets/pylons-0001-toposorter-names-list-membership.md

pylons-0001: TopologicalSorter.add() — O(N²) if name in self.names list scan

Severity: HIGH File: src/pyramid/util.py (Pyramid web framework, Pylons project) Line: 481 Status: PATCHED

Description

TopologicalSorter.add() maintains self.names as a plain list. Every call to add() performs if name in self.names — an O(N) linear scan. During Pyramid application startup the framework calls add() N times (once per tween, once per view deriver, once per predicate): total O(N²) scans.

The same self.names list is scanned again in sorted() at line 577:

for name in sorted_names:       # O(N) loop
    if name in self.names:      # O(N) list scan — CWE-407

That gives a second O(N²) pass on every call to sorted().

TopologicalSorter is used in four hot-path config callsites:

• config/tweens.py:166 — tween chain construction (every request lifecycle)
• config/views.py:117 — Accept header ordering
• config/views.py:1315,1405 — view deriver chain
• config/predicates.py:109 — predicate ordering

Root Cause

self.names = [] at line 432. Python list.__contains__ is O(N); there is no parallel set to give O(1) membership.

Fix

Maintain a parallel self.names_set = set() alongside self.names list.

• add() line 481: if name in self.names_set: — O(1)
• sorted() line 577: if name in self.names_set: — O(1)
• remove() line 449: replace self.names.remove(name) with indexed pop after O(1) set confirmation; update self.names_set.discard(name).

See patch: defects/pylons/patch/pylons-0001-toposorter-names-set.patch

Speedup

N=1000 nodes (realistic large tween+deriver+predicate config):

• Slow: ~O(N²) = ~1,000,000 list element comparisons
• Fast: ~O(N) = ~1,000 set hash lookups
• Speedup: ~1000x at N=1000; scales quadratically vs linearly