GNOME Bugzilla – Bug 131019
TreeStore has no decent performance on massive inserts
Last modified: 2004-12-22 21:47:04 UTC
As reported by several people on the net there seems to be a performance problem with Gtk::TreeStore insertions. I personally have seen more than 30seconds for inserting 10k lines when generating a tree out of a linear multi-columned list. My std::map based custom model manages 100k in less than 2 seconds (300MHz G3 powerpc). I'm going to simplify my example down to one file.
Created attachment 23168 [details] reported at http://mail.gnome.org/archives/gtk-list/2003-March/msg00361.html
See also the mailing list thread at http://mail.gnome.org/archives/gtkmm-list/2003-October/msg00090.html [I admit that I do no longer remember the exect timings but it was simply too much and more O(N^2+) than O(N logN).]
The problem is that gtkmm only has append() and insert_before() methods. I've talked to gtk+ developers and they say append() is O(n), as it iterates through the whole tree/list until the end so it can insert something. For appending large amounts of rows, they suggested using insert_after() with the iterator from the previous insertion.
Did you have that conversation on a mailing list or irc? Who told you this?
On IRC, I believe it was Federico Mena who told me that. Looking at the gtk+ sources, the append function calls g_node_append(), which indeed traverses the whole list of nodes until the end to insert the new node.
OK, I have added ListStore/TreeStore::insert_after() in gtkmm 2.4. We already have prepend() which might also be faster. Thanks for investigating. Please reopen this bug if it is still a problem.
I remember that some people proposed a function which appends a line and sets the values in one step (append which takes an array of GValues for the columns). I do not remember whether this speedup proposal was realized [it wasn't]. Looks like gtk_tree_store_set[_valist] is most equivalent to the thing I remember. This is not wrapped in gtkmm (as of CVS today). Perhaps the additional speedup (only two gtk+ calls per line, instead of (columns+1)) would warrant designing a type safe interface ... perhaps ... I have no need for it yet. Should I file this as a wish list bug? Also the API would be non-trivial to design (most probably a container like structure which checks the type and collects the GValues). This sounds like gtk_tree store in disguise to me (and I doubt it would be more efficient than gtk_tree_store_set_value). [I should not cease to investigate whether my custom model still has much speed benefits over a tree_store, I suspect massive (2M+) GValue::ref calls to be the next bottleneck]