Page MenuHome

WIP/Demonstration patch about undo speedup project.
Changes PlannedPublic

Authored by Bastien Montagne (mont29) on Tue, Jan 14, 1:39 PM.

Details

Summary

This patch is by no mean considered ready for production, it's rather a proof-of-concept demoing current idea to speed up undo's in Blender.

As such, if you try it, expect crashes, .blend files corruptions, etc.

The intent of this patch is to get early reviews/advices/comments from other devs knowing well the affected areas: Undo system (based on memfile, i.e. undo in object/pose modes mostly), read/write code of .blend files, and depsgraph.

Related design task: T60695.

Here is a quick demo video of the same set of actions, followed by complete undo's, performed on a 'worst case' file (we are editing simple objects, with a very heavily modified mesh one that remain unchanged). Left side is current patch, right one is current master.

One can notice some of the glitches/limitations still present in the patch (the very first undo step does not currently benefit from any speed-up, due to some annoying detail, switching in/out of Edit modes will also enfore a full re-evaluated undo step, etc.).

Also, if your edit affects in any way a heavy-to-evaluate object, there will be limited to no improvements, as currently this requires rebuilding all the caches.


General Idea

General idea of the project is to detect unchanged data-blocks, and only re-read and re-evaluate those who need it. This implies re-using existing depsgraphes, such that caches and general internal relations data in them remain valid for unchanged IDs, since their memory addresses will remain the same.

Here are the main changes for each area:

Undo System

Modifications to the undo system itself are quite minimal. We need to store a 'future' unchanged flag in memory chunks (in addition to the regular 'unchanged compared to past' one), needed when doing undo's (as we need to know which IDs changed between step n and n - 1, and not between step n and n + 1 like for redo's).

And we also need to extract and restore depsgraphes around the actual undo step 'reading', as by default depsgraphes are completely lost during this process.

File Read/Write

The heaviest changes are done in reading code, to enable re-using unchanged data-blocks from existiong ('old') bmain, instead of using their newly-read versions. This requires some careful remapping of the old pointers to new ones (either new from newly read data-blocks, or from re-used data-blocks).

After quiet a few trials and errors, using idnames as 'uid' was chosen as the only viable solution, having too many 'memory realms' at play during undo history makes using pointers values themselves close to impossible. This implies that renaming of IDs has to enforce a complete undo step (in most of the cases this would not be needed, but some corner-cases could generate bad naming collisions, completely breaking the remapping process). This has some cost over the readfile part of the undo, but it remains neglectable compared to the undo process as a whole.

Write part of the code was mainly changed to ensure we do have a write flush for every ID, so that each ID has at least one 'own' memory chunk, to make detecting unchanged IDs easy and simple.

Depsgraph

There is no changes to the behavior of the depsgraph itself, but some APIs were added to allow extraction/storage of the depsgraphes into a temp ghash (using scenes' and viewlayers' names as keys). 'Extraction' means that those depsgraph are fully removed from current scenes, hences said scenes can be freed without loosing any evaluation data.

Restoration of the depsgraphes simply searches for stored ones in the ghash, and restore them when found. A way to change their Main reference was also needed, to point it to the newly created Main after the undo.

Diff Detail

Repository
rB Blender
Branch
undo-experiments-idnames
Build Status
Buildable 6245
Build 6245: arc lint + arc unit

Event Timeline

  • Cleanup .orig files from some merge...
Bastien Montagne (mont29) edited the summary of this revision. (Show Details)
Bastien Montagne (mont29) retitled this revision from WIP undo speedup. to WIP/Demonstration patch about undo speedup project..Tue, Jan 14, 2:04 PM
Bastien Montagne (mont29) edited the summary of this revision. (Show Details)

Sergey dropped by to look at the depsgraph part of the patch. He seems to like the isolated approach where depsgraph is left close to what it is. He did not look at the rest of the patch though.

source/blender/depsgraph/intern/depsgraph.cc
345

If we are also tagging on update, the function name should reflect that - Sergey

Overall this patch is smaller than I expected, and makes sense to me. Still, I think there is some tricky logic here which we can avoid.

After discussion with Bastien, he may be able to simplify implementation by reusing memory locations for changed datablocks and not lib linking unchanged datablocks again.

If that works, it means fd->libmap_undo_reused and blo_undo_merge_and_fix_collisions_in_libmaps can be removed. We do have to be careful to keep ID user count correct, probably by preserving the count written to undo memory.

There would not be immediate benefits for performance since the bottleneck is elsewhere, but changing datablocks as little as possible helps with optimizations later on.

After quiet a few trials and errors, using idnames as 'uid' was chosen as the only viable solution, having too many 'memory realms' at play during undo history makes using pointers values themselves close to impossible. This implies that renaming of IDs has to enforce a complete undo step (in most of the cases this would not be needed, but some corner-cases could generate bad naming collisions, completely breaking the remapping process). This has some cost over the readfile part of the undo, but it remains neglectable compared to the undo process as a whole.

It would be nice if we could get rid of the naming barrier somehow.

I'm not sure exactly which corner cases cause the problem. I can maybe see some problems related to the second call to BKE_main_idmap_lookup in read_libblock, or the pointer collision fixing. And then somehow ending up in a state where we point to old deleted datablocks that have the same name as a newly added one. If we can remove fd->libmap_undo_reused, that problem may also go away with it? It's a bit of a blind guess though.

I think using names is ok, and maybe later it can be optimized to use pointers so undoing a rename is faster, but it's not a big issue. Just the barrier feels like a weakness in the implementation is leaking outside of the blenloader module.

Bastien Montagne (mont29) planned changes to this revision.Sun, Jan 26, 8:47 PM

I don’t see how we could avoid naming barrier, at least py scripts can rename all IDs within a single undo step, and even user-triggered rename from UI can lead to name swapping (Object becoming Object.001 and Object.001 becoming Object - and all kind of variations). Trying to find a data-block from its old name in history would then lead to finding a completely different data-block in current Main…

Note that if we manage to get memory swapping/old pointer reuse working for changed data, then we could try to switch back to pointer-based search, provided we:

  1. Store history of used pointers in each ID (this should not be such a huge issue anymore, as an ID's pointer would almost never change during an editing session, only in cases of deletion/creation).
  2. Find a way to avoid potential collisions in pointer values across history. Again, as that would be very uncommon, we could try something as stupid as storing all ID pointer values ever allocated in a GSet, and in case a new ID allocation gives us again a previously used address, just re-allocate until we get a never used value. Or use some kind of virtual pointers mapping in write/read code, or…

In any case, will try to make memory swap work, hoping that user refcount won't mess up things too much in that scenario (especially when some linked data are present, since those already have their own handling in current undo code…).

I don’t see how we could avoid naming barrier, at least py scripts can rename all IDs within a single undo step, and even user-triggered rename from UI can lead to name swapping (Object becoming Object.001 and Object.001 becoming Object - and all kind of variations). Trying to find a data-block from its old name in history would then lead to finding a completely different data-block in current Main…

Right, it could be a completely different datablock. But in principle the undo system can be merely less memory efficient then while still working.

But if we can avoid using names at all, that would be ideal.