Appendix A — Performance tricks

Author

Iacopo Moles

A.1 Hurwitz Check

Create our nice model. Assume to have run the poles function and that you have a vector of eigenvalues. For simplicity I will create an arbitrary vector with the first 100 values in \(-1\) and the last 100 values as random around \(0\).

Code 
using BenchmarkTools

vbig = [zeros(ComplexF64,100).-1 ; rand(ComplexF64,100).-0.5];

vbig[[1,end]]
2-element Vector{ComplexF64}:
                 -1.0 + 0.0im
 -0.24799024016810423 + 0.8662500972954771im

A.1.1 for loop

With a naive approach we check if all the elements are in the LHP: make a function that iterates and returns false if it hits a pole with positive real part.

Code 
function isHurwitz(v)
    for i in eachindex(v)
        if real(v[i])>0.0
            return false
        end
    end
    return true
end

@benchmark isHurwitz($(Ref(vbig))[])
BenchmarkTools.Trial: 10000 samples with 987 evaluations per sample.
 Range (min … max):  50.659 ns … 360.588 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     52.280 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   53.140 ns ±   7.422 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █▆▆▃▄ █ ▅▁▁▆  ▁▁▁                                            ▂
  █████▇███████▇███▆▆▇▆▆▄▄▅▄▃▄▄▄▄▁▅▁▄▃▁▃▄▁▄▄▁▁▃▃▃▄▃▃▃▁▁▁▃▄▁▄▁▃ █
  50.7 ns       Histogram: log(frequency) by time      73.2 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

We have our baseline. We can probably squeeze out some more performance but I’m still a Julia noob.

A.1.2 all()

Let’s try using some of the built-in declarative functions:

Code 
@benchmark all(real($vbig).<=0.0)
BenchmarkTools.Trial: 10000 samples with 776 evaluations per sample.
 Range (min … max):  170.876 ns …  18.307 μs  ┊ GC (min … max):  0.00% … 96.10%
 Time  (median):     238.660 ns               ┊ GC (median):     0.00%
 Time  (mean ± σ):   411.172 ns ± 851.020 ns  ┊ GC (mean ± σ):  36.72% ± 17.16%

  █▆▂  ▁▁                                                       ▁
  ████▇██▆▆▁▃▃▁▃▁▁▁▃▁▁▁▁▆▆▆▅▃▃▃▁▁▃▁▃▃▅▆▆▆▆▇▇▆▅▅▅▄▅▅▅▅▅▄▅▅▅▅▄▆▆▆ █
  171 ns        Histogram: log(frequency) by time       5.54 μs <

 Memory estimate: 1.75 KiB, allocs estimate: 5.

Simple all(), when given a tuple it checks if all the values are True, otherwise it stops when it encounters the first False.

We can see that it’s a tad slower. This is because it’s creating a new vector with just the real parts, then it’s creating a new vector with only the boolean results and then it’s checking if there are any False results.

This results in a lot of allocations and wasted resources.

Code 
@benchmark all(<=(0.0),real($vbig))
BenchmarkTools.Trial: 10000 samples with 796 evaluations per sample.
 Range (min … max):  150.000 ns …  24.051 μs  ┊ GC (min … max):  0.00% … 98.68%
 Time  (median):     215.327 ns               ┊ GC (median):     0.00%
 Time  (mean ± σ):   310.133 ns ± 551.533 ns  ┊ GC (mean ± σ):  22.76% ± 15.72%

  ▂█▇▄▂         ▃▁                                           ▁▁ ▂
  █████▇▇▆▅▅▃▃▃▇███▆▆▅▆▅▆▅▅▄▅▅▄▁▁▃▁▁▁▃▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▃▁▄▅▇███ █
  150 ns        Histogram: log(frequency) by time       2.14 μs <

 Memory estimate: 1.62 KiB, allocs estimate: 2.

A smarter way is to skip on of the allocations by creating the vector of real parts and then checking row by row if the non-positivity check fails.

Code 
@benchmark all(i -> real(i)<=0.0,$vbig)
BenchmarkTools.Trial: 10000 samples with 987 evaluations per sample.
 Range (min … max):  49.544 ns … 219.656 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     51.570 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   53.682 ns ±  11.983 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▁█▆▂▃▂                                                    ▁  ▁
  ███████▆▇▆▅▅▄▄▇▅▅▅▅▆▄▅▅▄▁▄▄▄▄▃▆▄▄▄▄▃▅▃▄▁▄▃▃▅▃▃▁▁▄▁▄▃▃▁▃▄▅▁██ █
  49.5 ns       Histogram: log(frequency) by time       116 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

We can do better: Instead of converting into real the full vector it checks element by element if it’s in the LHP. It returns false at the first failure. We finally have a comparable result to the benchmark function but in a more compact way.

Is it cleaner? That’s subjective.

A.1.3 mapreduce()

Finally we try the MapReduce approach. This allows a better utilization of your processor without the necessity of learning parallel programming.

Code 
@benchmark mapreduce(i->real(i)<=0.0, &, $vbig)
BenchmarkTools.Trial: 10000 samples with 992 evaluations per sample.
 Range (min … max):  42.036 ns … 633.871 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     42.339 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   43.741 ns ±  10.518 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █▄▁▂▂                                                        ▁
  █████▇█▆▆▆▆▅▇▄▄▁▇▇▄▃▄▅▃▃▁▁▁▄▁▃▁▁▁▃▁▁▁▄▁▁▁▃▁▁▃▁▁▃▁▁▁▁▁▃▃▃▁▃▃█ █
  42 ns         Histogram: log(frequency) by time      95.4 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

We squeeze the last bit of performance and beat the initial benchmark, not by much but still appreciable.