Re: Is GTK+ 3.x 2x slower than GTK+ 2.x?

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().


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]