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.
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
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.
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:
# 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.
Necrosorting alert