diff mbox series

[FFmpeg-devel,8/8] avutil/fifo: Grow FIFO faster when growing automatically

Message ID DB6PR0101MB221436BE93DAF8B1A44449198F819@DB6PR0101MB2214.eurprd01.prod.exchangelabs.com
State New
Headers show
Series [FFmpeg-devel,1/8] avutil/mem: Handle fast allocations near UINT_MAX properly | expand

Checks

Context Check Description
yinshiyou/make_loongarch64 success Make finished
yinshiyou/make_fate_loongarch64 success Make fate finished
andriy/make_x86 success Make finished
andriy/make_fate_x86 success Make fate finished
andriy/make_armv7_RPi4 success Make finished
andriy/make_fate_armv7_RPi4 success Make fate finished

Commit Message

Andreas Rheinhardt July 5, 2022, 8:26 p.m. UTC 
Up until now, when the FIFO is grown automatically, it
would be resized by double the amount needed (if possible,
i.e. if compatible with the auto-grow limit).
This implies that if e.g. the user always writes a single
element to the FIFO, the FIFO will be reallocated once
for every two writes (presuming no reads happen inbetween).
This is potentially quadratic (depending upon the realloc
implementation).

This commit changes this by using av_fast_realloc_array
to realloc the buffer. Its ability to not overallocate
beyond a given size allows to honour the user-specified
auto-grow limit.

Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
---
 libavutil/fifo.c | 35 +++++++++++++++++++++++------------
 1 file changed, 23 insertions(+), 12 deletions(-)
diff mbox series

Patch

diff --git a/libavutil/fifo.c b/libavutil/fifo.c
index 53359a2112..04f4d057ca 100644
--- a/libavutil/fifo.c
+++ b/libavutil/fifo.c
@@ -96,6 +96,19 @@  size_t av_fifo_can_write(const AVFifo *f)
     return f->nb_elems - av_fifo_can_read(f);
 }
 
+static void fifo_readjust_after_growing(AVFifo *f, size_t old_size)
+{
+    const size_t inc = f->nb_elems - old_size;
+    // move the data from the end of the ring buffer
+    // to the end of the newly allocated space
+    if (f->offset_w <= f->offset_r && !f->is_empty) {
+        memmove(f->buffer + (f->offset_r + inc) * f->elem_size,
+                f->buffer + f->offset_r * f->elem_size,
+                (old_size - f->offset_r) * f->elem_size);
+        f->offset_r += inc;
+    }
+}
+
 int av_fifo_grow2(AVFifo *f, size_t inc)
 {
     uint8_t *tmp;
@@ -107,16 +120,8 @@  int av_fifo_grow2(AVFifo *f, size_t inc)
     if (!tmp)
         return AVERROR(ENOMEM);
     f->buffer = tmp;
-
-    // move the data from the end of the ring buffer
-    // to the end of the newly allocated space
-    if (f->offset_w <= f->offset_r && !f->is_empty) {
-        memmove(tmp + (f->offset_r + inc) * f->elem_size, tmp + f->offset_r * f->elem_size,
-                (f->nb_elems - f->offset_r) * f->elem_size);
-        f->offset_r += inc;
-    }
-
     f->nb_elems += inc;
+    fifo_readjust_after_growing(f, f->nb_elems - inc);
 
     return 0;
 }
@@ -133,9 +138,15 @@  static int fifo_check_space(AVFifo *f, size_t to_write)
     can_grow = f->auto_grow_limit > f->nb_elems ?
                f->auto_grow_limit - f->nb_elems : 0;
     if ((f->flags & AV_FIFO_FLAG_AUTO_GROW) && need_grow <= can_grow) {
-        // allocate a bit more than necessary, if we can
-        const size_t inc = (need_grow < can_grow / 2 ) ? need_grow * 2 : can_grow;
-        return av_fifo_grow2(f, inc);
+        // Use av_fast_realloc_array() to allocate in a fast way
+        // while respecting the auto_grow_limit
+        const size_t old_size = f->nb_elems;
+        int ret = av_fast_realloc_array(&f->buffer, &f->nb_elems, f->nb_elems + need_grow,
+                                        f->auto_grow_limit, f->elem_size);
+        if (ret < 0)
+            return ret;
+        fifo_readjust_after_growing(f, old_size);
+        return 0;
     }
 
     return AVERROR(ENOSPC);