[mythtv] MythMusic maintainer?

[Derek Atkins]

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.

-derek

"Joseph A. Caputo" <jcaputo1 at comcast.net> writes:

> On Wednesday 01 October 2003 07:22 am, Isaac Richards wrote:
> > On Tuesday 30 September 2003 10:57 pm, Joseph A. Caputo wrote:
> > > One of the drawbacks of MythMusic as it is now is the way it handles the
> > > tree list in the playback view (UIManagedTreeList, I think).  I think only
> > > MythMusic uses this widget (well, I think MythVideo recently started using
> > > it too, but I digress).  Anyway, for a really large playlist, it takes a
> > > long time to build the list GUI, because it has so many items.  I wanted 
> to
> > > look into an alternate approach that has been used by my company in the
> > > past. Basically, a list widget class that, instead of building all the
> > > items as list item objects, it just creates the *visible* list items, and
> > > changes their contents to reflect the current window into the data set.  
> In
> > > this way we could reduce memory requirements and provide a much-needed
> > > speed boost.
> > >
> > > What say ye?
> > 
> > MythGame uses that widget, but it builds the tree on demand, so it's quick.
> 
> Well, I see that it's 'on demand'  in the sense that it only build each level 
> of the tree as it's needed, but that won't help in MythMusic where a very 
> large playlist comprises a single (very large) level in the tree.  It doesn't 
> matter when you build the list UI for that level of the tree, it's still 
> going to take a long time if you have thousands of songs in a playlist.
> 
> You could extend the idea of 'on demand' to mean 'only build the items in a 
> level of the tree/list as they become visible for the first time'.  However, 
> that presents problems with MythMusic because in Random mode, with 'List as 
> Shuffled' turned off, the list items become visible non-sequentially, making 
> building the list properly a real pain.  Plus, if you have a playlist with 
> 4000 songs, you still eventually (if you let the whole playlist run) end up 
> with the memory usage of 4000 list nodes.
> 
> What I'm proposing is a list/tree with a fixed number of items (say, 15 for 
> argument's sake).  The text/contents of those 15 items will change to make it 
> appear as if you're scrolling through the list, when actually the list (UI) 
> is static, it's only the contents that would change.  This has the advantage 
> of being fast and using much less memory for large lists (you only ever have 
> 15 list nodes allocated).  We use this approach in my company in a Motif app 
> because we deal with lists that are hundreds of thousands of items long, and 
> it is *fast* and *lean*.  Of course, it has the disadvantage of requiring 
> basically a whole new UIManagedTreeList class to handle the interface.  I was 
> hoping to get around to it at some point, but since Tim seems to be 
> interested in doing a MythMusic overhaul, I wanted to present this idea.
> 
> And yes, I can volunteer to code it up, but I can't do it anytime soon.
> 
> -JAC
> 
> _______________________________________________
> mythtv-dev mailing list
> mythtv-dev at mythtv.org
> http://mythtv.org/cgi-bin/mailman/listinfo/mythtv-dev

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       warlord at MIT.EDU                        PGP key available