imcb_add_buddy is slow, let's not

[Alcaro]

This should improve #159, but is not a complete fix.

Full details: bee_user_by_handle is slow. It traverses a linked list of all users, doing string comparison for each; with one call per discord_handle_user, with 10000 users, yields 10000^2/2 = 50 million string comparisons.

In practice, there are three such calls. To solve #159, we must remove them. Two are direct, the third is via imcb_add_buddy.

Two are easy to remove. With group NULL and user known to not exist already, imcb_add_buddy does nothing except call bee_user_new, so let's do that directly. This also gives us the bee_user_t*, so the last bee_user_by_handle disappears too (though that lookup takes negligible time, since that user is the head of the list).

I expect this PR should reduce the login time to roughly half. @Corosauce, try it.

If this acts as expected, the next step is removing the last call. This is a fair bit more code (we probably need a GHashTable of users), so we should take the easy one first; if it does not yield the expected result, we have to examine the issue further and find another solution.

[sm00th]

Even though bee_user_new() is in an exported header the function itself is not exported for module use, even if it was I don't think that fixing an issue with imcb_add_buddy by hacking around it in bitlbee-discord is the right way to solve this - there are other plugins that can hit this.

This is a long known issue (#47) and I even had a patch (not sure if I have it anymore and if I do if it would properly apply) that would change bitlbee-discords user handling to hashtables, but that had little effect without changes on bitlbee's side.

Fixing it in bitlbee requires considerable amount of work, but it is not an excuse to fix it elsewhere.

This patch can be used by people to try and remedy the issue on their own risk, but I see no reason to merge it to mainline, sorry.

[Alcaro]

bee_user_new is right beside bee_user_by_handle, in both header and source code, with no attributes or comments stating only one should be used by plugins. Are you aware of any documentation I'm not?

Fixing it upstream is indeed the correct long-term solution, I forgot that's an option. Did anyone report it?

[sm00th]

bee_user_new is right beside bee_user_by_handle, in both header and source code, with no attributes or comments stating only one should be used by plugins. Are you aware of any documentation I'm not?

Hm, it is. I have a feeling I ran into some problems using functions that weren't prefixed with G_MODULE_EXPORT, but seeing bee_user_by_handle without it makes me think it might be a false memory.

Fixing it upstream is indeed the correct long-term solution, I forgot that's an option. Did anyone report it?

Don't see anything like that in trac, but @dequis is definitely aware of the problem.

[dequis]

Yeah, fairly high in my list of things i'd love to do if i had time to allocate to bitlbee. Life is kind of a mess lately (moved last month, moving back now).

One idea was adding a hash table to store buddies that is kept in sync with the original linked list to ensure that all API operations still behave the same. This may or may not be feasible given the amount of direct linked list access from plugins, and whether it is read-only or read-write.

Given that this is a big issue and the API boundaries are awkward here (that linked list shouldn't have been exposed in the first place IMO), I'm OK with minor technically-breaking changes that are known to not affect existing plugins (the builtin ones plus the ones linked from the bitlbee wiki).

Of course direct linked list access should be deprecated and removed at some point in the future.

Alternatively, consider more cache-friendly linked list alternatives, something that is backed by a flat preallocated array but otherwise looks like a linked list may be enough to solve performance problems with no api changes (unless, of course, some plugin decides to keep potentially-outdated pointers around - reallocating invalidates every pointer of the list)

[Corosauce]

Alrighty, finally got a performance test run, did a test with latest of master branch vs this pr, strangely enough with or without the pr, doing a full discord join which includes the minecraft discord there has been a whole minute shaved off the connect time, so my leaving and then rejoining the discord might have messed with something, in a good way, not sure whats going on there, either way, heres my data:

with PR 160 fix:

Jun 05 22:45:50 <Corosus>   account discord on
Jun 05 22:47:32 <root>  discord - Logging in: Logged in
Jun 05 22:47:32 <root>  discord - Remote host is closing websocket connection
Jun 05 22:47:32 <root>  discord - Performing soft-reconnect

- 102 seconds to process

without fix (master branch latest):

Jun 05 22:52:41 <Corosus>   account discord on
Jun 05 22:54:25 <root>  discord - Logging in: Logged in
Jun 05 22:54:28 <root>  discord - Remote host is closing websocket connection
Jun 05 22:54:28 <root>  discord - Performing soft-reconnect

- 104 seconds to process

After seeing the similar times, I made sure that I properly pulled the source for the PR and master and that the md5 checksum on the .so file was different for each test.

Noticed I was able to actually connect in fine now too, so I dug out the logs from the testing a few days ago:

2 days ago, before i left the minecraft discord and rejoined it, with sm00ths code changes since my issue was made:

Jun 03 21:57:57 <Corosus>   account discord on
Jun 03 22:00:37 <root>  discord - Logging in: Logged in
Jun 03 22:00:42 <root>  discord - Remote host is closing websocket connection
Jun 03 22:00:42 <root>  discord - Performing soft-reconnect
Jun 03 22:00:57 <root>  discord - Error: Invalid session, reconnecting
Jun 03 22:00:57 <root>  discord - Signing off..
Jun 03 22:01:00 <root>  discord - Reconnecting in 5 seconds..

- 160 seconds to process

O_o

extra info: the discord server in question is the official minecraft discord, as of writing it has 31,109 members

[sm00th]

Closing this one as it is being solved in bitlbee itself.