From 95d8bb2e8551e61d1603f588dbed053344fada80 Mon Sep 17 00:00:00 2001 From: Rapptz Date: Mon, 24 Sep 2018 22:06:49 -0400 Subject: 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. --- discord/utils.py | 34 +++++++++++++++++++++++++++++++++- 1 file changed, 33 insertions(+), 1 deletion(-) (limited to 'discord/utils.py') 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 -- cgit v1.2.3