Editing scenes with many datablocks can be slow, for example adding, deleting or duplicating many objects.
Adding or deleting a single object has time complexity O(N), where N is the number of objects. This is due to unique name tests, looping over all datablocks to clear all pointers, and other operations that require accessing many datablocks. In general all such operations must become O(log(N)) or O(1), along with possible access of just the other datablocks linking to it.
Undo push (T60695) and dependency graph rebuild are also O(N). We are not trying to improve those as part of this task, and note these can be run once after making many edits.
Practical steps to reduce time complexity would be:
- Store two-way links for all (non-COW) data-blocks, so that iterating over all datablocks that link to a given datablock is fast. There are transient data structures for this, but it should become permanent. Every id_us_min() and id_us_plus() should be turned into an operation that sets the datablock pointer and creates a link in the other direction as well.
- Extend or modify datablock lists in Main to support quick testing for duplicate names.
- Change view layer collection syncing to not require looping over all objects.