Data transformations (meta bug)

[gregtatum]

In order to properly fix charging to callers and other Quantum Flow related filtering requests we need to re-architect how we filter and transform the data. I realized I didn't have an issue opened to track it, and it's blocking important features. Here is what needs to happen.

Work blocking filtering features

• Testing and/or flow typing existing code to ensure refactors do not break things. Add flow to process-profile.js and symbolication.js #434
• Remove the FuncStackTable in favor of a selector over the profile that effectively does the same thing, but uses the StackTable data structure. (abandoned)
• Change our profile data structure to provide a mapping from original IDs to transformed IDs (abandoned)
• Implement data transformation stack that you can push transformations onto. It cannot be arbitrarily re-ordered, but transforms can be popped off from the stack.
• Charge to call node to caller. Merge to caller #521
• Issue Charge to callers #242 Charge function to caller

Continue working on other data transformations

• Data transform: Focus on a function (not on a call node) #409 Focus on a function (not a call node)
• Data transform: Collapse recursion #243 Collapse recursion
• Data transform: Collapse all functions in a given namespace #244 Collapse all functions in a given namespace
• Data transform: Collapse all functions in a given file path #544 Collapse all functions in a given path
• Data transform: Collapse a subtree #545 Collapse subtree

@bzbarsky, @bholley I created this meta bug, since there is some work spread across multiple issues, and I'd like to keep you both up to speed on what I'm working on, since some of it is non-obvious that it's blocking some of the filtering features.

[bholley]

This is awesome - thanks Greg! Feel free to ping me if the usefulness or priority of anything is unclear.

[gregtatum]

I'm making some progress on the second bullet point:

Remove the FuncStackTable in favor of a selector over the profile that effectively does the same thing, but uses the StackTable data structure. This will allow for stable indices into tables as the data transforms.

#458

It's a bit slow going. My next step will be to attempt to rip out the existing implementation with funcStacks.

[gregtatum]

We've been (slowly) working through a solution for making this work through conversations on Slack. Here's the current gameplan, I'll update the bullet points above as needed.

• Complete the removal of FuncStacks in favor of a deDuplicateFunctionFrames selector
• Change call tree filters to use frame paths with transformed (deduplicated) frame indexes instead of function paths.
• Provide proper URL versioning, and a way to upgrade profile URLs to take this change into account

Send in PR

• Implement a transform stack that you can push onto.
• It doesn't allow for arbitrary re-ordering of transforms, only popping off of transforms.

Send in PR

• Complete charging to caller work, by adding it as a transform that works on the transform stack.

[gregtatum]

My removal of funcStacks is failing in ways that our current tests are not helpful. I created PR #476 for adding more granular tests to help move this work along, which is much more explicit in how it asserts the shape of the generated call tree. It will good for the additional data transformation work as well.

[gregtatum]

I decided not to move forward with my plans to remove the funcStack tables and may mapping of stack indexes during transformations. I found that my assumptions about how things could work were not correct. I did end up getting some new tests and documentation out of the work. The actual work I was able to salvage is as follows.

#476
#498
#495
#497

For a detailed explanation of my findings and current plan with the data transformations please read the following documentation I wrote. At this point re-ordering transformations is an open question, although it's clear that Instruments is able to do it. We're finding that each transformation is dependent on the current graph of the call tree, and once operations are re-ordered, our information stored becomes invalidated.

[bholley]

FWIW, I don't think re-ordering transformations is important. Stack-ordering is totally logical from my perspective, and at first glance I would not assume that all the transformations must be arbitrarily composable.

[gregtatum]

I have a PR open for data transformations:

#512

[gregtatum]

PR #512 is merged in, now I need to update my implementation of charge to caller to use the new transform stacks 💪

In addition we now have new testing infrastructure in place to assert valid transformation.

I'm getting close!

[gregtatum]

I have charging working on an un-inverted call tree. I'm still working on the inverted call tree.

[gregtatum]

Charging a call node to caller is landed and deployed. Charging a function to caller is in review. I used the word "merge" instead of "charge" for these operations. Things are moving much faster now that the we've refactors, have lots of docs, and tests to support these changes. If you want any additional transformations that are not listed here, now is the time to request them as all of this work is really top-of-mind for me.

[gregtatum]

@bholley @bzbarsky charging a function is deployed, you may need to refresh to see it. It's currently called "Merge function into caller across the entire tree"

[bholley]

Great! I'll try them out tomorrow. Is "Focus on all topmost calls to this function ignoring everything above" in the pipe? That would be very useful for us to analyze all the DoProcessPendingRestyles calls together, which can be triggered from lots of different places.

[gregtatum]

That's what I'm working on right now and is #409.

[gregtatum]

I'm going to close this bug as Q3 work is wrapping up and it's a little outdated at this point and I think this issue has served its purpose. Most of the architecture work that was hard to follow has been completed. There are still a few transforms that are in the backlog, but we have a label data-transform that can be used to track the outstanding issues. I have 2 more transforms in the review process (collapse libraries, and collapse recursion)

We're still planning on completing the transform work, and landing some new UI around searching, but we'll most likely change our primary focus for Q4. The broader architecture changes are implemented, and implementing transforms is a much more straightforward process. Please continue to comment on any issues that are blocking your work.

Current call tree transformation list in my dev environment:

[bholley]

I just played around with some of this stuff for the frame constructor, and it work great. Thank you @gregtatum!

One missing piece (which I think we discussed before) is the ability to exclude functions and their descendants (i.e. "I know about this stuff, drop it from the profile so I can see what's left"). Would that be a straightforward thing to implement on top of the new transformation machinery? It would greatly benefit our efforts to expand and extend the stylo architecture.

[jrmuizel]

One missing piece (which I think we discussed before) is the ability to exclude functions and their descendants

Instruments has this feature and it is indeed useful.

[gregtatum]

@bholley I believe this would be the Collapse subtree transform. This is going to be my next transform to work on as I really want it too! I got a little bogged down on work focusing on the web developer workflow this quarter, but I do plan to chug through the remaining transforms on the side.

All of the remaining transform work is under the data transform label.

Also thanks for chiming in on features you are still needing, as this helps us prioritize the work as we go through it.

[jrmuizel]

Instruments has 'Prune [symbol] and subtrees' that's different from 'Collapse subtree' because it just removes those samples.

[gregtatum]

@jrmuizel I believe a "collapse subtree" and then "merge node" (this is "charge to caller" in instruments but for a specific node, not all functions) is the same operation. Also to be clear on terminology (because this is hard to talk about) we're modifying the shape of the call tree, not actually removing any samples.

We're trying to pick some consistent words to describe our operations, and will eventually have some support graphics explaining technically what is happening to the nodes.

Collapse: any operation that takes multiple call tree nodes, and merges them together into a new node. e.g. collapse subtree, collapse recursion

Merge: Any operation that takes a call tree node and charges its self time to the calling function, and removes the node. This could be for a single node, or multiple functions.

Focus: Set the node or function as the root node, remove all parents, and then recompute the call tree.

[jrmuizel]

Ok, it's worth noting having the ability to prune/drop samples is valuable functionality. This lets you get rid of noise that you're not interested in or otherwise don't care about.

[gregtatum]

@jrmuizel Could you describe what a prune operation looks like?

Given the following 3 samples:

A -> B -> C
A -> B -> C -> D
A -> B -> E

Produces this call tree:

A -> B -> C -> D
       \
        E

Then you could prune function C across the entire tree:

Gives these samples:

A -> B
A -> B
A -> B -> E

And then has this call tree:

A -> B -> E

With the self times:

A: 0
B: 2
E: 1

Which in this case would not remove any samples. Could you describe the operation you had in mind? This is what I think of when I hear of a "prune" operation.

[jrmuizel]

Pruning C would drop any samples that contain C in the stack. So given:

A -> B -> C
A -> B -> C -> D
A -> B -> E

Pruning C transforms this to:

A -> B -> E

With the self times:

A: 0
B: 0
E: 1

[gregtatum]

Which of the following would you want?

A -> B -> C
A -> B -> C -> D
A -> C
A -> B -> E

Prune function C:

A -> B -> E

Or prune call node A -> B -> C:

A -> C
A -> B -> E

I will file a new bug for this.

[bholley]

I think both "prune function" and "prune subtree" would be useful. The former lets you prune certain kinds of work (i.e. "ignore any styling that happens in frame construction so that I can focus on frame construction proper"), while the latter lets you slice and dice a large function, analyzing each callee and then pruning it to see what's left.

If I had to pick one, I'd probably pick the former, but hopefully they're both relatively easy to implement?

Thanks Greg!