Skip to content
Hari KharelStudy

Event-driven simulation and timers

intermediateCommon atAnthropicStripeGoogleJane StreetRead firstHeaps / priority queuesQueues and dequesPractise in the Sandbox →

An event-driven system keeps every future event in a min-heap keyed by (time, seq). The loop pops the earliest event, moves the clock to its time, handles it, and pushes any new events that handling creates. The seq counter makes ties deterministic. Each event costs O(log n), and the clock jumps over idle time for free.

The idea in plain words

Section titled “The idea in plain words”

Think of a desk diary with sticky notes: “at 9:05, call Ana”, “at 9:05, email Bo”, “at 9:30, stand-up”. You don’t stare at the clock every second. You look at the earliest note, wait until then, do it, and maybe write new notes (“call Ana back at 10:00”).

That’s the whole model:

  • An event is “at time t, do x”.
  • The queue holds future events, earliest first. A heap gives you the earliest in O(1) and insert/remove in O(log n).
  • The loop pops the earliest, sets now = event.time, and runs it. Running it may schedule more events.

Two details make it trustworthy:

  1. The clock is data, not a system call. In a simulation, now only moves when the loop moves it. Same input, same output, every run. That’s what makes it testable.
  2. Ties need a rule. Two events at the same time must come out in an order you chose, not the order a heap happens to produce. The usual rule is creation order, enforced with a sequence number.

See it

Section titled “See it”

The program schedules timers A–E at t = 0 and a repeating tick every 4. Press Run or step tick by tick. Add your own timers at any time, cancel one, then try jump to next event. Finally, untick break ties by seq and run to t = 5: A, C and D share a fire time, and the heap alone returns them in a different order.

A timer heap driving an event loop
run · step · schedule
fired
pending in heap
B
tick
C
D
A
E
0102030
The heap as an array (root = next to fire). Each cell is time name#id.
3 B#2
4 tick#5
5 C#3
5 D#4
5 A#1
8 E#6
012345
fire log:(nothing yet)
now0
next_fire3
heap_size6
dead_entries0
pops0
skipped0
pendingfiredcancelled, still in heapheap root
t = 0: the program schedules its timers. Nothing fires yet; each entry goes into the heap keyed by (fire time, seq).
t = 0

What to notice:

  • The root of the heap is always the next timer to fire. The rest of the array is only partly ordered; that’s why push and pop are O(log n), not O(n).
  • Cancel doesn’t search the heap. It marks the id as dead. The entry stays (dimmed) until it reaches the root, then gets popped and skipped. This is lazy deletion, the approach the Python heapq docs recommend.
  • A repeating timer is popped, fired, and pushed back with its next fire time.

When to reach for it

Section titled “When to reach for it”
The problem says… Why an event queue fits
“time is passed in” / “advance the clock by ms” You own the clock, so a jump-to-next-event loop is natural and deterministic.
timers, timeouts, retries, deadlines, expiries Each is a future event. The earliest deadline is a heap peek.
“simulate N workers / machines / arrivals” Arrivals and completions are events; handling one schedules the next.
“in order of time, ties broken by id / insertion” Exactly the (time, seq) key.
huge time ranges with few events Jumping costs per event, not per millisecond.

How it works

Section titled “How it works”

The queue: a heap with a tie-breaker

Section titled “The queue: a heap with a tie-breaker”
  1. Keep a counter seq that only goes up. Every pushed event takes the next value.
  2. Order entries by (time, seq). Equal times now pop in insertion order, and the payload is never compared (so it needn’t be comparable).
  3. Pop is O(log n). Peek at the root to learn the next fire time without removing it.
EventQueue.py
import heapq
from itertools import count
from typing import Generic, TypeVar


T = TypeVar("T")




class EventQueue(Generic[T]):
    """Min-heap of (time, seq, item). seq makes equal times pop in insertion order."""


    def __init__(self) -> None:
        self._heap: list[tuple[int, int, T]] = []
        self._seq = count()  # 1. a monotonically increasing tie-breaker


    def push(self, time: int, item: T) -> None:
        # 2. the tuple compares time first, then seq; item is never compared,
        #    so items don't need to be orderable at all
        heapq.heappush(self._heap, (time, next(self._seq), item))


    def peek_time(self) -> int | None:
        return self._heap[0][0] if self._heap else None


    def pop(self) -> tuple[int, T]:
        time, _, item = heapq.heappop(self._heap)  # 3. O(log n)
        return time, item


    def __len__(self) -> int:
        return len(self._heap)




if __name__ == "__main__":
    q: EventQueue[str] = EventQueue()
    for t, name in [(5, "a"), (3, "b"), (5, "c"), (5, "d"), (1, "e")]:
        q.push(t, name)
    assert q.peek_time() == 1
    order = [q.pop() for _ in range(len(q))]
    # ties at t=5 come out a, c, d: the order they were pushed
    assert order == [(1, "e"), (3, "b"), (5, "a"), (5, "c"), (5, "d")]
    print("ok")

The loop: a classic discrete-event simulation

Section titled “The loop: a classic discrete-event simulation”

Here’s the textbook example: send a message across a network with link latencies and find when each node first hears it.

  1. Seed the queue with the starting event.
  2. Pop the earliest event and jump the clock to its time. Never step through empty time.
  3. If the event is stale (here: the node already heard the message), skip it.
  4. Handle it, which may push new events with time = now + delay.
flood.py
import heapq
from itertools import count


Graph = dict[str, list[tuple[str, int]]]  # node -> [(neighbour, link latency)]




def flood(graph: Graph, source: str) -> dict[str, int]:
    """Discrete-event simulation: when does each node first hear a message?"""
    seq = count()
    events: list[tuple[int, int, str]] = [(0, next(seq), source)]  # 1. seed the queue
    heard: dict[str, int] = {}
    while events:
        now, _, node = heapq.heappop(events)  # 2. jump the clock to the next event
        if node in heard:
            continue  # 3. a later copy of the message: stale, skip it
        heard[node] = now
        for nxt, latency in graph.get(node, []):
            # 4. handling an event schedules new events in the future
            heapq.heappush(events, (now + latency, next(seq), nxt))
    return heard




if __name__ == "__main__":
    net: Graph = {
        "a": [("b", 4), ("c", 1)],
        "c": [("b", 2), ("d", 7)],
        "b": [("d", 1)],
        "d": [],
    }
    # b hears via c at 1+2=3, before the direct link would deliver at 4
    assert flood(net, "a") == {"a": 0, "c": 1, "b": 3, "d": 4}
    assert flood(net, "d") == {"d": 0}
    print("ok")

If that looks like Dijkstra’s algorithm, it is. Dijkstra is a discrete-event simulation where events are “the wavefront reaches node v”.

Inside real event loops

Section titled “Inside real event loops”
Runtime What it does with timers
Node.js setTimeout timers sit in per-duration lists, and the lists sit in a priority queue by expiry with an id as tie-break; libuv’s own timer heap breaks ties with a start_id counter. All queued Promise callbacks (microtasks) run before the next timer callback.
Python asyncio call_at / call_later push a TimerHandle onto a heapq heap. Handles compare by time only, so equal-time timers have no documented order. cancel() just marks the handle; the loop drops dead handles lazily and rebuilds the heap once they exceed half of it.
.NET Task.Delay and System.Threading.Timer are backed by runtime timer queues; for your own simulation, PriorityQueue with a (time, seq) tuple priority is the tool.

What it costs

Section titled “What it costs”
Operation Cost Why
schedule (push) O(log n) sift up a heap of n pending events
next fire time (peek) O(1) it’s the root
fire (pop) O(log n) sift down
cancel, lazy O(1) now, O(log n) later mark dead; pay when it surfaces
cancel, eager O(n) or O(log n) find it (O(n)), or keep an index map in an indexed heap
advance over idle time O(1) jump now to the next event

Lazy deletion has a hidden cost: dead entries take memory and inflate n. If programs cancel most timers (very common for timeouts that usually don’t fire), the heap can fill with corpses. Fixes: rebuild when dead entries exceed half the heap (CPython’s asyncio does this), or use a timer wheel.

Ticking every millisecond vs jumping to the next event
drag the sliders
Tick loop (check every ms)
1.0M
Jump loop (pop next event)
10.0k
A tick loop does about T + n steps, so an idle hour of simulated time costs 3.6 million iterations. Jumping does about n log n: cost follows the number of events, not the length of time.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Repeating timers. After firing, push again at time + period. Use the scheduled time, not “now”, or the schedule drifts. Decide (and ask!) what happens if one advance covers several periods, and whether the repeat keeps its original tie-break rank.
  • Timer wheel. A ring of buckets, one per tick (Varghese and Lauck, 1987). O(1) insert and cancel, used by the Linux kernel and Kafka for huge numbers of timeouts. Costs precision and needs a fixed tick.
  • Indexed heap. Keep id → heap position so you can cancel or reschedule in O(log n) without leaving corpses.
  • Ready queue + timer heap. Real loops separate “runnable now” (a FIFO) from “runnable later” (the heap). Due timers move into the FIFO.
  • Two-level ordering. (time, priority, seq) when same-time events have priorities, such as “completions before arrivals”.

Pitfalls

Section titled “Pitfalls”
  • No tie-breaker. Tests pass by luck, then fail when the heap shape changes. Always (time, seq).
  • Comparing payloads. In Python, (time, task) tuples crash with TypeError on a tie if tasks aren’t orderable. The seq in the middle prevents it.
  • Firing events scheduled during the same advance. If a handler schedules something with delay 0, does it run in this pass or the next? Decide, and say so.
  • < vs <= at the boundary. “Fires at now + delay” with advance to exactly that time: due or not? Pin it down.
  • Mutating the heap while iterating it. Pop in a loop instead (while heap and heap[0].time <= target).
  • Drift in intervals. next = now + period drifts when now overshoots; next = scheduled + period doesn’t.

In the interview

Section titled “In the interview”
  • Ask: who owns the clock (passed in, or real time)? Can time go backwards? What order for ties? Can a handler schedule or cancel other events while firing?
  • Say the invariant: “Every pending event is in the heap, keyed by (time, seq); anything with time ≤ now has already fired.”
  • State costs per operation, and the lazy-delete trade-off.
  • Follow-ups to expect: repeating timers, cancellation, “next fire time” queries, priorities among same-time events, millions of timers (timer wheel), and thread safety if real threads schedule timers.

Check yourself

Section titled “Check yourself”
Check yourself
pick one
You store Python heap entries as (fire_time, callback). Two timers have the same fire_time. What happens on push?
Check yourself
pick one
A system schedules a 30-second timeout for every request, and 99% of requests finish in time and cancel their timeout. With lazy deletion, what grows?
Check yourself
pick one
A simulation covers one simulated year with 10,000 events. Why jump to the next event instead of ticking every millisecond?

Practice on your own

Section titled “Practice on your own”

These are classic exercises, not gym questions:

  • Simulate a supermarket with k checkout lanes and random arrivals; report average wait. (Events: arrival, service done.)
  • Elevator simulation: requests arrive over time, one car, compute when each rider arrives.
  • Compute when each cell catches fire in a grid where fire spreads to neighbours with different delays.
  • Implement an indexed min-heap that supports decrease_key and remove(id) in O(log n).

Go deeper

Section titled “Go deeper”
Section titled “Related”
Heaps / priority queuesThe structure underneath every event queue.
Scheduling and task queuesWhat to run next when many tasks are ready at once.
Concurrency semanticsReal threads, races and the JS event loop's microtasks.
Rate limitingTime-based state with caller-supplied clocks.