# Topological sort (performance)

**URL:** <https://discourse.julialang.org/t/topological-sort-performance/17153>\
**Category:** Performance\
**Tags:** sort\
**Created:** [November 5, 2018, 4:27am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153 "2018-11-05T04:27:55Z")\
**Posts on this page:** 4\
**Page:** 3

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [November 8, 2018, 3:49pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/42 "2018-11-08T15:49:13Z")

</div>

With not so important and small cosmetic change (If Stefan change word “probably” =\> “maybe”) his claim seems to me to be correct. (in short version: Julia is pretty good 😉 )

But I also think that warning in “Performance tips” and “Notable difference from python” about generators (and maybe also about strings) are still useful.

---

<div class="post-metadata">

**Author:** ![y4lu](https://avatars.discourse-cdn.com/v4/letter/y/47e85d/32.png) [@y4lu](https://discourse.julialang.org/u/y4lu)\
**Post date:** [November 8, 2018, 10:36pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/43 "2018-11-08T22:36:15Z")

</div>

I got about a 50x iteration time speed-up (comparing directly) replacing the dict with vectors and using @views on a better sized test set (~10000 items, with a max three links per node)  
49x for xloop = 1, 85x for xloop = 10

Julia doesn’t seem to allocate if the set is small enough, even with less than optimal `@codewarn_type`  
add: ~30x against the (cheat-ish) non-allocating 10,000x11 approximation, 0.06 sec to 0.002x sec

---

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [November 10, 2025, 10:02am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/44 "2025-11-10T10:02:29Z")

</div>

Not to necropost, but I found myself wanting a quick-n-dirty toposort, and thought I’d try to steal some code before writing any myself, and this was the top search result.

So, given that I _didn’t_ end up using any of the code here, I figure I might as well toss my code onto the list.

```julia
function toposort!(data::Dict{T, Set{T}}) where T
    order = T[]
    sizehint!(order, length(data))
    revdeps = Dict(k => T[] for (k, _) in data)
    for (node, deps) in data
        if isempty(deps)
            push!(order, node)
        else
            for dep in deps
                push!(revdeps[dep], node)
            end
        end
    end
    for node in order, rdep in revdeps[node]
        isempty(delete!(data[rdep], node)) && push!(order, rdep)
    end
    order, length(order) == length(data)
end

```

This does rely on a well-formatted input (no implicit nodes, no cyclic references to be removed).

Basic benchmarks:

```julia-auto
# The original python translation + data
>>> timeit.timeit(lambda: list(toposort2(data))) # Python 3.14
14.198098400025629 # 14.2 μs / iteration

julia> @b deepcopy(data) toposort2
9.198 μs (243 allocs: 19.297 KiB)

julia> @b deepcopy(data) toposort!
734.829 ns (21.29 allocs: 1.366 KiB)

# The graphs example, and data
julia> @b deepcopy(data2) toposort2
9.919 μs (475 allocs: 29.469 KiB)

julia> @b topological_sort_by_dfs(g)
304.857 ns (11 allocs: 1.203 KiB)

julia> @b deepcopy(data2) toposort!
376.571 ns (18.17 allocs: 1.071 KiB)

```

This isn’t going to win any competitions, but I’m pretty happy with this for the LOC it takes.

Hopefully it helps anybody else who just wants a decent drop-in topological sort.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [November 10, 2025, 5:36pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/45 "2025-11-10T17:36:27Z")

</div>

Necrosorting alert

[Previous page](https://discourse.julialang.org/t/topological-sort-performance/17153.md?page=2)