Hi, Audacious 1.4 has parts of this. The main issue is that GList is not O(n). Additionally, playlist operations are asynchronous in Audacious 1.4 as well, which alleviates the need for having a mutex unless you require a synchronized operation. This works because most operations are read operations and usually do not require an atomic operation. Write operations are still atomic, obviously.
I think have multiple mutexes won't offer much gain past making the playlist asynchronous; and will only contribute to the complexity of the code. Audacious 1.4 (SVN) uses a libmowgli managed heap for playlist entries themselves which has provided a significant gain already. The Playlist code still needs to be ported to libmowgli, but that is pending the 0.2 release of it. (libmowgli is at http://www.atheme.org/projects/mowgli.shtml) The tail trick is more of a workaround for 1.3 to make performance in the playlist improve over what was available in 1.2. It's a poor workaround and the general opinion is that we will be more happy when the playlist is a derivation of mowgli_list. Basically, you had the same idea I did but implemented slightly differently. If you want, we'd love to have you on the team. :) - William On Sun, 15 Apr 2007, Rostislav wrote: > Hi there! > > Many thanks to audacious devs for a good piece of software > they are working on. I'm quite happy with it, though there some things > that aren't satisfying for me. On of these is slowness of the > playlist on large lists (of thousands of files). > > Recently I've took a look at the audacious code and found some > performance issues there which could be improved. These are just some > random thoughts so I feel this list is the right place to send them. > > First of all (I think that this is a legacy of the old xmms code, > correct me if I'm wrong) I believe that double-linked list is not a good > choice of the playlist entries container. Most of the playlist api uses either > indexed access (which has O(N) complexity for lists) or involves entry > lookup which is also O(N). This efficiently takes away benefits of > insertion and deletion in which lists are fast. > I have some ideas how to organize it avoiding these flaws. > Please let me know if you are interested in this. Though changing container > will > involve almost entire reworking playlist code and I do not feel that I've > investigated sources enough to start rewriting right now. > > Anyway beside transition from lists to something else there are lots of > other things to play with. One of them is playlist locking. > I've changed localy audacious code (based on 1.3.2 release, though svn > version seem to be not very different in the affected areas) so that > there are 2 mutexes instead of one. The main idea is that code pieces > which are just reading shouldn't block other read-only operations. > There are 3 lock (and 3 unlock) macroses in my code: > > #define PLAYLIST_WRITELOCK(playlist) {g_mutex_lock(playlist->rmutex); > g_mutex_trylock(playlist->wmutex); g_mutex_unlock(playlist->rmutex); } > #define PLAYLIST_WRITEUNLOCK(playlist) {g_mutex_unlock(playlist->wmutex); } > #define PLAYLIST_RWLOCK(playlist) {g_mutex_lock(playlist->rmutex); > g_mutex_trylock(playlist->wmutex); } > #define PLAYLIST_RWUNLOCK(playlist) {g_mutex_unlock(playlist->rmutex); > g_mutex_unlock(playlist->wmutex); } > #define PLAYLIST_READLOCK(playlist) {g_mutex_lock(playlist->rmutex); } > #define PLAYLIST_READUNLOCK(playlist) {g_mutex_unlock(playlist->rmutex); } > > RWLOCK/UNLOCK is for modifying operations and lock every read/write opration. > WRITELOCK/UNLOCK for read-only operations and locks write operations and > doesn't lock read-only ones. Finally READLOCK/UNLOCK is for locking > small chunks of code which is changing playlist inside WRITELOCK/UNLOCK pair. > > This allows for example to reduce time of the playlist being blocked for > update because of getinfo thread (by locking read operations only when the > tuple > loaded for single entry is updated. On my box (AthlonXP 2400+) with getting > info on demand turned on playlist scrolling is extermely laggy. > With my patch it is as smooth as scrolling when all info is already > loaded. I've also changed some code in playlist_get_info_func because > there was 2 redundant iterations through the whole list (one is for > recalculating of the position in each iteration of the for loop and > second is for lookup for dissappeared entry) because both of them aren't > needed when the playlist is locked for modifying operations. > > I'm not sending this patch, since it is not tested well yet (and also is > not applied to the current svn version), though it seems it didn't > caused any new bugs to audacious. Again let me know if you are intersted > in this patch. > > Another thing, much simpler to apply is that in playlist code there are > to functions for inserting entry: > > __playlist_ins_with_info > and > __playlist_ins_with_info_tuple > > the second one is using the trick of remembering the tail of the list > to do the manual appeding of the entry to the end of the list with constant > complexity while the first one is using g_list_insert which involves > iteration through the list which is much longer. Since the first one is > indirectly used in function playlist_add_dir it would be good to use > "tail trick" there too, so loading files from directory will be O(N) and > not O(N^2). > > Also as a partial solution to the redundant list iteration problem I could > suggest to maintain something like bookmark for the last accessed entry > (this wouldn't be very complex to update it in the modifying operations) > so whenever we are trying to indexed lookup for the entry near the bookmark > (which should be the common case) we could iterate starting from the > bookmark and not the list beginning. > > Well, thats all for now. I will be glad if the audacious developers > will found my letter useful. > > P.S. Sorry for my English, I'm not a native speaker. > P.P.S Also I wanted to know is there going to be some major > modifications in playlist code in the nearest future > (There is nothing like this in roadmap page on audacious site, > though it is quite internal feature so it could be not highlighted there) > > Regards, > Rostislav. > _______________________________________________ > Audacious mailing list > [email protected] > http://mail.atheme.org/mailman/listinfo/audacious > _______________________________________________ Audacious mailing list [email protected] http://mail.atheme.org/mailman/listinfo/audacious
