[FFmpeg-devel,v1] filter select - avoid 2 times rounding

Submitted by Ulf Zibis on July 19, 2019, 4:52 p.m.

Details

Message ID 74177968-0eaf-671a-bb1e-237502e5a6d6@CoSoCo.de
State New
Headers show

Commit Message

Ulf Zibis July 19, 2019, 4:52 p.m.
Hi,

I have seen, that filter select sometimes doesn't catch a frame
determined by t as cause of floating point rounding. I could experience
less problems after removing 2 times rounding in filter select. I'm
aware that there still is a chance to miss a catch, but I believe it
should be much more rare.

The patch works fine e.g. with:
$ ./ffmpeg in.mp4 -vf
select='eq(t\,10.16)+eq(t\,10.2)+eq(t\,10.24)+eq(t\,10.28)+eq(t\,10.32)+eq(t\,10.36)+eq(t\,10.4)+eq(t\,10.44)+eq(t\,17.52)+eq(t\,47.96)+eq(t\,49.08)+eq(t\,49.2)+eq(t\,55.72)+eq(t\,83.0)'
-vsync vfr out_%02d.png

Without the patch the frame for eq(t\,10.2) was missing.

-Ulf

Comments

Nicolas George July 19, 2019, 4:57 p.m.
Ulf Zibis (12019-07-19):
> >From f14142a22d340cba48b3e2352a33026590dec3a5 Mon Sep 17 00:00:00 2001
> From: Ulf Zibis <Ulf.Zibis@CoSoCo.de>
> Date: 19.07.2019, 18:27:51
> 

> avfilter/select: avoid twice rounding

Maybe I a missing something, I see no change in rounding in this code. I
suspect your diagnosis is wrong.

> 
> diff --git a/libavfilter/f_select.c b/libavfilter/f_select.c
> index 1132375..39cc004 100644
> --- a/libavfilter/f_select.c
> +++ b/libavfilter/f_select.c
> @@ -297,6 +297,7 @@
>  
>  #define D2TS(d)  (isnan(d) ? AV_NOPTS_VALUE : (int64_t)(d))
>  #define TS2D(ts) ((ts) == AV_NOPTS_VALUE ? NAN : (double)(ts))

> +#define TS2DT(ts, tb) (TS2D((ts) * (tb).num / (double)(tb).den))

You are multiplying two possibly large integers: it can overflow. I am
not sure if it is really a concern, but it must not be done blindly.

>  
>  static void select_frame(AVFilterContext *ctx, AVFrame *frame)
>  {
> @@ -307,11 +308,11 @@
>      if (isnan(select->var_values[VAR_START_PTS]))
>          select->var_values[VAR_START_PTS] = TS2D(frame->pts);
>      if (isnan(select->var_values[VAR_START_T]))
> -        select->var_values[VAR_START_T] = TS2D(frame->pts) * av_q2d(inlink->time_base);
> +        select->var_values[VAR_START_T] = TS2DT(frame->pts, inlink->time_base);
>  
>      select->var_values[VAR_N  ] = inlink->frame_count_out;
>      select->var_values[VAR_PTS] = TS2D(frame->pts);
> -    select->var_values[VAR_T  ] = TS2D(frame->pts) * av_q2d(inlink->time_base);
> +    select->var_values[VAR_T  ] = TS2DT(frame->pts, inlink->time_base);
>      select->var_values[VAR_POS] = frame->pkt_pos == -1 ? NAN : frame->pkt_pos;
>      select->var_values[VAR_KEY] = frame->key_frame;
>      select->var_values[VAR_CONCATDEC_SELECT] = get_concatdec_select(frame, av_rescale_q(frame->pts, inlink->time_base, AV_TIME_BASE_Q));


Regards,
Ulf Zibis July 19, 2019, 5:17 p.m.
Am 19.07.19 um 18:57 schrieb Nicolas George:
>
>> avfilter/select: avoid twice rounding
> Maybe I a missing something, I see no change in rounding in this code.
So please give an alternative theory than a rounding issue, why I
actually experience a different result.

>  I suspect your diagnosis is wrong

In the current code there is a 1st rounding with "(double)(time_base.nom
/ time_base.den)" and then a 2nd with multipliying this value with
"frame->pts". In my code there is only 1 rounding after division of
(int64_t)(frame->pts * time_base.nom) with "(double)time_base.den".

Additionally I think, the video must have millions of hours to trap into
integer overflow with int64_t.

-Ulf
Nicolas George July 19, 2019, 5:23 p.m.
Ulf Zibis (12019-07-19):
> So please give an alternative theory than a rounding issue, why I
> actually experience a different result.

Code with doubles is very fragile, changing anything in the structure of
your formula will give slightly different results. You were just lucky
that this change made your use case work.

> In the current code there is a 1st rounding with "(double)(time_base.nom
> / time_base.den)" and then a 2nd with multipliying this value with
> "frame->pts". In my code there is only 1 rounding after division of
> (int64_t)(frame->pts * time_base.nom) with "(double)time_base.den".

There is no rounding, all is done in double.

Regards,
Ulf Zibis July 19, 2019, 5:44 p.m.
Am 19.07.19 um 19:23 schrieb Nicolas George:
> Ulf Zibis (12019-07-19):
>> So please give an alternative theory than a rounding issue, why I
>> actually experience a different result.
> Code with doubles is very fragile, changing anything in the structure of
> your formula will give slightly different results. You were just lucky
> that this change made your use case work.

May be, but I believe single rounding over twice rounding is less fragile.

If I see right, the expression evaluation in libavutil/eval.c only
rounds once, so the chance of equal results against one rounding in
filter select should be higher.

>> In the current code there is a 1st rounding with "(double)(time_base.nom
>> / time_base.den)" and then a 2nd with multipliying this value with
>> "frame->pts". In my code there is only 1 rounding after division of
>> (int64_t)(frame->pts * time_base.nom) with "(double)time_base.den".
> There is no rounding, all is done in double.
Try this:
    printf("single rounding: %.40f\n", 130560LL * 1 / (double)12800);
    printf("twice rounding:  %.40f\n", 130560LL * (double)(1 /
(double)12800));
Result:
single rounding: 10.1999999999999992894572642398998141288757
twice rounding:  10.2000000000000010658141036401502788066864
The 1st result is closer to 10.2 as the 2nd.
Nicolas George July 19, 2019, 6:01 p.m.
Ulf Zibis (12019-07-19):
> May be, but I believe single rounding over twice rounding is less fragile.

Yes. And two plastic bags will slow your fall more than one when you
jump from a plane.

> Try this:
>     printf("single rounding: %.40f\n", 130560LL * 1 / (double)12800);
>     printf("twice rounding:  %.40f\n", 130560LL * (double)(1 /
> (double)12800));
> Result:
> single rounding: 10.1999999999999992894572642398998141288757
> twice rounding:  10.2000000000000010658141036401502788066864
> The 1st result is closer to 10.2 as the 2nd.

By a completely negligible difference. And that is assuming it would
hold for other values of 10.2, which I am not convinced.

You are wasting your time and making the code less readable for no
actual benefit.

Regards,
Ulf Zibis July 19, 2019, 8:23 p.m.
Am 19.07.19 um 20:01 schrieb Nicolas George:
> Ulf Zibis (12019-07-19):
>> May be, but I believe single rounding over twice rounding is less fragile.
> Yes. And two plastic bags will slow your fall more than one when you
> jump from a plane.
>
>> Try this:
>>     printf("single rounding: %.40f\n", 130560LL * 1 / (double)12800);
>>     printf("twice rounding:  %.40f\n", 130560LL * (double)(1 /
>> (double)12800));
>> Result:
>> single rounding: 10.1999999999999992894572642398998141288757
>> twice rounding:  10.2000000000000010658141036401502788066864
>> The 1st result is closer to 10.2 as the 2nd.
> By a completely negligible difference. 
The wing beat of a butterfly can trigger a hurricane.
> And that is assuming it would hold for other values of 10.2, which I am not convinced.
Then try this:
#define TIME_BASE 12800 // typical time base for 25 fps video
    int false_single = 0, false_twice = 0;
    for (int t = 0; t < 100 * 100; t += 4) {
        char expr_str[16], end, *end_p = &end;
        sprintf(expr_str, "%6g", t/(float)100); // simulate string from
command line
        double expr_parsed = strtod(expr_str, &end_p); //    ... to parse
        int64_t pts = t * TIME_BASE / 100;
        double t_single = pts * 1 / (double)TIME_BASE;
        double t_twice = pts * (double)(1 / (double)TIME_BASE);
        int r_single = expr_parsed == t_single;
        int r_twice = expr_parsed == t_twice;
/*
        printf("time:%6s, pts:%8ld, parsed:%22.18f, t_single:%22.18f=%s,
t_twice:%22.18f=%s\n",
                expr_str, pts, expr_parsed, t_single, r_single ? "true "
: "false", t_twice, r_twice ? "true " : "false");
*/
        false_single += !r_single;
        false_twice += !r_twice;
    }

    printf("single rounding fails: %d, twice rounding fails: %d, in %d
frames\n", false_single, false_twice, 100 * 100 / 4);

Result:
single rounding fails: 0, twice rounding fails: 327, in 2500 frames

> You are wasting your time and making the code less readable for no
> actual benefit.

Finding out, why the select filter doesn't work as I expected, wasted
enough time, so some time more doesn't matter ;-)

-Ulf
Hendrik Leppkes July 19, 2019, 8:46 p.m.
On Fri, Jul 19, 2019 at 7:44 PM Ulf Zibis <Ulf.Zibis@cosoco.de> wrote:
>
>
> Am 19.07.19 um 19:23 schrieb Nicolas George:
> > Ulf Zibis (12019-07-19):
> >> So please give an alternative theory than a rounding issue, why I
> >> actually experience a different result.
> > Code with doubles is very fragile, changing anything in the structure of
> > your formula will give slightly different results. You were just lucky
> > that this change made your use case work.
>
> May be, but I believe single rounding over twice rounding is less fragile.
>
> If I see right, the expression evaluation in libavutil/eval.c only
> rounds once, so the chance of equal results against one rounding in
> filter select should be higher.
>
> >> In the current code there is a 1st rounding with "(double)(time_base.nom
> >> / time_base.den)" and then a 2nd with multipliying this value with
> >> "frame->pts". In my code there is only 1 rounding after division of
> >> (int64_t)(frame->pts * time_base.nom) with "(double)time_base.den".
> > There is no rounding, all is done in double.
> Try this:
>     printf("single rounding: %.40f\n", 130560LL * 1 / (double)12800);
>     printf("twice rounding:  %.40f\n", 130560LL * (double)(1 /
> (double)12800));
> Result:
> single rounding: 10.1999999999999992894572642398998141288757
> twice rounding:  10.2000000000000010658141036401502788066864


This has absolutely nothing to do with "rounding", since there is no
rounding being performed, but all to do with that floating point
arithmetic is just always inaccurate.
What this comes down to is this:

a) 130560 / 12800
b) 130560 * (1 / 12800)

There is no rounding there, since everything is kept in full double
precision. But anyone working with doubles should know that they are
inherently inaccurate.
Instead of re-ordering the floating point math to somehow give you a
slightly more favorable result, maybe there should be actual rounding
to something reasonable when its evaluating the conditions, so that
such inaccuracies just don't matter in the first place?

- Hendrik
Ulf Zibis July 19, 2019, 10:06 p.m.
Am 19.07.19 um 22:46 schrieb Hendrik Leppkes:
> This has absolutely nothing to do with "rounding", since there is no
> rounding being performed, but all to do with that floating point
> arithmetic is just always inaccurate.

Floating point representation and arithmetic *is* "aproximating
(=rounding) a real (and here a rational, wich is a subset of real)
value", see 1st paragraph here:
https://en.wikipedia.org/wiki/Floating-point_arithmetic


> What this comes down to is this:
>
> a) 130560 / 12800
> b) 130560 * (1 / 12800)
>
> There is no rounding there, since everything is kept in full double
> precision. But anyone working with doubles should know that they are
> inherently inaccurate.
> Instead of re-ordering the floating point math to somehow give you a
> slightly more favorable result, maybe there should be actual rounding
> to something reasonable when its evaluating the conditions, so that
> such inaccuracies just don't matter in the first place?
$1 The captain is always right.

$2 If the captain fails, see $1.

0 against 327 fails in 2500 frames is a "slightly more favorable
result". See my last post from 22:23 CEST.

-Ulf
Hendrik Leppkes July 19, 2019, 10:37 p.m.
On Sat, Jul 20, 2019 at 12:06 AM Ulf Zibis <Ulf.Zibis@cosoco.de> wrote:
>
>
> Am 19.07.19 um 22:46 schrieb Hendrik Leppkes:
> > This has absolutely nothing to do with "rounding", since there is no
> > rounding being performed, but all to do with that floating point
> > arithmetic is just always inaccurate.
>
> Floating point representation and arithmetic *is* "aproximating
> (=rounding) a real (and here a rational, wich is a subset of real)
> value", see 1st paragraph here:
> https://en.wikipedia.org/wiki/Floating-point_arithmetic
>
>
> > What this comes down to is this:
> >
> > a) 130560 / 12800
> > b) 130560 * (1 / 12800)
> >
> > There is no rounding there, since everything is kept in full double
> > precision. But anyone working with doubles should know that they are
> > inherently inaccurate.
> > Instead of re-ordering the floating point math to somehow give you a
> > slightly more favorable result, maybe there should be actual rounding
> > to something reasonable when its evaluating the conditions, so that
> > such inaccuracies just don't matter in the first place?
> $1 The captain is always right.
>
> $2 If the captain fails, see $1.
>
> 0 against 327 fails in 2500 frames is a "slightly more favorable
> result". See my last post from 22:23 CEST.
>

The entire point is that your change is not a fix, its a bandaid at best.

The behavior will still depend on many outside factors, like the
platform, if SSE or x87 FP math is being used, if fast or precise FP
mode is used by the compiler, and who knows what - because you are
expecting an equals comparison on a floating point value stemming from
a division to be true, which will just fail sometimes if one doesn't
round intentionally to get rid of the inaccuracy introduced by the
calculation itself.

- Hendrik
Ulf Zibis July 19, 2019, 10:39 p.m.
Am 20.07.19 um 00:06 schrieb Ulf Zibis:
> Am 19.07.19 um 22:46 schrieb Hendrik Leppkes:
>> This has absolutely nothing to do with "rounding", since there is no
>> rounding being performed, but all to do with that floating point
>> arithmetic is just always inaccurate.
> Floating point representation and arithmetic *is* "aproximating
> (=rounding) a real (and here a rational, wich is a subset of real)
> value", see 1st paragraph here:
> https://en.wikipedia.org/wiki/Floating-point_arithmetic

And if your concern is about the term "rounding" take "approximation"
for all places I've used "rounding", English is not my home language.

-Ulf
Ulf Zibis July 20, 2019, 12:02 a.m.
Am 20.07.19 um 00:37 schrieb Hendrik Leppkes:
>> $1 The captain is always right.
>>
>> $2 If the captain fails, see $1.
>>
>> 0 against 327 fails in 2500 frames is a "slightly more favorable
>> result". See my last post from 22:23 CEST.
>>
> The entire point is that your change is not a fix, its a bandaid at best.
I never have talked about a fix. What is the drawback of implementing
such a bandaid?

> The behavior will still depend on many outside factors, like the
> platform, if SSE or x87 FP math is being used, if fast or precise FP
> mode is used by the compiler, and who knows what - because you are
> expecting an equals comparison on a floating point value stemming from
> a division to be true, which will just fail sometimes if one doesn't
> round intentionally to get rid of the inaccuracy introduced by the
> calculation itself.
This is all correct. (the part about intentional rounding I don't
understand, may please give an example)

But keep in mind, that both calculations, the parsing from a string to a
double floating point and the transform oft an integer pts to a double
floating point value happen on the same machine with the same SSE and
x87 FP math and binaries from the same build with the same compiler
mode, so equality of both results is very very likely when doing only
exactly 1 approximation step on both sides.

The point is, that with e.g "10.2" the user is seeing a fixed point
value (= 10,200 ms) which is equivalent to an exact rational value, and
moreover FFmpeg claims to calculate with exact rationals where even
possible. So how should a user come to the idea, that "10.2" becomes
internally corrupted by "stupid" floating point
representation/conversion, and additionally in light of an exact time
base rational representation as e.g. 1/12800 s.
From my point of view it was a half-baked or "lousy" idea to internally
base all values of the select filter on a common double float array
instead on a multityped struct, so honouring that, my patch is indeed a
bandaid, but IMHO really helpful.

If FFmpeg engineers still want to persevere on the "just always
inaccurate" FP representation, why don't they provide a convenient
like(x, y) expression besides eq(x, y)?

-Ulf
Paul B Mahol July 21, 2019, 9 a.m.
On 7/20/19, Ulf Zibis <Ulf.Zibis@cosoco.de> wrote:
>
> Am 20.07.19 um 00:37 schrieb Hendrik Leppkes:
>>> $1 The captain is always right.
>>>
>>> $2 If the captain fails, see $1.
>>>
>>> 0 against 327 fails in 2500 frames is a "slightly more favorable
>>> result". See my last post from 22:23 CEST.
>>>
>> The entire point is that your change is not a fix, its a bandaid at best.
> I never have talked about a fix. What is the drawback of implementing
> such a bandaid?
>
>> The behavior will still depend on many outside factors, like the
>> platform, if SSE or x87 FP math is being used, if fast or precise FP
>> mode is used by the compiler, and who knows what - because you are
>> expecting an equals comparison on a floating point value stemming from
>> a division to be true, which will just fail sometimes if one doesn't
>> round intentionally to get rid of the inaccuracy introduced by the
>> calculation itself.
> This is all correct. (the part about intentional rounding I don't
> understand, may please give an example)
>
> But keep in mind, that both calculations, the parsing from a string to a
> double floating point and the transform oft an integer pts to a double
> floating point value happen on the same machine with the same SSE and
> x87 FP math and binaries from the same build with the same compiler
> mode, so equality of both results is very very likely when doing only
> exactly 1 approximation step on both sides.
>
> The point is, that with e.g "10.2" the user is seeing a fixed point
> value (= 10,200 ms) which is equivalent to an exact rational value, and
> moreover FFmpeg claims to calculate with exact rationals where even
> possible. So how should a user come to the idea, that "10.2" becomes
> internally corrupted by "stupid" floating point
> representation/conversion, and additionally in light of an exact time
> base rational representation as e.g. 1/12800 s.
> From my point of view it was a half-baked or "lousy" idea to internally
> base all values of the select filter on a common double float array
> instead on a multityped struct, so honouring that, my patch is indeed a
> bandaid, but IMHO really helpful.
>
> If FFmpeg engineers still want to persevere on the "just always
> inaccurate" FP representation, why don't they provide a convenient
> like(x, y) expression besides eq(x, y)?

That is good idea, also provide same function but with 3rd parameter
which will set likeness amount. This is rather trivial to code.

>
> -Ulf
>
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
> To unsubscribe, visit link above, or email
> ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Patch hide | download patch | download mbox

From f14142a22d340cba48b3e2352a33026590dec3a5 Mon Sep 17 00:00:00 2001
From: Ulf Zibis <Ulf.Zibis@CoSoCo.de>
Date: 19.07.2019, 18:27:51

avfilter/select: avoid twice rounding

diff --git a/libavfilter/f_select.c b/libavfilter/f_select.c
index 1132375..39cc004 100644
--- a/libavfilter/f_select.c
+++ b/libavfilter/f_select.c
@@ -297,6 +297,7 @@ 
 
 #define D2TS(d)  (isnan(d) ? AV_NOPTS_VALUE : (int64_t)(d))
 #define TS2D(ts) ((ts) == AV_NOPTS_VALUE ? NAN : (double)(ts))
+#define TS2DT(ts, tb) (TS2D((ts) * (tb).num / (double)(tb).den))
 
 static void select_frame(AVFilterContext *ctx, AVFrame *frame)
 {
@@ -307,11 +308,11 @@ 
     if (isnan(select->var_values[VAR_START_PTS]))
         select->var_values[VAR_START_PTS] = TS2D(frame->pts);
     if (isnan(select->var_values[VAR_START_T]))
-        select->var_values[VAR_START_T] = TS2D(frame->pts) * av_q2d(inlink->time_base);
+        select->var_values[VAR_START_T] = TS2DT(frame->pts, inlink->time_base);
 
     select->var_values[VAR_N  ] = inlink->frame_count_out;
     select->var_values[VAR_PTS] = TS2D(frame->pts);
-    select->var_values[VAR_T  ] = TS2D(frame->pts) * av_q2d(inlink->time_base);
+    select->var_values[VAR_T  ] = TS2DT(frame->pts, inlink->time_base);
     select->var_values[VAR_POS] = frame->pkt_pos == -1 ? NAN : frame->pkt_pos;
     select->var_values[VAR_KEY] = frame->key_frame;
     select->var_values[VAR_CONCATDEC_SELECT] = get_concatdec_select(frame, av_rescale_q(frame->pts, inlink->time_base, AV_TIME_BASE_Q));