Resolved

Python video rendering stuck at 24 percent with 100 percent CPU usage

Python
Performance
Multiprocessing
Video Rendering
Algorithm Optimization
Debugging
Parallel Processing
Data Structures

Token detection in frame metadata calculation caused catastrophic O(n²) performance degradation | Long videos with 9,000+ frames took 36+ minutes for metadata processing instead of seconds | Single-core CPU maxed out during list membership checks

Issue

The video rendering pipeline encountered severe performance degradation during frame metadata calculation, particularly for long videos. Processing stalled at 24% progress, with a single-core CPU utilization at 100% for over 36 minutes on videos containing 9,144 frames. Short videos (e.g., 228 frames) processed normally within ~2 seconds, but scaling to longer videos became impractical. The bottleneck occurred during the ‘Pre-calculating frame metadata’ phase, where progress indicators froze and parallel rendering failed to initiate.

Culprit

The root cause was an inefficient O(n²) algorithm in the token completion detection process. The algorithm used nested loops with a linear list membership check, leading to exponential time complexity. Specifically:

  • An outer loop processed visible characters (typically ~150 per frame).
  • An inner loop scanned all characters (~4,400) in the token sequence.
  • Each check for membership in the list of visible indices had a time complexity of O(n), resulting in an overall complexity of O(V² × T), where V is the number of visible characters and T is the token length.

This led to catastrophic performance degradation, where processing time scaled disproportionately with frame count (e.g., 2 seconds for 228 frames vs. 36 minutes for 9,144 frames).

Solution

The inefficiency was addressed through two key optimizations:

Set-Based Lookup Optimization

The list of visible indices was converted into a set to enable O(1) membership checks. This eliminated the O(n) overhead of linear list searches, significantly accelerating the token detection process.

Bounded Token Scan

The range of the inner loop was limited to a bounded maximum token length (empirically determined to be 100 characters). This prevented unnecessary scanning of the entire character sequence for each visible character, reducing the complexity to a manageable level.

Performance Impact

  • Metadata calculation time: Reduced from 36 minutes to approximately 10 seconds (~200x speedup).
  • Operations: Decreased from 2 billion to 137 million operations (~15x reduction).
  • Throughput: Sustained processing of ~1,000 frames per second during metadata calculation.
  • Memory overhead: Negligible increase (~11MB additional for 9,144 frames).

The solution maintains all visual functionality, including token-based syntax highlighting, while eliminating the quadratic scaling bottleneck. This ensures efficient processing of both short and long videos, improving overall pipeline performance.