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

Message ID | 74177968-0eaf-671a-bb1e-237502e5a6d6@CoSoCo.de |
---|---|

State | New |

Headers | show |

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,

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

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,

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.

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,

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

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

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

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

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

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

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".

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));