Faster code analysis

[wlandau]

Related: #41. The code analysis for automatic dependency detection is the biggest bottleneck in initialization. A couple goals:

1. Detect true globals in the existing recursion so we can avoid codetools::findGlobals().
2. Consider a custom C++ backend for the code analysis.

I think we should do (1) before (2).

[wlandau]

So apparently, we can remove a lot of overhead just by removing calls to parse(). Here is a profvis for a really long command. I was using a custom is_parsable() to filter out bad symbols, and calling it too often resulted in a lot of this overhead. Similarly, we could probably avoid calls to wide_deparse(), which calls deparse().

[wlandau]

After #574, the benchmarks look much better.

library(drake)
n <- 1000
x <- parse(
  text = paste0(
    "max(",
    paste0(paste0("target_", seq_len(n)), collapse = ", "),
    ")"
  )
)[[1]]
pkgconfig::set_config("drake::strings_in_dots" = "literals")
profvis::profvis(drake:::command_dependencies(x))

^{Created on 2018-11-05 by the reprex package (v0.2.1)}

[wlandau]

Now, the bottleneck really is codetools.

[wlandau]

I plan to emulate codetools::findGlobals() by inserting steps in drake's existing code_dependencies() function to check for local variables. Some relevant functions in codetools:

• getCollectLocalsHandler()
• collectUsageFun()
• collectLocalsAssignHandler()
• collectLocalsForHandler()
• collectLocalsLocalHandler()

[wlandau]

I learned a lot from the codetools source, particularly getCollectLocalsHandler(). We can modify code_dependencies() to catch locals.

• Change the name of the globals argument of command_dependencies(). It should be called allowed_globals.
• Add an exclude argument to walk() for the recursion. Start with the strings in the exclude argument to code_dependencies(). Use an environment-based hash table so the excluded variables carry over to the appropriate recursion steps that follow.
• Turn the allowed_globals argument into its own hash table.
• Before appending a variable to results$globals, verify that it is not in exclude and it is in allowed_globals. This is where hash tables could really speed things up.
• Do not hold onto the locals found in function definitions (either the arguments or the body) or calls to local(). For these cases, make a deep copy of exclude before calling walk(). Creating this deep copy may or may not be slow enough to create a bottleneck. We need to check with profiling.
• Preregister function argument names in this deep copy of exclude.
• Walk the default values of function arguments as well as the body.
• Record local variables assigned with =, <-, and ->.
• If assign() or delayedAssign() is detected, do a match.call() and x to exclude.
• Do not analyze calls to quote(), Quote(), and expression().
• Add a ton of special tests to compare codetools to drake's code analysis. They should agree on the most important points. We can precompute the expected results so we can remove codetools from the stack entirely instead of putting it in Suggests:.

I will implement this in branch 573. The merge into master will be after tomorrow's CRAN release of drake 6.2.0. (I need to release 6.2.0 tomorrow because it ensures compatibility with development tibble, which in turn goes to CRAN on December 17.)

[wlandau]

To close this issue, it is enough to:

• Merge Code analysis without codetools #625.
• Address the edge case described in Code analysis without codetools #625.
• Do more profiling.

[wlandau]

In #625, the bottleneck seems to appending stuff results$globals. Maybe we should use a hash table.

[wlandau]

The last thing I will try before closing this issue is to pre-compute an ignored_symbols_list, a list that we can use for creating and populating locals faster (using list2env(hash = TRUE)) at the beginning of analyze_code(). After that, we can work on improvements on a case-by-case basis.

[wlandau]

As of 4cce238, I think I have exhausted the lowest-hanging fruit to speed up the code analysis. A lot more work needs to be done to speed up drake overall. Issues like this one are coming up (though I do not know if OP was using version 6.2.1, which is faster than its predecessors).

I am closing this issue in favor of more targeted ones that will come up later.

[wlandau]

I will say that I could really use help with the profiling. Realistic test cases are usually too large for profvis to handle, and more targeted ones are not realistic enough to be useful. cc @bpbond.

[bpbond]

You mentioned this previously, and I'm happy to take a hard look if useful.

[wlandau]

Thanks, that would be fantastic! Profiling is going to be super important going forward.

I expect #630 will solve #572 and speed things up, but there will be more bottlenecks after that.

One thing I have noticed: profvis generates a ton of output, and even on my decently-powered Linux desktop, I cannot interact with the visuals generated by fully-fledged calls to make(). We may want to consider a static profiling tool. I have used used gperftools + pprof for Rcpp projects at work, and I think it might be nice to find something similar for R. Maybe jointprof?

[wlandau]

@bpbond, an update: #633 sped up drake quite a lot, and I am currently out of hypotheses about the next potential bottlenecks.

[wlandau]

I think what we're after is Rprof() + profile. The overhead example may be a good place to start.