[FFmpeg-devel] [PATCH] [libavutil] Add saturated add/sub operations for int64_t.

[Michael Niedermayer]

On Mon, May 04, 2020 at 02:19:47PM -0700, Dale Curtis wrote:
> On Mon, May 4, 2020 at 1:48 PM Michael Niedermayer <michael at niedermayer.cc>
[...]
> 
> 
> > lets consider a simple random expression
> > a*x + b*y
> >
> > overflow  = av_checked_sat_mul64(a, x, &T0);
> > overflow |= av_checked_sat_mul64(b, y, &T1);
> > overflow |= av_checked_sat_add64(T0, T1, &result);
> > if (overflow)
> >     ...
> >
> > vs.
> >
> > int64_t result = av_add_eint64( av_mul_eint64(a, x),
> >                                 av_mul_eint64(b, y) );
> > if (!av_is_finite_eint64(result))
> >     ....
> >
> > To me the 2nd variant looks easier to read, (eint here is supposed to mean
> > extended integer, that is extended by +/- infinity and NaN with IEEE like
> > semantics)
> 
> 

> > also the NaN element should have the same value as AV_NOPTS_VALUE, that
> > would
> > likely be most usefull.
> > This could also allow the removial of alot of AV_NOPTS_VALUE special
> > casing ...
> >
> 

> Are you just proposing sentinel values for those extensions? E.g., +inf =
> INT64_MAX, -inf=-INT64_MAX, nan=INT64_MIN?

yes


> It seems like you could just
> layer that on top of the saturated versions I'm proposing here. I don't
> think I'd recommend that solution though, instead it seems more legible and
> familiar to just use a float/double type in those cases where it'd be
> relevant. Once you start introducing sentinel checks everywhere, I doubt
> you'd keep much if any performance over a known type like float/double.

float/double is avoided (for timestamp computations) because it is
"inexactly specified", 2 platforms, 2 different compilers and the results can be
different. With reproducing things and regression testing thats just a
rather annoying thing.

Performance does matter for some code but for computations done per video
frame of a 60fps video 2 cpu cycles more would not matter
for many small packets it could matter, but somehow all of this kind
of feels like its too much and avoidable when its on a codepath that
is actually speed relevant ...

but how much worse is it performance wise ?

your code does 3 checks for normal numbers
   if (b >= 0 && a >= INT64_MAX - b)
     return INT64_MAX;
   if (b <= 0 && a <= INT64_MIN - b)
     return INT64_MIN;
   return a + b;

but this needs additional operations for tracking overflows if checking
is wanted

for handling the eint stuff, you would likely check if the inputs
are finite, thats a simple value + constant > constant2 check
per input though in case of previous operations the compiler could
already know if the value is finite depending on the branch it comes
from. 

When they are finite (common case) the following code is
basically the same but it does not need explicit overflow tracking, 
the uncommon non finite code path would need some more checks.

one can of course also implement this eint stuff differently to reduce
the checks.
a int64_t and a seperate "finite" flag would be an option

The main advantage of keeping track of finiteness in the "value"
itself instead of a obverflow return code is that it naturally
propagates the information instead of explicitly keeping track
of it.
for a single isolated operation there is no advantage

That all said, this leaves many question open. which may be interresting
to awnser.
A. how much time in % do we actually spend in timestamp computations which
   would need checks, saturation or other ?
B. how much actual performance difference is there for the different
   possible options
C. in the cases which affect performance most, can we avoid the computations
   alltogether ?
   very very small constant sized audio packets come to mind, the obvious idea would be
   to group them in bigger chunks. That would likely gain more than any
   difference between anything done by these checks 
   
not saying you should awnser any of these questions, these are more meant in
a general sense related to the subject

Thanks

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The educated differ from the uneducated as much as the living from the
dead. -- Aristotle 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20200505/87cf5f4b/attachment.sig>