Ian Eure <ian@retrospec.tv> writes:
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.
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.