Optimizations in a multicore pipeline
November 6, 2014
This is a story that happened during the development of
Video Enhancer a few minor versions ago.
It is a video processing application that, when doing its work, shows two
images: "before" and "after", i.e. part of original video frame and the same part
It uses DirectShow and has a graph where vertices (called filters) are things like
file reader, audio/video streams splitter, decoders, encoders, a muxer, a file writer
and a number of processing filters, and the graph edges are data streams.
What usually happens is: a reader reads the source video file, splitter splits it in two
streams (audio and video) and splits them by frames, decoder turns compressed frames
into raw bitmaps, a part of bitmap is drawn on screen (the "before"), then
processing filters turn them into stream of different bitmaps (in this case our
Super Resolution filter increases resolution, making each frame bigger),
then a part of processed frame is displayed on screen (the "after"), encoder
compresses the frame and sends to AVI writer that collects frames from both video and audio streams
and writes to an output AVI file.
Doing it in this order sequentially is not very effective because now we usually have multiple CPU
cores and it would be better to use them all. In order to do it special Parallelizer filters were
added to the filter chain. Such filter receives a frame, puts it into a queue and immediately returns.
In another thread it takes frames from this queue and feeds them to downstream filter. In effect,
as soon as the decoder decompressed a frame and gave it to parallelizer it can immediately start
decoding the next frame, and the just decoded frame will be processed in parallel. Similarly,
as soon as a frame is processed the processing filter can immediately start working on the next frame
and the just processed frame will be encoded and written in parallel, on another core. A pipeline!
At some point I noticed this pipeline didn't work as well on my dual core laptop as on quad core desktop,
so I decided to look closer what happens, when and where any unnecessary delays may be. I added some
logging to different parts of the pipeline and, since in text form they weren't too clear, made a converter
into SVG, gaining some interesting pictures.
Here's how the process looked like on a quad core box with DivX used for encoding. The source was a FLV
file but its splitter and decoder are not shown here because they don't write to my logs, being
third-party components. Time in this picture goes down. Different colors mark different frames.
Decoder gives a frame to the first Sample Grabber which remembers the part of frame we want to display
on screen. It sends the frame to a Parallelizer that puts it into its queue. In another thread
(different threads are shown with different background colors here) the frame is processed by SR
(Super Resolution) filter and sent to another Parellelizer. In yet another thread processed frame from
the Parallelizer queue is given to second Sample Grabber which takes a part of it to display and sends
the frame to an encoder (DivX) which later gives the compressed frame to AVI writer.
DivX doesn't write anything to my logs but since on both sides of it are my filters I know exactly
when it takes a frame and when it gives it out, compressed. In this picture everything goes smoothly:
speed of whole pipeline is limited by its slowest part (here it's SR), this part works 100% of the time
and the other parts work in parallel, taking a rest from time to time waiting for next data portion.
And here's how a similar process looked on my dual core laptop. Source file and processing was the same
but instead of DivX I was using XviD.
None of the pipeline parts work 100% of the time! The processing thread is idle half of the time, waiting
for the encoding-and-writing thread. And that thread is acting weird: sometimes taking a part of bitmap
for displaying happens in a snap and sometimes it takes a lot of time. And while it's
working the encoder does nothing. Also, we can see that the encoder is working weirdly: compressing
some frames takes significant time while some others are compressed in no time at all. Knowing that
we're dealing with MPEG4 where there are B-frames (bidirectional, they are based on both previous and
following frames), it's clear that XviD just remembers every other frame and when receiving the next
frame it compresses both the remembered and the new one. After compressing two frames it outputs one of them
immediately and the second one on the next call, when it will be remembering a new frame. But why does
extracting a part of frame for displaying takes so long sometimes? It is such a simple operation! If we
look closer at the picture here we'll notice: this extraction works super fast (as it should) when the
received frame is still hot, just processed. But if it spends some time in the queue, waiting, then
extracting a part from it takes much longer. It's CPU cache! In first case the frame is still in the cache
and everything is quick. In second case the cache gets filled with other data and to extract part of frame
it needs to be loaded from memory which is much slower, hence the delays.
This lead to first solution: I need to swap places the second Sample Grabber and Parallelizer. Then
extracting a part of frame in the grabber will happen immediately after processing the frame, it won't
leave the cache. And indeed, swapping these two filters made this extraction invariably fast.
The extraction operation became faster without changing a letter in its implementation!
In this picture encoder's times are not really displayed correctly because we know exactly only when a
frame is finished compressing but not when its encoding started. But even so, another problem is
clearly visible here. XviD here is still the slowest part of the pipeline and ideally it should work
100% of the time while other parts of pipeline should sometimes wait until XviD can take another frame.
But here it's not working all the time, part of time it waits until another frame is finished processing.
But why wasn't that frame processed earlier? The processing filter already had this frame and had the time
to process it.
Here's what happened. When some splitter, decoder or other filter wants to create another sample of data
(like a video frame) it requests memory buffer for it from an allocator. This allocator is negotiated
with downstream filter before processing starts (particularly, downstream filter might be a renderer and
provide an allocator that allocates samples directly in video memory). Number of buffers that an allocator
has is strictly limited. If a filter requests a buffer when all of them are taken, this request blocks
until some buffer gets released and becomes free to use. This is how Parallelizer limits its queue length:
by limiting number of buffers in its allocator. Because if we don't limit this length and producing filter
will work faster than consuming one, it will quickly eat all the memory. If we set a limit but make it
rather big, it may take too much RAM for uncompressed video frames. So a long time ago it was decided to
limit Parallelizer's queue by just two samples: one buffer is used by downstream consumer filter, while
the other buffer is getting filled by upstream producing filter in parallel. When the downstream filter
finishes its processing it will release the buffer to allocator and it will become available for the
upstream filter to place one more sample in the queue. This way they work in parallel without consuming
too much memory, but the queue may not have more than one frame waiting. When XviD compresses a frame
and swallows the next one (which was waiting in the queue), remembering it for compressing later,
the queue suddenly becomes empty, and now XviD needs to wait until the upstream processing filter
makes a new processed frame. And before this moment processing filter couldn't do it because both
buffers were taken - one was being compressed, another one waited in the queue.
Hence another solution: taking into account that some codecs behave this way, the queue of frames
for encoder should be made longer. After increasing number of buffers in the second Parallelizer
from 2 to 3 I got the following picture (samples in encoder not depicted, as they overlap because of
increased queue length):
Processing thread started to work fulltime, no more unnecessary waiting! Overall speed increased, although
not too much, because XviD still took too long for some frames but that was out of my control already.
Again, the acceleration happened without changing a bit in the processing parts doing the hard work,
just a change of one constant in the pipeline organization. That was fun!
tags: programming video_enhancer directshow