kdenlive-0010 — CWE-407: KeyframeModelList::checkConsistency() QList::contains() O(P*K^2)

Target

Kdenlive (KDE video editor) — src/assets/keyframes/model/keyframemodellist.cpp

MOAD

0001 — The Sedimentary Defect (CWE-407)

Severity

LOW-MEDIUM

Complexity

O(P * K^2) where P = number of linked parameters, K = number of keyframe positions

Description

KeyframeModelList::checkConsistency() is called at clip load time when a clip has a multi-parameter keyframe model (e.g., a position/transform effect with linked X, Y, scale, and rotation parameters). It performs two O(P * K^2) sweeps:

Phase 1 — building union keyframe list:

QList<GenTime> fullList;
for (const auto &param : m_parameters) {        // O(P)
    QList<GenTime> list = param.second->getKeyframePos();
    for (auto &time : list) {                    // O(K)
        if (!fullList.contains(time)) {          // O(K) — QList linear scan!
            fullList << time;
        }
    }
}

Phase 2 — checking each param has all positions:

for (const auto &param : m_parameters) {        // O(P)
    QList<GenTime> list = param.second->getKeyframePos();
    for (auto &time : fullList) {               // O(K)
        if (!list.contains(time)) {             // O(K) — QList linear scan!
            // re-add missing keyframe
        }
    }
}

QList<GenTime>::contains() is a linear scan — O(K) per call. Both phases are O(P * K^2). P is small (2-10 parameters), but K grows with clip duration and keyframe density. A motion-tracked clip, a clip with per-frame opacity changes, or a clip exported from animation software can have 1000+ keyframes.

GenTime uses floating-point delta equality (fabs(m_time - op.m_time) < s_delta), which is incompatible with hash-based sets. However, GenTime has operator< (strict weak ordering), making std::set<GenTime> a correct O(log K) alternative.

Hot Path

Called from AssetParameterModel::setParameter() (line 254) for every clip with a linked keyframe model during project load, paste, or undo/redo. On a timeline with 50 clips each having 500 keyframes on 3 linked parameters:

Defect: 50 * 750,000 = 37.5M comparisons at load
Fixed: 50 * 3,000 = 150,000 comparisons at load
Speedup: 250x

Fix

Replace QList<GenTime> fullList deduplication with std::set<GenTime> using fullSet.insert(time).second (returns true if inserted), and build a per-param std::set<GenTime> listSet for the membership check in phase 2:

#include <set>

void KeyframeModelList::checkConsistency()
{
    if (m_parameters.size() < 2) return;

    std::set<GenTime> fullSet;
    QList<GenTime> fullList;
    for (const auto &param : m_parameters) {
        QList<GenTime> list = param.second->getKeyframePos();
        for (auto &time : list) {
            if (fullSet.insert(time).second)   // O(log K), true if newly inserted
                fullList << time;
        }
    }
    Fun local_update = []() { return true; };
    auto type = KeyframeType::KeyframeEnum(KdenliveSettings::defaultkeyframeinterp());
    for (const auto &param : m_parameters) {
        QList<GenTime> list = param.second->getKeyframePos();
        const std::set<GenTime> listSet(list.begin(), list.end());  // O(K log K) once
        for (auto &time : fullList) {
            if (listSet.find(time) == listSet.end()) {   // O(log K)
                // re-add missing keyframe
            }
        }
    }
}

Benchmark

P	K	Before (ops)	After (ops)	Speedup
3	100	30,200	600	50x
3	500	751,000	3,000	250x
3	1000	3,002,000	6,000	500x

Files

src/assets/keyframes/model/keyframemodellist.cpp — checkConsistency()
src/assets/model/assetparametermodel.cpp:254 — call site

3.8 KiB Raw Permalink Blame History