[FFmpeg-devel,3/8] avutil/mem: Add av_fast_realloc_array()

From: Andreas Rheinhardt <andres.rheinhardt@outlook.com>

This is an array-equivalent of av_fast_realloc(). Its advantages
compared to using av_fast_realloc() for allocating arrays are as
follows:

a) It performs its own overflow checks for the multiplication that is
implicit in array allocations. (And it only needs to perform these
checks (as well as the multiplication itself) in case the array needs to
be reallocated.)
b) It allows to limit the number of elements to an upper bound given
by the caller. This allows to restrict the number of allocated elements
to fit into an int and therefore makes this function usable with
counters of this type. It can also be used to avoid overflow checks in
the caller: E.g. setting it to UINT_MAX - 1 elements makes it safe to
increase the desired number of elements in steps of one. And it avoids
overallocations in situations where one already has an upper bound.
c) av_fast_realloc_array() will always allocate in multiples of array
elements; no memory is wasted with partial elements.
d) By returning an int, av_fast_realloc_array() can distinguish between
ordinary allocation failures (meriting AVERROR(ENOMEM)) and failures
because of allocation limits (by returning AVERROR(ERANGE)).
e) It is no longer possible for the user to accidentally lose the
pointer by using ptr = av_fast_realloc(ptr, ...).

Because of e) there is no need to set the number of allocated elements
to zero on failure.

av_fast_realloc() usually allocates size + size / 16 + 32 bytes if size
bytes are desired and if the already existing buffer isn't big enough.
av_fast_realloc_array() instead allocates nb + (nb + 14) / 16. Rounding
up is done in order not to reallocate in steps of one if the current
number is < 16; adding 14 instead of 15 has the effect of only
allocating one element if one element is desired. This is done with an
eye towards applications where arrays might commonly only contain one
element (as happens with the Matroska CueTrackPositions).

Which of the two functions allocates faster depends upon the size of
the elements. E.g. if the elements have a size of 32B and the desired
size is incremented in steps of one, allocations happen at
1, 3, 5, 7, 9, 11, 13, 15, 17, 20, 23, 26 ... for av_fast_realloc(),
1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 21, 24 ... for
av_fast_realloc_array(). For element sizes of 96B, the numbers are
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 21, 23, 25, 27, 30 ...
for av_fast_realloc() whereas the pattern for av_fast_realloc_array() is
unchanged.

Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
---
This patch (and some of the other patches of this patchset)
are mostly the same as the one in these threads:
https://ffmpeg.org/pipermail/ffmpeg-devel/2019-December/254836.html
https://ffmpeg.org/pipermail/ffmpeg-devel/2020-January/255182.html

 doc/APIchanges      |  3 +++
 libavutil/mem.c     | 33 +++++++++++++++++++++++++++++++++
 libavutil/mem.h     | 30 ++++++++++++++++++++++++++++++
 libavutil/version.h |  2 +-
 4 files changed, 67 insertions(+), 1 deletion(-)

tis 2022-07-05 klockan 22:26 +0200 skrev Andreas Rheinhardt:
> From: Andreas Rheinhardt <andres.rheinhardt@outlook.com>
> 
> This is an array-equivalent of av_fast_realloc(). Its advantages
> compared to using av_fast_realloc() for allocating arrays are as
> follows:
> 
> a) It performs its own overflow checks for the multiplication that is
> implicit in array allocations. (And it only needs to perform these
> checks (as well as the multiplication itself) in case the array needs
> to
> be reallocated.)
> b) It allows to limit the number of elements to an upper bound given
> by the caller. This allows to restrict the number of allocated
> elements
> to fit into an int and therefore makes this function usable with
> counters of this type. It can also be used to avoid overflow checks
> in
> the caller: E.g. setting it to UINT_MAX - 1 elements makes it safe to
> increase the desired number of elements in steps of one. And it
> avoids
> overallocations in situations where one already has an upper bound.
> c) av_fast_realloc_array() will always allocate in multiples of array
> elements; no memory is wasted with partial elements.
> d) By returning an int, av_fast_realloc_array() can distinguish
> between
> ordinary allocation failures (meriting AVERROR(ENOMEM)) and failures
> because of allocation limits (by returning AVERROR(ERANGE)).
> e) It is no longer possible for the user to accidentally lose the
> pointer by using ptr = av_fast_realloc(ptr, ...).

If you add an option for clearing the newly allocated memory then this
could work for my av_fast_recalloc() use case in the jpeg2000 decoder.
Or we could have two functions.

Small bikeshed: since the function takes a pointer to a pointer as
argument, av_fast_realloc_arrayp() might be a better name. I had in
mind to similarly rename av_fast_recalloc() to av_fast_recallocp().


> +
> +    nb = min_nb + (min_nb + 14) / 16;

Not +15? Or +0?

> +
> +    /* If min_nb is so big that the above calculation overflowed,
> +     * just allocate as much as we are allowed to. */
> +    nb = nb < min_nb ? max_nb : FFMIN(nb, max_nb);

Looks OK, but an explicit check for overflow is easier to verify

> +
> +    memcpy(&array, ptr, sizeof(array));
> +
> +    array = av_realloc(array, nb * elsize);
> +    if (!array)
> +        return AVERROR(ENOMEM);
> +
> +    memcpy(ptr, &array, sizeof(array));

An optional memset() here would be useful for me

Else it looks OK

/Tomas

Tomas Härdin:
> tis 2022-07-05 klockan 22:26 +0200 skrev Andreas Rheinhardt:
>> From: Andreas Rheinhardt <andres.rheinhardt@outlook.com>
>>
>> This is an array-equivalent of av_fast_realloc(). Its advantages
>> compared to using av_fast_realloc() for allocating arrays are as
>> follows:
>>
>> a) It performs its own overflow checks for the multiplication that is
>> implicit in array allocations. (And it only needs to perform these
>> checks (as well as the multiplication itself) in case the array needs
>> to
>> be reallocated.)
>> b) It allows to limit the number of elements to an upper bound given
>> by the caller. This allows to restrict the number of allocated
>> elements
>> to fit into an int and therefore makes this function usable with
>> counters of this type. It can also be used to avoid overflow checks
>> in
>> the caller: E.g. setting it to UINT_MAX - 1 elements makes it safe to
>> increase the desired number of elements in steps of one. And it
>> avoids
>> overallocations in situations where one already has an upper bound.
>> c) av_fast_realloc_array() will always allocate in multiples of array
>> elements; no memory is wasted with partial elements.
>> d) By returning an int, av_fast_realloc_array() can distinguish
>> between
>> ordinary allocation failures (meriting AVERROR(ENOMEM)) and failures
>> because of allocation limits (by returning AVERROR(ERANGE)).
>> e) It is no longer possible for the user to accidentally lose the
>> pointer by using ptr = av_fast_realloc(ptr, ...).
> 
> If you add an option for clearing the newly allocated memory then this
> could work for my av_fast_recalloc() use case in the jpeg2000 decoder.
> Or we could have two functions.
> 

I'd prefer it if the zeroing function were a wrapper around the
non-zeroing function.

> Small bikeshed: since the function takes a pointer to a pointer as
> argument, av_fast_realloc_arrayp() might be a better name. I had in
> mind to similarly rename av_fast_recalloc() to av_fast_recallocp().
> 
> 
>> +
>> +    nb = min_nb + (min_nb + 14) / 16;
> 
> Not +15? Or +0?

"av_fast_realloc_array() instead allocates nb + (nb + 14) / 16. Rounding
up is done in order not to reallocate in steps of one if the current
number is < 16; adding 14 instead of 15 has the effect of only
allocating one element if one element is desired."

> 
>> +
>> +    /* If min_nb is so big that the above calculation overflowed,
>> +     * just allocate as much as we are allowed to. */
>> +    nb = nb < min_nb ? max_nb : FFMIN(nb, max_nb);
> 
> Looks OK, but an explicit check for overflow is easier to verify
> 
>> +
>> +    memcpy(&array, ptr, sizeof(array));
>> +
>> +    array = av_realloc(array, nb * elsize);
>> +    if (!array)
>> +        return AVERROR(ENOMEM);
>> +
>> +    memcpy(ptr, &array, sizeof(array));
> 
> An optional memset() here would be useful for me
> 
> Else it looks OK
>

ons 2022-07-06 klockan 16:46 +0200 skrev Andreas Rheinhardt:
> Tomas Härdin:
> > tis 2022-07-05 klockan 22:26 +0200 skrev Andreas Rheinhardt:
> > > From: Andreas Rheinhardt <andres.rheinhardt@outlook.com>
> > > 
> > > This is an array-equivalent of av_fast_realloc(). Its advantages
> > > compared to using av_fast_realloc() for allocating arrays are as
> > > follows:
> > > 
> > > a) It performs its own overflow checks for the multiplication
> > > that is
> > > implicit in array allocations. (And it only needs to perform
> > > these
> > > checks (as well as the multiplication itself) in case the array
> > > needs
> > > to
> > > be reallocated.)
> > > b) It allows to limit the number of elements to an upper bound
> > > given
> > > by the caller. This allows to restrict the number of allocated
> > > elements
> > > to fit into an int and therefore makes this function usable with
> > > counters of this type. It can also be used to avoid overflow
> > > checks
> > > in
> > > the caller: E.g. setting it to UINT_MAX - 1 elements makes it
> > > safe to
> > > increase the desired number of elements in steps of one. And it
> > > avoids
> > > overallocations in situations where one already has an upper
> > > bound.
> > > c) av_fast_realloc_array() will always allocate in multiples of
> > > array
> > > elements; no memory is wasted with partial elements.
> > > d) By returning an int, av_fast_realloc_array() can distinguish
> > > between
> > > ordinary allocation failures (meriting AVERROR(ENOMEM)) and
> > > failures
> > > because of allocation limits (by returning AVERROR(ERANGE)).
> > > e) It is no longer possible for the user to accidentally lose the
> > > pointer by using ptr = av_fast_realloc(ptr, ...).
> > 
> > If you add an option for clearing the newly allocated memory then
> > this
> > could work for my av_fast_recalloc() use case in the jpeg2000
> > decoder.
> > Or we could have two functions.
> > 
> 
> I'd prefer it if the zeroing function were a wrapper around the
> non-zeroing function.

That should work, the change in allocated entries can be detected

> 
> > Small bikeshed: since the function takes a pointer to a pointer as
> > argument, av_fast_realloc_arrayp() might be a better name. I had in
> > mind to similarly rename av_fast_recalloc() to av_fast_recallocp().
> > 
> > 
> > > +
> > > +    nb = min_nb + (min_nb + 14) / 16;
> > 
> > Not +15? Or +0?
> 
> "av_fast_realloc_array() instead allocates nb + (nb + 14) / 16.
> Rounding
> up is done in order not to reallocate in steps of one if the current
> number is < 16; adding 14 instead of 15 has the effect of only
> allocating one element if one element is desired."

Wups, I actually read that part of the commit message then forgot about
it. I blame sickness

/Tomas

Andreas Rheinhardt:
> From: Andreas Rheinhardt <andres.rheinhardt@outlook.com>
> 
> This is an array-equivalent of av_fast_realloc(). Its advantages
> compared to using av_fast_realloc() for allocating arrays are as
> follows:
> 
> a) It performs its own overflow checks for the multiplication that is
> implicit in array allocations. (And it only needs to perform these
> checks (as well as the multiplication itself) in case the array needs to
> be reallocated.)
> b) It allows to limit the number of elements to an upper bound given
> by the caller. This allows to restrict the number of allocated elements
> to fit into an int and therefore makes this function usable with
> counters of this type. It can also be used to avoid overflow checks in
> the caller: E.g. setting it to UINT_MAX - 1 elements makes it safe to
> increase the desired number of elements in steps of one. And it avoids
> overallocations in situations where one already has an upper bound.
> c) av_fast_realloc_array() will always allocate in multiples of array
> elements; no memory is wasted with partial elements.
> d) By returning an int, av_fast_realloc_array() can distinguish between
> ordinary allocation failures (meriting AVERROR(ENOMEM)) and failures
> because of allocation limits (by returning AVERROR(ERANGE)).
> e) It is no longer possible for the user to accidentally lose the
> pointer by using ptr = av_fast_realloc(ptr, ...).
> 
> Because of e) there is no need to set the number of allocated elements
> to zero on failure.
> 
> av_fast_realloc() usually allocates size + size / 16 + 32 bytes if size
> bytes are desired and if the already existing buffer isn't big enough.
> av_fast_realloc_array() instead allocates nb + (nb + 14) / 16. Rounding
> up is done in order not to reallocate in steps of one if the current
> number is < 16; adding 14 instead of 15 has the effect of only
> allocating one element if one element is desired. This is done with an
> eye towards applications where arrays might commonly only contain one
> element (as happens with the Matroska CueTrackPositions).
> 
> Which of the two functions allocates faster depends upon the size of
> the elements. E.g. if the elements have a size of 32B and the desired
> size is incremented in steps of one, allocations happen at
> 1, 3, 5, 7, 9, 11, 13, 15, 17, 20, 23, 26 ... for av_fast_realloc(),
> 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 21, 24 ... for
> av_fast_realloc_array(). For element sizes of 96B, the numbers are
> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 21, 23, 25, 27, 30 ...
> for av_fast_realloc() whereas the pattern for av_fast_realloc_array() is
> unchanged.
> 
> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
> ---
> This patch (and some of the other patches of this patchset)
> are mostly the same as the one in these threads:
> https://ffmpeg.org/pipermail/ffmpeg-devel/2019-December/254836.html
> https://ffmpeg.org/pipermail/ffmpeg-devel/2020-January/255182.html
> 
>  doc/APIchanges      |  3 +++
>  libavutil/mem.c     | 33 +++++++++++++++++++++++++++++++++
>  libavutil/mem.h     | 30 ++++++++++++++++++++++++++++++
>  libavutil/version.h |  2 +-
>  4 files changed, 67 insertions(+), 1 deletion(-)
> 
> diff --git a/doc/APIchanges b/doc/APIchanges
> index 20b944933a..f633ae6fee 100644
> --- a/doc/APIchanges
> +++ b/doc/APIchanges
> @@ -14,6 +14,9 @@ libavutil:     2021-04-27
>  
>  API changes, most recent first:
>  
> +2022-07-05 - xxxxxxxxxx - lavu 57.28.100 - mem.h
> +  Add av_fast_realloc_array() to simplify reallocating of arrays.
> +
>  2022-06-12 - xxxxxxxxxx - lavf 59.25.100 - avio.h
>    Add avio_vprintf(), similar to avio_printf() but allow to use it
>    from within a function taking a variable argument list as input.
> diff --git a/libavutil/mem.c b/libavutil/mem.c
> index 18aff5291f..6e3942ae63 100644
> --- a/libavutil/mem.c
> +++ b/libavutil/mem.c
> @@ -532,6 +532,39 @@ void *av_fast_realloc(void *ptr, unsigned int *size, size_t min_size)
>      return ptr;
>  }
>  
> +int av_fast_realloc_array(void *ptr, size_t *nb_allocated,
> +                          size_t min_nb, size_t max_nb, size_t elsize)
> +{
> +    void *array;
> +    size_t nb, max_alloc_size_bytes;
> +
> +    if (min_nb <= *nb_allocated)
> +        return 0;
> +
> +    max_alloc_size_bytes = atomic_load_explicit(&max_alloc_size, memory_order_relaxed);
> +    max_nb = FFMIN(max_nb, max_alloc_size_bytes / elsize);
> +
> +    if (min_nb > max_nb)
> +        return AVERROR(ERANGE);
> +
> +    nb = min_nb + (min_nb + 14) / 16;
> +
> +    /* If min_nb is so big that the above calculation overflowed,
> +     * just allocate as much as we are allowed to. */
> +    nb = nb < min_nb ? max_nb : FFMIN(nb, max_nb);
> +
> +    memcpy(&array, ptr, sizeof(array));
> +
> +    array = av_realloc(array, nb * elsize);
> +    if (!array)
> +        return AVERROR(ENOMEM);
> +
> +    memcpy(ptr, &array, sizeof(array));
> +    *nb_allocated = nb;
> +
> +    return 0;
> +}
> +
>  static inline void fast_malloc(void *ptr, unsigned int *size, size_t min_size, int zero_realloc)
>  {
>      size_t max_size;
> diff --git a/libavutil/mem.h b/libavutil/mem.h
> index d91174196c..f040de08fc 100644
> --- a/libavutil/mem.h
> +++ b/libavutil/mem.h
> @@ -375,11 +375,41 @@ int av_reallocp_array(void *ptr, size_t nmemb, size_t size);
>   * @return `ptr` if the buffer is large enough, a pointer to newly reallocated
>   *         buffer if the buffer was not large enough, or `NULL` in case of
>   *         error
> + * @see av_fast_realloc_array()
>   * @see av_realloc()
>   * @see av_fast_malloc()
>   */
>  void *av_fast_realloc(void *ptr, unsigned int *size, size_t min_size);
>  
> +/**
> + * Reallocate the given array if it is not large enough, otherwise do nothing.
> + *
> + * If `ptr` points to `NULL`, then a new uninitialized array is allocated.
> + *
> + * @param[in,out] ptr           Pointer to `NULL` or pointer to an already
> + *                              allocated array. `*ptr` will be set to point
> + *                              to the new array on success.
> + * @param[in,out] nb_allocated  Pointer to the number of elements of the array
> + *                              `*ptr`. `*nb_allocated` is updated to the new
> + *                              number of allocated elements.
> + * @param[in]     min_nb        Desired minimal number of elements in array `*ptr`
> + * @param[in]     max_nb        Maximal number of elements to allocate.
> + * @param[in]     elsize        Size of a single element of the array.
> + *                              Must not be zero.
> + * @return 0 on success, < 0 on failure. On failure, `*ptr` is not freed and
> + *         `*ptr` as well as `*nb_allocated` are unchanged.
> + * @note `max_nb` can be used to limit allocations and make this function
> + *       usable with counters of types other than size_t. It can also be used
> + *       to avoid overflow checks in callers: E.g. setting it to `UINT_MAX - 1`
> + *       means that incrementing an unsigned int in steps of one need not be
> + *       checked for overflow.
> + * @see av_fast_realloc()
> + * @see av_realloc()
> + * @see av_fast_malloc()
> + */
> +int av_fast_realloc_array(void *ptr, size_t *nb_allocated,
> +                          size_t min_nb, size_t max_nb, size_t elsize);
> +
>  /**
>   * Allocate a buffer, reusing the given one if large enough.
>   *
> diff --git a/libavutil/version.h b/libavutil/version.h
> index 2e9e02dda8..87178e9e9a 100644
> --- a/libavutil/version.h
> +++ b/libavutil/version.h
> @@ -79,7 +79,7 @@
>   */
>  
>  #define LIBAVUTIL_VERSION_MAJOR  57
> -#define LIBAVUTIL_VERSION_MINOR  27
> +#define LIBAVUTIL_VERSION_MINOR  28
>  #define LIBAVUTIL_VERSION_MICRO 100
>  
>  #define LIBAVUTIL_VERSION_INT   AV_VERSION_INT(LIBAVUTIL_VERSION_MAJOR, \

Anton really dislikes the av_fast_* naming and instead wants this to be
called av_realloc_array_reuse(). I don't care either way. Any more
opinions on this (or on the patch itself)?

- Andreas

Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
> Anton really dislikes the av_fast_* naming and instead wants this to be
> called av_realloc_array_reuse(). I don't care either way. Any more
> opinions on this (or on the patch itself)?

If people dislike _reuse(), I am open to other reasonable suggestions.
This 'fast' naming sucks because
- it tells you nothing about how this function is "fast"
- it is added at the beginning rather than the end, which is
  against standard namespacing conventions

Anton Khirnov:
> Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
>> Anton really dislikes the av_fast_* naming and instead wants this to be
>> called av_realloc_array_reuse(). I don't care either way. Any more
>> opinions on this (or on the patch itself)?
> 
> If people dislike _reuse(), I am open to other reasonable suggestions.
> This 'fast' naming sucks because
> - it tells you nothing about how this function is "fast"
> - it is added at the beginning rather than the end, which is
>   against standard namespacing conventions
> 

Isn't reusing the basic modus operandi for a reallocation function? So
your suggested name doesn't seem to fit either.
(The actual difference of this function to an ordinary function is that
it overallocates and does not shrink the buffer even if it is too big.)

- Andreas

Quoting Andreas Rheinhardt (2022-07-14 14:51:07)
> Anton Khirnov:
> > Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
> >> Anton really dislikes the av_fast_* naming and instead wants this to be
> >> called av_realloc_array_reuse(). I don't care either way. Any more
> >> opinions on this (or on the patch itself)?
> > 
> > If people dislike _reuse(), I am open to other reasonable suggestions.
> > This 'fast' naming sucks because
> > - it tells you nothing about how this function is "fast"
> > - it is added at the beginning rather than the end, which is
> >   against standard namespacing conventions
> > 
> 
> Isn't reusing the basic modus operandi for a reallocation function? So
> your suggested name doesn't seem to fit either.

Ordinary realloc just keeps the data, I wouldn't call that "reuse" since
it will often be a copy. This "fast" realloc OTOH reuses the actual
buffer, same as all the other "fast" mem.h functions.

But feel free to suggest another naming pattern if you can think of one.

tis 2022-07-12 klockan 16:12 +0200 skrev Andreas Rheinhardt:
> 
> Anton really dislikes the av_fast_* naming and instead wants this to
> be
> called av_realloc_array_reuse(). I don't care either way. Any more
> opinions on this (or on the patch itself)?

That's going to cause some "impedance mismatch" given that the other
functions are still called fast rather than reuse, and changing that
would requite a major bump.

Ideally we'd come up with a coherent naming scheme for all of these
functions because frankly it's a mess at the moment. I tried
summarizing all functions in a spreadsheet, and there's a lot of gaps
functionality wise. Best solution would be to write the cartesian
product of all features in one go, with an accompanying coherent naming
scheme.

{pointer, pointer-to-pointer} * {don't care what the data is, copy old
data, copy and zero newly allocated memory, zero entire buffer} * {size
in bytes, nelem*elemsize}

/Tomas

Quoting Tomas Härdin (2022-07-21 23:23:25)
> tis 2022-07-12 klockan 16:12 +0200 skrev Andreas Rheinhardt:
> > 
> > Anton really dislikes the av_fast_* naming and instead wants this to
> > be
> > called av_realloc_array_reuse(). I don't care either way. Any more
> > opinions on this (or on the patch itself)?
> 
> That's going to cause some "impedance mismatch" given that the other
> functions are still called fast rather than reuse, and changing that
> would requite a major bump.

One of my other points was that the existing "fast" functions use
unsigned int rather than size_t, so that's another reason to replace
them.

Adding new functions and using them to replace all uses of the old ones
in our codebase does not need a major bump. Actually removing the old
ones does, but that can be done whenever.

Anton Khirnov:
> Quoting Andreas Rheinhardt (2022-07-14 14:51:07)
>> Anton Khirnov:
>>> Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
>>>> Anton really dislikes the av_fast_* naming and instead wants this to be
>>>> called av_realloc_array_reuse(). I don't care either way. Any more
>>>> opinions on this (or on the patch itself)?
>>>
>>> If people dislike _reuse(), I am open to other reasonable suggestions.
>>> This 'fast' naming sucks because
>>> - it tells you nothing about how this function is "fast"
>>> - it is added at the beginning rather than the end, which is
>>>   against standard namespacing conventions
>>>
>>
>> Isn't reusing the basic modus operandi for a reallocation function? So
>> your suggested name doesn't seem to fit either.
> 
> Ordinary realloc just keeps the data, I wouldn't call that "reuse" since
> it will often be a copy. This "fast" realloc OTOH reuses the actual
> buffer, same as all the other "fast" mem.h functions.
> 
> But feel free to suggest another naming pattern if you can think of one.
> 

I see two differences between this function and ordinary realloc: It
never shrinks the buffer and it overallocates. These two properties make
it more likely that these functions can avoid copies more often than
plain realloc (but in contrast to realloc, we can not grow the buffer in
case there is free space after it), but it is nevertheless the same as
realloc.

But I don't really care that much about the name and will therefore use
your name as I can't come up with anything better.
(Of course, I am still open to alternative suggestions.)

- Andreas

Andreas Rheinhardt:
> Anton Khirnov:
>> Quoting Andreas Rheinhardt (2022-07-14 14:51:07)
>>> Anton Khirnov:
>>>> Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
>>>>> Anton really dislikes the av_fast_* naming and instead wants this to be
>>>>> called av_realloc_array_reuse(). I don't care either way. Any more
>>>>> opinions on this (or on the patch itself)?
>>>>
>>>> If people dislike _reuse(), I am open to other reasonable suggestions.
>>>> This 'fast' naming sucks because
>>>> - it tells you nothing about how this function is "fast"
>>>> - it is added at the beginning rather than the end, which is
>>>>   against standard namespacing conventions
>>>>
>>>
>>> Isn't reusing the basic modus operandi for a reallocation function? So
>>> your suggested name doesn't seem to fit either.
>>
>> Ordinary realloc just keeps the data, I wouldn't call that "reuse" since
>> it will often be a copy. This "fast" realloc OTOH reuses the actual
>> buffer, same as all the other "fast" mem.h functions.
>>
>> But feel free to suggest another naming pattern if you can think of one.
>>
> 
> I see two differences between this function and ordinary realloc: It
> never shrinks the buffer and it overallocates. These two properties make
> it more likely that these functions can avoid copies more often than
> plain realloc (but in contrast to realloc, we can not grow the buffer in
> case there is free space after it), but it is nevertheless the same as
> realloc.
> 
> But I don't really care that much about the name and will therefore use
> your name as I can't come up with anything better.
> (Of course, I am still open to alternative suggestions.)
> 

Here is a rebased branch that uses av_realloc_array_reuse:
https://github.com/mkver/FFmpeg/commits/fast_realloc

- Andreas

mån 2022-09-26 klockan 14:25 +0200 skrev Andreas Rheinhardt:
> Anton Khirnov:
> > Quoting Andreas Rheinhardt (2022-07-14 14:51:07)
> > > Anton Khirnov:
> > > > Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
> > > > > Anton really dislikes the av_fast_* naming and instead wants
> > > > > this to be
> > > > > called av_realloc_array_reuse(). I don't care either way. Any
> > > > > more
> > > > > opinions on this (or on the patch itself)?
> > > > 
> > > > If people dislike _reuse(), I am open to other reasonable
> > > > suggestions.
> > > > This 'fast' naming sucks because
> > > > - it tells you nothing about how this function is "fast"
> > > > - it is added at the beginning rather than the end, which is
> > > >   against standard namespacing conventions
> > > > 
> > > 
> > > Isn't reusing the basic modus operandi for a reallocation
> > > function? So
> > > your suggested name doesn't seem to fit either.
> > 
> > Ordinary realloc just keeps the data, I wouldn't call that "reuse"
> > since
> > it will often be a copy. This "fast" realloc OTOH reuses the actual
> > buffer, same as all the other "fast" mem.h functions.
> > 
> > But feel free to suggest another naming pattern if you can think of
> > one.
> > 
> 
> I see two differences between this function and ordinary realloc: It
> never shrinks the buffer and it overallocates. These two properties
> make
> it more likely that these functions can avoid copies more often than
> plain realloc (but in contrast to realloc, we can not grow the buffer
> in
> case there is free space after it), but it is nevertheless the same
> as
> realloc.
> 
> But I don't really care that much about the name and will therefore
> use
> your name as I can't come up with anything better.
> (Of course, I am still open to alternative suggestions.)
> 
> - Andreas

So this means av_realloc_array_reuse()? Eh, it works. I will add a
function that also zeroes the newly allocated space, what should we
call that? av_realloc_array_reusez()?
av_realloc_array_reuse_zerofill()?

/Tomas

mån 2022-09-26 klockan 16:24 +0200 skrev Tomas Härdin:
> mån 2022-09-26 klockan 14:25 +0200 skrev Andreas Rheinhardt:
> > Anton Khirnov:
> > > Quoting Andreas Rheinhardt (2022-07-14 14:51:07)
> > > > Anton Khirnov:
> > > > > Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
> > > > > > Anton really dislikes the av_fast_* naming and instead
> > > > > > wants
> > > > > > this to be
> > > > > > called av_realloc_array_reuse(). I don't care either way.
> > > > > > Any
> > > > > > more
> > > > > > opinions on this (or on the patch itself)?
> > > > > 
> > > > > If people dislike _reuse(), I am open to other reasonable
> > > > > suggestions.
> > > > > This 'fast' naming sucks because
> > > > > - it tells you nothing about how this function is "fast"
> > > > > - it is added at the beginning rather than the end, which is
> > > > >   against standard namespacing conventions
> > > > > 
> > > > 
> > > > Isn't reusing the basic modus operandi for a reallocation
> > > > function? So
> > > > your suggested name doesn't seem to fit either.
> > > 
> > > Ordinary realloc just keeps the data, I wouldn't call that
> > > "reuse"
> > > since
> > > it will often be a copy. This "fast" realloc OTOH reuses the
> > > actual
> > > buffer, same as all the other "fast" mem.h functions.
> > > 
> > > But feel free to suggest another naming pattern if you can think
> > > of
> > > one.
> > > 
> > 
> > I see two differences between this function and ordinary realloc:
> > It
> > never shrinks the buffer and it overallocates. These two properties
> > make
> > it more likely that these functions can avoid copies more often
> > than
> > plain realloc (but in contrast to realloc, we can not grow the
> > buffer
> > in
> > case there is free space after it), but it is nevertheless the same
> > as
> > realloc.
> > 
> > But I don't really care that much about the name and will therefore
> > use
> > your name as I can't come up with anything better.
> > (Of course, I am still open to alternative suggestions.)
> > 
> > - Andreas
> 
> So this means av_realloc_array_reuse()? Eh, it works. I will add a
> function that also zeroes the newly allocated space, what should we
> call that? av_realloc_array_reusez()?
> av_realloc_array_reuse_zerofill()?

Here's a draft patch that calls it av_reallocz_array_reuse(). Needs a
minor version bump of course

/Tomas

tis 2022-09-27 klockan 17:23 +0200 skrev Tomas Härdin:
> mån 2022-09-26 klockan 16:24 +0200 skrev Tomas Härdin:
> > mån 2022-09-26 klockan 14:25 +0200 skrev Andreas Rheinhardt:
> > > Anton Khirnov:
> > > > Quoting Andreas Rheinhardt (2022-07-14 14:51:07)
> > > > > Anton Khirnov:
> > > > > > Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
> > > > > > > Anton really dislikes the av_fast_* naming and instead
> > > > > > > wants
> > > > > > > this to be
> > > > > > > called av_realloc_array_reuse(). I don't care either way.
> > > > > > > Any
> > > > > > > more
> > > > > > > opinions on this (or on the patch itself)?
> > > > > > 
> > > > > > If people dislike _reuse(), I am open to other reasonable
> > > > > > suggestions.
> > > > > > This 'fast' naming sucks because
> > > > > > - it tells you nothing about how this function is "fast"
> > > > > > - it is added at the beginning rather than the end, which
> > > > > > is
> > > > > >   against standard namespacing conventions
> > > > > > 
> > > > > 
> > > > > Isn't reusing the basic modus operandi for a reallocation
> > > > > function? So
> > > > > your suggested name doesn't seem to fit either.
> > > > 
> > > > Ordinary realloc just keeps the data, I wouldn't call that
> > > > "reuse"
> > > > since
> > > > it will often be a copy. This "fast" realloc OTOH reuses the
> > > > actual
> > > > buffer, same as all the other "fast" mem.h functions.
> > > > 
> > > > But feel free to suggest another naming pattern if you can
> > > > think
> > > > of
> > > > one.
> > > > 
> > > 
> > > I see two differences between this function and ordinary realloc:
> > > It
> > > never shrinks the buffer and it overallocates. These two
> > > properties
> > > make
> > > it more likely that these functions can avoid copies more often
> > > than
> > > plain realloc (but in contrast to realloc, we can not grow the
> > > buffer
> > > in
> > > case there is free space after it), but it is nevertheless the
> > > same
> > > as
> > > realloc.
> > > 
> > > But I don't really care that much about the name and will
> > > therefore
> > > use
> > > your name as I can't come up with anything better.
> > > (Of course, I am still open to alternative suggestions.)
> > > 
> > > - Andreas
> > 
> > So this means av_realloc_array_reuse()? Eh, it works. I will add a
> > function that also zeroes the newly allocated space, what should we
> > call that? av_realloc_array_reusez()?
> > av_realloc_array_reuse_zerofill()?
> 
> Here's a draft patch that calls it av_reallocz_array_reuse(). Needs a
> minor version bump of course

This makes me realize something: av_realloc_array_reuse() requires that
*nb_allocated == 0 initially but this isn't specified in the
documentation. Patch attached relaxes this.

/Tomas

Tomas Härdin:
> tis 2022-09-27 klockan 17:23 +0200 skrev Tomas Härdin:
>> mån 2022-09-26 klockan 16:24 +0200 skrev Tomas Härdin:
>>> mån 2022-09-26 klockan 14:25 +0200 skrev Andreas Rheinhardt:
>>>> Anton Khirnov:
>>>>> Quoting Andreas Rheinhardt (2022-07-14 14:51:07)
>>>>>> Anton Khirnov:
>>>>>>> Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
>>>>>>>> Anton really dislikes the av_fast_* naming and instead
>>>>>>>> wants
>>>>>>>> this to be
>>>>>>>> called av_realloc_array_reuse(). I don't care either way.
>>>>>>>> Any
>>>>>>>> more
>>>>>>>> opinions on this (or on the patch itself)?
>>>>>>>
>>>>>>> If people dislike _reuse(), I am open to other reasonable
>>>>>>> suggestions.
>>>>>>> This 'fast' naming sucks because
>>>>>>> - it tells you nothing about how this function is "fast"
>>>>>>> - it is added at the beginning rather than the end, which
>>>>>>> is
>>>>>>>   against standard namespacing conventions
>>>>>>>
>>>>>>
>>>>>> Isn't reusing the basic modus operandi for a reallocation
>>>>>> function? So
>>>>>> your suggested name doesn't seem to fit either.
>>>>>
>>>>> Ordinary realloc just keeps the data, I wouldn't call that
>>>>> "reuse"
>>>>> since
>>>>> it will often be a copy. This "fast" realloc OTOH reuses the
>>>>> actual
>>>>> buffer, same as all the other "fast" mem.h functions.
>>>>>
>>>>> But feel free to suggest another naming pattern if you can
>>>>> think
>>>>> of
>>>>> one.
>>>>>
>>>>
>>>> I see two differences between this function and ordinary realloc:
>>>> It
>>>> never shrinks the buffer and it overallocates. These two
>>>> properties
>>>> make
>>>> it more likely that these functions can avoid copies more often
>>>> than
>>>> plain realloc (but in contrast to realloc, we can not grow the
>>>> buffer
>>>> in
>>>> case there is free space after it), but it is nevertheless the
>>>> same
>>>> as
>>>> realloc.
>>>>
>>>> But I don't really care that much about the name and will
>>>> therefore
>>>> use
>>>> your name as I can't come up with anything better.
>>>> (Of course, I am still open to alternative suggestions.)
>>>>
>>>> - Andreas
>>>
>>> So this means av_realloc_array_reuse()? Eh, it works. I will add a
>>> function that also zeroes the newly allocated space, what should we
>>> call that? av_realloc_array_reusez()?
>>> av_realloc_array_reuse_zerofill()?
>>
>> Here's a draft patch that calls it av_reallocz_array_reuse(). Needs a
>> minor version bump of course
> 
> This makes me realize something: av_realloc_array_reuse() requires that
> *nb_allocated == 0 initially but this isn't specified in the
> documentation. Patch attached relaxes this.
> 

* @param[in,out] nb_allocated  Pointer to the number of elements of the
array
*                              `*ptr`. `*nb_allocated` is updated to the new
*                              number of allocated elements.

If *ptr == NULL, then the number of elements of said array is (of
course) zero, so *nb_allocated has to be set to that. (But if you think
that this needs to be said explicitly, I can document it.)

- Andreas

ons 2022-09-28 klockan 13:06 +0200 skrev Andreas Rheinhardt:
> Tomas Härdin:
> > tis 2022-09-27 klockan 17:23 +0200 skrev Tomas Härdin:
> > > mån 2022-09-26 klockan 16:24 +0200 skrev Tomas Härdin:
> > > > mån 2022-09-26 klockan 14:25 +0200 skrev Andreas Rheinhardt:
> > > > > Anton Khirnov:
> > > > > > Quoting Andreas Rheinhardt (2022-07-14 14:51:07)
> > > > > > > Anton Khirnov:
> > > > > > > > Quoting Andreas Rheinhardt (2022-07-12 16:12:16)
> > > > > > > > > Anton really dislikes the av_fast_* naming and
> > > > > > > > > instead
> > > > > > > > > wants
> > > > > > > > > this to be
> > > > > > > > > called av_realloc_array_reuse(). I don't care either
> > > > > > > > > way.
> > > > > > > > > Any
> > > > > > > > > more
> > > > > > > > > opinions on this (or on the patch itself)?
> > > > > > > > 
> > > > > > > > If people dislike _reuse(), I am open to other
> > > > > > > > reasonable
> > > > > > > > suggestions.
> > > > > > > > This 'fast' naming sucks because
> > > > > > > > - it tells you nothing about how this function is
> > > > > > > > "fast"
> > > > > > > > - it is added at the beginning rather than the end,
> > > > > > > > which
> > > > > > > > is
> > > > > > > >   against standard namespacing conventions
> > > > > > > > 
> > > > > > > 
> > > > > > > Isn't reusing the basic modus operandi for a reallocation
> > > > > > > function? So
> > > > > > > your suggested name doesn't seem to fit either.
> > > > > > 
> > > > > > Ordinary realloc just keeps the data, I wouldn't call that
> > > > > > "reuse"
> > > > > > since
> > > > > > it will often be a copy. This "fast" realloc OTOH reuses
> > > > > > the
> > > > > > actual
> > > > > > buffer, same as all the other "fast" mem.h functions.
> > > > > > 
> > > > > > But feel free to suggest another naming pattern if you can
> > > > > > think
> > > > > > of
> > > > > > one.
> > > > > > 
> > > > > 
> > > > > I see two differences between this function and ordinary
> > > > > realloc:
> > > > > It
> > > > > never shrinks the buffer and it overallocates. These two
> > > > > properties
> > > > > make
> > > > > it more likely that these functions can avoid copies more
> > > > > often
> > > > > than
> > > > > plain realloc (but in contrast to realloc, we can not grow
> > > > > the
> > > > > buffer
> > > > > in
> > > > > case there is free space after it), but it is nevertheless
> > > > > the
> > > > > same
> > > > > as
> > > > > realloc.
> > > > > 
> > > > > But I don't really care that much about the name and will
> > > > > therefore
> > > > > use
> > > > > your name as I can't come up with anything better.
> > > > > (Of course, I am still open to alternative suggestions.)
> > > > > 
> > > > > - Andreas
> > > > 
> > > > So this means av_realloc_array_reuse()? Eh, it works. I will
> > > > add a
> > > > function that also zeroes the newly allocated space, what
> > > > should we
> > > > call that? av_realloc_array_reusez()?
> > > > av_realloc_array_reuse_zerofill()?
> > > 
> > > Here's a draft patch that calls it av_reallocz_array_reuse().
> > > Needs a
> > > minor version bump of course
> > 
> > This makes me realize something: av_realloc_array_reuse() requires
> > that
> > *nb_allocated == 0 initially but this isn't specified in the
> > documentation. Patch attached relaxes this.
> > 
> 
> * @param[in,out] nb_allocated  Pointer to the number of elements of
> the
> array
> *                              `*ptr`. `*nb_allocated` is updated to
> the new
> *                              number of allocated elements.
> 
> If *ptr == NULL, then the number of elements of said array is (of
> course) zero, so *nb_allocated has to be set to that.

Keep in mind av_malloc(0) and av_realloc(ptr, 0) are both legal and
will allocate one byte. Seems it's not a problem in this case luckily

> (But if you think
> that this needs to be said explicitly, I can document it.)

It's best to be explicit IMO, so that callers know they can't just use
an uninitialized size_t on the stack or something.

/Tomas