Changeset 9e83b15

Timestamp:

2018-07-03T05:58:47Z (6 years ago)

Author:

dequis <dx@…>

Branches:

master

Children:

c17d0af

Parents:

49ab3cb

git-author:

dequis <dx@…> (03-07-18 05:27:59)

git-committer:

dequis <dx@…> (03-07-18 05:58:47)

Message:

Add a hash table to speed up bee_user_by_handle()

This maintains a hash table next to the linked list, which results in
negligible additional memory usage (~300kb for 10k users) but allows
instant lookups.

This was a big problem with discord, which has huge user lists and joins
everyone to every channel. In my test, the GUILD_SYNC event for 10k-50k
user lists is now approximately 5 times faster.

This hash table based code is only used if handle_cmp is either
exact or case-insensitive string comparison (g_ascii_strcasecmp or
strcmp/g_strcmp0).

The old function that goes through the bee->users linked list is now
called bee_user_by_handle_slow() and used for protocols with unusual
handle_cmp functions - skimming through the code, just oscar.
May revisit this if it happens to more meaningful protocols.

The case-insensitive hashtable functions are copied from irssi, which is
also GPLv2. I renamed them from g_ to b_ (g_istr_equal to b_istr_equal)

Files:

• lib/misc.c (modified) (1 diff)
• lib/misc.h (modified) (1 diff)
• protocols/bee_user.c (modified) (4 diffs)
• protocols/nogaim.c (modified) (3 diffs)
• protocols/nogaim.h (modified) (1 diff)

lib/misc.c

@@ -774 +774 @@
         }
 }
+
+/* copied from irssi's misc.c, by timo sirainen */
+int b_istr_equal(gconstpointer v, gconstpointer v2)
+{
+        return g_ascii_strcasecmp((const char *) v, (const char *) v2) == 0;
+}
+
+/* copied from irssi's misc.c, by lemonboy */
+guint b_istr_hash(gconstpointer v)
+{
+        const signed char *p;
+        guint32 h = 5381;
+
+        for (p = v; *p != '\0'; p++) {
+                h = (h << 5) + h + g_ascii_toupper(*p);
+        }
+
+        return h;
+}

lib/misc.h

@@ -151 +151 @@
 G_MODULE_EXPORT char *str_pad_and_truncate(const char *string, long char_len, const char *ellipsis);
 
+G_MODULE_EXPORT int b_istr_equal(gconstpointer v, gconstpointer v2);
+G_MODULE_EXPORT guint b_istr_hash(gconstpointer v);
+
 #endif

protocols/bee_user.c

@@ -42 +42 @@
         bee->users = g_slist_prepend(bee->users, bu);
 
+        if (ic->bee_users) {
+                g_hash_table_insert(ic->bee_users, bu->handle, bu);
+        }
         if (bee->ui->user_new) {
                 bee->ui->user_new(bee, bu);
@@ -67 +70 @@
                 bu->ic->acc->prpl->buddy_data_free(bu);
         }
-
+        if (bu->ic->bee_users) {
+                g_hash_table_remove(bu->ic->bee_users, bu->handle);
+        }
         bee->users = g_slist_remove(bee->users, bu);
 
@@ -80 +85 @@
 }
 
-bee_user_t *bee_user_by_handle(bee_t *bee, struct im_connection *ic, const char *handle)
+bee_user_t *bee_user_by_handle_slow(bee_t *bee, struct im_connection *ic, const char *handle)
 {
         GSList *l;
@@ -93 +98 @@
 
         return NULL;
+}
+
+bee_user_t *bee_user_by_handle(bee_t *bee, struct im_connection *ic, const char *handle)
+{
+        if (!ic->bee_users) {
+                return bee_user_by_handle_slow(bee, ic, handle);
+        }
+
+        return g_hash_table_lookup(ic->bee_users, handle);
 }
 

protocols/nogaim.c

@@ -298 +298 @@
 {
         struct im_connection *ic;
+        GHashFunc fn_hash = NULL;
+        GEqualFunc fn_equal = NULL;
 
         ic = g_new0(struct im_connection, 1);
@@ -304 +306 @@
         ic->acc = acc;
         acc->ic = ic;
+
+        /* figure out if we have hashing functions compatible with handle_cmp */
+        if (acc->prpl->handle_cmp == g_ascii_strcasecmp) {
+                fn_hash = b_istr_hash;
+                fn_equal = b_istr_equal;
+        } else if (acc->prpl->handle_cmp == g_strcmp0 || acc->prpl->handle_cmp == strcmp) {
+                fn_hash = g_str_hash;
+                fn_equal = g_str_equal;
+        }
+
+        /* only create the hash table if we found them */
+        if (fn_hash && fn_equal) {
+                ic->bee_users = g_hash_table_new_full(fn_hash, fn_equal, NULL, NULL);
+        }
 
         connections = g_slist_append(connections, ic);
@@ -320 +336 @@
                         break;
                 }
+        }
+
+        if (ic->bee_users) {
+                g_hash_table_destroy(ic->bee_users);
         }
 

protocols/nogaim.h

@@ -97 +97 @@
         GSList *groupchats;
         GSList *chatlist;
+        GHashTable *bee_users;
 };