Blender editing performance with many datablocks #73359

Open
opened 2020-01-24 13:01:58 +01:00 by Dalai Felinto · 48 comments

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

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:** - ---
Author
Owner

Added subscribers: @ZedDB, @mont29, @dfelinto

Added subscribers: @ZedDB, @mont29, @dfelinto

Added subscriber: @MACHIN3

Added subscriber: @MACHIN3

Added subscriber: @Teds

Added subscriber: @Teds

Added subscriber: @Lumpengnom-3

Added subscriber: @Lumpengnom-3

Added subscriber: @MichaelWeisheim

Added subscriber: @MichaelWeisheim

Added subscriber: @rwman

Added subscriber: @rwman

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.

Added subscriber: @slumber

Added subscriber: @slumber

Added subscriber: @Scaredyfish

Added subscriber: @Scaredyfish

Added subscriber: @AditiaA.Pratama

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

Added subscriber: @dcolli23

Added subscriber: @dcolli23

Added subscriber: @Pipeliner

Added subscriber: @Pipeliner

Removed subscriber: @Pipeliner

Removed subscriber: @Pipeliner

Added subscriber: @Pipeliner

Added subscriber: @Pipeliner

Added subscriber: @MizManFryinPan

Added subscriber: @MizManFryinPan

Added subscriber: @DuarteRamos

Added subscriber: @DuarteRamos

Added subscriber: @ManuelAlbert

Added subscriber: @ManuelAlbert

Added subscriber: @elven_inside

Added subscriber: @elven_inside

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

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

Added subscriber: @VladimirKunyansky

Added subscriber: @VladimirKunyansky

Added subscriber: @1D_Inc

Added subscriber: @1D_Inc

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))

Added subscriber: @Moult

Added subscriber: @Moult

Added subscriber: @Yianni

Added subscriber: @Yianni
Member

Added subscriber: @JacquesLucke

Added subscriber: @JacquesLucke
Author
Owner

Added subscriber: @brecht

Added subscriber: @brecht

Added subscriber: @filibis

Added subscriber: @filibis

Added subscriber: @MeshVoid

Added subscriber: @MeshVoid
Contributor

Added subscriber: @RedMser

Added subscriber: @RedMser

Added subscriber: @Noto

Added subscriber: @Noto

Added subscriber: @MichaelHermann

Added subscriber: @MichaelHermann

Added subscriber: @bblanimation

Added subscriber: @bblanimation

Added subscriber: @pauanyu_blender

Added subscriber: @pauanyu_blender

Added subscriber: @PhilippeCrassous

Added subscriber: @PhilippeCrassous

Added subscriber: @MiroHorvath

Added subscriber: @MiroHorvath

Added subscriber: @2046411367

Added subscriber: @2046411367

Added subscriber: @Ricardo-Navarro

Added subscriber: @Ricardo-Navarro

Added subscriber: @AlexeyAdamitsky

Added subscriber: @AlexeyAdamitsky

Added subscriber: @ckohl_art

Added subscriber: @ckohl_art

Added subscriber: @aras_p

Added subscriber: @aras_p

Added subscriber: @JanKaderabek

Added subscriber: @JanKaderabek

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!

Added subscriber: @Lorenzo-Clerici

Added subscriber: @Lorenzo-Clerici

Added subscriber: @Dangry

Added subscriber: @Dangry

This issue was referenced by 7f8d05131a

This issue was referenced by 7f8d05131a7738327ae125d065df44be492ff1f2

Added subscriber: @ahmed.hindy96

Added subscriber: @ahmed.hindy96

Removed subscriber: @Ricardo-Navarro

Removed subscriber: @Ricardo-Navarro

Added subscriber: @sebastian_k

Added subscriber: @sebastian_k
Philipp Oeser removed the
Interest
Core
label 2023-02-09 14:43:15 +01:00
Sign in to join this conversation.
No Label
Interest
Alembic
Interest
Animation & Rigging
Interest
Asset Browser
Interest
Asset Browser Project Overview
Interest
Audio
Interest
Automated Testing
Interest
Blender Asset Bundle
Interest
BlendFile
Interest
Collada
Interest
Compatibility
Interest
Compositing
Interest
Core
Interest
Cycles
Interest
Dependency Graph
Interest
Development Management
Interest
EEVEE
Interest
EEVEE & Viewport
Interest
Freestyle
Interest
Geometry Nodes
Interest
Grease Pencil
Interest
ID Management
Interest
Images & Movies
Interest
Import Export
Interest
Line Art
Interest
Masking
Interest
Metal
Interest
Modeling
Interest
Modifiers
Interest
Motion Tracking
Interest
Nodes & Physics
Interest
OpenGL
Interest
Overlay
Interest
Overrides
Interest
Performance
Interest
Physics
Interest
Pipeline, Assets & IO
Interest
Platforms, Builds & Tests
Interest
Python API
Interest
Render & Cycles
Interest
Render Pipeline
Interest
Sculpt, Paint & Texture
Interest
Text Editor
Interest
Translations
Interest
Triaging
Interest
Undo
Interest
USD
Interest
User Interface
Interest
UV Editing
Interest
VFX & Video
Interest
Video Sequencer
Interest
Virtual Reality
Interest
Vulkan
Interest
Wayland
Interest
Workbench
Legacy
Blender 2.8 Project
Legacy
Milestone 1: Basic, Local Asset Browser
Legacy
OpenGL Error
Meta
Good First Issue
Meta
Papercut
Meta
Retrospective
Meta
Security
Module
Animation & Rigging
Module
Core
Module
Development Management
Module
EEVEE & Viewport
Module
Grease Pencil
Module
Modeling
Module
Nodes & Physics
Module
Pipeline, Assets & IO
Module
Platforms, Builds & Tests
Module
Python API
Module
Render & Cycles
Module
Sculpt, Paint & Texture
Module
Triaging
Module
User Interface
Module
VFX & Video
Platform
FreeBSD
Platform
Linux
Platform
macOS
Platform
Windows
Priority
High
Priority
Low
Priority
Normal
Priority
Unbreak Now!
Status
Archived
Status
Confirmed
Status
Duplicate
Status
Needs Info from Developers
Status
Needs Information from User
Status
Needs Triage
Status
Resolved
Type
Bug
Type
Design
Type
Known Issue
Type
Patch
Type
Report
Type
To Do
No Milestone
No project
No Assignees
42 Participants
Notifications
Due Date
The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Dependencies

No dependencies set.

Reference: blender/blender#73359
No description provided.