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
