Improve performance of basic incidence matrix computation

[mtanneau]

A substantial amount of time is spent in this line

PowerModels.jl/src/core/data_basic.jl

Line 250 in 8824212

branch_ordered = sort(b, by=(x) -> x["index"])

mainly because the sort does two dictionary lookups every time is needs to compare two branches.

This is un-necessary for two reasons:

• basic network data has branches indexed from 1 to E (number of branches) and no disabled branches
• the subsequent call to sparse will re-sort any non-ordered indices if needed

Removing this step, plus some type annotations to help the compiler, result in a substantial performance improvement.
note that relative gains get better as system size increases.

---

Performance benchmark on the 9241_pegase case from PGLib

Before

BenchmarkTools.Trial: 91 samples with 1 evaluation per sample.
 Range (min … max):  52.836 ms … 68.059 ms  ┊ GC (min … max): 0.00% … 19.06%
 Time  (median):     54.393 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   55.223 ms ±  2.611 ms  ┊ GC (mean ± σ):  1.80% ±  3.92%

   ▁▁ ▂███▄▁▄                                                  
  ▅██████████▅▃▁▁▁▁▁▁▁▁▁▃▅▁▁▃▅▆▃▅▃▁▁▁▁▁▁▁▁▁▁▁▁▃▃▁▁▁▁▁▁▁▁▁▁▁▁▃ ▁
  52.8 ms         Histogram: frequency by time          65 ms <

 Memory estimate: 7.12 MiB, allocs estimate: 95887.

After

BenchmarkTools.Trial: 456 samples with 1 evaluation per sample.
 Range (min … max):  10.062 ms … 22.820 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     10.464 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   10.962 ms ±  1.485 ms  ┊ GC (mean ± σ):  2.49% ± 6.83%

  ▃▆█▅▃▂▆▂                                                     
  █████████▇▇▇▄▁▅▁▁▁▁▁▄▄▁▁▆▆▆▅▅▆▇▅▁▄▁▁▁▁▁▁▄▁▁▄▁▁▁▁▁▄▄▄▁▁▁▁▄▁▄ ▇
  10.1 ms      Histogram: log(frequency) by time        18 ms <

 Memory estimate: 2.84 MiB, allocs estimate: 32133.

[mtanneau]

type annotation here didn't seem to yield any improvement, so I didn't include it to keep the code simple.

[odow]

What about

    E, N = length(data["branch"])::Int, length(data["bus"])::Int
    # I = [..., e, e, ...]
    I = repeat(1:E; inner = 2)
    J = zeros(Int, 2 * E)
    for e in 1:E
        branch = data["branch"]["$e"]
        J[2e-1] = branch["f_bus"]::Int
        J[2e] = branch["t_bus"]::Int
    end
    # V = [..., 1, -1, ...]
    V = repeat([1, -1]; inner = 2)

[mtanneau]

Thanks! This gives a nice extra 10% performance boost :)

BenchmarkTools.Trial: 517 samples with 1 evaluation per sample.
 Range (min … max):  8.979 ms … 20.571 ms  ┊ GC (min … max): 0.00% … 48.89%
 Time  (median):     9.165 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   9.671 ms ±  1.367 ms  ┊ GC (mean ± σ):  3.19% ±  8.24%

  ██▅ ▃▂▁   ▄▃                                                
  ███████▅▆▆██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄██▅▄▅▁▅▆▁▁▄▁▄▁▁▁▁▁▁▁▄▁▁▄▄ ▇
  8.98 ms      Histogram: log(frequency) by time     15.7 ms <

 Memory estimate: 2.84 MiB, allocs estimate: 32135.

[ccoffrin]

Updates look good to me. Just need to add a note to the change log and merge.

Open to ideas for adding a test, but also know it can be very hard to accurately capture runtime performance in CI.

[mtanneau]

Change log updated --> this should go into the "staged" section, correct?

[codecov]

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 93.71%. Comparing base (8824212) to head (9e438f2).
Report is 1 commits behind head on master.

Additional details and impacted files

@@           Coverage Diff           @@
##           master     #946   +/-   ##
=======================================
  Coverage   93.71%   93.71%           
=======================================
  Files          43       43           
  Lines        9636     9636           
=======================================
  Hits         9030     9030           
  Misses        606      606           

Files with missing lines	Coverage Δ
src/core/data_basic.jl	88.49% <100.00%> (ø)

---

Continue to review full report in Codecov by Sentry.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 8824212...9e438f2. Read the comment docs.