GNOME Bugzilla – Bug 617045
[caps] New method for intersecting caps while retaining order
Last modified: 2011-03-30 12:56:57 UTC
Right now gst_caps_intersect() intersects the caps by zig-zagging through the structures of each caps. While this tries to keep a homogenous ordering for the output, there are some cases where we want to intersect two caps but keep the exact same ordering as one of the caps. This is essential in two cases so far: * default caps fixation in GstBaseSrc : we want to fixate to the first intersecting caps from downstream. * caps filtering in GstBaseTransform : we want to keep the ordering of caps that the element gave to us. c1 = Gst.Caps("A;B;C;D") # our sorted caps c2 = Gst.Caps("D;A;B;C") # the unsorted caps Example with gst_caps_intersect: gst_caps_intersect(c1, c2) => "B;A;D;C" gst_caps_intersect(c2, c1) => "A;B;D;C" Example with gst_caps_sorted: gst_caps_intersect_sorted(c1, c2) => "A;B;C;D" gst_caps_intersect_sorted(c2, c1) => "D;A;B;C"
Created attachment 159758 [details] [review] gstcaps: new API : gst_caps_intersect_sorted Acts like gst_caps_intersect, except that the returned caps as ordered in the same way as the first provided caps. Keeping the order of one caps is needed for properly fixated caps and retaining the ordering through caps negotiation.
Created attachment 159759 [details] [review] basesrc: Keep downstream caps order when fixating This allows use to use the first intersecting format prefered by downstream.
Created attachment 159760 [details] [review] basetransform: Retain caps order when getting caps If the element gave us caps in a specific order, let's retain that by intersecting against the template but retaining the order given by the element.
Definintely a good idea, I remember seeing another bug about this some time ago.
I dislike the name because it implies that gst_caps_intersect() does not sort the caps. I'm also wondering if it would make sense to instead: - Change gst_caps_intersect() to sort like your gst_caps_intersect_sorted() Would that change the current API too much? - Have a gst_caps_reorder (GstCaps *caps, GstCaps *order) function that does sort caps according to a specific order. I'm asking because there's a lot of places where elements would be happy if there was an easy way to reorder caps. Examples are getcaps()ing on filters that want to prefer passthrough or my hw-accelerated converters that want to prefer hw-accelerated formats. So I think having something like gst_caps_reorder (caps, gst_caps_from_string ("favorite/format; *")); would be very useful.
(In reply to comment #3) > Created an attachment (id=159760) [details] [review] > basetransform: Retain caps order when getting caps > > If the element gave us caps in a specific order, let's retain that > by intersecting against the template but retaining the order given > by the element. Shouldn't that intersecting with the template be removed? Isn't it a bug to return caps that are not a subset of the template caps?
(In reply to comment #6) > Shouldn't that intersecting with the template be removed? Isn't it a bug to > return caps that are not a subset of the template caps? You'd be amazed by the number of filters that don't obey that rule :( And yes, that check should be removed since gst_pad_get_caps() will check/filter the caps itself. The problem is that that code does it gracefully, whereas gst_pad_get_caps spurts out errors and g_warning assertions. (In reply to comment #5) > I dislike the name because it implies that gst_caps_intersect() does not sort > the caps. > > I'm also wondering if it would make sense to instead: > > - Change gst_caps_intersect() to sort like your gst_caps_intersect_sorted() > Would that change the current API too much? The zig-zagging comes from the very first 0.9 commit that introduced that method. Wim should have his word on this. I guess there's a reason behind it. The other problem is that it is going to check the order of the outputted caps, so we might see some hidden side effects (like going from going from a result that was mostly sorted for the callee to something that is not at all sorted as the callee would expect (because of the ordering of arguments). > > - Have a gst_caps_reorder (GstCaps *caps, GstCaps *order) function that does > sort caps according to a specific order. > I'm asking because there's a lot of places where elements would be happy if > there was an easy way to reorder caps. Examples are getcaps()ing on filters > that want to prefer passthrough or my hw-accelerated converters that want to > prefer hw-accelerated formats. > So I think having something like gst_caps_reorder (caps, gst_caps_from_string > ("favorite/format; *")); would be very useful. That one is trivial, create caps with your format, result = gst_caps_merge(yourformats, theothers).
Hrm, looking at the two patches you posted, the GstBaseTransform one is working around bugs and shouldn't even be there and the second one is trying to select a single caps structure - it does a gst_caps_copy_nth() immediately after intersecting. It seems to me like we could avoid the need for this API. And I'd be very happy about that, because less API is good - especially if it's less similar API.
(In reply to comment #7) > That one is trivial, create caps with your format, result = > gst_caps_merge(yourformats, theothers). (This is off-topic now, but anyway): I want a function that can reorder caps like these: video/x-raw-yuv,width=20; video/x-cairo,width=20; video/x-raw-rgb,width=20; to: video/x-cairo,width=20; video/x-raw-yuv,width=20; video/x-raw-rgb,width=20; with a function that I can tell something like "I prefer video/x-cairo to anything else". The current way I do that is roughly like this: ordered = gst_caps_intersect (caps, my_preferred_caps); if (ordered == NULL) return caps; gst_caps_append (ordered, caps); return ordered; but this only works for one level of preference. It also results in duplicated structures, as this code will return for the above example: video/x-cairo,width=20; video/x-raw-yuv,width=20; video/x-cairo,width=20; video/x-raw-rgb,width=20;
I can't quite remember why the algortihm you now propose again was replaced with a zig-zag algorithm.. It might simply have something to do with the lack of other negotiation API at that time (or other missing basetransform things). It sounds like the zigzag does not work so well because some caps intersections simply result in empty caps which then cause it to try the next less optimal intersections. Maybe the zigzag should only proceed to the next caps when an intersection returns something non-empty. The main problem with the proposed patch is that it seriously overprefers the first caps, you could end up with an intersection totally at the bottom of both lists while there exist an intersection at say the second position of the lists.
An example: caps1: A, B, C, D caps2: B, E, F, A proposed patch would result in A as the intersection while (arguably) B should be prefered. I have no idea if it's really a problem in practice. I can't seem to come up with an example where it chooses the last intersection of both lists.
Another think that the zigzag imho provides is intersect(a,b) == intersect(b,a).
That is not true. intersect ("a;b", "b;a") != intersect ("b;a", "a;b") It is usually reasonably close, but not equal.
Would changing the naming make people happier ? gst_caps_intersect_keep_order() ? gst_caps_intersect_with_order() ? gst_caps_intersect_with_first_order() ? Ending-up with non-optimal caps-nego because of this is getting increasingly painful with complex pipelines.
The problem is, that you don't always know if the upstream or downstream order should be preffered. And if the order is for quality or performance or some other metric. (You said that downstream order should be preffered but there are cases where this isn't optimal, i.e. if you have a source that can output all video formats but internally only uses a single one and then converts... but much slower than ffmpegcolorspace)
But I agree that the current intersection is not optimal in all cases. What we probably need is some kind of ranking of caps structures and then search the "path" of caps structures from the source to the sink with the best overall ranking. For example we could use ranking between 0 and 1 and multiply along the path to get the overall ranking. Of course this makes everything even more complex than it is now already ;)
(In reply to comment #15) > The problem is, that you don't always know if the upstream or downstream order > should be preffered. And if the order is for quality or performance or some > other metric. Would that not be up to the caller to know what/where it is using it (and as such use the arguments in proper order)? > > (You said that downstream order should be preffered but there are cases where > this isn't optimal, i.e. if you have a source that can output all video formats > but internally only uses a single one and then converts... but much slower than > ffmpegcolorspace) We might come up with algorithms to cover this case, but how we are going to be aware of and express the above situation (i.e. input the proper parameters/data to it) is not evidently clear to me. In the meantime, it's not even complex pipelines going down the drain, but even pulsesrc ! audioconvert ! alawenc ! fakesink (or comparable) has float coming out pulsesrc, which is most unlikely (hardware) desirable. Basetransform code specifically seem written given preference to one of the caps (e.g. downstream), and it seems unlikely the proposed intersection order will make matters worse (at least there).
Note that these caps problems mess up the typical empathy voip pipeline pulsesrc ! audioconvert ! audioresample ! audioconvert (see also bug #628939), which then needs capsfilter to hack around.
(In reply to comment #15) > (You said that downstream order should be preffered but there are cases where > this isn't optimal, i.e. if you have a source that can output all video formats > but internally only uses a single one and then converts... but much slower than > ffmpegcolorspace) In that case the *source* can decide it prefers a certain format and do its own intersection.
After some more thinking about it: 1) The zigzag simulates a simple cost model where each caps list entry has an equal weight. It then orders the resulting intersection based on the lowest sum of weights. This model would find an 'overall' fair intersection as seen in Comment #11. 2) The sorted one tries to maintain the order of the downstream caps as much as possible. This by definition tries to maintain the same caps order as far upstream as possible. It is not fair because the order of the upstream caps is ignored. 1) Is easy to throw off balance. When something is not the first element of the list, we don't really know how much worse it is compared to the top of the list because it uses a fixed cost model (comment #11). Trying to add more fine grained sorting weights (comment #16) might make things better but it sounds too complicated. This model favours 'small' conversions to get an overall best format. 2) Tries to minimize conversions as much as possible but can cause 'very expensive' conversions because there is no fair cost model. This is the case in comment #15. The source has no other option than taking the cost of providing the first downstream format (and doing the conversion) because it can't know if any other format is going to be even more expensive downstream. The current 1) seems to fail because it uses a too broken cost model, so, 2) seems like it might indeed work better. Let's try this after the release then.
Created attachment 181909 [details] [review] gstcaps: new API : gst_caps_intersect_full Updated bilboed's patch to latest master HEAD and changed _sorted to _first, made it static/private and added gst_caps_intersect_full with an extra 'mode' parameter
Created attachment 181910 [details] [review] tests: caps: Tests for the new caps intersection mode Adds a simple test for the caps 'first' intersect mode
Looks good to me but you forgot the Since markers in the docs. Also some documentation about when to use which intersection mode with some examples would be really useful
Created attachment 181912 [details] [review] gstcaps: new API : gst_caps_intersect_full Added since markers and some more docs to the intersection modes. Wasn't sure of where to add them, so I added to the enum docs.
Anyone?
This was committed (bugzilla status reverted because of bugzilla database restoration from backup): commit d979eb3e9e8590da66f8948273ba276e700b97fc Author: Edward Hervey <bilboed@bilboed.com> Date: Mon Apr 19 20:39:53 2010 +0200 basesrc: Keep downstream caps order when fixating This allows use to use the first intersecting format prefered by downstream. https://bugzilla.gnome.org/show_bug.cgi?id=617045 commit 0f0a62f316aff3a135ca4bcfe98964f1d053be73 Author: Edward Hervey <bilboed@bilboed.com> Date: Mon Apr 19 20:40:56 2010 +0200 basetransform: Retain caps order when getting caps If the element gave us caps in a specific order, let's retain that by intersecting against the template but retaining the order given by the element. https://bugzilla.gnome.org/show_bug.cgi?id=617045 commit 0e1a56146728563e84e95521c856425bebf78506 Author: Thiago Santos <thiago.sousa.santos@collabora.co.uk> Date: Fri Feb 25 10:25:26 2011 -0300 tests: caps: Tests for the new caps intersection mode Adds test cases for the caps 'first' intersect mode Adds another test for the 'zigzag' mode Fixes #617045 commit 09d83e589ab24becbe9171407e8b5a865f7d898d Author: Edward Hervey <bilboed@bilboed.com> Date: Fri Feb 25 08:50:12 2011 -0300 gstcaps: new API : gst_caps_intersect_full Just like gst_caps_intersect, but adds a new parameter 'mode' that allows selecting the intersection algorithm to use. Currently we have GST_CAPS_INTERSECT_MODE_ZIG_ZAG (default) and GST_CAPS_INTERSECT_MODE_FIRST. API: gst_caps_intersect_full API: GstCapsIntersectMode API: GST_CAPS_INTERSECT_MODE_ZIG_ZAG API: GST_CAPS_INTERSECT_MODE_FIRST https://bugzilla.gnome.org/show_bug.cgi?id=617045