Optimizing librespot seeking and streaming performance

[roderickvd]

Sorry to have hijacked #154! Continuing here.

Not issues perse but I have been at working optimising it. In librespot <= 0.4 we have been downloading 16 kB chunks over Mercury (which is cheap to setup headerless), so seek performance never was an issue. Now that we switched to HTTPS things are different, and it's a balancing act between larger chunk sizes (better throughput, less overhead) and latency (when seeking).

Right now I have tuned it so that it initially grabs 64 kB chunks (which I took from buffer_len) until it is at the desired start position. Then it continues to grow download chunk sizes as network performance permits within ~1 second to keep acceptable seeking performance.

I see. I assume you're using range requests now?

Probably the most ideal solution would be to have a background thread download the file into a cache, from which Symphonia can read. But on seek you can immediately move to where Symphonia requests.

You'd probably need to track the ranges you have cached, but this would probably be an improvement.

😄 this is all in librespot today.

It does trigger me to immediately launch a new thread when in seeking mode, and not await the current sequential chunk. Yes it will share bandwidth, but is likely to have better latency.

You could try just using the read length Symphonia issues your Reader. It'll grow from 1 kB to a maximum of 32 kB.

While getting the desired/suggested chunk size from Symphonia would be great, <32 kB chunks does not seem ideal for HTTPS. It would result in many network requests with a relatively low header-to-content ratio.

I am a bit confused about the minimum buffer_len in MediaSourceStreamOptions and how that relates to the 1-32 kB buffer you describe. The documentation states that buffer_len must be >32 kB and a power of two. Indeed setting it to <64 kB returns thread '<unnamed>' panicked at 'assertion failed: options.buffer_len > Self::MAX_BLOCK_LEN'.

Ultimately though, the fastest solution would be to decode the Spotify seek table since instead of many seeks we can only do one.

I've read that Spotify adds a non-standard seek index packet to their OGG files reduce the number of seeks. If you have any docs on that I could look into implementing support for it.

Spotify does prepend the file with its own Ogg header which is 167 bytes in length. Right now we get the normalisation values from it (they are not there with normal ReplayGain tags, but as specific bytes), then skip ahead and act as if byte 168 were actually byte 0 and we feed that to Symphonia.
This is the Spotify Ogg header deciphered as far as I know: https://sourceforge.net/p/despotify/code/346/tree/java/trunk/src/main/java/se/despotify/client/player/SpotifyOggHeader.java

This is just a guess from looking at the code, but...

It looks like the /* Table Lookup */ section is reading 100 bytes from the packet and uses each of those bytes to index into a lookup table that specifies a length value. On each iteration, the length value is added to an accumulator, and the value of the accumulator is stored in that iteration's respective table index.

So, based off this I assume that the seek table splits the file up into 100 segments, and stores the byte (or kB) offset to the start of each segment in the table. This is my hypothesis, but perhaps there's more too it.

Well thought out! Assuming that were the case, how would that best work its way into Symphonia? I think it would need to be an extension there somewhere, fed by librespot?

[pdeljanov]

Sorry to have hijacked #154! Continuing here.

Not issues perse but I have been at working optimising it. In librespot <= 0.4 we have been downloading 16 kB chunks over Mercury (which is cheap to setup headerless), so seek performance never was an issue. Now that we switched to HTTPS things are different, and it's a balancing act between larger chunk sizes (better throughput, less overhead) and latency (when seeking).
Right now I have tuned it so that it initially grabs 64 kB chunks (which I took from buffer_len) until it is at the desired start position. Then it continues to grow download chunk sizes as network performance permits within ~1 second to keep acceptable seeking performance.

I see. I assume you're using range requests now?
Probably the most ideal solution would be to have a background thread download the file into a cache, from which Symphonia can read. But on seek you can immediately move to where Symphonia requests.
You'd probably need to track the ranges you have cached, but this would probably be an improvement.

smile this is all in librespot today.

It does trigger me to immediately launch a new thread when in seeking mode, and not await the current sequential chunk. Yes it will share bandwidth, but is likely to have better latency.

If I understand correctly, you keep the one background thread downloading the song, and spawn a new connection for each seek then?

If that's correct, I wonder how that compares to using a single HTTP connection and issuing smaller range requests on the same connection. I believe this is possible with HTTP, but its been a while! 😅

Ultimately, removing as many seeks as possible is the best optimization though :)

You could try just using the read length Symphonia issues your Reader. It'll grow from 1 kB to a maximum of 32 kB.

While getting the desired/suggested chunk size from Symphonia would be great, <32 kB chunks does not seem ideal for HTTPS. It would result in many network requests with a relatively low header-to-content ratio.

I am a bit confused about the minimum buffer_len in MediaSourceStreamOptions and how that relates to the 1-32 kB buffer you describe. The documentation states that buffer_len must be >32 kB and a power of two. Indeed setting it to <64 kB returns thread '<unnamed>' panicked at 'assertion failed: options.buffer_len > Self::MAX_BLOCK_LEN'.

So, internally MediaSourceStream has a ring buffer of length buffer_len bytes.

When the ring buffer is empty, or it has been entirely consumed, MediaSourceStream reads a new chunk of data from the underlying Reader and stores it in the ring buffer.

The size of those chunks that are read from underlying Reader start at 1 kB in size, and grow up-to a maximum of 32 kB. When a seek occurs, the chunk size is reset back down to 1 kB.

So when a demuxer is simply consuming the media sequentially, MediaSourceStream reads big (32 kB) chunks from the underlying source. But if a demuxer is seeking around the file a lot, the MediaSourceStream will only read small (1 kB) chunks from the source. This optimizes the time it takes to perform the seek which is important in cases where we need to bisect the file (e.g., OGG seeks).

The reason why buffer_len must be a minimum of 64 kB is because:

1. The ring buffer must be atleast 32 kB since that's the maximum chunk size the MediaSourceStream will read from the underlying Reader.
2. The MediaSourceStream allows you to always rewind min(32kB, num_bytes_read) bytes without performing a real seek on the underlying source (see MediaSourceStream::seek_buffered, MediaSourceStream::seek_buffered_rel).

In practice, these requirements mean that the ring buffer can't be smaller than 64 kB. We also have the function MediaSourceStream::ensure_seekback_buffer that allows a demuxer to request an even larger rewind length if required.

Ultimately though, the fastest solution would be to decode the Spotify seek table since instead of many seeks we can only do one.

I've read that Spotify adds a non-standard seek index packet to their OGG files reduce the number of seeks. If you have any docs on that I could look into implementing support for it.

Spotify does prepend the file with its own Ogg header which is 167 bytes in length. Right now we get the normalisation values from it (they are not there with normal ReplayGain tags, but as specific bytes), then skip ahead and act as if byte 168 were actually byte 0 and we feed that to Symphonia.
This is the Spotify Ogg header deciphered as far as I know: https://sourceforge.net/p/despotify/code/346/tree/java/trunk/src/main/java/se/despotify/client/player/SpotifyOggHeader.java

This is just a guess from looking at the code, but...
It looks like the /* Table Lookup */ section is reading 100 bytes from the packet and uses each of those bytes to index into a lookup table that specifies a length value. On each iteration, the length value is added to an accumulator, and the value of the accumulator is stored in that iteration's respective table index.
So, based off this I assume that the seek table splits the file up into 100 segments, and stores the byte (or kB) offset to the start of each segment in the table. This is my hypothesis, but perhaps there's more too it.

Well thought out! Assuming that were the case, how would that best work its way into Symphonia? I think it would need to be an extension there somewhere, fed by librespot?

I think first we need to prove that's how the seek table works.

Since you mentioned that librespot already parses this OGG packet, why not have it print out the seek table. Then we can compare the byte offsets for those 100 segments and see how they compare to the byte offsets of the OGG packets themselves.

The following command can be used to dump all the packet information to a file:

ffprobe -show_packets -of json /path/to/file.ogg > packets.json

If this is how the seek table works, then I think we may need to make it an optional feature of the Symphonia OGG demuxer since it's a proprietary feature of Spotify. Or, like you suggested, maybe we have to provide a way for external users to hook in custom packet parsers... Going to need to have a think on that one.