Re: GtkListStore and GtkSequence

[Jonathan Blandford <jrb redhat com>]

Soeren Sandmann <sandmann daimi au dk> writes:

> The attached patch reimplements GtkListStore in terms of a new data
> structure, GtkSequence. This data structure has the API of a list, but
> is internally implemented as a tree, making inserting into a sorted
> GtkListStore O(log n) instead of O(n) as it is now.
> 
> For now the GtkSequence is internal API. I think it makes sense at
> some point to add it to glib (as GSequence), but not until it has at
> least tests and documentation, Also, actually porting GtkListStore to
> use it uncovered a ton of small issues that needs to be considered.


> A testprogram written by Matthias shows that the new data structure is
> much faster on some operations and only a little slower on others. The
> most spectacular result I have is inserting 16384 into a sorted
> ListStore. Before:

I'm Okay with changing GtkListStore to use GtkSequence.  I initially
intended to use the rb tree for Gtk{Tree,List}Store as well as
GtkTreeView when writing the widget.  I wrote the GList/GNode versions
just to get something to test GtkTreeView with, fully intending to move
them over.  However, GtkRBNode became pretty TreeView specific, and it
never happened.

I feel that the memory cost is worth paying, as:

1) While it's hard to know exactly what people are using the ListStore
   for, for many lists the data stored is larger than the increase in
   size (such as images.)

2) GtkRBNode is larger than GtkSequenceNode, so we're not exactly
   tripling the memory requirements for a list.

3) There have been many complaints about the speed of sorting/lists
   already.

One thing we may want to consider is what's involved with changing
GtkTreeStore to use GtkSequence as well.

Thanks,
-Jonathan