Tree with 20k+ nested nodes

[mm-shah]

Hi,

I'm trying to create a searchable tree with 24k nested nodes but it takes forever for the tree to be rendered. I tried using a subset of the nodes (1.3k) and it took 10 secs to render. I have the contents in form of a list of lists. Here is the code:

library(shinyWidgets)
library(shinyTree)
load(GOlist.Rdata)
sub <- list('Biological Process' = bp_list[[1]],
            'Molecular Function' = mf_list[[1]],
            'Cellular Component' = cc_list[[1]])
ori <- list('Biological Process' = bp_list,
            'Molecular Function' = mf_list,
            'Cellular Component' = cc_list)
ui <- fluidPage(dropdownButton(circle = F, label = "Select GO groups...",
                        shinyTree('go',checkbox=T,search=T,animation=FALSE,theme='proton')))
server <- function(input, output){output$go <- renderTree({sub})}
shinyApp(ui = ui, server = server)

Here, is the file which contains the list for each subcategroy. GOlist.zip

I'd like something like this but to be able to render 24k nodes.

I understand the packages uses jsTree in the background and after searching online I came across progressive_render https://stackoverflow.com/questions/13509542/jstree-rendering-optimization-very-long-rendering-with-2000-nodes

progressive_render A Boolean. Default is false. If this option is set to true only the visible (open nodes) parts of the returned JSON are converted to DOM nodes, any hidden parts are saved away and parsed ondemand (when a node becomes visible). This is useful when you have a large nested tree which would result in a heavy DOM

I was wondering if anyone can help me use progressive_render in with shinyTree.

Thanks!

[trafficonese]

I dont know if that option is still available. The link from that SO answer is not pointing to something called "progressive_render". I also couldnt find it in the source code of jsTree.

[mm-shah]

@trafficonese Yes, there seems to be an issue with the link. I have no additional information on progressive render other than this this github link shared in this question . Another thing I'd like to suggest is to implement lazy loading in shinyTree, i.e. only child nodes of a parent are shown at a time and server renders more nodes when called.

[trafficonese]

I think progressive_render is already the default of jsTree, if you look at the HTML of the tree.

There is only HTML for the nodes that are visible and as soon as you open a node, new HTML will be inserted in the body.

But the R code does not care if the node is visible or not, it will always go through all list elements (in get_flatlist), so I think there is the bottleneck for massive trees.

This function could definitly be optimized and maybe exported to C++, but maybe you're better of forking the package and creating an optimized and customized get_flatlist function for the tree you require. You could probably also omit the fixIconName function and give the icon-string directly. This would already save you quite some time.

You might also consider switching from jsonlite to rjson for the toJSON function in Rlist2json. It does not produce identical results right out of the box, but if you include this line, it might be identical: gsub(d, pattern = "null", fixed = TRUE, replacement = "{}") and is slighlty faster. You can also look up my fork, where I played around with the mentioned ideas.

Little example to play around, which is already quite slow for 8000 total nodes (20 root nodes, 200 sub-nodes and 2 sub-sub-nodes):

library(shiny)
library(shinyTree)

tree <- rep(list(
  root1 = rep(list(
    SubListA = list(leaf1 = "", leaf2 = ""),
    SubListB = structure(list(leafA = "", leafB = ""))
  ),100),
  root2 = rep(list(
    SubListA = list(leaf1 = "", leaf2 = ""),
    SubListB = structure(list(leafA = "", leafB = ""))
  ), 100)
), 10)

ui <- fluidPage(
  shinyTree("tree", checkbox = TRUE)
)

server <- function(input, output, session) {
  output$tree <- renderTree({
    tree
  })
}

shinyApp(ui, server)

[trafficonese]

I made a gist with 2 optimized functions and some benchmarking. You will see that the "Optimized 2" functions are almost 4 times faster than the original functions.

Here's the benchmark result:

> Unit: seconds
>  expr      min       lq     mean   median       uq      max neval
>     a 3.997309 4.056221 4.089866 4.096501 4.143633 4.155666     5
>     b 1.591382 1.598335 1.683710 1.649939 1.754972 1.823923     5
>     c 1.003630 1.023259 1.098210 1.090561 1.155245 1.218355     5

And you might also try out jsonify which is also considerably faster than jsonlite and produces identical results right out of the box.

mc <- microbenchmark::microbenchmark(times = 10,
  jsonlite = jsonlite::toJSON(get_flatList2(tree)),
  rjson    = rjson::toJSON(get_flatList2(tree)),
  jsonify  = jsonify::to_json(get_flatList2(tree))
); mc

> Unit: milliseconds
>      expr       min        lq     mean   median       uq      max neval
>  jsonlite 2624.7578 2809.9325 2838.483 2855.127 2881.626 3034.711    10
>     rjson  938.0947  960.5565 1050.257 1028.163 1163.452 1201.784    10
>   jsonify 1242.0977 1325.1063 1380.966 1353.156 1390.430 1715.114    10

@schaffman5, @bellma-lilly: Could we switch to jsonify or is there a particular reason to keep jsonlite?

[trafficonese]

Just an update since I found the new package yyjsonr and it's much faster. Here is some data & benchmarks. Almost 4 times faster than rjson and jsonify and more than 200 times faster than jsonlite. 💣 🎉

The only difference is that yyjsonr will return a character object and not a json object, but that should not matter for shinyTree.

library(shinyTree)
library(rjson)
library(jsonlite)
library(jsonify)
library(yyjsonr)

treelist <- rep(list(
  root1 = rep(list(
    SubListA = list(leaf1 = "", leaf2 = ""),
    SubListB = structure(list(leafA = "", leafB = ""))
  ),10),
  root2 = rep(list(
    SubListA = list(leaf1 = "", leaf2 = ""),
    SubListB = structure(list(leafA = "", leafB = ""))
  ), 10)
), 10)

flatlist <- shinyTree:::get_flatList(treelist)
mc <- microbenchmark::microbenchmark(
  times = 10,
  jsonlite = jsonlite::toJSON(flatlist),
  rjson    = rjson::toJSON(flatlist),
  jsonify  = jsonify::to_json(flatlist),
  yyjsonr  = yyjsonr::write_json_str(flatlist,opts = opts_write_json(auto_unbox = TRUE))
); mc

Unit: microseconds
     expr      min       lq      mean    median       uq      max neval
 jsonlite 180623.2 183495.6 186043.08 186004.80 187672.6 191801.9    10
    rjson   3013.5   3410.5   3919.71   3660.75   3813.8   7101.5    10
  jsonify   3341.9   3611.8   4638.47   4083.30   5013.5   7989.6    10
  yyjsonr    793.3    838.9   1427.56   1197.25   1684.0   3437.6    10