Speeding up simplify_neuron

[dokato]

Apart from suggestions @jefferis listed in #471 I noticed (following profiling) that calling apply on columns is much longer than just running dijkstra from start node again, compare:

> system.time(which.max(apply(dd, 2, robust_max)) )
   user  system elapsed 
  3.784   0.744   4.622 

> system.time(igraph::distances(ng, v=start, to=leaves, mode = 'out'))
   user  system elapsed 
  0.204   0.004   0.209 

This already reduces time by half:

> system.time(simplify_neuron(large_neuron[[1]]))
   user  system elapsed 
  5.489   1.780   7.399 
> system.time(simplify_neuron(large_neuron[[1]]))
   user  system elapsed 
  2.730   0.834   3.565 

Said neuron below to compare: large_neuron.rds.zip

[dokato]

I benchmarked your latest commits:

# large neuron
benchmark("simplify_neuron_old" = {
  simplify_neuron_old(nrn[[1]], n=2)
},"simplify_neuron" = {
  simplify_neuron(nrn[[1]], n=2)
},"simplify_neuron2" = {
  simplify_neuron2(nrn[[1]], n=2)
}, replications = 25)

                 test replications elapsed relative user.self sys.self
2     simplify_neuron           25  52.759    1.000    49.262    3.017
1 simplify_neuron_old           25 202.476    3.838   124.206   63.886
3    simplify_neuron2           25 113.827    2.157   112.653    0.965

# small neuron
benchmark("simplify_neuron_old" = {
  simplify_neuron_old(Cell07PNs[[11]], n=2)
},"simplify_neuron" = {
  simplify_neuron(Cell07PNs[[11]], n=2)
},"simplify_neuron2" = {
  simplify_neuron2(Cell07PNs[[11]], n=2)
}, replications = 25)

                 test replications elapsed relative user.self sys.self
2     simplify_neuron           25   0.209    1.035     0.202    0.007
1 simplify_neuron_old           25   0.202    1.000     0.184    0.018
3    simplify_neuron2           25   0.232    1.149     0.228    0.004

Looks like we get almost 4x gain and are slightly faster than simplify_neuron2.

Some outstanding comments:

• # FIXME check if dist was 0 => no valid path - should we stop and throw error here?
• can simplify_neuron2 be removed?
• why CI gets stuck?

[jefferis]

Thanks @dokato. I added another commit, which changes things quite a bit more (still for the better I hope in most cases).

[jefferis]

• [X] # FIXME check if dist was 0 => no valid path - should we stop and throw error here? Redundant as removed by f1a686e
• [x] can simplify_neuron2 be removed? Yes I think so.
• [x] why CI gets stuck? Probably travis.org deactivation. I have got some complex github actions setups working e.g. fafbseg but I never finished the nat PR.

[dokato]

Great, that looks really good - almost 8x gain on complex cases. See updated benchmarks below:

# large neuron
                 test replications elapsed relative user.self sys.self
2     simplify_neuron           25  37.768    1.000    31.178    2.541
1 simplify_neuron_old           25 296.742    7.857   131.747   86.796
3    simplify_neuron2           25 126.646    3.353   115.958    3.775

# small neuron
                 test replications elapsed relative user.self sys.self
2     simplify_neuron           25   0.252    1.000     0.228    0.011
1 simplify_neuron_old           25   0.275    1.091     0.217    0.028
3    simplify_neuron2           25   0.319    1.266     0.297    0.014

[codecov[bot]]

Codecov Report

Merging #472 (234a8ba) into master (0fe1b29) will decrease coverage by 0.03%. The diff coverage is 84.61%.

@@            Coverage Diff             @@
##           master     #472      +/-   ##
==========================================
- Coverage   76.89%   76.85%   -0.04%     
==========================================
  Files          47       47              
  Lines        5856     5825      -31     
==========================================
- Hits         4503     4477      -26     
+ Misses       1353     1348       -5     

Impacted Files	Coverage Δ
R/neuron.R	83.49% <83.33%> (-0.06%)	:arrow_down:
R/ngraph.R	86.63% <100.00%> (+0.07%)	:arrow_up:

---

Continue to review full report at Codecov.

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

[jefferis]

@dokato I'm going to merge this now. Thanks for getting it going. The codecov/project diff failure is a false positive (the missing lines are warnings that are never triggered because they shouldn't be!). Is there a way to adjust the config for codecov to be a bit more forgiving?

[dokato]

Not sure, but I'll take a look into that. I'm still confused of why coveralls hasn't worked for us.