Make shuffling more random

[Yanpas]

Reopening #4997 Steps to repro:

1. Open playlist with sevevral songs, play song a
2. Then hit next, you will be listening to song b
3. Hit next several times
4. Double click song a, hit next and again you are listening to song b!

Hitting "stop" or "previous song" resets random seed

[Ferroin]

I can't reproduce this as of c4c094aa716335c359d16b329e76581a8ae7ff69 on 64-bit Gentoo Linux.

[santigl]

I was able to reproduce it with ce77a0acb8c3c595eadb44ab49f908518eb47407 on 64-bit Debian, both with Repeat and Repeat Album.

[Ferroin]

Correction, I can reproduce it, I had been stopping between 3 and 4, which was resetting the ordering.

I'd actually be kind of curious to see how may other music players display similar behavior. I know at least most MP3 players other than iPods do this (iPods might, but I'm not sure), and I know that at least at one point Windows Media Player did this too.

The reason this happens is that Clementine is generating the randomized play order when you start playing the first song, and then caching that order. This allows for (theoretically) seamless playback of local music on slower devices (on such devices, determining the next song when we switch can introduce a noticeable delay between songs, which is undesirable for most people, and trying to determine while the current song is playing can cause stuttering in playback).

[Yanpas]

Deadbeef and Banshee reset order each time. Maybe it should be optional.

Didn't know about reseting by pressing stop (I don't use this button at all), I guess I will be satisfied with it

[Ferroin]

To be honest, I didn't realize before this that Clementine was caching the play order when shuffling, so I guess we both learned something.

I do think it would be a nice feature to be able to tell Clementine to not cache the play order though, but I have no idea how difficult that might be to implement.

[santigl]

I was wondering if it could be fixed by forcing it to re-shuffle on manual track changes. I then went to the source code, and it seems to me that it could be the behaviour that's intended.

In player.cpp there's this function:

// Manual track change to the specified track    
virtual void PlayAt(int i, Engine::TrackChangeFlags change, bool reshuffle) = 0;

Which has the following statement:

if (reshuffle) app_->playlist_manager()->active()->ReshuffleIndices();

Looking at its usages, it is always called with reshuffle=true from mainwindow.cpp (in particular, from MainWindow::PlaylistDoubleClick()).

Shouldn't that avoid the behaviour that @Yanpas described? (Assuming that ReshuffleIndices() does what is says.)

Edit - Here's the thing: ReshuffleIndices() is re-shuffling, but from the currently playing song onwards. The ones already played are left in the same order.

I imagine one reason for that could be to keep the previous button working properly. But is there any other scenario where it would make more sense to keep that order?

[Ede123]

As you note this ensures "previous track" is working. Also it prevents the same track to play multiple times (e.g. random order without repetitions).

Edit: If that's always desirable is probably the real question here...

[santigl]

I agree. I guess we need to think in what would be most intuitive.

If you follow @Yanpas' steps but in the last one instead of hitting next you press the back button, the playback stops. It doesn't go to the actual previously-played track.

[Ferroin]

Well, that depends on user expectations. If we change this in any way, there needs to be an option to select the old behavior. In general, I see three options for how this could behave:

1. The current behavior, the play order is determined when playback starts, and is cached until playback stops. This means the back button always works, and that you get no duplicate songs when playing through a playlist unless you manually select one.
2. The behavior I would expect, the play order is determined when playback starts, and is cached until the user manually selects a specific song (double clicking it, not seeking to it), at which point it gets regenerated. This means that as long as you don't manually select a track, the same guarantees as the above option still hold.
3. True randomness, the play order is determined dynamically by selecting a song at random from the playlist each time the track changes. This would break the back button completely, and almost guarantee duplicate songs played on short playlists, but based on some other discussions I've seen, there are people who would likely prefer this kind of behavior.

Both option 2 and 3 could have an optional queue of recently played songs that lets you go back up to some limit of times before you get a random song.

The other thing to ask though, is how any changes to this might impact the Queue functionality in Clementine. Under the current semantics, when you Queue a song and shuffle is enabled, you got o that song next, and then resume the ordering dictated by the cached play order when the queue is empty. I personally would really like to see this behavior (being able to queue a couple of songs, and then let Clementine go back to what it was doing when the queue is finally empty) preserved regardless of how shuffling works.

[santigl]

I agree with you, I find option 2 to be the most intuitive. What it is not that clear to me is what should be expected of the previous button.

What if on manual selection of a track we also re-shuffle the previous songs but keeping them in their relative order to the current track (i.e. to the left of the current track)? That way we could avoid the current behaviour, and the previous button would give you a "previous" track, also using a random logic.

[Ferroin]

OK, just to make sure I understand what you mean: Assuming you have a playlist of seven songs numbered 1 to 7, and you decide to shuffle the playlist with repeat off and get this order internally: 3, 1, 2, 4, 7, 5, 6 Assume you play through to track 4: 3, 1, 2, [4], 7, 5, 6 And then decide you want to listen to track 5 next. Using the current behavior, you would end up with: 3, 1, 2, 4, 7, [5], 6 Using the second behavior I listed, you might end up with: [5], 7, 3, 1, 4, 6, 2 Under your suggestion , would you get something like this: 2, 3, 1, [5], 6, 4, 7 Or something like this: 2, 4, 7, 1, 3, [5], 6

The biggest benefit to either way would be that it's less likely when you switch tracks that you'll end up with a track that just got played. However, I think the idea would be difficult to clearly explain to some people (keep in mind if these get added as configuration options, we need to be able to explain them in a short sentence), and it would likely result in a bigger spike in resource usage when the track is changed manually (because you have to then process two lists, and do some other fancy handling potentially).

[santigl]

Shuffling the two portions, unless I am wrong about the way the list is handled on manual changes, you would get: 2, 3, 1, 4, [5], 6, 7; or 2, 4, 1, 3, [5], 7, 6

That would be the result of doing shuffle(begin, current-1) and shuffle(current+1, end), where current is the one between brackets.

However, after [5] you would still get tracks you have already listened to, but in a different order. I don't know if it's a good idea. It might be better to do a complete reshuffle and avoid listened tracks altogether...

[capponz]

Hi, I use Clementine 1.3.1. I have a playlist of mixed files mp3, mp4, wav, ogg and flac. Unfortunately some songs are not played at all. I mean never. The playlist runs for half a year now in a little caffe. It's different with amarok or rhythmbox. The randomness is much better with those. the remote android option is better though thats why I stick with Clementine.

[yetisyny]

Following the steps in the original post of this issue by @Yanpas this problem still exists. However, there is a workaround now, at least in current builds.

1) Make sure shuffle mode is on and a playlist full of songs is loaded. 2) Click on a song in the playlist to play it. 3) Click on the exact same song again to play it again, while the song is still playing.

This should alter the play order that shuffle mode uses.

It took me awhile to figure this out. Anyway if you want to reshuffle you can use this trick for now.

Of course if you click on song A, and then skip forward to song B, and click on song A again, and skip forward, it will play the exact same song B again and have the same shuffle order, so the original issue is still present if you follow those steps.

You have to click the same song that is currently playing, WHILE it is playing, to change the shuffle order.

So while there is still an issue in the shuffle mode being set in stone unless you do a trick to change it, there IS a trick to change it, at least, and it is pretty easy, just double-click a song to play it and double-click that exact same song a second time while it is still playing, and the shuffle order is changed. I think issue #571 is the one that made this trick to change the shuffle order work.

Of course the new shuffle order will be set in stone until you use this trick again to change it again, which is still an annoyance. And this issue should not be considered resolved unless the steps in the initial post of this issue produce different results each time rather than the same results each time. Still, at least there has been some progress since this issue was first posted.

And as far as making the randomness better, there are some much better pseudorandom number generator algorithms out there that are very fast with very good randomness characteristics, not too much memory usage, and very few lines of code. Currently the best PRNG (pseudorandom number generator) is one called xoroshiro128+, please see http://xoroshiro.di.unimi.it/ for info on that. Here is the source code for the xoroshiro128+ algorithm in C (also works in C++), from that website. It is public domain code, that means you can use it in anything, I highly suggest using this as the random number generator, it is currently the best pseudorandom number generator out there for general-purpose stuff, it generates pseudorandom 64-bit unsigned integers:

/*  Written in 2016 by David Blackman and Sebastiano Vigna (vigna@acm.org)

To the extent possible under law, the author has dedicated all copyright
and related and neighboring rights to this software to the public domain
worldwide. This software is distributed without any warranty.

See <http://creativecommons.org/publicdomain/zero/1.0/>. */

#include <stdint.h>

/* This is the successor to xorshift128+. It is the fastest full-period
   generator passing BigCrush without systematic failures, but due to the
   relatively short period it is acceptable only for applications with a
   mild amount of parallelism; otherwise, use a xorshift1024* generator.

   Beside passing BigCrush, this generator passes the PractRand test suite
   up to (and included) 16TB, with the exception of binary rank tests, as
   the lowest bit of this generator is an LFSR of degree 128. The next bit
   can be described by an LFSR of degree 8256, but in the long run it will
   fail linearity tests, too. The other bits needs a much higher degree to
   be represented as LFSRs.

   We suggest to use a sign test to extract a random Boolean value, and
   right shifts to extract subsets of bits.

   Note that the generator uses a simulated rotate operation, which most C
   compilers will turn into a single instruction. In Java, you can use
   Long.rotateLeft(). In languages that do not make low-level rotation
   instructions accessible xorshift128+ could be faster.

   The state must be seeded so that it is not everywhere zero. If you have
   a 64-bit seed, we suggest to seed a splitmix64 generator and use its
   output to fill s. */

uint64_t s[2];

static inline uint64_t rotl(const uint64_t x, int k) {
    return (x << k) | (x >> (64 - k));
}

uint64_t next(void) {
    const uint64_t s0 = s[0];
    uint64_t s1 = s[1];
    const uint64_t result = s0 + s1;

    s1 ^= s0;
    s[0] = rotl(s0, 55) ^ s1 ^ (s1 << 14); // a, b
    s[1] = rotl(s1, 36); // c

    return result;
}

/* This is the jump function for the generator. It is equivalent
   to 2^64 calls to next(); it can be used to generate 2^64
   non-overlapping subsequences for parallel computations. */

void jump(void) {
    static const uint64_t JUMP[] = { 0xbeac0467eba5facb, 0xd86b048b86aa9922 };

    uint64_t s0 = 0;
    uint64_t s1 = 0;
    for(int i = 0; i < sizeof JUMP / sizeof *JUMP; i++)
        for(int b = 0; b < 64; b++) {
            if (JUMP[i] & UINT64_C(1) << b) {
                s0 ^= s[0];
                s1 ^= s[1];
            }
            next();
        }

    s[0] = s0;
    s[1] = s1;
}

Anyway this xoroshiro128+ pseudorandom number generator is much, much better than what you are using, that ancient PRNG from 1997 in the file RandomNumberGenerators.hpp, back before modern pseudorandom number generators with much better randomness characteristics coupled with high speed were gradually developed over the course of the 2000s-2010s. For the specific purposes of shuffling songs in an audio player or most other general-purpose stuff, xoroshiro128+ is the best PRNG to use. There are also other kinds of PRNGs such as long-period ones or ones that are cryptographically secure but those properties are entirely unnecessary here and would only slow things down and use more CPU and memory for no practical reason. This one is very fast and very random.

[hatstand]

I promise you that you Clementine doesn't need a better random number generator. What you're looking for is something which feels more random by doing tricks like never playing the same track twice in a row.

[yetisyny]

Oops, my previous suggestion causes weird things to happen. If you double-click a playing song to play it again and get a different song to play after it, you get weird results. I have a playlist of over 500 songs, for instance, and there are about 20 tracks where, if any one of them is playing, it will play the next one in its cached list of those 20 or so tracks, when shuffle mode is on. So those 20 or so tracks are played again and again and the other close to 500 tracks do not get played at all. Yeah the shuffle mode is totally broken in Clementine, I am using the latest nightly build. Also broken in latest stable build of Clementine too.

So wow the shuffle thing is seriously broken, yeah. Playing about 1/25th of the songs in my playlist and ignoring the rest, pretty annoying hearing those songs again and again and not hearing the rest of them. And if I play one of the songs that isn’t one of those 20 or so tracks, the shuffle order typically has, a couple tracks later, typically one of the 20 tracks that is in this weird loop. So I would like it more random, in the sense of, hey it should play all the songs on the playlist instead of just a fraction of them, geez. Over time this problem has gotten worse with my trick of changing the shuffle order for just one song, since that makes multiple songs point to the same next song as the next song, and then there are songs that do not have any song at all point to them as the next song so they never get played. So my trick to change the shuffle order I mentioned in the previous comment just makes this problem get worse and worse.

How do I delete the shuffle order cache so it is regenerated from scratch? I need to do that.

EDIT: I figured out how to do it. I deleted the SQLite database for Clementine whose location is indicated in the FAQ at https://github.com/clementine-player/Clementine/wiki/Frequently-asked-questions. That fixes this temporarily at least. But then I have to avoid double-clicking on the currently playing item or else that will change the shuffle order and get things messed up again so that some songs never get played. So annoying!

[gabuzom]

All glory to Clementine, the best media player ever! <3

I can confirm that the issue is still there in Clementine 1.3.1.

@hatstand may be right that it isn't the random generator that has a problem. Yet the shuffle is still terribly broken (and the result is something that is not random at all).

It happened to me frequently on very big playlists (x0.000 tracks), when shuffle gets stuck over a very small number of albums (6-10) and shuffles only among tracks there (usually some track that were added around the same time) and still unsure if it actually plays them all in this subset... so out of dozen thousand tracks, a few get played many times, while a vast majority will never ever be played. Very frustrating.

Was looking for a work-around for a while and @yetisyny showed me the way! I think that if while a track is playing you actually press stop then press play (did that a few times), on the same track, you unf*ck the situation and free the shuffle from its sad buggy loops... still testing, but since i tried this the shuffle now jumps up and down again all over the place!

Hope it helps. <3

[Venryx]

I'm also a bit annoyed by the shuffling behavior of Clementine. I prefer the 2nd approach listed by @Ferroin here: https://github.com/clementine-player/Clementine/issues/5201#issuecomment-171385730

However, I'd prefer it to have one modification: If you listen to every song in a playlist, and thus a loop operation for the playlist is activated, a new shuffling should automatically be applied at that point.

This way, you don't have to re-hear the same song sequence on the second playthrough of the playlist! (when just leaving it running on its own in the background)

This is especially important for smaller playlists where you might go over all the songs multiple times in one sitting.

I'd also like the 3rd option in his post to be available (true random after each song play).

The main reason is that I like the idea that "which song comes next" is undetermined until the moment I reach the next song (like Shrodinger's Cat). I know this will increase the occurrence of "the same song playing twice in a row", and it's not a "functional" advantage; but the option of having it undetermined before the time of playing is something I'd still like to see. (certainly lower priority than making his 2nd option, + my shuffling-after-playlist-completion addendum, added however)

[jdoe1024]

I do see the same behavior as others, where shuffling is stuck to some albums while the playlist contains much more. After digging into the code, I think I've found the cause of that in Playlist::ReshuffleIndices():

  // If the user is already playing a song, advance the begin iterator to
  // only shuffle items that haven't been played yet.
  QList<int>::iterator begin = virtual_items_.begin();
  QList<int>::iterator end = virtual_items_.end();
  if (current_virtual_index_ != -1)
    std::advance(begin, current_virtual_index_ + 1);

So basically, when reshuffling the list of songs while playing a song (for instance, when changing shuffling mode while playing a song), only the songs from the next song in the playlist to the last song in the playlist will be part of the shuffling, excluding all the songs from the beginning of the playlist to the current song being played. I do not see the logic behind this: when I want to shuffle the songs playing order, I want all the songs from the playlist to be included, not just the songs at the end of the playlist! This also explains why stopping the playback of current song and starting it again fixes the issue (it reshuffles the full playlist before playback is started again since there is no song being played).

The changes come from commit b8ee548eb495f53d3509fd41c832ddf74c2ff964. Removing the check and the call to std::advance() fixes the issue for me.