Changeset 9e83b15


Ignore:
Timestamp:
2018-07-03T05:58:47Z (6 months 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:
5 edited

Legend:

Unmodified
Added
Removed
  • lib/misc.c

    r49ab3cb r9e83b15  
    774774        }
    775775}
     776
     777/* copied from irssi's misc.c, by timo sirainen */
     778int b_istr_equal(gconstpointer v, gconstpointer v2)
     779{
     780        return g_ascii_strcasecmp((const char *) v, (const char *) v2) == 0;
     781}
     782
     783/* copied from irssi's misc.c, by lemonboy */
     784guint b_istr_hash(gconstpointer v)
     785{
     786        const signed char *p;
     787        guint32 h = 5381;
     788
     789        for (p = v; *p != '\0'; p++) {
     790                h = (h << 5) + h + g_ascii_toupper(*p);
     791        }
     792
     793        return h;
     794}
  • lib/misc.h

    r49ab3cb r9e83b15  
    151151G_MODULE_EXPORT char *str_pad_and_truncate(const char *string, long char_len, const char *ellipsis);
    152152
     153G_MODULE_EXPORT int b_istr_equal(gconstpointer v, gconstpointer v2);
     154G_MODULE_EXPORT guint b_istr_hash(gconstpointer v);
     155
    153156#endif
  • protocols/bee_user.c

    r49ab3cb r9e83b15  
    4242        bee->users = g_slist_prepend(bee->users, bu);
    4343
     44        if (ic->bee_users) {
     45                g_hash_table_insert(ic->bee_users, bu->handle, bu);
     46        }
    4447        if (bee->ui->user_new) {
    4548                bee->ui->user_new(bee, bu);
     
    6770                bu->ic->acc->prpl->buddy_data_free(bu);
    6871        }
    69 
     72        if (bu->ic->bee_users) {
     73                g_hash_table_remove(bu->ic->bee_users, bu->handle);
     74        }
    7075        bee->users = g_slist_remove(bee->users, bu);
    7176
     
    8085}
    8186
    82 bee_user_t *bee_user_by_handle(bee_t *bee, struct im_connection *ic, const char *handle)
     87bee_user_t *bee_user_by_handle_slow(bee_t *bee, struct im_connection *ic, const char *handle)
    8388{
    8489        GSList *l;
     
    9398
    9499        return NULL;
     100}
     101
     102bee_user_t *bee_user_by_handle(bee_t *bee, struct im_connection *ic, const char *handle)
     103{
     104        if (!ic->bee_users) {
     105                return bee_user_by_handle_slow(bee, ic, handle);
     106        }
     107
     108        return g_hash_table_lookup(ic->bee_users, handle);
    95109}
    96110
  • protocols/nogaim.c

    r49ab3cb r9e83b15  
    298298{
    299299        struct im_connection *ic;
     300        GHashFunc fn_hash = NULL;
     301        GEqualFunc fn_equal = NULL;
    300302
    301303        ic = g_new0(struct im_connection, 1);
     
    304306        ic->acc = acc;
    305307        acc->ic = ic;
     308
     309        /* figure out if we have hashing functions compatible with handle_cmp */
     310        if (acc->prpl->handle_cmp == g_ascii_strcasecmp) {
     311                fn_hash = b_istr_hash;
     312                fn_equal = b_istr_equal;
     313        } else if (acc->prpl->handle_cmp == g_strcmp0 || acc->prpl->handle_cmp == strcmp) {
     314                fn_hash = g_str_hash;
     315                fn_equal = g_str_equal;
     316        }
     317
     318        /* only create the hash table if we found them */
     319        if (fn_hash && fn_equal) {
     320                ic->bee_users = g_hash_table_new_full(fn_hash, fn_equal, NULL, NULL);
     321        }
    306322
    307323        connections = g_slist_append(connections, ic);
     
    320336                        break;
    321337                }
     338        }
     339
     340        if (ic->bee_users) {
     341                g_hash_table_destroy(ic->bee_users);
    322342        }
    323343
  • protocols/nogaim.h

    r49ab3cb r9e83b15  
    9797        GSList *groupchats;
    9898        GSList *chatlist;
     99        GHashTable *bee_users;
    99100};
    100101
Note: See TracChangeset for help on using the changeset viewer.