C++下大型UI表格中UI自动化树搜索的性能问题及优化困境

问题描述 #

我正在C++中使用UI Automation框架在类Excel的大型表格UI结构中查找特定元素。目标元素可能深度嵌套（如第90行第100列），导致当前实现存在严重性能问题。

原始实现 #

原始代码采用**深度优先搜索（DFS）**遍历UI元素，遍历过程中为每个元素重复构建缓存，这被怀疑是性能瓶颈的根源。简化代码如下：

std::shared_ptr<IUIElement> UIAutomationSession::FindElement(
    HWND topWnd, PCWCHAR name, LONG classTypeId, LONG x, LONG y, LONG w, LONG h)
{
    LOG_TRACE(L"BEGIN");

    auto element = root->ElementFromHandleBuildCacheNoThrow(topWnd, cache.get()).value; // Invokes IUIAutomation::ElementFromHandleBuildCache
    if (element)
    {
        RECT wndRect;
        windowApi->GetWindowRect(topWnd, &wndRect);

        return FindElement(element.get(), wndRect, x, y, w, h);
    }
    else
    {
        element = root->ElementFromHandleNoThrow(topWnd).value; // Invokes IUIAutomation::ElementFromHandle
        if (element)
        {
            cache->PutTreeScope(TreeScope_Element);
            AddCacheableProperties(CachingPropertySets::TREEWALKER_SEARCH_PROP_SET);

            auto rawWalker = root->GetRawViewWalkerNoThrow().value; // Invokes IUIAutomation::get_RawViewWalker
            if (rawWalker)
            {
                std::function<std::shared_ptr<IUIElement>(IUIElement*)> F
                    = [&](IUIElement* processingElement) -> std::shared_ptr<IUIElement>
                {
                    auto currentElement = rawWalker->GetFirstChildElementBuildCacheNoThrow(processingElement, cache.get()).value; // Invokes IUIAutomationTreeWalker::GetFirstChildElementBuildCache
                    if (currentElement)
                    {
                        while (currentElement != nullptr)
                        {
                            const auto manipulator = factory->MakeManipulator(topWnd, currentElement);
                            const auto elementName = manipulator->GetName();
                            const auto elementTypeId = currentElement->GetCachedControlTypeNoThrow().value; // Invokes IUIAutomationElement::GetCachedPropertyValue

                            if (elementName == name && elementTypeId == classTypeId)
                            {
                                return currentElement;
                            }

                            auto targetElement = F(currentElement.get());

                            if (targetElement != nullptr)
                            {
                                return targetElement;
                            }

                            currentElement = rawWalker
                                ->GetNextSiblingElementBuildCacheNoThrow(currentElement.get(), cache.get()).value; // Invokes IUIAutomationTreeWalker::GetNextSiblingElementBuildCache
                        }
                    }

                    return nullptr;
                };

                return F(element.get());
            }
        }
    }

    return {};
}

原始实现问题

• 性能瓶颈：遍历树时反复为每个元素构建缓存，在深度嵌套的大型表格中会造成显著延迟。

优化尝试 #

我重写函数，通过TreeScope_Subtree预先构建整个子树缓存，并将遍历算法改为广度优先搜索（BFS）。但优化版本无法找到需滚动（垂直/水平）才能显示的元素，仅能识别当前视口中的可见元素。

优化后代码如下：

std::shared_ptr<IUIElement> UIAutomationSession::FindElement(
    HWND topWnd, PCWCHAR name, LONG classTypeId, LONG x, LONG y, LONG w, LONG h)
{
    LOG_TRACE(L"BEGIN");

    // Build cache for the entire tree
    cache->PutTreeScope(TreeScope_Subtree);
    AddCacheableProperties(CachingPropertySets::TREEWALKER_SEARCH_PROP_SET);

    LOG_DEBUG(L"Name of the element: {}", name);
    LOG_DEBUG(L"Class ID: {}, x: {}, y: {}, w: {}, z: {}", classTypeId, x, y, w, h);

    auto element = root->ElementFromHandleBuildCacheNoThrow(topWnd, cache.get()).value;
    if (!element)
    {
        LOG_DEBUG(L"!element is true");
        element = root->ElementFromHandleNoThrow(topWnd).value;
    }

    if (!element)
    {
        LOG_DEBUG(L"!element is true, returning nullptr");
        return nullptr;
    }

    auto rawWalker = root->GetRawViewWalkerNoThrow().value;

    if (!rawWalker)
    {
        LOG_DEBUG(L"!rawWalker is true, returning nullptr");
        return nullptr;
    }
    
    LOG_DEBUG(L"IUITreeWalker count is: {}", rawWalker.use_count());

    std::function<std::shared_ptr<IUIElement>(IUIElement*)> FindTargetElement = [&](IUIElement* startElement) -> std::shared_ptr<IUIElement>
    {
        std::queue<std::shared_ptr<IUIElement>> queue;
        queue.push(std::shared_ptr<IUIElement>(startElement, [](IUIElement*) {}));

        while (!queue.empty())
        {
            auto current = queue.front();
            queue.pop();
            auto controlType = current->GetCachedControlTypeNoThrow().value;
            LOG_DEBUG(L"Cached Control Type: {}", controlType);

            if (controlType == classTypeId)
            {
                const auto currentName = current->GetCachedNameNoThrow().value;
                const auto currentClassId = current->GetCachedControlTypeNoThrow().value;
                LOG_DEBUG(L"The current class ID of the element: {}", currentClassId);
                LOG_DEBUG(L"Get cached name of the control: {}", currentName);

                if (currentName == name && classTypeId == currentClassId)
                {
                    LOG_DEBUG(L"Retrieved name and class type ID matched with the passed one!");
                    return current;
                }
            }
            LOG_DEBUG(L"Getting children of current node");
            auto children = current->GetCachedChildrenNoThrow().value;
            if (children)
            {
                LOG_DEBUG(L"There are children. Number is: {}", children.use_count());
                for (int i = 0; i < children->GetLengthNoThrow().value; ++i)
                {
                    queue.push(children->GetElementNoThrow(i).value);
                }
            }
        }
        LOG_DEBUG(L"Did not find the element we were looking for :(");
        return nullptr;
    };

    LOG_DEBUG(L"Call lambda recursively");
    auto targetElement = FindTargetElement(element.get());
    if (targetElement)
    {
        LOG_DEBUG(L"Got the element? Yeah!!");
        return targetElement;
    }

    return nullptr;
}

优化实现问题

• 无法定位需滚动元素：仅对可视元素有效，无法找到视口外需滚动访问的元素，且能识别水平滚动条但无法识别垂直滚动条。

核心问题 #

1. 原始实现的性能瓶颈是什么？为何在深度嵌套的表格元素中耗时过长？
2. 优化版本无法找到需滚动元素的原因是什么？如何改进以支持非可视元素的定位？

恳请提供相关指导、建议或改进方案！

额外背景 #

• UI Automation框架：C++版Microsoft UI Automation。
• 目标UI：类Excel的大型表格/网格结构，包含大量行和列。
• 当前工具：使用IUIAutomationElement、IUIAutomationTreeWalker及缓存策略优化性能。

内容的提问来源于stack exchange，提问作者Stew