java-topology/docs/tickets/jitsi-videobridge-0001-prioritize-source-list-contains.md

jitsi-videobridge-0001 — Prioritize.kt: List.contains() per source (O(n²))

Severity: HIGH File: jvb/src/main/kotlin/org/jitsi/videobridge/cc/allocation/Prioritize.kt Lines: 41, 52

Pattern

conferenceSources.forEach { source -> if (selectedSourceNames.contains(source.sourceName)) ... }

selectedSourceNames is List<String> — O(n) scan per source. Also sortBy { selectedSourceNames.indexOf(it.sourceName) } — O(n) indexOf per sort comparison → O(n² log n).

Complexity

• contains loop: O(|conferenceSources| × |selectedSourceNames|)
• indexOf in sort: O(|selectedSourceNames| × |conferenceSources| × log|conferenceSources|)

prioritize() is called on every bandwidth allocation cycle (per BandwidthAllocator.update()). In a 100-participant conference both lists can reach N=100+ sources.

Fix

Pre-build val selectedSet = selectedSourceNames.toHashSet() before the forEach. Pre-build val selectedIndex = selectedSourceNames.withIndex().associate { (i, s) -> s to i } before sortBy.

Replace selectedSourceNames.contains(...) → selectedSet.contains(...). Replace selectedSourceNames.indexOf(...) → selectedIndex.getOrDefault(..., Int.MAX_VALUE).

Speedup (estimated)

~50× at N=100 sources. O(n²) → O(n).