When profiling jabber.el, I found that much time was spent in jabber-roster-update, and that it was called many times. This is because of the inefficient processing of presence.
If the roster holds N items and you change M of them, jabber-roster-update runs for O(N + MlogM) time. However, most often jabber-roster-update is run in response to a presence packet, with a single item. Doing this M times gives a running time of O(N * M), which is slower than it needs to be.
Maybe the resorting should be delayed, until the roster buffer is shown, or something...
/Magnus (too lazy to log in)