JuliaGraphs / Graphs.jl

An optimized graphs package for the Julia programming language
http://juliagraphs.org/Graphs.jl/
Other
451 stars 87 forks source link

Avoid materializing intermediate adjacency list #372

Closed simsurace closed 2 months ago

simsurace commented 2 months ago

For graphs where the adjacency is not stored, this can lead to a lot of allocations when iterating over edges.

Before PR:

julia> g
{58089, 120148} directed simple Int32 graph

julia> typeof(g)
StaticGraphs.StaticDiGraph{Int32, Int32}

julia> @time collect(Graphs.edges(g));
 21.959129 seconds (330.20 k allocations: 260.015 GiB, 27.19% gc time, 0.21% compilation time)

After PR:

julia> @time collect(Graphs.edges(g));
  0.000396 seconds (3 allocations: 938.844 KiB)
KristofferC commented 2 months ago

Couldn't this be done in the iterate above as well?

codecov[bot] commented 2 months ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 97.27%. Comparing base (48c42c7) to head (4efde07).

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #372 +/- ## ========================================== - Coverage 97.28% 97.27% -0.01% ========================================== Files 118 118 Lines 6876 6874 -2 ========================================== - Hits 6689 6687 -2 Misses 187 187 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.