java-topology/docs/tickets/linphone-0001-offeranswer-match-payloads-quadratic.md

linphone-0001 — offeranswer.cpp: matchPayloads O(n²) codec negotiation

Severity: MEDIUM File: liblinphone/src/sal/offeranswer.cpp Lines: 237-338 (matchPayloads), 196-227 (genericMatch inner scan)

Pattern

// Outer loop over remote payloads
for (const auto &p2 : remote) {
    // Inner: findPayloadTypeBestMatch → genericMatch → linear scan of local
    matched = findPayloadTypeBestMatch(local, p2, remote, reading_response);
    ...
}

// Also lines 308-315: nested loop for CAN_RECV fallback
for (const auto &p1 : local) {
    for (const auto &p2 : remote) {
        if (payload_type_get_number(p2) == payload_type_get_number(p1)) { found=true; break; }
    }
}

genericMatch at line 196-201 iterates local_payloads linearly for each element of remote. The CAN_RECV fallback at lines 308-315 is an explicit nested double loop.

Complexity

O(|remote| × |local|). SDP offers can contain 20-50 codec entries in video calls with RED/FEC/RTX variants. Called once per stream per call setup/re-INVITE.

Fix

For matchPayloads: pre-build std::unordered_map<std::string, OrtpPayloadType*> keyed by mime_type+clock_rate+channels from local before the outer loop. O(1) lookup per remote entry.

For the CAN_RECV fallback: pre-build std::unordered_set<int> of remote payload numbers before the outer local loop. O(1) per check instead of O(|remote|).

Also matchCryptoAlgo at lines 345-360 is a similar O(|remote| × |local|) nested loop over SalSrtpCryptoAlgo vectors — fix with an unordered_set of remote algo IDs.

Speedup (estimated)

~15× at N=30 codecs. O(n²) → O(n).