14 March 2007

Improving Performance

With the recent release of 1.2.8 I decided to do another significant change in the stable release series of Liferea. I need to thank Matthew Garrett for suggesting a patch to change the internal link list item searching to a hash table based one. Matthew like some other users I know about set the default cache size to a very high value, effectively disabling the cache limit. As a result he suffered significantly from the linear item searching that is necessary on different user interactions.

Now while the hash table lookup improves speed directly for his use case it also does for the default use case with a cache limit of 100 items, but for another reason. And here is why: while trying to find a way to merge the patch I found that I cannot simply use a single hash map to provide a more efficient way to find items in a given item set (e.g. a feed, all items in a folder, all items matched by a search folder...). While there would be the possibility to construct a hash key out of the item number (which is unique per feed) and the feed id, it is easier to have a two level hash structure where there is first a hash of feeds whose items are in the item set and for each feed an own hash containing the item references for each item number.

This simple decision was derived just from the necessity to integrate the patch. But after looking at the search folder code I found that using the new item set lookup structure it could be significantly simplified, because search folders do require exactly this type of searching on exactly this type of hierarchical item list. So merging the patch uncovered a misdesign, a missing abstraction which wasn't obvious before but that made realizing search folders more easier. And more importantly: even more performance gain, even for smaller cache sizes!

So what do we learn from it?

Submitting patches is still one of the best ways to improve your programs!


gilir said...

Hi :)

Liferea is a very awesome apps. Thanks you :)

Is it possible to send the unread count with Dbus to another application ? I'm using a dock (http://code.google.com/p/avant-window-navigator/). which can display informations about others applications (http://njpatel.blogspot.com/2007/02/to-quote-destinys-child.html). If we could have the number of unread feed on the dock, it could be more awesome :)

Lars said...

Adding a DBUS method to return the global unread count to Liferea would be pretty simple.

So if you supply a patch doing it (I can help you with any programming questions) I'll happily add it to the next release.

gilir said...

Thanks :)

But I'm not very good for programming. I post
on AWN forum a piece of code but I can test it. Maybe people on the forum will help. And I'll not have acces to the net in the next weeks :(

Anonymous said...