Re: Is GTK+ 3.x 2x slower than GTK+ 2.x?
- From: sandmann cs au dk (Søren Sandmann)
- To: Oscar Lazzarino <oscar lazzarino i-m3d com>
- Cc: gtk-list gnome org
- Subject: Re: Is GTK+ 3.x 2x slower than GTK+ 2.x?
- Date: Tue, 18 Oct 2011 15:49:29 +0200
Oscar Lazzarino <oscar lazzarino i-m3d com> writes:
> So appending n rows costs n*log(n), instead of n. Could be worse, but
> could also be better, considering that the g_sequence has a
> g_sequence_append method...
g_sequence_append() is Theta(n*log(n)) too.
Also, GSequence is not actually a splay tree anymore, it is a treap
If GSequence actually *were* a splay tree, and the GtkListStore were
unsorted, then append() would be O(1) due to the move-to-root nature of
splay trees. In practice, this log n factor disappears in the noise, and
the horrible (CPU-)cache behavior of splay trees make them much slower
than treaps. See:
> Incidentally, I found that calling calling gtk_list_store_prepend with
> rows in reverse order is faster than using gtk_list_store_append
The difference is almost certainly very tiny, but _prepend() does avoid
one call to g_sequence_get_length().
] [Thread Prev