Blender editing performance with many datablocks #73359

New Issue

Dalai Felinto · 2020-01-24T13:01:58+01:00

Dalai Felinto commented

2020-01-24 13:01:58 +01:00

Status: 1st milestone almost complete, need final optimizations.

Team
Commissioner: @brecht
Project leader: @mont29
Project members: @ZedDB
Big picture: In heavy scenes, new features in Blender 2.8x are making the inherently linear (O(N)), when not quadratic (O(N²)), complexity of most operations over data-blocks more problematic than in 2.7x era. The general goal is to bring those operations back to a constant (O(1)) or logarithmic (O(log(N))) complexity.

Description
Use cases:
Need specific test cases.

Undo changes in object mode in a heavy scene.
Undo changes in pose mode in a heavy scene.
Duplicating objects in a heavy scene.
Adding many objects in a scene.

Note: There are two types of “heavyness” in scenes (that can be combined of course):

Scenes that have many objects and/or collections.
Scenes that have very heavy geometry, either in the geometry data itself, or generated from modifiers like subdivision surface.

Design:

Dependency graph should not have to re-evaluate objects that did not change.

** This is mainly a problem currently during global undo, as all data-blocks are replaced by new ones on each undo step.

Handling naming of data-blocks should be `O(log(N))` (it is currently close to `O(N²)`, or `O(N log(N))` in best cases).

This will require caching currently used names.* We will probably also have to handle smartly the numbering in that cache, if we really want to be efficient in typical “worst case” scenarii (addition of thousands of objects with same base name e.g.).

Caches/runtime data helpers should be always either:
- Lazily-built/updated on-demand (code affecting related data should only ensure that the 'dirty' flag is set then).
  *** This approach can usually be easily managed in a mostly lock-less way in a threaded context (proper locking is only needed when actually rebuilding a dirty cache).

***Such cache should be easy to incrementally update (it should almost never have to be rebuilt from scratch).*This implies that the cache is highly local (changes on a data-block only ever affect that data-block and a well-defined, easy to reach small number of “neighbors”). In general keeping this kind of cache valid will always be harder and more error-prone than approach #A.
*** This approach often needs proper complete locking (mutexes & co) in a threaded context.

Note: The ViewLayer's collections/objects cache e.g. currently uses the worst mix of #A and #B - it is always assumed valid, but updating it requires a complete rebuild from scratch almost all the time.

Note: Approach #B is usually interesting only if a complete rebuild of the cache is very costly, and/or if the cache is invalidated very often while being used.

Engineer plan: -

Work plan

Milestone 1 - Optimized per-datablock global undo
Time estimate: 6 months

Re-use as much as possible existing data, and try to swap newly read (modified) data to the original memory, during 'memfile' undo step. Updating the depsgraph should then be much less work.
** #60695 (Optimized per-datablock global undo)
** D6580: WIP/Demonstration patch about undo speedup project.

Milestone 2 - Lazy collection synchronizations
Time estimate: 1 month

Fix view layer collection syncing (to not require looping over all objects, or to be ran much less often...).
** #73411 (Fix ViewLayers cache building)

Milestone 3 - Data-blocks management performances with many of them
Time estimate: 5 months

Investigate how to best handle naming conflicts issues.

Most obvious idea would be store all used base-names in a GHash (one per ID type), along with used indices. Needs further design though. #73412 (Improve name conflict handling in ID management)

Investigate the best way to cache bi-directional relationships info between data-blocks.

We already have a start of this with BKE_main_relations_create() & co, but it is heavily under-used and needs better design to be usable more widely. #73413 (Cache data-block relationships info )

Fix/Improve handling of the Bone pointers (which are sub-data of `Armature` ID) stored in poses (which are sub-data of `Object` ID).

Ideally such horrible pointers should not exist ever. They are a very solid recurrent source of bugs in Blender. Not sure how to best deal with them, at the very least we could add some generic ID API to ensure those kind of caches are up-to-date?

See also #68938 (Blender editing performance with many datablocks).

Later

Dependency graph rebuild to be O(1) or O(log(N)) (it is also O(N) at the moment). ???? would assume linear would already be nice performance for such a code?

Notes: -

**Status:** 1st milestone almost complete, need final optimizations. --- **Team** **Commissioner:** @brecht **Project leader:** @mont29 **Project members:** @ZedDB **Big picture:** In heavy scenes, new features in Blender 2.8x are making the inherently linear (`O(N)`), when not quadratic (`O(N²)`), complexity of most operations over data-blocks more problematic than in 2.7x era. The general goal is to bring those operations back to a constant (`O(1)`) or logarithmic (`O(log(N))`) complexity. **Description** **Use cases:** *Need specific test cases.* * Undo changes in object mode in a heavy scene. * Undo changes in pose mode in a heavy scene. * Duplicating objects in a heavy scene. * Adding many objects in a scene. *Note:* There are two types of “heavyness” in scenes (that can be combined of course): * Scenes that have many objects and/or collections. * Scenes that have very heavy geometry, either in the geometry data itself, or generated from modifiers like subdivision surface. **Design:** # Dependency graph should not have to re-evaluate objects that did not change. ** This is mainly a problem currently during global undo, as all data-blocks are replaced by new ones on each undo step. # Handling naming of data-blocks should be `O(log(N))` (it is currently close to `O(N²)`, or `O(N log(N))` in best cases). **This will require caching currently used names.*** We will probably also have to handle smartly the numbering in that cache, if we really want to be efficient in typical “worst case” scenarii (addition of thousands of objects with same base name e.g.). - Caches/runtime data helpers should be always either: - Lazily-built/updated on-demand (code affecting related data should only ensure that the 'dirty' flag is set then). *** This approach can usually be easily managed in a mostly lock-less way in a threaded context (proper locking is only needed when actually rebuilding a dirty cache). ## Kept valid/in sync all the time (code affecting related data should take care of updating it itself, code using the cache can always assume it is valid and up-to-date). ***Such cache should be easy to incrementally update (it should almost never have to be rebuilt from scratch).****This implies that the cache is highly local (changes on a data-block only ever affect that data-block and a well-defined, easy to reach small number of “neighbors”).*** In general keeping this kind of cache valid will always be harder and more error-prone than approach #A. *** This approach often needs proper complete locking (mutexes & co) in a threaded context. *Note: The ViewLayer's collections/objects cache e.g. currently uses the worst mix of #A and #B - it is always assumed valid, but updating it requires a complete rebuild from scratch almost all the time.* *Note: Approach #B is usually interesting only if a complete rebuild of the cache is **very** costly, and/or if the cache is invalidated very often while being used.* **Engineer plan:** `-` **Work plan** **Milestone 1 - Optimized per-datablock global undo** Time estimate: `6 months` * Re-use as much as possible existing data, and try to swap newly read (modified) data to the original memory, during 'memfile' undo step. Updating the depsgraph should then be much less work. ** #60695 (Optimized per-datablock global undo) ** [D6580: WIP/Demonstration patch about undo speedup project.](https://archive.blender.org/developer/D6580) **Milestone 2 - Lazy collection synchronizations** Time estimate: `1 month` * Fix view layer collection syncing (to not require looping over all objects, or to be ran much less often...). ** #73411 (Fix ViewLayers cache building) **Milestone 3 - Data-blocks management performances with many of them** Time estimate: `5 months` # Investigate how to best handle naming conflicts issues. **Most obvious idea would be store all used base-names in a GHash (one per ID type), along with used indices. Needs further design though.** #73412 (Improve name conflict handling in ID management) # Investigate the best way to cache bi-directional relationships info between data-blocks. **We already have a start of this with `BKE_main_relations_create()` & co, but it is heavily under-used and needs better design to be usable more widely.** #73413 (Cache data-block relationships info ) # Fix/Improve handling of the Bone pointers (which are sub-data of `Armature` ID) stored in poses (which are sub-data of `Object` ID). **Ideally such horrible pointers should not exist ever. They are a very solid recurrent source of bugs in Blender.** Not sure how to best deal with them, at the very least we could add some generic ID API to ensure those kind of caches are up-to-date? See also #68938 (Blender editing performance with many datablocks). **Later** * Dependency graph rebuild to be `O(1)` or `O(log(N))` (it is also `O(N)` at the moment). *???? would assume linear would already be nice performance for such a code?* **Notes:** - ---

Dalai Felinto commented

2020-01-24 13:01:58 +01:00

Added subscribers: @ZedDB, @mont29, @dfelinto

MACHIN3 commented

2020-01-24 19:10:25 +01:00

First-time contributor

Added subscriber: @MACHIN3

Ted Milker commented

2020-01-25 01:12:30 +01:00

First-time contributor

Added subscriber: @Teds

Johannes Kollmer commented

2020-01-25 01:35:09 +01:00

First-time contributor

Added subscriber: @Lumpengnom-3

Michael Weisheim commented

2020-01-25 01:54:54 +01:00

First-time contributor

Added subscriber: @MichaelWeisheim

Roman commented

2020-01-26 11:24:06 +01:00

First-time contributor

Added subscriber: @rwman

Bastien Montagne commented

2020-01-26 18:42:45 +01:00

Edited task, sorted stage 2 sup-steps in order I think is the most relevant, and added sub-tasks for all those three ones.

Please not that this is still very vague, and mostly there to keep track of random ideas at this point. Proper technical design is still required, stage 2 is not likely to happen in immediate coming months anyway.

Edited task, sorted stage 2 sup-steps in order I think is the most relevant, and added sub-tasks for all those three ones. Please not that this is still very vague, and mostly there to keep track of random ideas at this point. Proper technical design is still required, stage 2 is not likely to happen in immediate coming months anyway.

swann commented

2020-01-26 23:10:04 +01:00

First-time contributor

Added subscriber: @slumber

Andrew Charlton commented

2020-01-28 01:46:57 +01:00

First-time contributor

Added subscriber: @Scaredyfish

Aditia A. Pratama commented

2020-01-28 08:05:33 +01:00

Added subscriber: @AditiaA.Pratama

Dalai Felinto changed title from ~~Scene editing in object mode~~ to Blender editing performance with many datablocks

2020-01-28 12:24:16 +01:00

Dylan Colli commented

2020-01-28 18:01:42 +01:00

First-time contributor

Added subscriber: @dcolli23

Pipeliner commented

2020-01-29 12:58:09 +01:00

First-time contributor

Added subscriber: @Pipeliner

Pipeliner commented

2020-01-29 12:58:13 +01:00

First-time contributor

Removed subscriber: @Pipeliner

Pipeliner commented

2020-01-29 12:58:16 +01:00

First-time contributor

Added subscriber: @Pipeliner

Tchelet Levi commented

2020-01-30 11:49:11 +01:00

First-time contributor

Added subscriber: @MizManFryinPan

Duarte Farrajota Ramos commented

2020-02-04 16:18:13 +01:00

First-time contributor

Added subscriber: @DuarteRamos

Manuel Albert commented

2020-02-05 07:45:49 +01:00

First-time contributor

Added subscriber: @ManuelAlbert

Daniele commented

2020-02-10 11:07:06 +01:00

First-time contributor

Added subscriber: @elven_inside

Campbell Barton commented

2020-02-12 08:29:06 +01:00

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

Vladimir commented

2020-02-14 13:29:27 +01:00

First-time contributor

Added subscriber: @VladimirKunyansky

Paul Kotelevets commented

2020-02-20 00:09:51 +01:00

First-time contributor

Added subscriber: @1D_Inc

Paul Kotelevets commented

2020-02-20 00:09:51 +01:00

First-time contributor

In #73359#858877, @mont29 wrote:

Please not that this is still very vague, and mostly there to keep track of random ideas at this point. Proper technical design is still required, stage 2 is not likely to happen in immediate coming months anyway.

Of course, algorithmization is primarily a complex mathematical problem.
(One of my favorite explanations for the big O notations )

> In #73359#858877, @mont29 wrote: > Please not that this is still very vague, and mostly there to keep track of random ideas at this point. Proper technical design is still required, stage 2 is not likely to happen in immediate coming months anyway. Of course, algorithmization is primarily a complex mathematical problem. ([One of my favorite explanations for the big O notations ](https://stackoverflow.com/a/2307314))

Dion Moult commented

2020-03-06 06:19:32 +01:00

First-time contributor

Added subscriber: @Moult

Yianni Papazis commented

2020-03-08 15:54:42 +01:00

First-time contributor

Added subscriber: @Yianni

Jacques Lucke commented

2020-05-01 11:39:02 +02:00

Added subscriber: @JacquesLucke

Dalai Felinto commented

2020-05-19 14:45:50 +02:00

Added subscriber: @brecht

Emir Sinan Gürlek commented

2020-05-25 23:21:32 +02:00

First-time contributor

Added subscriber: @filibis

Chingiz Jumagulov commented

2020-06-01 13:03:26 +02:00

First-time contributor

Added subscriber: @MeshVoid

RedMser commented

2020-09-12 22:45:23 +02:00

Added subscriber: @RedMser

Tone Dragos commented

2020-11-14 18:24:51 +01:00

First-time contributor

Added subscriber: @Noto

Michael Hermann commented

2021-04-09 00:29:12 +02:00

First-time contributor

Added subscriber: @MichaelHermann

Christopher Gearhart commented

2021-04-18 08:31:04 +02:00

First-time contributor

Added subscriber: @bblanimation

Pauan commented

2021-05-01 04:41:24 +02:00

First-time contributor

Added subscriber: @pauanyu_blender

Philippe Crassous commented

2021-05-03 12:14:16 +02:00

First-time contributor

Added subscriber: @PhilippeCrassous

Miro Horváth commented

2021-05-03 14:24:11 +02:00

First-time contributor

Added subscriber: @MiroHorvath

hujin commented

2021-09-12 14:48:22 +02:00

First-time contributor

Added subscriber: @2046411367

Ricardo commented

2021-11-19 10:34:32 +01:00

First-time contributor

Added subscriber: @Ricardo-Navarro

Alexey Adamitsky commented

2021-12-01 08:15:07 +01:00

First-time contributor

Added subscriber: @AlexeyAdamitsky

Chris Kohl commented

2021-12-09 22:48:17 +01:00

First-time contributor

Added subscriber: @ckohl_art

Aras Pranckevicius commented

2022-05-20 12:36:11 +02:00

Added subscriber: @aras_p

Jan Kadeřábek commented

2022-07-13 21:29:24 +02:00

First-time contributor

Added subscriber: @JanKaderabek

Jan Kadeřábek commented

2022-07-13 21:29:24 +02:00

First-time contributor

Any update on this?
We have projects with thousands of objects and to process them we are forced to rewrite many built-in methods just to avoid using incredibly slow bpy.ops :-/
Thanks!

Any update on this? We have projects with thousands of objects and to process them we are forced to rewrite many built-in methods just to avoid using incredibly slow bpy.ops :-/ Thanks!

Lorenzo Clerici commented

2022-07-13 21:51:06 +02:00

First-time contributor

Added subscriber: @Lorenzo-Clerici

Daniel Gryningstjerna commented

2022-07-14 01:03:33 +02:00

First-time contributor

Added subscriber: @Dangry

blender-admin commented

2022-07-20 13:27:14 +02:00

First-time contributor

This issue was referenced by 7f8d05131a

This issue was referenced by 7f8d05131a7738327ae125d065df44be492ff1f2

Ahmed Hindy commented

2022-07-25 19:15:08 +02:00

First-time contributor

Added subscriber: @ahmed.hindy96

Ricardo commented

2022-07-26 08:27:47 +02:00

First-time contributor

Removed subscriber: @Ricardo-Navarro

Sebastian Koenig commented

2022-10-12 15:54:19 +02:00

Added subscriber: @sebastian_k

Philipp Oeser removed the

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Blender editing performance with many datablocks #73359

Dependency graph should not have to re-evaluate objects that did not change.

Handling naming of data-blocks should be O(log(N)) (it is currently close to O(N²), or O(N log(N)) in best cases).

Kept valid/in sync all the time (code affecting related data should take care of updating it itself, code using the cache can always assume it is valid and up-to-date).

Investigate how to best handle naming conflicts issues.

Investigate the best way to cache bi-directional relationships info between data-blocks.

Fix/Improve handling of the Bone pointers (which are sub-data of Armature ID) stored in poses (which are sub-data of Object ID).

Handling naming of data-blocks should be `O(log(N))` (it is currently close to `O(N²)`, or `O(N log(N))` in best cases).

Fix/Improve handling of the Bone pointers (which are sub-data of `Armature` ID) stored in poses (which are sub-data of `Object` ID).