# Improving performance of recursions by avoiding closures

**URL:** https://discourse.julialang.org/t/improving-performance-of-recursions-by-avoiding-closures/76026
**Category:** Performance
**Tags:** recursion
**Created:** [February 8, 2022, 2:15pm UTC](https://discourse.julialang.org/t/improving-performance-of-recursions-by-avoiding-closures/76026 "2022-02-08T14:15:06Z")
**Posts on this page:** 1
**Page:** 1

<div class="post-metadata">

### Author: ![lucifer1004](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lucifer1004/32/22311_2.png) [@lucifer1004](https://discourse.julialang.org/u/lucifer1004)
#### Post date: [February 8, 2022, 2:15pm UTC](https://discourse.julialang.org/t/improving-performance-of-recursions-by-avoiding-closures/76026/1 "2022-02-08T14:15:06Z")

</div>

Just implemented Tarjan’s SCC (strongly-connected components) algorithm. In the first version, I created the `dfs()` function (which is recursive) inside the `scc()` function, and let it capture the needed variables from the body of the `scc()` function.

> Note that in this version I already moved `now` and `group_num` into a mutable struct, since I need to modify them during the recursion, and using them as plain `Int` was much more expensive. The other variables, `low`, `ord`, `visited`, `ids`, were defined in the outer `scc()` function.

```julia
function dfs(v::Int)
    info.now += 1
    low[v] = info.now
    ord[v] = info.now
    push!(visited, v)

    for to in csr[v]
        if ord[to] == 0
            dfs(to)
            low[v] = min(low[v], low[to])
        else
            low[v] = min(low[v], ord[to])
        end
    end

    if low[v] == ord[v]
        info.group_num += 1

        while true
            u = pop!(visited)
            ord[u] = n
            ids[u] = info.group_num
            if u == v
                break
            end
        end
    end
end

```

Benchmarking showed that there were a lot of allocations. For a randomly generated graph with 200,000 nodes and 500,000 edges:

```julia
julia --project=. main.jl
  26.753 ms (199511 allocations: 19.07 MiB)

```

And after I moved all the information into the `info` variable, and made it a parameter of the recursive function:

```julia
function dfs(v::Int, info::SCCIterationInfo)
    info.now += 1
    info.low[v] = info.now
    info.ord[v] = info.now
    push!(info.visited, v)

    for to in info.csr[v]
        if info.ord[to] == 0
            dfs(to, info)
            info.low[v] = min(info.low[v], info.low[to])
        else
            info.low[v] = min(info.low[v], info.ord[to])
        end
    end

    if info.low[v] == info.ord[v]
        info.group_num += 1

        while true
            u = pop!(info.visited)
            info.ord[u] = info.n
            info.ids[u] = info.group_num
            if u == v
                break
            end
        end
    end
end

```

I got ~25% performance improvement.

```julia
julia --project=. main.jl
  19.920 ms (15 allocations: 12.97 MiB)

```