move_item is horribly slow

Version of Dear PyGui

Version: 1.11.2 Operating System: Windows

My Issue/Question

dpg.move_item() can take seconds and even minutes to complete even on relatively lightweight UI's. Its performance depends on the max nesting level in the widgets tree, and grows exponentially with the nesting level (see the output below).

The problem occurs because the main body of AddRuntimeChild() (mvItemRegistry.cpp) is repeated in a loop for every childslot, even though for the before == 0 branch, childslots are iterated again:

https://github.com/hoffstadt/DearPyGui/blob/6541ac7ed914163e865cb4eefd909a7857758792/src/mvItemRegistry.cpp#L392-L412

                // check children
                for (auto& childslot : rootitem->childslots)   // <-- here we iterate childslots again
                {
                    for (auto& child : childslot)

This multiplies the number of iterations by 4 on each nesting level within the widget tree, which in the end leads to exponential performance.

To Reproduce

Steps to reproduce the behavior:

Run the example below.
Click the button and see the output in the console.

Expected behavior

Less-than-exponential performance (ideally, use GetItem and rely on its performance).

Standalone, minimal, complete and verifiable example

import time
import dearpygui.dearpygui as dpg

dpg.create_context()
dpg.create_viewport(title='Test', width=600, height=600)

nesting_level = 1
last_parent = 0
target_parent = 0
move_parent = 0

def test_move_item():
    with dpg.mutex():
        global last_parent, nesting_level, target_parent
        # Trying to add a widget
        tm = time.time_ns()
        new_item = dpg.add_group(parent=target_parent)
        duration = (time.time_ns() - tm) / 1000_000
        print(f"Level {nesting_level:3}: add_group took {duration} ms")
        # Testing move_item
        tm = time.time_ns()
        dpg.move_item(new_item, parent=move_parent)
        duration = (time.time_ns() - tm) / 1000_000
        print(f"Level {nesting_level:3}: move_item took {duration} ms, total widgets = {nesting_level + 4}")
        # Deleting it to get back to the original state
        tm = time.time_ns()
        dpg.delete_item(new_item)
        duration = (time.time_ns() - tm) / 1000_000
        print(f"Level {nesting_level:3}: delete_item took {duration} ms")
        # Increasing the nesting level
        last_parent = dpg.add_group(parent=last_parent)
        nesting_level += 1

with dpg.window(label="Test", pos=(0, 0)) as wnd:
    # To demonstrate that `AddRuntimeChild` does a lot of extra work, we need
    # a chain of nested parents deep enough to cause 4^N lookup to be visibly slow.
    # Each button click adds just one group, but the chain becomes one level deeper.
    # `last_parent` points to the tail of that chain.  It only serves the purpose
    # of slowing down `AddRuntimeChild`; we have to actually add the test widget
    # to a different location so that `AddRuntimeChild` doesn't quit too early.
    dpg.add_button(label="Click me", callback=test_move_item)
    last_parent = dpg.add_group(show=False)

    target_parent = dpg.add_group()
    move_parent = dpg.add_group()

# Initial fill so that we don't have to click the button too many times
for i in range(5):
    dpg.add_group(parent=last_parent)
    last_parent = dpg.add_group(parent=last_parent)
    nesting_level += 1

dpg.setup_dearpygui()
dpg.show_viewport()
dpg.start_dearpygui()
dpg.destroy_context()

Here's typical output from the script:

Level   8: add_group took 0.0 ms
Level   8: move_item took 0.0 ms, total widgets = 12
Level   8: delete_item took 0.0 ms
Level   9: add_group took 0.0 ms
Level   9: move_item took 15.6 ms, total widgets = 13
Level   9: delete_item took 0.0 ms
Level  10: add_group took 0.0 ms
Level  10: move_item took 93.6001 ms, total widgets = 14
Level  10: delete_item took 0.0 ms
Level  11: add_group took 0.0 ms
Level  11: move_item took 483.6008 ms, total widgets = 15
Level  11: delete_item took 0.0 ms
Level  12: add_group took 0.0 ms
Level  12: move_item took 2402.4042 ms, total widgets = 16
Level  12: delete_item took 0.0 ms
Level  13: add_group took 0.0 ms
Level  13: move_item took 12014.0212 ms, total widgets = 17
Level  13: delete_item took 0.0 ms
Level  14: add_group took 0.0 ms
Level  14: move_item took 60151.9906 ms, total widgets = 18
Level  14: delete_item took 1.0 ms

"Level" here is the max nesting level in the widget tree.

Notice how in a UI with fewer than 20 widgets, move_item performance quickly degrades from 0 ms per call to a minute per call.

hoffstadt / DearPyGui