Appending new segments into old hls segment list is very slow for large m3u8 file

[litzh]

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³), 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