Unreliable caching and readahead of video frames

Question

Hi, I'm working on an application that displays several videos at once. The videos are stored in the form of directories full of image files. For each frame number, there are up to 9 images that must be loaded from disk. I'd like to implement caching and read-ahead for the images. This would be pretty simple, but the complication is that the filesystem (sometimes a network FS) is nowhere near fast enough to display every image. So the readahead should choose which frames it's going to try to load, and only issue read() requests for those images. Also, it would be best if it could take into account which images are already cached, when deciding which frames it's going to load.

I came up with a greedy algorithm that will do alright, but I was wondering if this is a problem that's been studied, and there are better/optimal algorithms out there.

I'm assuming that time is measured with respect to frame rate, not seconds, to make this easier to pseudocode.

load_time_per_image = how long it takes to load an image
images_per_frame = the number of images to display simultaneously
worst_time = images_per_frame * load_time_per_image

def decide_next_frame_to_load:
    for each frame from now to now + worst_time:
        loadable = (frame - now) / load_time_per_image
        if number_of_images_cached(frame) > images_per_frame - loadable:
            # this frame is the first one it's possible to load in time.
            return frame

Anyone have suggestions? Thanks for your help! -Thomas

Answer 1

Is this intended for real-time operation?

Some of the worst-performing video editors I've seen will "index" each frame by storing each frame into its own image file. Are you stuck with using this storage mechanism? It would be significantly more efficient if the source videos were stored in a video format already (one per file) and there was an index for each video (basically the file offsets for each frame). Then you can use the operating system's caching mechanism to help improve your performance.

Another thing you may want to consider, although it probably won't help much with networked filesystems, is to store the images in YUV format. Your application which displays the videos might run faster (partly because the RGB-to-YUV conversion isn't necessary, and often because you can offload the work of drawing the YUV image to the video card), thus leaving more time for the filesystem work. I do this when drawing onto an X display just to avoid jitter.

As far as caching the images, I would probably use a separate thread to read the images from disk as fast as you can while the main thread assembles and presents the image. The main thread can do its loop once per frame presentation interval, and the separate thread can block when the amount of buffered/prepared images reaches a certain threshold. Video players like mplayer use such strategies.