Dependency Graph Evaluation Optimizations #75208

New Issue

Jeroen Bakker · 2020-03-30T09:14:41+02:00

Jeroen Bakker commented

2020-03-30 09:14:41 +02:00

During Animation Playback performance analysis we detected some areas the dependency graph evaluation could be improved.

- Store RNA_path_resolve during dependency graph build
  ** Design Note: If RNA_path_resolve points to a sub-data of ID you are in trouble as CoW pointers aren't available on build time.
- Reference Custom Data layers During Viewport Dependency Graph Evalution
- minimize number of relations and nodes.
  ** we should make sure transitive reduction works fine. and remove unused nodes

During Animation Playback performance analysis we detected some areas the dependency graph evaluation could be improved. * - [ ] Store RNA_path_resolve during dependency graph build ** Design Note: If RNA_path_resolve points to a sub-data of ID you are in trouble as CoW pointers aren't available on build time. * - [ ] Reference Custom Data layers During Viewport Dependency Graph Evalution * - [ ] minimize number of relations and nodes. ** we should make sure transitive reduction works fine. and remove unused nodes

Jeroen Bakker commented

2020-03-30 09:14:41 +02:00

Added subscriber: @Jeroen-Bakker

Jeroen Bakker commented

2020-03-30 09:15:07 +02:00

This comment was removed by @Jeroen-Bakker

*This comment was removed by @Jeroen-Bakker*

Jeroen Bakker commented

2020-03-30 09:15:47 +02:00

Changed status from 'Needs Triage' to: 'Confirmed'

Paul Szajner commented

2020-04-03 03:45:48 +02:00

Added subscriber: @sozap

Sergey Sharybin commented

2020-04-14 10:53:14 +02:00

Added subscriber: @Sergey

Sergey Sharybin commented

2020-04-14 10:53:14 +02:00

Store RNA_path_resolve during dependency graph build
Design Note: If RNA_path_resolve points to a sub-data of ID you are in trouble as CoW pointers aren't available on build time.

Other notes:

Builder does not resolve all RNA paths. It does resolution for drivers, but not for f-curves in actions.
Builder works in a single thread, so adding more resolutions than needed will give a huge penalty.
Builder resolves paths in original datablocks. So you can not re-use resolution result to access properties in evaluated (copy-on-written datablock).

So it's either something like evaluation cache stored in ID which will try to re-use resolved path if it is known. Just similar to how simple Python expressions are parsed and stores. Or, builder would need to do actual datablock copy and switched to work on copied objects (but then sub-data pointers are still a problem).

Reference Custom Data layers During Viewport Dependency Graph Evalution

For the viewport is fine.

For render is safer to copy them rather than reference. Same for dependency graphs which might be used to evaluate same subset of scene from multiple threads.

I would also add TBB flow graphs here. Seems like natural fit, which should reduce amount of code to maintain from our side.

> Store RNA_path_resolve during dependency graph build > Design Note: If RNA_path_resolve points to a sub-data of ID you are in trouble as CoW pointers aren't available on build time. Other notes: - Builder does not resolve all RNA paths. It does resolution for drivers, but not for f-curves in actions. - Builder works in a single thread, so adding more resolutions than needed will give a huge penalty. - Builder resolves paths in original datablocks. So you can not re-use resolution result to access properties in evaluated (copy-on-written datablock). So it's either something like evaluation cache stored in ID which will try to re-use resolved path if it is known. Just similar to how simple Python expressions are parsed and stores. Or, builder would need to do actual datablock copy and switched to work on copied objects (but then sub-data pointers are still a problem). > Reference Custom Data layers During Viewport Dependency Graph Evalution For the viewport is fine. For render is safer to copy them rather than reference. Same for dependency graphs which might be used to evaluate same subset of scene from multiple threads. I would also add TBB flow graphs here. Seems like natural fit, which should reduce amount of code to maintain from our side.

Chris Kohl commented

2020-04-29 22:37:11 +02:00

Added subscriber: @ckohl_art

Jeroen Bakker commented

2020-05-08 14:01:43 +02:00

In #75208#909376, @Sergey wrote:

I would also add TBB flow graphs here. Seems like natural fit, which should reduce amount of code to maintain from our side.

The challenge with TBB flow graphs is that a join_node can have max 10 pending tasks. Some options to overcome this limitation are:

stack several join_nodes, but this has a penalty and the general advice is not to do this, but use a different scheduling.
Only schedule parts of the graph that fit within this limitation and schedule the rest when the pending tasks of a node becomes equal or less then 10. This is tricky as this changes the tree during execution and requires a fence.
Only schedule parts that have a 0 or 1 parent. Schedule children only when they get 1 parent. This fits in the current implementation of D7578: Task: Graph Flow Task Scheduling.
Schedule only a child when all the parents have been executed. This does not fit the TBB flow graph anymore and we should keep the current implementation.

Looking at it I wouldn't bet too much on TBB flow for depsgraph evaluation, without making sure that num_links_pending fits within this limitation.

> In #75208#909376, @Sergey wrote: > I would also add TBB flow graphs here. Seems like natural fit, which should reduce amount of code to maintain from our side. The challenge with TBB flow graphs is that a join_node can have max 10 pending tasks. Some options to overcome this limitation are: * stack several join_nodes, but this has a penalty and the general advice is not to do this, but use a different scheduling. * Only schedule parts of the graph that fit within this limitation and schedule the rest when the pending tasks of a node becomes equal or less then 10. This is tricky as this changes the tree during execution and requires a fence. * Only schedule parts that have a 0 or 1 parent. Schedule children only when they get 1 parent. This fits in the current implementation of [D7578: Task: Graph Flow Task Scheduling](https://archive.blender.org/developer/D7578). * Schedule only a child when all the parents have been executed. This does not fit the TBB flow graph anymore and we should keep the current implementation. Looking at it I wouldn't bet too much on TBB flow for depsgraph evaluation, without making sure that `num_links_pending` fits within this limitation.

RedMser commented

2020-08-29 21:50:57 +02:00

Added subscriber: @RedMser

Sybren A. Stüvel commented

2020-11-20 12:20:26 +01:00

Added subscriber: @dr.sybren

Sybren A. Stüvel commented

2020-11-20 12:20:26 +01:00

This task doesn't contain enough information to actually work on it. Since there is some discussion going on, I've reclassified it as Design task.
See the 2020-11-12 module meeting notes for more information.

This task doesn't contain enough information to actually work on it. Since there is some discussion going on, I've reclassified it as Design task. See the [2020-11-12 module meeting notes](https://devtalk.blender.org/t/2020-11-12-animation-rigging-module-meeting/16092) for more information.

Garek commented

2021-12-21 07:21:33 +01:00

Added subscriber: @Garek

Philipp Oeser removed the

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Dependency Graph Evaluation Optimizations #75208