search

AlgebraicJulia / Catlab.jl

A framework for applied category theory in the Julia language
https://www.algebraicjulia.org
MIT License
608 stars 58 forks source link

Make `neighbors` for graphs faster by returning an iterator #824

Closed epatters closed 1 year ago

epatters commented 1 year ago

I guess this will technically be a breaking change but I'm pretty sure that my original implementation did return an iterator and it got changed somewhere along the way.

In the benchmarks on my local machine, we can see the "within a factor of 2 to 3" performance with Graphs.jl that we should expect. Previously, it was off by several orders of magnitude.

BenchmarkGroup:
        10-element BenchmarkTools.BenchmarkGroup:
          tags: []
          "Graph" => 3-element BenchmarkTools.BenchmarkGroup:
              tags: []
              "LightGraphs" => 4-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "iter-neighbors" => Trial(5.085 μs)
                  "iter-edges" => Trial(9.170 μs)
                  "make-path" => Trial(1.482 ms)
                  "has-edge" => Trial(28.376 μs)
              "Catlab" => 4-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "iter-neighbors" => Trial(14.507 μs)
                  "iter-edges" => Trial(3.625 ns)
                  "make-path" => Trial(3.298 ms)
                  "has-edge" => Trial(32.828 μs)
              "Catlab-vectorized" => 2-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "iter-edges" => Trial(1.203 ms)
                  "make-path" => Trial(7.161 ms)
          "SymmetricGraph" => 3-element BenchmarkTools.BenchmarkGroup:
              tags: []
              "LightGraphs" => 4-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "iter-neighbors" => Trial(4.747 μs)
                  "iter-edges" => Trial(27.143 μs)
                  "make-path" => Trial(990.531 μs)
                  "has-edge" => Trial(27.050 μs)
              "Catlab" => 4-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "iter-neighbors" => Trial(14.172 μs)
                  "iter-edges" => Trial(4.400 ns)
                  "make-path" => Trial(131.336 ms)
                  "has-edge" => Trial(34.737 μs)
              "Catlab-vectorized" => 2-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "iter-edges" => Trial(2.383 ms)
                  "make-path" => Trial(18.830 ms)