GNOME Bugzilla – Bug 350579
EggSequence iter_is_end performance improvement
Last modified: 2006-12-02 20:48:36 UTC
EggSequence's current implementation of iter_is_end is O(log N). By trading off one bit of the n_nodes integer to a flag (reducing max size from 2^32-1 to 2^31-1), it can be replaced by a trivial O(1) implementation. I think it unlikely that anyone using EggSequence is storing >= 2^31 elements in one. Depending on how EggSequence is used, this can result in *very* large improvements in some algorithms; for example Rhythmbox sorting a large "query model" on my machine changes from ~15 sec to <0.1 sec with this.
Created attachment 70546 [details] [review] patch
cc'ing Søren who's maintaining this, AFAIK.
Well, EggSequence used to have an O(1) is_end() implementation, but it was changed to the current scheme, which I consider cleaner (relying on bitfields is a little icky - what about 64 bit computers for example? There is not good reason to restrict to 31 bits there). I would really like to know exactly what is going on in your benchmark. Why is it calling is_end() so much? Just sorting a sequence shouldn't call is_end() at all ... All that aside, the patch needs at least egg_sequence_new() to set seq->end_node->is_end to TRUE.
Ah, Rhythmbox currently has a several-year-old version of GSequence (which I was planning to update to EggSequence), and my searching didn't find enough of the history of the code to see that it wasn't a local modification someone had made. Calling is_end() often is something a few part of Rhythmbox code currently (probably pointlessly) does, but I can modify our code to fix that. Feel free to close as WONTFIX/NOTABUG if you think the current method is better.
I'll close it WONTFIX then, but if you do come up with a benchmark where O(1) is_end vs O(log n) is_end makes a huge difference, please reopen. I hope at some point to get this into glib and at that point it would be kind of silly for Rhythmbox to maintain its own copy.
Created attachment 76320 [details] [review] don't use is_end() in node_find_closest This isn't strictly the same issue, but it is due to is_end's performance. I've noticed that egg_sequence_insert_sorted is much slower than the older version we had, due to calling is_end() on each iteration of the loop in node_find_closest. This patch passes the end node around internally to the function, so that it can just do a comparison. This makes inserting a large number of items into a sorted sequence several times faster.
Do you have a benchmark that shows how much of a difference this makes?
Created attachment 76367 [details] [review] benchmark This patch (inside libegg/sequence) adds a benchmark for this, but it doesn't work with eggsequence from due to a bug I just noticed. The second insertion fails due to the following: 1) to compare the new node to the first-inserted one, iter_compare() is called. 2) is_end() gets called on the new node (node2 here) 3) since the new node isn't in a sequence yet, get_sequence() returns the node data instead, which then explodes when seq->end_node is accessed. If you are passing actual pointers as the node data this doesn't explode becuse it dereferences the pointer, which is incorrect but usually works. But for my benchmark I'm using GINT_TO_POINTER, so the dereferencing crashes.
Any comment on this?
I will try and take a look at this sometime this week.
Ugh, yeah, that's a very bad bug. And your patch not only fixes that, but also likely makes things a lot faster, although I haven't measured (no point comparing a correct to a broken implementation). I have committed your patch and added testcases that should catch this. Thanks a lot, and sorry I was unresponsive.