How Switching to a Min‑Heap Cut Cron Scheduler CPU Usage by 5×

This article describes how the author optimized a Go cron scheduling framework by replacing the original sorting‑based approach with a min‑heap implementation.

The original implementation sorted all tasks on each execution, leading to O(k·n·log n) complexity and high CPU usage when handling hundreds of tasks per second.

By building a min‑heap of tasks, the scheduler can peek the next task, pop and push only when necessary, reducing the per‑execution complexity to O(k·log n). In production the CPU usage dropped from around 50 % to 10 %, a 4‑5× improvement.

Key steps of the min‑heap approach:

Construct a min‑heap when initializing the task list.

On each tick, peek the heap’s top element; if its scheduled time is due, pop it, run the job, recompute its next time, and push it back.

If the top element is not due, calculate the sleep duration until it becomes due.

Insert new tasks with heap push (O(log n)) and remove tasks similarly.

Below is a simplified excerpt of the original loop (sorting version):

for {
    // Determine the next entry to run.
    sort.Sort(byTime(c.entries))

    var timer *time.Timer
    if len(c.entries) == 0 || c.entries[0].Next.IsZero() {
        timer = time.NewTimer(100000 * time.Hour)
    } else {
        timer = time.NewTimer(c.entries[0].Next.Sub(now))
    }

    for {
        select {
        case now = <-timer.C:
            // run due entries, then recompute next times and sort again
            ...
        case newEntry := <-c.add:
            // add new entry and resort
            ...
        case <-c.stop:
            return
        }
        break
    }
}

And the optimized loop using a min‑heap (no sorting):

for {
    // Determine the next entry to run.
    // Use min‑heap, no need to sort any more

    var timer *time.Timer
    if len(c.entries) == 0 || c.entries[0].Next.IsZero() {
        timer = time.NewTimer(100000 * time.Hour)
    } else {
        timer = time.NewTimer(c.entries[0].Next.Sub(now))
    }

    for {
        select {
        case now = <-timer.C:
            for {
                e := c.entries.Peek()
                if e.Next.After(now) || e.Next.IsZero() {
                    break
                }
                e = heap.Pop(&c.entries).(*Entry)
                c.startJob(e.WrappedJob)
                e.Prev = e.Next
                e.Next = e.Schedule.Next(now)
                heap.Push(&c.entries, e)
            }
        case newEntry := <-c.add:
            timer.Stop()
            now = c.now()
            newEntry.Next = newEntry.Schedule.Next(now)
            heap.Push(&c.entries, newEntry)
        case <-c.stop:
            timer.Stop()
            return
        }
        break
    }
}

The full source code and tests are available in the author’s GitHub fork.