performance hit of getPopStats for large gating trees

[mikejiang]

Description

To reproduce the issue, we simulate a dummy gs of 2^11-1 nodes

library(flowWorkspace)
data(GvHD)
gs <- GatingSet(GvHD[1])

fork <- function(gs, p, i){
  add(gs , rectangleGate(`FSC-H`= c(-Inf, Inf)), name = "L", parent = p) 
  add(gs , rectangleGate(`FSC-H`= c(-Inf, Inf)), name = "R", parent = p)  
  if(i < 10)
  {
    fork(gs, file.path(p, "L"), i + 1)
    fork(gs, file.path(p, "R"), i + 1)
  }
}

suppressMessages(fork(gs, "root", 1))
> length(getNodes(gs))
[1] 2047

Then run getPopStats, which appears to be slower-than-normal

> system.time(res <- getPopStats(gs))
   user  system elapsed 
  9.521   0.000   9.519

Solution

However, if we turn path from the default "auto" to "full", the speed issue is immediately gone

> system.time(res <- getPopStats(gs, path = "full"))
   user  system elapsed 
  0.558   0.000   0.559

Explanation

The default path = 'auto' will try to grow the gating path for each node from bottom toward the root. During the process, it needs to stop at each ancestor and check if the current partial path is unique within the tree. The potential overhead could be resulted from the exception catching during the check. For now, simply setting path = 'full' will do. The reason we keep auto as the default was the shortest-unique-partial-path is more human readable and the speed difference was typically unnoticeable for regular-sized tree. (@gfinak , let me know what your preference is and we can easily change the default if makes more sense) We can loop back to tackle the auto case when it is needed for the use case like this size.

[mikejiang]

Here is the results from the real gs generated by faust

> length(getNodes(gs))
[1] 948
> system.time(leaf <- get_leaf_nodes(gs))
   user  system elapsed 
  0.071   0.004   0.075 
> system.time(res <- getPopStats(gs, sub = leaf, path = "full"))
   user  system elapsed 
  7.384   0.000   7.384 
> system.time(res <- getPopStats(gs, sub = leaf))
   user  system elapsed 
150.572   0.000 150.561 

[mikejiang]

After eliminating the exception from the shortest-unique-path-check, the speed doesn't seem to improve significantly for path = 'auto' case

> system.time(res <- getPopStats(gs, sub = leaf))
   user  system elapsed 
132.705   0.012 132.718 

It means the computation time resides in gating path matching process(involves tree traversing) when checking the uniqueness of each partial path candidate. I don't see anyway around it at this moment. Maybe add concurrency to getPopStats will help.

[mikejiang]

With parallel (on 4 cores), total elapsed time is decreased in proportion to number of threads.

> system.time(res <- getPopStats(gs, sub = leaf, path = "auto"))
   user  system elapsed 
182.220   0.135  45.973 

[mikejiang]

With RGLab/cytolib@f0540930ccc86c9c2a397152b225d99f24a3b27a, getPopStats for auto path finally speeds up

> system.time(res <- getPopStats(gs, sub = leaf, path = "auto"))
   user  system elapsed 
 25.916   0.010   8.786 

[SamGG]

Very nice work!