Resolved

Video rendering frame metadata calculation causes quadratic slowdown

Python
Performance
Video Processing
Algorithm Optimization
Backend
Rendering
Complexity Analysis

Frame metadata pre-calculation in video rendering scales quadratically with video length | 5K chars take 10s, 15K chars become unusable due to O(F×V²) complexity

A video rendering system suffered from severe performance degradation due to quadratic scaling in frame metadata pre-calculation. For animated text videos, the system recalculated character visibility, token completion, and special character detection for each frame, leading to impractical processing times for longer videos.

Issue

The metadata pre-calculation step exhibited quadratic scaling behavior, making long videos impractical to process:

  • 5,000 characters: ~10 seconds processing time
  • 15,000 characters: Multiple minutes (effectively unusable) The bottleneck manifested during the precalculate_frame_metadata() execution, causing CPU spikes while other rendering steps completed quickly.

Culprit

The original algorithm rebuilt metadata for every frame using three nested operations:

  1. Recalculating visible character indices for each frame (linear in visible characters per frame).
  2. Scanning all visible characters to detect colons (linear in visible characters per frame).
  3. Checking token completion for each visible character by scanning up to 100 subsequent characters (leading to quadratic complexity).

The root cause was the lack of leveraging monotonic properties (characters only appear, never disappear) and token completion (once complete, remains complete). The 100-character lookahead for token verification created the dominant O(V²) term.

Solution

Incremental Algorithm Design

The quadratic approach was replaced with a two-phase incremental system:

  1. Pre-computation phase:

    • Detected token boundaries based on color or segment changes.
    • Sorted characters by appearance time.
    • Created a token mapping array.

  2. Frame iteration phase:

    • Maintained persistent state tracking (visible characters, complete tokens, token visibility count).
    • Processed only newly visible characters per frame using a time-pointer-based approach.
    • Enabled O(1) updates for token completion checks via pre-computed counters.

Key Optimizations

  • Monotonic processing: Characters were processed exactly once when they became visible.
  • Token tracking: Counters tracked visible characters per token, enabling O(1) completion checks.
  • Colon detection: Performed in a single pass during initial visibility processing.

Performance Improvements

The optimization reduced operations from billions to hundreds of thousands:

  • Before: ~60 billion operations for a 15,000-character video.
  • After: ~180,000 operations for the same video.

This reduced processing time from several minutes to less than 1 second, effectively eliminating the quadratic bottleneck and enabling real-time processing for all video lengths.