Data structures are important (or maybe I’ve just wasted my week)

This week I spent the entire time working on the tablist and more generally the table API.  I got drag and drop working after a day or two, then I spent almost all of the rest of the week changing the way we access the data that goes in our TableModel classes.

In some ways that means that I didn’t get much done, but I just kept thinking how important it is that we get a things working really fast.  We want to support things like rendering a feed with 1000 or maybe even 10,000 items in it, so there’s a lot of motivation to make sure that we have fast data structures in place.

The main problem is how access each individual row.  I started using the equivelent of GTK’s RowReference class.  This is like an index that gets updated whenever a row gets added or removed.  It’s probably the simplest in terms of what the programmer has to think about, but it’s quite inefficient since we need to update them whenever things are inserted or removed.  The next try was using Tree Paths, which is basically just an index that doesn’t get updated.  This was probably an improvement, but then I realized that GTK implements it’s model classes with linked lists and whenever we used one of the tree paths we were iterating through the list.  So if we wanted to access each row in the list it was O(n^2) time, which is shameful.  Finally I settled on an using Tree iterators, which is basically a pointer to a node in a linked list.  This is the fastest way to access things and I realized that, like RowReferences, they don’t get invalidated when other rows are added/removed.  So it seems like definitely the way to go.

I may spend one more day trying to work on the model classes on OS X.  Unlike GTK we have to roll our own there and the current design could use a couple improvements.

The other thing I did this week was work on those startup tweaks that we talked about.  I made it so that we don’t re-download thumbnails on startup and implemented a queue for updating feeds.  Both changes seem to be working ok so far.

This week I hope to get a lot of visible changes to the widgets branch.  Now that the behind the scenes table code seems pretty complete it means I can work on the fun part of rendering things.