GNOME Bugzilla – Bug 335365
inefficient use of GList in gst-plugins-base
Last modified: 2006-03-21 17:51:12 UTC
excerpt of the interesting part of find gst-plugins-base/ -name "*\.c" | xargs egrep "\bfor [(].*[(]" Measuring the list lenght at each iteration doesn't sound like a good idea (unless the list lenght changes in the for body). Measuring should be factored out of the loop. I also inclueded loops doing gst_caps_get_size etc, but maybe those are O(1) and are ok. gst-plugins-base/ext/alsa/gstalsasink.c: for (i = 0; i < gst_caps_get_size (tmpl_caps); ++i) { gst-plugins-base/ext/ogg/gstoggparse.c: for (i = 0; i < g_slist_length (parser->oggstreams); i++) { gst-plugins-base/ext/ogg/gstoggparse.c: for (i = 0; i < g_slist_length (ogg->oggstreams); i++) { gst-plugins-base/ext/ogg/gstoggparse.c: for (i = 0; i < g_slist_length (ogg->oggstreams); i++) { gst-plugins-base/ext/ogg/gstoggparse.c: for (j = 1; j < g_slist_length (stream->headers); j++) { gst-plugins-base/ext/ogg/gstoggparse.c: for (i = 0; i < g_slist_length (ogg->oggstreams); i++) { gst-plugins-base/ext/ogg/gstoggparse.c: for (i = 0; i < g_slist_length (ogg->oggstreams); i++) { gst-plugins-base/ext/ogg/gstoggparse.c: for (j = 1; j < g_slist_length (stream->headers); j++) { gst-plugins-base/ext/ogg/gstoggparse.c: for (i = 0; i < g_slist_length (ogg->oggstreams); i++) { gst-plugins-base/ext/ogg/gstoggparse.c: for (j = 0; j < g_slist_length (stream->unknown_pages); j++) { gst-plugins-base/ext/libvisual/visual.c: for (i = 0; i < visual_list_count (list); i++) { gst-plugins-base/gst/audioconvert/gstaudioconvert.c: for (i = 0; i < gst_caps_get_size (ret); ++i) { gst-plugins-base/gst/ffmpegcolorspace/gstffmpegcolorspace.c: for (i = 0; i < gst_caps_get_size (caps); i++) { gst-plugins-base/gst/ffmpegcolorspace/gstffmpegcolorspace.c: for (i = 0; i < gst_caps_get_size (rgbcaps); i++) { gst-plugins-base/gst/ffmpegcolorspace/gstffmpegcolorspace.c: for (i = 0; i < gst_caps_get_size (graycaps); i++) { gst-plugins-base/gst/playback/gstplaybasebin.c: for (i = 0; i < gst_caps_get_size (caps); ++i) { gst-plugins-base/gst/videorate/gstvideorate.c: for (i = 0; i < gst_caps_get_size (intersect); i++) { gst-plugins-base/gst/videoscale/gstvideoscale.c: for (i = 0; i < gst_caps_get_size (ret); i++) { gst-plugins-base/gst-libs/gst/audio/multichannel.c: for (c = 0; c < gst_value_list_get_size (pos_val_entry); c++) { gst-plugins-base/gst-libs/gst/audio/multichannel.c: for (c1 = 0; c1 < gst_value_list_get_size (pos_val_entry); c1++) { gst-plugins-base/gst-libs/gst/tag/gstvorbistag.c: for (i = 0; i < gst_tag_list_get_tag_size (list, tag); i++) { gst-plugins-base/sys/v4l/gstv4lsrc.c: for (i = 0; i < gst_caps_get_size (caps); ++i) { gst-plugins-base/sys/v4l/v4l_calls.c: for (i = 0; i < gst_v4l_get_num_chans (v4lelement); i++) {
gst plugins has some too :) gst-plugins-good/ext/jpeg/smokecodec.c: for (i = 0; i < strlen (SMOKECODEC_ID_STRING); i++) { gst-plugins-good/ext/jpeg/smokecodec.c: for (i = 0; i < strlen (SMOKECODEC_ID_STRING); i++) { [though maybe the compiler is smart enough here since IIRC strlen is marked with the "pure" attribute.] There are also some matches with: for (i = 0; i < gst_caps_get_size (caps); ++i) since I am not sure if gst_caps_get_size is problematic I have skipped them here
if the i variable isn't used in the loop the following could be used for GList/GSList : for (i = g_list_length(x); i; i--) { ... } for (i = g_slist_length(x); i; i--) { ... }
Actually a quick look at gstoggparse reveals that things are even worse: for each iteration g_slist_nth_data wolks the list a *third* time: for (i = 0; i < g_slist_length (parser->oggstreams); i++) { GstOggStream *stream = g_slist_nth_data (parser->oggstreams, i); what about the good old: for (l = parser->oggstreams; l != NULL; l = l->next) { GstOggStream *stream = l->data
gst_caps_get_size(), gst_value_list_get_size() and gst_tag_list_get_size() are all O(1) (internally arrays of some sort), so that only really leaves the stuff in oggparse AFAICS.
Fixed in CVS: 2006-03-21 Tim-Philipp Müller <tim at centricular dot net> * ext/ogg/gstoggparse.c: (gst_ogg_parse_find_stream), (gst_ogg_parse_chain): Fix very inefficient usage of linked lists (#335365). I don't think the strlen() cases in -good are an issue (and the compiler should be smart enough to recognise that the string passed to it is a const string anyway, and then take the length determined at compile time). But even if not, the strings here are very very short, and code readability is also a factor IMHO.