EventList performance degradation under heavy cancellation due to lazy deletion #3358
Description
Summary
Currently EventList uses lazy deletion, so canceled events remain in the heap and are skipped during pop_event(). Current implementation:
def pop_event(self) -> Event:
while self._events:
event = heappop(self._events)
if not event.CANCELED:
return event
raise IndexError("Event list is empty")When a large fraction of events are canceled, pop_event() may repeatedly discard canceled entries before reaching live ones. This makes pop cost proportional to total heap size rather than active size.
Reproducible Benchmark
import time
from heapq import heapify
from mesa.time import Event, EventList, Priority
def dummy():
pass
N = 200_000
CANCEL_RATIO = 0.9
event_list = EventList()
events = []
# Insert events
for i in range(N):
e = Event(i, dummy, priority=Priority.DEFAULT)
events.append(e)
event_list.add_event(e)
# Cancel 90%
for e in events[:int(N * CANCEL_RATIO)]:
e.cancel()
print("Heap size:", len(event_list._events))
print("Active events:", len(event_list))
# Pop without compaction
start = time.perf_counter()
try:
while True:
event_list.pop_event()
except IndexError:
pass
print("Pop time (no compaction):", time.perf_counter() - start)The observed result is,
Heap size: 200000
Active events: 20000
Pop time (no compaction): ~0.70s
If we manually compact the heap before popping,
event_list._events = [
e for e in event_list._events if not e.CANCELED
]
heapify(event_list._events)Pop time becomes,
Heap size: 20000
Pop time (after compaction): ~0.05s
The slowdown is caused by repeatedly popping and discarding canceled entries.
Proposed Direction
Introducing adaptive heap compaction when canceled entries are large in number. For example,
Track _canceled_count . If _canceled_count > len(self._events) // 2, rebuild the heap,
self._events = [
e for e in self._events if not e.CANCELED
]
heapify(self._events)
self._canceled_count = 0This preserves current semantics and ordering while preventing pathological heap bloat under heavy cancellation.