Understand where styler spends most of the time

[krlmlr]

This is crucial for #558.

Because we use mostly recursive calls, and effectively each function can call each other function, I suspect it is difficult to see where exactly styler spends most of its time, and which parts perhaps should be optimized. Can you confirm that?

To work around, I propose processing the .Rprof files created from a profiler run. If we erase the right places from the call stack for each sample, we might just end up with a clean flat structure that immediately shows where the time is spent. What do you think?

Alternatively, we could (temporarily) replace the recursive calls with later::later() or replace recursion with a queue and a while {} loop. Editing the call stack sounds like less work.

[lorenzwalthert]

The recursive calls are time consuming, yes. In particular, there are two important recursions:

• building the nested parse table in compute_parse_data_nested()
• apply the transformer rules in apply_transformers()

I can't remember correctly but I think they take up similar amount of time. Recently, there were two important speed improvements made (speed change in unseen example code benchmarked with the {here} package). #739 removed unnecessary sorting in merge() inside a recursion since we sort right afterwards anyways (-4%) and in #711, transformers that are never used are removed (-10%).

That said, I think your proposed approach sounds interesting. I can confirm that it's hard for me to understand where bottlenecks are. I already spend quite some time optimising R code, maybe not very systematically though. And I think the cost/benefit ratio is too high for me now. I think time is better spent on parallelisation at the moment. I think the latest release (1.4.0) introduced speed improvements of about 25%+ with the few changes described in the NEWS.md, but then there were edge case fixes and new features that slowed things down again in this release, leaving us with like 15% diff. Because minor changes were always so hard to measure, I built {touchstone}, so now every PR is benchmarked and we benchmark against the current release as well on merge in master and for all new code, I tried to write is as efficient as possible while keeping it maintainable and understandable. You can find the speed implications under the comment PR step in the benchmarking workflow:

I am not familiar enough with {later} to comment on whether or not we should use it. I just think moving large parts of the code base into C++ would force me to learn C++, which I want to avoid xD.

[IndrajeetPatil]

@lorenzwalthert If this is still up for grabs, I would be happy to work on trying to improve performance using C++ (via {cpp11} package).

I just think moving large parts of the code base into C++ would force me to learn C++, which I want to avoid xD.

LOL, I have the opposite problem where I have learned a fair bit of C++, but haven't found a "real" project to contribute to.

I should mention though that I'd be slow to implement this because I can work on FOSS projects only during free time, and not during office hours.

Lemme know if that works for you, and I can get started by creating a fork. :)

[lorenzwalthert]

Thanks @IndrajeetPatil, I really appreciate your offer. Using C++ code in {styler} is quite a big decision that comes with a number of implications, so I think this needs to be well thought out. As @krlmlr said, we first need to identify the bottlenecks before starting implementing C++ functionality. Also, I would not be able to review your pull requests, we'd have to ask @krlmlr to do that. Would you have time to review these PRs @krlmlr?

That being said, would you want to start witht he profiling as Kirill suggested?

[IndrajeetPatil]

would you want to start witht he profiling as Kirill suggested?

On it!

Also, I would not be able to review your pull requests, we'd have to ask @krlmlr to do that

Yes, I would really appreciate if he could do that! :)

[krlmlr]

Thanks. I agree profiling should be the first step.

There are four steps:

• Parsing (done by base R, should be fast enough)
• Nesting of parse data (compute_parse_data_nested())
• Walking the parse data (apply_transformers() and the transformers)
• Composition of the styled text

Optimizing the third part will be hardest. Do we have a good understanding which parts take how long for a typical file?

Of course caching should be off in all experiments.

[lorenzwalthert]

I agree @krlmlr and I added the names of the functions that are relevant in your post.

In addition, I want to highlight that styling rules that we know are not affecting the code are removed before all transformers are applied. Which tokens affect which rules is specified in transformers_drop argument in create_style_guide(). See #711 and the doc of create_style_guide().

[IndrajeetPatil]

Thank you both for pointers on what might be the best places to start digging into this.

Will keep you posted as I go through them.

[krlmlr]

I took another look at styling performance.

With the two new PRs combined, and when replacing %>% with |>, we now finally get usable stack traces when profiling. With proffer::pprof(filter.callframes = TRUE, line.profiling = TRUE), we get a helpful call graph. With profvis() we would need to post-process the stack traces to remove recursive calls, should be easy to do with {profile}.

For a small-ish file from this repo, R/nest.R, the overhead (nesting and composition of the styled text) takes the lion's share of the time. Composition looks like an easy target, optimizing the nesting will be a bit trickier.

For easier profiling, it seems useful to specifically isolate the time spent styling from the overhead, by temporarily injecting calls to Rprof(...) and Rprof(NULL) in the appropriate places.

By and large, a whole lot of time seems to be spent in $<-.tbl_df() . Could we get noticeable results by consistently using unclass(pd_flat) and new_tibble(pd_flat)?