[mythtv] MythMusic maintainer?

[Joseph A. Caputo]

On Wednesday 01 October 2003 05:44 pm, Derek Atkins wrote:
> If 4000 items is causing a large performance hit, I would suggest the
> problem is the algorithm and not the fact that it's using a list or
> trying to insert 4000 items.  A 4000-item insert should be nearly
> instantaneous on any current platform, assuming you use an O(1) insert
> algorithm, resuling in an O(n) insert process.  If you use an O(n)
> insert algorithm you get an O(n^2) insert process, which is
> significantly slower.  Moreover, if you're causing a re-display at
> every insert operation then you've probably just increased to O(n^3).
> 
> I would suggest that you look at the list creation algorithms in use.
> Make sure you're inserting in the correct order and make sure you're
> not re-drawing at every insert.  Gtk has the concept of "freezing" a
> list while you're doing massive changes (e.g. building the widget) so
> that it's not forcing a redisplay on every insert; I'm sure that Qt
> has a similar feature -- make sure it's used.

Well, I have to admit I'm not really familiar with how the UIManagedTreeList 
builds its GUI.  I believe that in order to support themes, the Qt list UI 
object was eschewed in favor of a custom one that supports multiple levels.  
It's quite possible that the custom UI code can't do an O(1) insert.  Also, 
the memory usage issue is the same regardless of how fast the insertions are 
done -- 15 (or some small constant number) list objects consume far less 
memory than 4000.

Actually, now that I think about it, it probably *is* an O(1) insertion 
process.  It's just that O(1) for the custom tree/list UI seems to be rather 
expensive, even atomically.  So, multiply that by thousands of insertions, 
you get a delay.  I'm talking in the vicinity of 10-20 seconds for my 
playlist of over 4000 songs, which is not too bad, but we can do better I'm 
sure.  I'm pretty sure this is not O(n^2), because the old original mythmusic 
had a DB scanning/playlist building algorithm that was O(n^2) (before I fixed 
it), and that took *minutes*.

Regardless, whether the current method is O(1) or O(n) for inserts, it just 
doesn't seem to hold up very well for really large data sets.  I've proposed 
a method for achieving a consistently fast UI independent of set size.  I'd 
be interested to hear others as well.  Hopefully we can hit upon a good 
design, preferably one that doesn't require too much rework of the existing 
UIManagedTreeList class (which is pretty cool, all things considered).

-JAC