Accessing frames to minimise cache misses

[mg262]

So, I have a filter which needs to compute a property (the "dot product") for every pair of frames within a given diameter of each other -- so for example, if the diameter is 3, I need to compute d(F0, F1), d(F0, F2), d(F0, F3) but not d(F0, F4). It is possible the diameter will be relatively large; I could use any advice on a sensible way in which to compute these parameters so that the re-requesting of a non-cached frame is minimised...

[IanB]

Can you express your pattern in a pseudo-GetFrame implementation or give examples of the source frames required to produce say frames 5 and frame 9 with diameters of say 3 and 5.

[mg262]

This is a bit messy. I will describe it, but if it just seems too horrendous to do anything with, please don't put too much effort into thinking about it! The precise numbers may change.

The clip is cut up into blocks of length 50; certain information (namely, blend pattern) is guessed for each block at a time. (For the sake of argument, we may as well say that this information is encoded into a small clip and passed out, i.e. that it is the information required by GetFrame.) Around each block we consider a window of radius 50. So for example, output frames 100 to 149 are given by considering frame 75 to 174 of the input. All 50 output frames are computed simultaneously.

Now, to compute these 50 output frames, we need to compute a function on a large number of pairs of input frames from the range 75 to 174, and (approximately) those pairs are precisely the pairs which are no more than n frames apart. example for n=3:

75, 76
75, 77
75, 78
76, 77
76, 78
76, 79
77, 78
77, 79
77, 80
...
170, 173
171, 172
171, 173
171, 174
172, 173
172, 174
173, 174

(It is possible that the relevant number may be a fair bit larger than 3 -- it depends to some extent on the parameters the filter will be called with.)

Perhaps a better way of putting it is this: if I knew how many relevant frames could be held in the cache at once, then I could try and think about sensible orders in which to request them to avoid re-generation -- but I can't see any sensible way of getting at that information?

[Bidoche]

You shouldn't try too much to outsmart cache logic. It isn't very easy and since it is bound to change, you may end up doing wrong.

A solution could be to hold onto the frames you need yourself to do your dot product (ie an array of PVideoFrame).

But personally I would rather trust the cache to do the right thing.
I can't say about the new 2.5 cache logic, but the 3.0 cache will detects the misses and grow to accomodate them (unless memory gets tight)

[IanB]

Yes, what Bidoche said! ;)

The pattern you indicated above
> 75, 76
> 75, 77
> 75, 78
> 76, 77
> 76, 78
> ...
Would not cause a problem for even the 2.5.5 cache, it's a simple 3 element cycle. However what I think you are trying to explain is that after each block of 50 you back up and hit the overlap a second time.So for example, output frames 100 to 149 are given by considering frame 75 to 174 of the inputSo in the next block of output frames, 150 to 199, you would consider frame 125 to 224 of the input, thus you re-hit frames 125 to 174 a second time. Have I got it right If so you need the cache to hold at least 50 frames, so you need to do a SetMemoryMax() with enough memory to hold 50 frames plus say 15% for other uses and overhead, and you had better be sure the machine has enough free physical memory to provide this. And hording large numbers of PVideoFrames in an array is a pretty sure way to visit page-fault hell.

Also why can't you just save your dot product partial answer for the overlap region then you would not need to bash such a wide span of frames. Maybe you could put your real source up somewhere for us to look at, it would stop the guess work.

IanB

[mg262]

I'm sorry if I was unclear above. I haven't started writing anything yet. I wasn't planning to recompute any values that had already been computed. What I was worried about was the case where n is much larger than 3. I will illustrate with n =10, cache assumed to hold ~5 frames -- I know that's not accurate but if I use much larger numbers it will become hard to read.

A simple order of computation:

75 76
75 77<--a
75 78
75 79
75 80
75 81
75 82
75 83
75 84
75 85<--b

76 77<--c
76 78
76 79
76 80
76 81
76 82
76 83
76 84
76 85
76 86

77 78
77 79
77 80
77 81
77 82
77 83
77 84
77 85
77 86
77 87

78 79
78 80
78 81
78 82
78 83
...

Now the problem I was worried about was that between times a and b, frames 76 and 77 would be removed from the cache, and then would be needed again at the time c. By changing the order in which things are computed, I could reduce the number of cache misses -- but only if I had an idea of how many frames would be held in the cache.

I really hope that is clear... but in any case, I have taken on the point about not trying to second-guess the cache -- so please don't worry about this one too much. Thanks for the thoughts,

M.

[Bidoche]

Removed from Cache is not a pb, and don't go assuming cache size.
It's the cache itself which is best placed to decide its own size.

On the other hand, what may be a pb is removed from cache requests history.
The history is what allows the cache to realize it has missed.
If that happens, the cache wont grow since it doesn't even know it is missing.

Currently 3.0 uses an history size of cache size + 20... which would fail to get any caching on your use case. :(
I guess I will have to put some more thoughts on that

[IanB]

Okay,I think I have it now.

The cache is simple LRU so probably this pattern or related,75 76
75 77
76 77
75 78
76 78
77 78
75 79
76 79
77 79
78 79
75 80
76 80
77 80
78 80
79 80
75 81
76 81
77 ....Or possible with reversal each sweep i.e....
75 79
76 79
77 79
78 79
79 80
78 80
77 80
76 80
75 80
75 81
76 81
77 ...However you order it you will be screwed once you exceed the cache width. The current maximum cache width is 200 entries. So for 720x576 YV12 frames thats about 120Mb, RGB32 about 320Mb so it's achievable.

IanB

[Bidoche]

Both patterns will work correctly on 3.0, but I find it kinda annoying to have to do something like that.

Why a limit to total number of frames cacheable !?

[IanB]

Both patterns will work correctly on 3.0, but I find it kinda annoying to have to do something like that.Why annoying? It is a generic problem with any cache technology, What is the optimum order to access data elements when you know the data set exceeds the cache size. It applies even more harshly with CPU L1 and L2 caches. Boffins spend ages pontificating on optimal strategies. These 2 orders are classics when using LRU caches, there are others. There are also many cache strategies specifically to deal with issue.

Why a limit to total number of frames cacheable !?It is actually number of frames trackable in each cache instance. I probably no longer need to limit this, but it is belt and braces protection against linear searching of very long lists. I originally added the limit to solve a problem caused by blankclip type sources where the cache ended up with 10000's of entries all pointing at the one vfb. It took much longer to search the list than to blit the frame, real bottleneck. Improved indexing might have been a better solution at the time, but fixing the pathology behind the problem was the right solution in the end.

IanB

[MfA]

I just ran across an almost trivial extension to LRU called ARC (http://www.almaden.ibm.com/StorageSystems/autonomic_storage/ARC/index.shtml) at IBM's site. Looks interesting :
* ARC has low space complexity. A realistic implementation had a total space overhead of less than 0.75%.
* ARC has low time complexity; virtually identical to LRU.
* ARC is self-tuning and adapts to different workloads and cache sizes. In particular, it gives very little cache space to sequential workloads, thus avoiding a key limitation of LRU.
* ARC outperforms LRU for a wide range of workloads. For example, for a huge, real-life workload generated by a large commercial search engine with a 4GB cache, ARC's hit ratio was dramatically better than that of LRU (40.44 percent vs. 27.62 percent).
* ARC is extremely simple to implement. Only a few lines of code are needed to convert an existing LRU implementation into an ARC implementation. For a "how-to" on this process, see the paper, "One Up on LRU."
Invented by a guy named Nimrod no less :)

[mg262]

Ian and others,

thank you for the thoughts -- they are much appreciated and I shall think hard on them before starting to code.

Since this is turning into a (very interesting!) general cache discussion, one thought to throw in: many filters with nontrivial frame access patterns "know" those patterns ahead of time.

(BTW, can I ask what "pb" means?)

[Bidoche]

@IanB

Ok, what you call cache width, I call cache history size.

You make me look petty with your 200 when i give 20 :p


@MfA

looks interesting, I will take a look


@mg262

pb = problem

[IanB]

You make me look petty with your 200 when i give 20For CACHE_RANGE mode I limit to 11 cache buffers, beyond that I revert to CACHE_ALL auto mode. I do it basicly to defend against Richard Cranium :D

IanB

[Bidoche]

Richard Cranium ?

[squid_80]

A person by the name of Richard is commonly known as Dick.
Cranium is another word for head.

I'm not going to risk translating any further in case I get myself into trouble.

[Bidoche]

ARC is probably worth trying, but it doesn't directly fit in avs case.
It supposes a fixed cache size and do the best of it, whereas avs has a lot of caches competing for memory and (possibly continuously) adapting their size.

[MfA]

Why not have 1 global cache instead of many little ones?

[MfA]

Or at least only 1 for every resolution.

[IanB]

Each cache is between each filter and caches the set of VideoFrameBuffer's specific to that point in the GetFrame() chain. The pool of VideoFrameBuffer's is global.

[MfA]

I was more talking to Bidoche there about ARC, so what is isnt so important. As long as the resolution&format are the same nothing of import is specific to videoframebuffers at different parts of the chain ... to me it would seem to make sense to use only 1 global algorithm for allocation within those buffers.

As for different resolutions&formats ... that's a bit of a headache. Even ignoring trying to find a good way to determine the size of the pool for the buffers of the different format there is the danger of fragmentation. If the CRT&windows are smart they will simply perform large allocations page aligned in a higher part of the memory space, if so then fragmentation should not be an issue ... but relying on windows being smart might not be a good idea, and even so there can still be internal fragmentation.

Digging around a bit virtualalloc/free would be the ideal solution in windows. Simply allocate large pools of videoframebuffer of all the variations needed. Except use virtualalloc to only reserve memory for videoframe->data. Cache frames into each pool, committing pages for data with virtualalloc if needed, use a global LRU (or ARC) to determine which videoframebuffer(s) needs to be "deleted" when a new one is inserted (because we are dealing with buffers of varying size you sometimes would need to "delete" multiple videoframebuffers of smaller size to make room). Instead of actually deleting them you just decommit the data though. Because virtualalloc only deals with complete pages there can be no external fragmentation, and because nothing is ever truely freed there is no internal fragmentation either. You need only 1 global cache allocation strategy ... which is just so much prettier than the present system.

[MfA]

Hmmm, would not even be necessary to create data buffers of differing size ... just commit all the data buffers with the largest size, and use MEM_RESET whenever they are replaced.

Might drop a bit of performance by not trying to replace data buffers of equal size in the cache, but since you are sure to get a TLB miss when accessing pages inside the databuffer for the first time the cost to assign a physical page to the virtual one is probably irrelevant (might even be faster, since the free page list should be easier to access than the tree which contains the virtual memory mapping).

PS. windows limits the amount of memory you can commit to your physical memory plus your page file size (even though it is not mapped to memory either in physical memory or the page file yet). So you would probably have to use commit/decommit instead of mem_reset ... commit causes pages to be zero'd, but the performance impact of that seems to be almost nil. The zeroing reads the data into the processor cache probably, and this has to happen anyway (even if you just write to an array desktop processors still first read the external data into cachelines, unless you use non-temporal stores ... retarded desktop processors (http://softwareforums.intel.com/ids/board/message?board.id=49&message.id=194)).

[Bidoche]

@MfA

I don't really get all these memory issues...
But you are welcome to write a memory recycler for 3.0 if you want, then we could test it against the regular malloc/free


use a global LRU (or ARC) to determine which videoframebuffer(s) needs to be "deleted" when a new one is inserted (because we are dealing with buffers of varying size you sometimes would need to "delete" multiple videoframebuffers of smaller size to make room).A LRU is not good enough.
The good idea is to allow slow and often used caches to consume more memory than fast and poorly used ones.

[mg262]

The good idea is to allow slow and often used caches to consume more memory than fast and poorly used ones.So you mean to measure frame generation speed and use it to control which frames are cached?

[MfA]

I don't really get all these memory issues...It's just a way to let you dynamically allocate videoframe->data each and every time without worrying about fragmentation. Makes managing the pool of videoframebuffers easier.

Why does Avisynth 3.0 build process have to be such a hell BTW? I know it's fugly, and doesnt allow you to debug the libraries ... but I would really love if you simply had a zip with include files/libs/dlls which you could put in the avisynth source directory and with which you could compile it directly :)

[Bidoche]

So you mean to measure frame generation speed and use it to control which frames are cached?At the filter level, not frame level.

And that's exactly what I already do :

Basically when a cache detects a miss, it grows and measure the generation speed of the missed frame to update his 'drop priority'

And globally the env enforces memory max by dispaching frame drop requests to caches as it needs in the order given by their drop priority.


It's just a way to let you dynamically allocate videoframe->data each and every time without worrying about fragmentation. Makes managing the pool of videoframebuffers easier.Are we even sure fragmentation is an issue ?

Why does Avisynth 3.0 build process have to be such a hell BTW?It's called linux portability... :p

I know it's fugly, and doesnt allow you to debug the libraries ... but I would really love if you simply had a zip with include files/libs/dlls which you could put in the avisynth source directory and with which you could compile it directlyI guess I can do that

[mg262]

Basically when a cache detects a miss, it grows and measure the generation speed of the missed frame to update his 'drop priority'Nice!

I think that before tryingcomplex changes it might be worth testing on real scripts... i.e. finding cases where the cache performs suboptimally and making sure that any changes actually help.

[MfA]

Are we even sure fragmentation is an issue ?Ian seemed to think it prevented him from just using a LRU scheme to delete unused buffers from the linkedvideoframebuffer pool, equivalent to your block recycling, and just allocating new buffers when needed. Or at least that's what the comments in the source code say :)
It's called linux portability... :pLinux distributions tend to just have all the -dev packages you need in their package system though.

[Bidoche]

I think that before tryingcomplex changes it might be worth testing on real scripts... i.e. finding cases where the cache performs suboptimally and making sure that any changes actually help.It should be better than the current one, as it doesn't require hinting and never cache more than it really needs.
On the other hand the growth and drop logics are probably improvable

Linux distributions tend to just have all the -dev packages you need in their package system though.Supposing those packages are the good ones...
Boost libs have often proved to be renamed when packaged :(

[mg262]

It should be better than the current one, as it doesn't require hinting and never cache more than it really needs.
On the other hand the growth and drop logics are probably improvableSorry, my comment wasn't meant to refer to your cache method (which as I said is nice!), but to the issues of fragmentation, etc.

[Bidoche]

Sorry, my comment wasn't meant to refer to your cache method (which as I said is nice!), but to the issues of fragmentation, etc.Oh.
Yes, it definitively should be tested

[mg262]

Addendum question: I'm thinking of implementing a temporal filter from a paper which behaves like this:

Output frame t = f( input frame t, output frame t-1 )

But if e.g. frame 100 is the first request, then each of the first 100 frames will need to be generated in order, which is not very helpful. (Scene detection will help a bit.) I may set it up so that it only goes back a certain number of frames... so it approximates like this:

Output frame 90 = f( input frame 90, input frame 89 )
Output frame 91 = f( input frame 91, output frame 90 )
Output frame 92 = f( input frame 92, output frame 91 )

... obviously the nondeterminism (dependence on request order) isn't particularly nice, but this is mainly for testing...

Q: Is any way in which I can check whether a given frame is held in the AVISynth cache?

[MfA]

If it's just for testing why not just cut the sequence down in size to what you need? :)

[mg262]

No, I mean that I want to be able to try it out on a large clip and seek around without having to repeatedly add trims. I might leave it in the final version with an appropriate warning... depends on the convergence behaviour.

[IanB]

Q: Is any way in which I can check whether a given frame is held in the AVISynth cache?From the debugger traverse the "video_frames" linked list member of the child cache filter to your filter, i.e. the instance your child->GetFrame() steps into. If you are super keen you could interogate the "child" object of your filter, it will be the cache instance you need to look at, it will be opaque to you so lots of naughty pointer fidling and casting will be required. :devil:

IanB

[mg262]

Ian, thanks for the reply. I am categorically not going to do anything that evil.:) I will probably work around the problem by holding the numbers of the last 10 frames generated...

[Bidoche]

Q: Is any way in which I can check whether a given frame is held in the AVISynth cache?There is in 3.0.
Since the cache is a clip member, you can get direct access to it and query it.
I have not yet decided exaclty what should queriable though.

[IanB]

While experimenting sure I can see lots of benefits, but not sure once the filter is written how knowing the cache population helps you. If you need frame 4321 to render the current output frame then you need frame 4321. How can you improve access by knowing? Are you hopeing by knowing the cache population you can ask for all those frames first so they won't get flushed if you ask for others? That would be pretty much a one shot advantage.

[mg262]

All this only applies in situation where it is acceptable to have the output slightly nondeterministic, i.e. have Filter->GetFrame(4322) able to return slightly different results in two subsequent calls. So Filter has two internal methods, one (fast) of which needs frame 4321 and is "exact", and one (slow) which doesn't need frame 4321 and is "an approximation".

I'm deeply ambivalent about this. On the one hand I find in intuitively very ugly/dissatisfying... but I had the same instinctive reaction to random algorithms when I first encountered them. I didn't use the word 'slightly' casually... the approximation should have a AAD luma difference from the original on the order of ~1 or lower if desired -- so this is very akin to using a random algorithm.

Most of this crops up when looking at algorithms presented in papers, which are often written with a semi-hardware mindset, and (as presented) always require the previous output frame to compute the current output frame. The algorithms could of course be modified to try and circumvent this, but that is another story...

[IanB]

Okay, so you are not really interested in looking in the input cache instance, you effectivly want to look into the output cache instance. i.e. you are recursive on yourself with a cache instance in between. So the determination is easy :- you do the "grandparent"->GetFrame() call to your "parent" cache. If the frame is cached it is returned, you do not see a recursive call to yourself and you build the exact answer. If the frame is not cached then you see the recursive call. Filters actually return an AVSValue, normally with a PVideoFrame, but here you could return something else i.e. a NULL to not pollute the cache. You see the null come back in and build an approximation answer. Devious enough :D

[mg262]

Oops -- I didn't realise I never replied to this. Sorry to be so rude, Ian -- and thank you very much!