Re: EMMS MPD consume patch

[Ian Eure]

Yoni Rabkin <yoni@rabkins.net> writes:

> Ian Eure <ian@retrospec.tv> writes:
>
> > Yoni Rabkin <yoni@rabkins.net> writes:
> >
> > > Ian Eure <ian@retrospec.tv> 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.

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.


> Also, can we please move this to the emms-help mailing list? I 
> didn't CC
> this to there because I don't want to do so without your 
> permission.

Definitely, I’ve moved you to bcc and redirected to the ML.

Thatnks,

 — Ian