GNOME Bugzilla – Bug 582564
[controller] Use ordered GSequence instead of GList in the interpolation control source
Last modified: 2009-06-01 08:13:36 UTC
Hi, the attached patch changes GstInterpolationControlSource to use a GSequence instead of a GList for the control points. This lowers the worst case O(n) lookup to a O(log n) lookup and also speeds up the insertion a lot ( before it was always O(n), now it's O(log n)). Please test if this introduces any regressions, I'll add some more comments to the changes later...
Created attachment 134623 [details] [review] controller-sequence.diff
Created attachment 134628 [details] [review] controller-sequence.diff
Cool stuff. Works fine for me.
commit ec5c918dbd9098e56e1c2802625af911c56a487c Author: Sebastian Dröge <sebastian.droege@collabora.co.uk> Date: Thu May 14 22:11:57 2009 +0200 controller: Use ordered GSequence instead of GList This makes lookups and insertions O(log n) instead of always O(n) for insertions and O(n) in worst case for lookups. Fixes bug #582564.
This seems to be causing a lot of critical warnings in rhythmbox. For the first track played, per buffer: GLib-CRITICAL **: g_sequence_get_begin_iter: assertion `seq != NULL' failed and for every track after that, when fading in: GLib-CRITICAL **: g_sequence_free: assertion `seq != NULL' failed Partial stack trace for the first warning:
+ Trace 215532
At this point there would not be any control points set. The second occurs in gst_interpolation_control_source_unset_all. There's no check to see if self->priv->values is NULL in _unset_all (or in _unset).
Thanks, I'll take a look at this in the next days. Good to know that RB also uses the controller :)
This should've been fixed in GIT by http://cgit.freedesktop.org/gstreamer/gstreamer/commit/?id=2437a08666e6aff80236e7dd1d9c1cd5517407da http://cgit.freedesktop.org/gstreamer/gstreamer/commit/?id=6784355d5221a9cdb6071b9322c7b27aa5a3fdb7
Thanks, it's behaving itself now.
gstinterpolation.c still has a lot of iter = g_sequence_get_begin_iter (self->priv->values); where we don't check that self->priv->values!=NULL. Regarding that I wonder if we just want to create the sequence when creating the control-source, to avoid the checks. Then there is code like this: iter = g_sequence_get_begin_iter (self->priv->values); \ cp = g_sequence_get (iter); \ or this iter = g_sequence_iter_next (iter); \ cp = g_sequence_get (iter); \ where we probably need to cehck the iter against NULL :/
Regarding perfromance, its worth it. I added a performance test app in core (test/benchmark controller) and this is the before/after linear insert of control-points: 0:00:00.491924240 random insert of control-points: 0:00:00.029950985 linear read of control-points: 0:00:01.618321687 linear insert of control-points: 0:00:00.051068274 random insert of control-points: 0:00:00.000325157 linear read of control-points: 0:00:00.877610880
I added another test. The cubis interpolation cehck the number of controlpoints and does a fallback to linear if there a re not enough.