UNDF: UNDF-2026-000000631

elixir-0001: Mix.Dep.Converger.topological_sort — O(N²) Enum.find in Enum.map

Severity: HIGH

Location

lib/mix/lib/mix/dep/converger.ex:33-35
Called from: converge/4 at line 76, Mix.Dep.Umbrella.converger.ex:75

Description

topological_sort/1 takes the sorted atom list returned by :digraph_utils.topsort/1 and reconstructs the ordered Mix.Dep struct list by calling Enum.find/2 (O(N) linear scan) inside Enum.map/2 (O(N) loop). The result is O(N²) where N = total flattened dependency count for the Mix project.

topological_sort is called on every invocation of Mix.Dep.Converger.converge/4, which runs during mix deps.get, mix deps.compile, mix compile, and umbrella builds. For large Mix projects with hundreds of transitive dependencies (common in Erlang/Elixir umbrella apps), this is a visible compilation bottleneck.

Root Cause

# converger.ex:32-35
if apps = :digraph_utils.topsort(graph) do
  Enum.map(apps, fn app ->
    Enum.find(deps, fn %Mix.Dep{app: other_app} -> app == other_app end)  # O(N) per app
  end)

:digraph_utils.topsort/1 returns a list of atom application names. deps is a list of N Mix.Dep structs. For each of the N apps, Enum.find walks up to N deps → O(N²) total.

Fix

Build a map from app atom to dep struct before the loop, then do O(1) lookups:

if apps = :digraph_utils.topsort(graph) do
  dep_index = Map.new(deps, fn %Mix.Dep{app: app} = dep -> {app, dep} end)
  Enum.map(apps, fn app -> dep_index[app] end)

Map.new/2 is O(N), dep_index[app] is O(1), total O(N).

Complexity

	Before	After
topological_sort	O(N²)	O(N)
per mix compile	O(N²)	O(N)

Impact

A Mix umbrella application with 200 apps triggers 200 × 200 = 40,000 comparisons per compile. With N=500 (Nerves embedded frameworks, large Phoenix monorepos) that is 250,000 comparisons. The fix reduces this to 500 comparisons.

1.9 KiB Raw Permalink Blame History Unescape Escape