Change internal representation of roles in Member and Emoji.

Introduce a new internal type, SnowflakeList, which has better memory
footprint over a regular list or set of roles. It is suspected that
there will be a 9x reduction of memory for every Emoji instance and a
48 byte saving per Member instance. However, these savings will
probably only be evident on larger bots.

As a consequence of this change, Member.roles is now computed lazily.

Currently I am not sure if I want to do the initial sorting on the
SnowflakeList for Member, as this comes with a O(n log n) cost when
creating a Member for little purpose since SnowflakeList.has is not
overly relied on. If CPU time becomes an issue this might change.

1 files changed, 33 insertions, 1 deletions

diff --git a/discord/utils.py b/discord/utils.py
index 6bdfc36e..f536200f 100644
--- a/discord/utils.py
+++ b/discord/utils.py
@@ -26,13 +26,16 @@ DEALINGS IN THE SOFTWARE.
 
 from re import split as re_split
 from .errors import InvalidArgument
-import datetime
 from base64 import b64encode
 from email.utils import parsedate_to_datetime
 from inspect import isawaitable as _isawaitable
+from bisect import bisect_left
+
+import datetime
 import asyncio
 import json
 import warnings, functools
+import array
 
 DISCORD_EPOCH = 1420070400000
 
@@ -289,3 +292,32 @@ async def sane_wait_for(futures, *, timeout, loop):
 def valid_icon_size(size):
     """Icons must be power of 2 within [16, 1024]."""
     return ((size != 0) and not (size & (size - 1))) and size in range(16, 1025)
+
+class SnowflakeList(array.array):
+    """Internal data storage class to efficiently store a list of snowflakes.
+
+    This should have the following characteristics:
+
+    - Low memory usage
+    - O(n) iteration (obviously)
+    - O(n log n) initial creation if data is unsorted
+    - O(log n) search and indexing
+    - O(n) insertion
+    """
+
+    __slots__ = ()
+
+    def __new__(cls, data, *, is_sorted=False):
+        return array.array.__new__(cls, 'Q', data if is_sorted else sorted(data))
+
+    def add(self, element):
+        i = bisect_left(self, element)
+        self.insert(i, element)
+
+    def get(self, element):
+        i = bisect_left(self, element)
+        return self[i] if i != len(self) and self[i] == element else None
+
+    def has(self, element):
+        i = bisect_left(self, element)
+        return i != len(self) and self[i] == element