Re: EMMS MPD consume patch

Yoni Rabkin <[email protected]> writes:

> Ian Eure <[email protected]> writes:
>
>> Yoni Rabkin <[email protected]> writes:
>>
>>> Ian Eure <[email protected]> writes:
>>>
>>>> Yoni Rabkin <[email protected]> writes:
>>>>
>>>>> Ian Eure <[email protected]> writes:
>>>>>
>>>>>> Hi again,
>>>>>>
>>>>>> Seeing as I’m currently unemployed, therefore no employer 
>>>>>> can
>>>>>> make
>>>>>> any
>>>>>> IP claims on my work, I started hacking on an enhanced 
>>>>>> cleanroom
>>>>>> take
>>>>>> on my previous work.  I’m sending over a WIP patch, since 
>>>>>> I’ve
>>>>>> run
>>>>>> into a situation I’m not sure how to deal with, and figured 
>>>>>> you
>>>>>> might
>>>>>> have some feedback.
>>>>>
>>>>> We'd be happy for that work; thank you.
>>>>>
>>>>>> I don’t have a great solution for this.  While leaning on 
>>>>>> track
>>>>>> order
>>>>>> certainly isn’t robust, it is very efficient.  The only 
>>>>>> solution
>>>>>> I’m
>>>>>> coming up with is shoving the songid into the EMMS track
>>>>>> structure
>>>>>> (in
>>>>>> emms-player-mpd-get-tracks-1), and doing a linear scans to 
>>>>>> locate
>>>>>> the
>>>>>> correct song(s).  I dislike this, since my own EMMS/MPD 
>>>>>> usage has
>>>>>> playlists with thousands of songs in them.
>>>>>
>>>>> Why not maintain a hash table to avoid the linear scan? Even 
>>>>> a
>>>>> 100,000-item hash table remains small in terms of memory 
>>>>> footprint
>>>>> and
>>>>> very fast.
>>>>>
>>>>
>>>> I don’t think a hash table buys anything here.  For it to be
>>>> useful,
>>>> the key would be the song ID, and the value would be either 
>>>> the
>>>> playlist or buffer position of that song in the playlist 
>>>> (both
>>>> amount
>>>> to the same thing).  But in consume mode, songs are deleted 
>>>> after
>>>> they’re played, which means the hash table has to be updated 
>>>> to
>>>> reflect the new positions, which is an O(n) operation as 
>>>> well. So I
>>>> think it’s more complexity for no gain over scanning the 
>>>> buffer.
>>>
>>> I'm probably not tracking the real problem since most hash 
>>> table
>>> operations are O(1) on average and only O(n) at their worst.
>>>
>>> Do we:
>>>
>>> Load in the remote playlist to emms. That's N operations where 
>>> N is
>>> the
>>> number of entries. The hash table is populated at that time.
>>>
>>> MPD consumes a track X. It takes O(1) to find track X in the 
>>> hash,
>>> which
>>> means we can go right to it in the playlist and delete it from 
>>> a
>>> playlist no matter where it is.
>>>
>>> Track X is then deleted from the hash as well (since we know 
>>> which
>>> track
>>> was played, we know what track X is.)
>>>
>>> But I don't actually know what I'm talking about. This is how 
>>> I
>>> imagine
>>> it to work. What am I missing?
>>
>> The problem to solve is: given two songids, how do we move from 
>> songid
>> A to songid B in a playlist?
>
>> To solve this with a hash table, the keys need to be a songid, 
>> and the
>> value needs to be the playlist position, which is a 0-based 
>> index into
>> the playlist.  The first song has position 0, second 1, on up 
>> to N-1,
>> where N is the number of songs in that playlist.
>>
>> Now you can do things like look up a songid, get its playlist 
>> index,
>> go to the beginning of the playlist buffer, and advance some 
>> number of
>> lines equal to the value from the hash; or look up two values,
>> subtract them, and move that number of lines.
>>
>> This works great as long as the playlist never changes.  If you 
>> delete
>> a track from the playlist (which consume mode does for you
>> automatically, after it’s been played), the index of every 
>> following
>> track is decremented.  The values in the hash table are now off 
>> by
>> one, and the error grows the more songs are removed.
>
>> Fixing that means updating the values in the hash table. 
>> Updating a
>> single value is O(1), but O(n) operations have to be performed 
>> to
>> update everything which changed.  So you end up with the worst
>> outcome, more complex code for the same O(n) performance
>> characteristic of a linear scan of the buffer.
>
> This only happens the result of the track being consumed by MPD 
> is that
> it is also killed from the playlist buffer. If you visually mark 
> the
> track as "consumed by mpd" in some way, then all of the tracks 
> remain in
> position.
>
>> I think I have an approach that will work, I’ll try to hack on 
>> that a
>> bit more this week.  It’s just not terribly elegant, which I 
>> dislike.
>>
>>
>>> Taking a step back, the hash table would not be an mpd-player
>>> specific
>>> tool, but an extension of emms-playlist-mode, which would 
>>> provide a
>>> different way of accessing tracks. This manner of access, 
>>> which
>>> would
>>> need to be kept syncronized with the playlist, can help 
>>> accelerate
>>> access to a specific track in cases where people create a 
>>> playlist
>>> with
>>> many thousands of tracks.
>>>
>>> A lot to think about...
>>>
>>
>> I don’t have a strong opinion on this, as it’s mostly outside 
>> the
>> scope of what I’m trying to accomplish.
>>
>> FWIW, consume mode issues aside, EMMS handles large playlists 
>> much,
>> much better than other Emacs MPD clients I’ve tried.  Emmet, 
>> for
>> example, refreshes the entire playlist on any change, which is 
>> slow
>> enough to make my whole Emacs session pause on every track 
>> change.  My
>> typical MPD use is to load nearly my entire music library, 
>> shuffle it,
>> then run that in consume mode until it’s empty, which means I
>> regularly have 8000+ songs in the playlist; so this is 
>> immediately
>> disqualifying.
>
> Please bear with me here as I try to understand the problem and 
> the use
> case. I don't use MPD. I apologize for my slow uptake here.
>

No problem, we’re pretty deep in the weeds at this point.

> If you start by loading 8,000 tracks and shuffling them in MPD, 
> then
> that will be the order that they appear in Emms. Why do you need 
> to do
> anything to find the next song? Isn't it simply the next track?
>
> What you are describing seems to be that the MPD playlist is 
> shuffled,
> but the Emms playlist has a different order. Is that correct? 
> Why can't
> we have the Emms playlist mirror the shuffled MPD playlist? 
> Looking for
> that next track would always take exactly one step. The track 
> doesn't
> even need to be killed from the playlist buffer as long as there 
> is an
> indication for the user that the remote end is in "consume" 
> mode.

Shuffle is a command that performs a one-time randomization of the 
playlist, so yes, if you shuffle, then connect up EMMS, things 
will be fine.  However, MPD also has four mode bits which change 
its behavior when it reaches the end of a song:

- "repeat" loops the song.
- "random" chooses a random songe in the playlist instead of 
  advancing to the next one.
- "consume" deletes the just-played song.
- "single" stops playback after the current song.

Any combination of these can be enabled at the same time, so you 
can both play random songs and delete when they finish.  When 
random is enabled, you can’t assume the next song in playlist 
order will be the next to get played, whether you shuffled the 
playlist or not.  MPD clients need to handle all these modes, 
singly, and in combination.

(Note that I’m using MPD terms here.  Many players have a 
"shuffle" option which is the equivalent of MPD’s "random.")

> In any case, I'll let you move forward with your idea. It is 
> indeed a
> unique use case. Assuming modern music, which has about 3-minute 
> tracks,
> you are describing over 16 days of non-stop music playing. My 
> machines
> will typically not be on for that long, let alone play music for 
> that
> long.

I have a low-power single-board computer dedicated to music 
playback which I never turn off; but MPD persists its state 
anyhow, so my playlist would survive a reboot.  It typically takes 
me a few months to get through the whole playlist.  Then I load it 
up and do it over again.

The problem of correctly handling MPD mode bits in EMMS isn’t 
necessarily unique to how I use it, though it certainly exposes 
those kind of bugs quickly.

  — Ian