The Critical Path

The Critical Path: after a run, combine the graph topology with measured durations to find the chain of tasks that determined the wall clock. Optimizing anything OFF that path is charity work - and this proves it by making a non-critical task instant and re-running.

source on github

a real captured run

CRITICAL PATH ANALYSIS

  wall clock:      344ms
  critical path:   343ms  =  pull:orders -> invoice:month -> report:board
  (path explains 100% of the wall clock - the rest is scheduling noise)

the experiment:
  make 'pull:catalog' (off-path) instant:   344ms -> 345ms  (nothing. told you.)
  halve 'pull:orders' (on-path):     344ms -> 254ms  (there it is)

profile the path, not the plan. optimizing off the critical path
is how teams burn a sprint making the fast part faster.

source

# frozen_string_literal: true

# The Critical Path: after a run, combine the graph topology with
# measured durations to find the chain of tasks that determined the
# wall clock. Optimizing anything OFF that path is charity work -
# and this proves it by making a non-critical task instant and
# re-running.
#
#   bundle exec ruby examples/critical_path.rb
#
# Runs offline; durations are simulated IO.

require class="s">"bundler/setup"
require class="s">"agentic"

WORK = {
  class="s">"pull:catalog" => {sleep: 0.05, deps: []},
  class="s">"pull:orders" => {sleep: 0.18, deps: []},
  class="s">"pull:reviews" => {sleep: 0.06, deps: []},
  class="s">"score:products" => {sleep: 0.09, deps: [class="s">"pull:catalog", class="s">"pull:reviews"]},
  class="s">"invoice:month" => {sleep: 0.12, deps: [class="s">"pull:orders"]},
  class="s">"report:board" => {sleep: 0.04, deps: [class="s">"score:products", class="s">"invoice:month"]}
}.freeze

def run(work, concurrency: 6)
  durations = {}
  hooks = {
    after_task_success: ->(task_id:, task:, result:, duration:) { durations[task_id] = duration }
  }
  orchestrator = Agentic:class="y">:PlanOrchestrator.new(concurrency_limit: concurrency, lifecycle_hooks: hooks)
  tasks = {}
  work.each do |name, spec|
    tasks[name] = Agentic:class="y">:Task.new(
      description: name,
      agent_spec: {class="s">"name" => name, class="s">"instructions" => class="s">"simulate"},
      payload: spec[class="y">:sleep]
    )
    orchestrator.add_task(tasks[name], spec[class="y">:deps].map { |d| tasks.fetch(d) },
      agent: ->(t) { sleep(t.payload) || class="y">:ok })
  end
  result = orchestrator.execute_plan
  [orchestrator.graph, durations, result.execution_time]
end

# Longest-duration path to each node, computed over the real topology
def critical_path(graph, durations)
  names = graph[class="y">:tasks].transform_values(&class="y">:description)
  memo = {}
  walk = lambda do |task_id|
    memo[task_id] ||= begin
      deps = graph[class="y">:dependencies][task_id]
      best = deps.map { |dep| walk.call(dep) }.max_by { |p| p[class="y">:cost] } || {cost: 0.0, path: []}
      {cost: best[class="y">:cost] + durations[task_id], path: best[class="y">:path] + [names[task_id]]}
    end
  end
  graph[class="y">:dependencies].keys.map { |id| walk.call(id) }.max_by { |p| p[class="y">:cost] }
end

graph, durations, wall = run(WORK)
path = critical_path(graph, durations)

puts class="s">"CRITICAL PATH ANALYSIS"
puts
puts format(class="s">"  wall clock:      %dms", wall * 1000)
puts format(class="s">"  critical path:   %dms  =  %s", path[class="y">:cost] * 1000, path[class="y">:path].join(class="s">" -> "))
puts format(class="s">"  (path explains %.0f%% of the wall clock - the rest is scheduling noise)",
  100 * path[class="y">:cost] / wall)
puts

# The proof: optimize a NON-critical task to zero... nothing happens
off_path = WORK.keys.find { |name| !path[class="y">:path].include?(name) }
faster = WORK.merge(off_path => WORK[off_path].merge(sleep: 0.0))
_, _, wall_after_wrong = run(faster)

# Now halve the SLOWEST task on the path... everything happens
bottleneck = path[class="y">:path].max_by { |name| WORK[name][class="y">:sleep] }
righter = WORK.merge(bottleneck => WORK[bottleneck].merge(sleep: WORK[bottleneck][class="y">:sleep] / 2))
_, _, wall_after_right = run(righter)

puts class="s">"the experiment:"
puts format(class="s">"  make '%s' (off-path) instant:   %3dms -> %3dms  (nothing. told you.)",
  off_path, wall * 1000, wall_after_wrong * 1000)
puts format(class="s">"  halve '%s' (on-path):     %3dms -> %3dms  (there it is)",
  bottleneck, wall * 1000, wall_after_right * 1000)
puts
puts class="s">"profile the path, not the plan. optimizing off the critical path"
puts class="s">"is how teams burn a sprint making the fast part faster."