[FFmpeg-trac] #9236(avformat:new): Appending new segments into old hls segment list is very slow for large m3u8 file

[FFmpeg]

#9236: Appending new segments into old hls segment list is very slow for large
m3u8 file
-------------------------------------+------------------------------------
             Reporter:  litzh        |                    Owner:  (none)
                 Type:  enhancement  |                   Status:  new
             Priority:  normal       |                Component:  avformat
              Version:  git-master   |               Resolution:
             Keywords:  HLS          |               Blocked By:
             Blocking:               |  Reproduced by developer:  0
Analyzed by developer:  0            |
-------------------------------------+------------------------------------
Description changed by litzh:

Old description:

> Summary of the bug:
>
> I am trying to record rtmp live stream into HLS with `append_list` flag.
> When the recording is interrupted and the m3u8 file is very large (see
> attached file), it would take several minutes to resume recording.
>
> With `append_list` enabled, `find_segment_by_filename` finds duplicate
> segment filenames by linearly traversing the singly linked list.
> `av_strcasecmp` is a simple loop and cannot be accelerated by SMID. The
> time complexity is O(n^3^), where n is the total bytes of the segment
> filenames.
>
> How to reproduce:
> {{{
> % ffmpeg -rw_timeout 10000000 -y -flv_ignore_prevtag 1 -i
> "rtmp://example.com/live/12544134-c2397sl2lrnb4obtt020" -vcodec copy
> -acodec copy -hls_time 4 -hls_flags append_list -hls_list_size 0
> -hls_segment_filename 12544134-c2397sl2lrnb4obtt020-0_540p-%04d.ts -f hls
> 12544134-c2397sl2lrnb4obtt020-0_540p.m3u8
> ffmpeg version N-102493-g7ce0f246f4 Copyright (c) 2000-2021 the FFmpeg
> developers
>   built with gcc 7 (Ubuntu 7.5.0-3ubuntu1~18.04)
>   configuration: --pkg-config-flags=--static --extra-ldflags='-ldl -lm
> -lpthread -lrt -lstdc++ -static' --enable-gpl --enable-nonfree --enable-
> version3 --extra-libs=-ldl --disable-programs --enable-ffmpeg --enable-
> ffprobe --enable-static
>   libavutil      57.  0.100 / 57.  0.100
>   libavcodec     59.  1.100 / 59.  1.100
>   libavformat    59.  0.101 / 59.  0.101
>   libavdevice    59.  0.100 / 59.  0.100
>   libavfilter     8.  0.101 /  8.  0.101
>   libswscale      6.  0.100 /  6.  0.100
>   libswresample   4.  0.100 /  4.  0.100
>   libpostproc    56.  0.100 / 56.  0.100
> Input #0, flv, from
> 'rtmp://example.com/live/12544134-c2397sl2lrnb4obtt020':
>   Metadata:
>     |RtmpSampleAccess: true
>     encoder         : DyEncoder58.40.100
>   Duration: 00:00:00.00, start: 661322.354000, bitrate: N/A
>   Stream #0:0: Data: none
>   Stream #0:1: Subtitle: text
>   Stream #0:2: Audio: aac (LC), 44100 Hz, stereo, fltp, 160 kb/s
>   Stream #0:3: Video: h264 (Main), yuv420p(progressive), 1920x1080, 8001
> kb/s, 62.50 fps, 62 tbr, 1k tbn
> }}}

New description:

 Summary of the bug:

 I am trying to record rtmp live stream into HLS with `append_list` flag.
 When the recording is interrupted and the m3u8 file is very large (see
 attached file), it would take several minutes to resume recording.

 With `append_list` enabled, `find_segment_by_filename` finds duplicate
 segment filenames by linearly traversing the singly linked list.
 `av_strcasecmp` is a simple loop and cannot be accelerated by SIMD. The
 time complexity is O(n^3^), where n is the total bytes of the segment
 filenames.

 How to reproduce:
 {{{
 % ffmpeg -rw_timeout 10000000 -y -flv_ignore_prevtag 1 -i
 "rtmp://example.com/live/12544134-c2397sl2lrnb4obtt020" -vcodec copy
 -acodec copy -hls_time 4 -hls_flags append_list -hls_list_size 0
 -hls_segment_filename 12544134-c2397sl2lrnb4obtt020-0_540p-%04d.ts -f hls
 12544134-c2397sl2lrnb4obtt020-0_540p.m3u8
 ffmpeg version N-102493-g7ce0f246f4 Copyright (c) 2000-2021 the FFmpeg
 developers
   built with gcc 7 (Ubuntu 7.5.0-3ubuntu1~18.04)
   configuration: --pkg-config-flags=--static --extra-ldflags='-ldl -lm
 -lpthread -lrt -lstdc++ -static' --enable-gpl --enable-nonfree --enable-
 version3 --extra-libs=-ldl --disable-programs --enable-ffmpeg --enable-
 ffprobe --enable-static
   libavutil      57.  0.100 / 57.  0.100
   libavcodec     59.  1.100 / 59.  1.100
   libavformat    59.  0.101 / 59.  0.101
   libavdevice    59.  0.100 / 59.  0.100
   libavfilter     8.  0.101 /  8.  0.101
   libswscale      6.  0.100 /  6.  0.100
   libswresample   4.  0.100 /  4.  0.100
   libpostproc    56.  0.100 / 56.  0.100
 Input #0, flv, from
 'rtmp://example.com/live/12544134-c2397sl2lrnb4obtt020':
   Metadata:
     |RtmpSampleAccess: true
     encoder         : DyEncoder58.40.100
   Duration: 00:00:00.00, start: 661322.354000, bitrate: N/A
   Stream #0:0: Data: none
   Stream #0:1: Subtitle: text
   Stream #0:2: Audio: aac (LC), 44100 Hz, stereo, fltp, 160 kb/s
   Stream #0:3: Video: h264 (Main), yuv420p(progressive), 1920x1080, 8001
 kb/s, 62.50 fps, 62 tbr, 1k tbn
 }}}

--
-- 
Ticket URL: <https://trac.ffmpeg.org/ticket/9236#comment:1>
FFmpeg <https://ffmpeg.org>
FFmpeg issue tracker