UNDF: UNDF-2026-000000486

opencv-0002: G-API pattern_matching — O(M×E) std::find on patternEndOpNodes/patternStartOpNodes inside match loop

Location

modules/gapi/src/compiler/passes/pattern_matching.cpp lines 289–312 Repository: https://github.com/opencv/opencv

Severity

MEDIUM — Called during G-API graph compilation when identifying kernel fusion patterns. With M matched nodes and E/S end/start op nodes in a pattern, each iteration of the matching loop does two O(E) and O(S) linear scans. For large compute graphs (video pipelines with many nodes), this is O(M×(E+S)) per pattern match attempt.

Complexity

Before: O(M × (E + S)) — two std::find calls inside the outer while loop over M matches
After: O(M + E + S) — two unordered_set lookups after O(E+S) set construction

Defective Code

// pattern_matching.cpp:289-312
while (!stop) {
    for (std::size_t index = 0u; index < size && !stop; ++index, ++matchIt) {
        // O(E) linear scan inside loop over M matched nodes
        bool cond1 = std::find(patternEndOpNodes.begin(),
                               patternEndOpNodes.end(),
                               matchIt->first)
                     != patternEndOpNodes.end();
        if (cond1) {
            subgraphEndOps[matchIt->first] = matchIt->second;
        }

        // O(S) linear scan inside loop over M matched nodes
        bool cond2 = std::find(patternStartOpNodes.begin(),
                               patternStartOpNodes.end(),
                               matchIt->first)
                     != patternStartOpNodes.end();
        if (cond2) {
            subgraphStartOps[matchIt->first] = matchIt->second;
        }

        if (!cond1 && !cond2) {
            subgraphInternals.push_back(matchIt->second);
        }
        // ...
    }
}

Problem: patternEndOpNodes and patternStartOpNodes are vectors. Each std::find call is O(E) and O(S) respectively. These searches happen inside a while loop over M matched nodes, giving O(M×E + M×S) total.

Fixed Code

// Build O(1)-lookup sets before the loop
std::unordered_set<ade::NodeHandle> endOpSet(
    patternEndOpNodes.begin(), patternEndOpNodes.end());
std::unordered_set<ade::NodeHandle> startOpSet(
    patternStartOpNodes.begin(), patternStartOpNodes.end());

while (!stop) {
    for (std::size_t index = 0u; index < size && !stop; ++index, ++matchIt) {
        bool cond1 = endOpSet.count(matchIt->first) > 0;    // O(1)
        if (cond1) {
            subgraphEndOps[matchIt->first] = matchIt->second;
        }

        bool cond2 = startOpSet.count(matchIt->first) > 0;  // O(1)
        if (cond2) {
            subgraphStartOps[matchIt->first] = matchIt->second;
        }

        if (!cond1 && !cond2) {
            subgraphInternals.push_back(matchIt->second);
        }
        // ...
    }
}

CWE

CWE-407: Inefficient Algorithmic Complexity — O(M×(E+S)) → O(M+E+S)

2.9 KiB Raw Permalink Blame History Unescape Escape