Oscar protocol performance improvement(s)

[oliver]

oscar.c:6581 oscar_normalize() does a string copy (line 6589) but the following loop effectively moves each byte (skipping the blanks). I think we can use only the loop to copy the string and remove the (expensive) call to strncpy(). vallgrind/callgrind says that the strncpy() call is responsible for more than half the time spent in this function and of all the liboscar function it is one of the most often called. See attached patch.

Which brings me to the next bottleneck/performance problem.

Lot's of time is spend in aim_sncmp() (util.c 232) because (a) the function is kind of expensive and (b) it's called a lot. I think the big rblem here is that all the aim_ssi_itemlist_* functions are littered with linear searches that call the compare function in the loop (family_feedbag.c:309 and family_feedbag.c:352).[[BR]]

It might be worth to sacrifice a few extra bytes of memory and either (i) store the uppercase&normalized version of the name and keep the linear search or (ii) use a hashmap to lookup the name, effectively getting rid of the linear searches.

This is a bigger change, I'll look into that but comments are welcome.

[MarkDoliner]

I committed this change, thanks.

For the ssi/feedbag change, yes, you're right, both of your proposed changes would help, and I think it's totally worth the added memory usage. It sounds like a great idea. My personal preference is for using a GHashTable where the key is the normalized version of the buddies name and the value points to the aim_ssi_item. I don't know if you would need two hash tables (one for OscarData?->ssi.official and one for OscarData?->ssi.local) or if one would be sufficient (just for OscarData?->ssi.local).

[markdoliner@…]

(In [d7ac6b99ef7882ae0af3758b0267dc2a47020712]) A patch from oliver to speed up oscar's normalize function a little by removing a call to strncpy(). Fixes #4816.

[MarkDoliner]

Oh, and do you have a full name you'd like to have listed in our COPYRIGHT file?

[oliver]

Replying to MarkDoliner:

Oh, and do you have a full name you'd like to have listed in our COPYRIGHT file?

"Oliver" will do, thanks for asking.

[oliver]

Replying to MarkDoliner:

I committed this change, thanks. My personal preference is for using a GHashTable ...

Yeah, definitely, but that would be a pretty big change. All the aim_ssi_* routines would have their signatures change cause you'd need to pass the hashtable.
I made a change to "struct aim_ssi_item" and added a key that i set to the normalized string of name when it's added (or changed) so i don't have to call aim_sncmp() each time it's looked up but i kept the linear search.
In the same way I could add a pointer to the hashtable to "struct aim_ssi_item" but that's kind of a waste and a hack.
If you have suggestions where to put (and how to reference) the hashtable(s), that'd be great.

[MarkDoliner]

A full name (rather than just 'Oscar') probably makes your claim on the copyright of your code a bit stronger. Although so far this is a pretty small amount of code, and in the grand scheme of things it will hopefully never be an issue.

I'm perfectly ok with changing the signatures of any function in the libpurple/protocols/oscar/ directory. Those functions are not publicly accessibly from plugins, so there are no concerns of breaking binary compatibility.

It doesn't seem like just adding a normalized version of the name would give that much of a performance benefit. You'd still have to make a call to strcmp(), right? Is aim_sncmp() that much more expensive? (I've never profiled it, so you'll have to tell me)

I haven't looked at this code in a while, but it seems like you could add an hash table to OscarData?->ssi (I may have said that in the email I sent to you). The key could be something like ("%s\n%s", group_name, buddy_name), and the value could be a pointer to the struct aim_ssi_item node in the linked list. Would that be sufficient?

[oliver]

ok, i got a patch done (oscar_ht.patch). It got a bit bigger than i thought/was hoping for but it works so far.

I added three hashtables to speed-up the most common searches:
- the gid+bid lookup
- finding buddies in a group
- finding groups


Have a look at the patch and let me know what you think.

[MarkDoliner]

I'll try to look at this soon, but I don't know when I'll get to it

[evands]

oscar_ht.diff no longer applies cleanly against im.pidgin.pidgin:

9 out of 58 hunks FAILED -- saving rejects to file family_feedbag.c.rej
5 out of 22 hunks FAILED -- saving rejects to file oscar.c.rej