Sorting members by highest role position takes extremely long in large servers (10k+ members)

[GDColon]

Please describe the problem you are having in as much detail as possible:

I made a function for the bot that finds members by their username, useful for moderation commands and such. Members with higher roles are prioritized, so the member list is sorted by highest role position to lowest. This process was near instant in v11, but ever since updating to v12 it has been taking significantly longer, sometimes up to three minutes in servers with over 10k members. The bot freezes during this process and no event handlers fire.

Include a reproducible code sample here, if possible:

let startTime = Date.now()
let sortedMembers = message.guild.members.cache.sort(function(x, y){return y.roles.highest.position - x.roles.highest.position})
console.log(Date.now() - startTime)  // 180117 (180 seconds)
console.log(sortedMembers.size)      // 13210

Further details:

• discord.js version: 12.0.2
• Node.js version: 12.6.1
• Operating system: Windows 10
• Priority this issue should have – please be realistic and elaborate if possible: Somewhat low

• [ ] I have also tested the issue on latest master, commit hash:

[SpeedyCraftah]

Can reproduce, tried this with a 100k member guild, the cluster got bottlenecked, stopped communicating with all clusters and after 20 minutes i got bored and and had to restart the whole bot due to no easy way to kill that specific cluster. It's most likely due to sort not being very efficient

[didinele]

The cause seems to be simple.

Collection#sort (v11) -> Collection#sorted (v12)

Currently, Collection#sorted returns a new sorted collection, while Collection#sort actually "sorts" the collection, updating all of the values and then returns it.

[bdistin]

Not exactly. The sorted method internally uses the new in-place sort. They will have the same performance issue they have with the new sort.

[didinele]

OH! My bad, I did not notice that.

[izexi]

The reason why it takes an absurd amount of time is because:

• Collection#sort#() sorts a Collection in place, so what that means is the Collection itself (rather an arrayified Collection#entries()) will be sorted and then the Collection will get cleared and each value from the sorted array will be set again in order
• Role#position will call Guild#_sortedRoles() which will call Util.discordSort() where Collection#sorted() will get called. The difference between the sorted and sort method is that sorted doesn't sort the Collection in place... but sorted ends up calling Collection#sort() anyways

You can workaround this by optimising this by not calling Role#position everytime to avoid the Guild#_sortedRoles() → Util.discordSort() → Collection#sorted() → Collection#sort() calls, but instead store an array of sorted role IDs and simply check the indexOf() that. As for getting the role that is in the highest position we can make use of the array that we just defined and find out which role within the GuildMemberRoleManager#cache has the highest position in respect to the array. There are multiple ways for going about this, I opted for passing an array of positions into Math.max() and some magic via the spread operator to ensure all values get passed as seperate arguements. Finally, we need to actually sort the GuildMemberRoleManager#cache Collection and for this we could emulate the behaviour of Collection#sorted() but sort the arrayified entries (instead of having it call Colleciton#sort()) which can be passed directly into the constructor of a new Collection instance.

As a result that looks something like this:

// where guild is defined as an instance of a Guild with ~23k members
const members = guild.members.cache;

console.time('oldSort');
const oldSort = members.sort(
  (prev, member) => member.roles.highest.position - prev.roles.highest.position
);
console.timeEnd('oldSort');

console.time('newSort');
const sortedRoles = guild._sortedRoles().keyArray();
const rolePos = roleId => sortedRoles.indexOf(roleId);
const highestRolePos = member =>
  Math.max(...member.roles.cache.keyArray().map(roleId => rolePos(roleId)));
const newSort = new Collection(
  [...members.entries()].sort(
    ([, prev], [, member]) => highestRolePos(member) - highestRolePos(prev)
  )
);
console.timeEnd('newSort');

// verify that they both produce both collections are in the same order
console.log(oldSort.keyArray().every((id, i) => id === newSort.keyArray()[i]));

Here are the outputs I got from the above:

oldSort: 25341.330ms
newSort: 121.948ms
true