IScriptEnvironment problem

[kassandro]

This is more a lack of robustness rather than a bug. The following filter conflicts with Avisynth's builtin filter avisource:

#define VC_EXTRALEAN
#include <Windows.h>
#include "avisynth.h"

static IScriptEnvironment* AVSenvironment;

class frame_handler
{
protected:
PClip clip;
public:
PVideoFrame __stdcall GetFrame(int n, IScriptEnvironment* env)
{
return clip->GetFrame(n, AVSenvironment);
}
frame_handler(PClip _clip) : clip(_clip) {}
};

AVSValue __cdecl Create_Filter(AVSValue args, void* user_data, IScriptEnvironment* env)
{
//AVSenvironment = env;
return new frame_handler(args[0].AsClip());
}

extern "C" __declspec(dllexport) const char* __stdcall AvisynthPluginInit2(IScriptEnvironment* env)
{
AVSenvironment = env;
env->AddFunction("Filter", "c", Create_Filter, 0);
return "RemoveDirt: dirt removal in film clips";
}

Using this filter in the following script:

input=avisource("input.avi")
Filter(input)

loading it into VirtualdubMod, then VirtualdubMod crashes upon exit.
The first line in the dll intialisation routine "AVSenvironment = env;
" and that I use "AVSenvironment" instead of "env" in GetFrame are the critical lines. Obviously AVSenvironment is messed up by GetFrame such that avisource is getting problems, surprisingly only upon termination. It is very desirable to have a global IScriptEnvironment* variable. The problem was detected Kintaro in the RemoveDirt thread (http://forum.doom9.org/showthread.php?s=&threadid=70856) but is much more prevalent in my yet unreleased plugin AlignFields. There are yet no other conflicts with this kind of IScriptEnvironment* usage. It would be nice if the conflict with avisource would disappear as well.

[sh0dan]

But why are you doing this?

[kassandro]

If I do not use a global environment, then I have to pass the local environment to any function, which may terminate with an error message. Some implementations of GetFrame, like RemoveDirt, pass on the request to frame specific subhandlers. If I would not use a global environment, I would have to pass on the lokal enviroment to all these subhandlers. Thus a global enviroment simplifies the design and makes the source code more transparent.
There is also philosophical reason for do this. When I think of an environment, then I have the desire that it should be as constant as possible. That applies for our planet and should also apply for Avisynth. And it is already almost the case. I'm only getting punished for my misdeeds, when I leave vdub, and only if I use avisource.

[sh0dan]

But there is a reason that ScriptEnv is passed along every getframe request - otherwise it might as well be a member of the GenericVideoFilter class, and just be stored at construction, as 'vi' and 'child'.

Global variables are evil. If you at least updated your global variable every GetFrame is it slightly better, but multiinstance/multithreading is still a problem.

Global variables are much worse design than passing parameters, and should be avoided if at all possible.

[kassandro]

Global variables are evil, I agree, but only if they change. If they are constant, multithreading is not endangered. And frankly, I have never seen a filter, which has ever changed IScriptEnvironment directly. Of course, as I learned recently, any filter is changing its environment somehow indirectly through Avisynth, if it makes a GetFrame call.
I thought that IScriptEnvironment contains script specific information, while GenericVideoFilter contains information specific to one single instance of a filter. On the other hand, for me after initialisation Avisynth works as follows: At the very beginning it calls GetFrame of the "last" filter. This filter may issue GetFrame calls to other filter instances and these have to be intercepted by Avisynth to check, whether the demanded frame is in the cache or not. If not, it passes the GetFrame call to the filter. Avisynth also has to deliever empty new frames to the filters, if requested, and to destroy unnecessary frames to avoid cache overflow. Everything else should be done by the filters, which are connected through GetFrame calls. Now, in my personal opinion, both tasks, caching and frame creating/destroying are specific to an instance of a filter and should therefore be done solely with GenericVideoFilter information, except, of course, some global information for memory management. So what is IScriptEnvironment really good for?

[sh0dan]

You still have the possibility of two instances accessing your filter - they will have completely different ScriptEnv's. There might be other cases.

[kassandro]

I have run tests with several instances of the same bad filter in a script. It works, as long as I don't use avisource. And if use avisource, I only get problems upon leaving vdub. But from the discussion I see, that you don't want to make any change. So I will now always use the local environment for GetFrame calls and the global one for Throwerror calls, that seems to cause no damages. Anyway, the function Throwerror should not be tied to any class.

[sh0dan]

FYI, Every time a script is opened a new ScriptEnvironment is created.

Furthermore if the app requests information about a script, a new env is created.

[Bidoche]

@kassandro

I agree, the ThrowError method is conceptually static.
But I believe it was made virtual instead so it got a place in the vtable and no worry to call it from a plugin...

[kassandro]

Compile the following plugin

#define VC_EXTRALEAN
#include <Windows.h>
#include "avisynth.h"

class Filter : public GenericVideoFilter
{
PVideoFrame __stdcall GetFrame(int n, IScriptEnvironment* env)
{
return child->GetFrame(n, env);
}
public:
Filter(PClip clip) : GenericVideoFilter(clip) {}
};

class dummy
{
PClip clip;
public:
dummy(PClip _clip) : clip(_clip) {}
};

AVSValue __cdecl Create_Filter(AVSValue args, void* user_data, IScriptEnvironment* env)
{
PClip clip = args[0].AsClip();
Filter *filter1 = new Filter(clip);
dummy *d = new dummy(clip);
//Filter *filter2 = new Filter(clip);
return filter1;
}

extern "C" __declspec(dllexport) const char* __stdcall AvisynthPluginInit2(IScriptEnvironment* env)
{
env->AddFunction("Filter", "c", Create_Filter, 0);
return "Avisource problem";
}

and use it in the script

avisource("input.avi")
Filter()

Then VirtualDubMod crashes upon exit. The critical source line is "dummy *d = new dummy(clip);". It creates a second reference to the IClip behind clip. Now don't tell me, that this is not allowed. If it would really not be allowed, then the smart pointer type PClip would be total rubbish. Here is another variant: replacing the above
Create_Filter by the following one:

AVSValue __cdecl Create_Filter(AVSValue args, void* user_data, IScriptEnvironment* env)
{
PClip clip = args[0].AsClip();
env->ThrowError("stop");
return new Filter(clip);
}

I am getting the same kind of crash (with the same script of course). Of course, this filter never takes off, but nevertheless I should be able to leave vdubmod gracefully. avisource seems to have problems with PClip variables. If I load the script into the original VirtualDub, then it crashes as well, but blames itself for an internal error. Nevertheless, I think the problem is with Avisynth.

[Bidoche]

The critical source line is "dummy *d = new dummy(clip);". It creates a second reference to the IClip behind clip.
Now don't tell me, that this is not allowed.I tell you.

If it would really not be allowed, then the smart pointer type PClip would be total rubbish.You purposely go out of your way to leak a pclip instance (with dummy help), and then you accuse it...
PClip works correctly as long as you use it correctly.

In your case, at script closure a ref to clip remains and it is not deleted.
I guess you detected problems with Avisource because its instances don't like not to be deleted, when others just don't care (as long as avisynth is closed at the same time).

[kassandro]

Smart pointers generate considerable overhead and there should be some pay off for that. Usually one wants to have more robustness. But now you say just the opposite. With IClip* such problems would be impossible. These crash filters show, that PClip variables must either be temporary on the stack or in objects which are under the control of Avisynth, otherwise avisource causes a crash. In my little program "dummy" objects are not under the control of Avisynth, while filters returned by a Creat_Filter are under Avisynth control. This behavior is not acceptable. Either you fix avisource or I simply steel an ordinary IClip pointer, by exploiting the Achilles' heel of any smart pointer. The class dummy then will look as follows:

class dummy
{
IClip *clip;
public:
dummy(PClip _clip)
{
clip = _clip.operator->();
}
};

Now the crash is gone and even overhead is reduced slightly. One shouldn't use such tricks. Of course, this trick is not so easily applicable for the second crash filter (the one with Throwerror). Such a situation occurs in the initialisation phase of most filters. Consequently, most filters in a script with avisource crash vdub, if they terminate with Throwerror during initialisation. One usually doesn't care much about such crashes, when exiting vdub, but now I know the reason.

[Bidoche]

Smart pointers generate considerable overhead and there should be some pay off for that. Considerable !? You are overreacting, the overhead is not that much, and totally unsignificative compared to filters processing time.
Look at the smart ptrs timings at http://www.boost.org/libs/smart_ptr/smarttests.htm (pclip is of the intrusive type)
With IClip* such problems would be impossible. Well, I defy you to code with IClip* (using AddRef and Release() yourself) and not leak...
These crash filters show, that PClip variables must either be temporary on the stack or in objects which are under the control of Avisynth, otherwise avisource causes a crashLike every object, they should be destroyed.
When they are on the stack, this is done automatically.
If they are on the heap, you have to make sure delete is called, which is not the case in your case.
It's leak a PClip and then the IClip it's handles...
This behavior is not acceptable. Are you suggesting that we hack Avisource so it will destroy its leaked instances at exit...
When the problem is obviously on your side, since your leak them.
Just make sure to delete your dummies.
What are they for anyway ?

Either you fix avisource As I already said, this is not a problem with Avisource, it crashes with it because it maintains external states with VFW.
or I simply steel an ordinary IClip pointer, by exploiting the Achilles' heel of any smart pointer.I guess you could do that, just beware of dangling references.

Of course, this trick is not so easily applicable for the second crash filter (the one with Throwerror).This one is a bug of avisynth.
The PClip in the AVSValue array is not destroyed when stack unwinds and the filter is leaked :(
I will look into it.

Edit: Apparently AVSValue arrays are always on the stack, so I got the problem wrong :'(

[kassandro]

Originally posted by Bidoche
Considerable !? You are overreacting, the overhead is not that much, and totally unsignificative compared to filters processing time.
Look at the smart ptrs timings at http://www.boost.org/libs/smart_ptr/smarttests.htm (pclip is of the intrusive type)

I agree, this was a blunt overstatement. Smart pointer should only be avoided in time critical low level functions. If the compiler is smart, PClip will only generate a little overhead during initialisation. During normal operation PClip is only used with clip->GetFrame and there should be no difference with IClip*.


Well, I defy you to code with IClip* (using AddRef and Release() yourself) and not leak...

I do not have to use AddRef and Release. In fact AddRef is the bad guy, who causes all the problems. When vdub wants to terminate, avisynth gets so surprised that the reference count of the IClip, to which dummy.clip is pointing, is not 0, that it knows no way out of this mess than to crash. The same happens with the second crash filter. This time it is
PClip clip = args[0].AsClip();
which causes AddRef to get active. Normally such stack variables do not hurt, because Release is called, when the stack frame is left. But in this case, the stack frame is not left. Instead Throwerror is called and Avisynth is surprised in the same way as with the first crash filter.


Like every object, they should be destroyed.
When they are on the stack, this is done automatically.
If they are on the heap, you have to make sure delete is called, which is not the case in your case.


Of course, it will be destroyed. It is the destructor of GenericVideoFilter, who destroys the IClip, which is called upon the death of the filter which is returned by CreateFilter. Unlike PFrame which points to a really temporary object, PClip points to a rather permanent object. IClip is usually only destroyed, when Avisynth is finished with a script. The only exception is, when the plugin directly calls delete filter1, but then again it is the destructor of GenericVideoFilter, which does the job. Thus only GenericVideoFilter should update the reference count of IClip and PClip should be an ordinary pointer. There is no reason to care about other references to IClip. In fact, as we have seen, Avisynth is unable to handle other references, if they forget to call Release.
Thus for Avisynth 3.0 I would suggest to simply put
typedef IClip *PClip
and only the constructors and the destructor of GenericVideoFilter should change the reference count of an IClip instance. Then there would be no leaks and no crashes. Of course, for Avisynth 2.5x
another solution has to be found to avoid the unaceptable recompilation of all filters.

[Bidoche]

Originally posted by kassandro
When vdub wants to terminate, avisynth gets so surprised that the reference count of the IClip, to which dummy.clip is pointing, is not 0The problem is that the filter is not destroyed, and in Avisource case then still maintains external VFW state.
Of course if the refcount had got to 0, it would have destroyed itself.
But in this case, the stack frame is not left. Instead Throwerror is called and Avisynth is surprised in the same way as with the first crash filter.ThrowError throws an exception, the stack is unwind, destructors being called in reverse creation order, PClip destructor is called, and Release() is called...
The leak doesn't come from this line.
But rather from the AVSValues array args, since the way they are handled is evil...

Of course, it will be destroyed. It is the destructor of GenericVideoFilter[...]I am talking about your dummy *, I see no delete dummy in the code you posted, so the leak.

IClip is usually only destroyed, when Avisynth is finished with a script.And what happens when one keep having scripts loaded (in a idle vdub for example) when rendering others.
It keeps eating the memory...

Thus only GenericVideoFilter should update the reference count of IClip and PClip should be an ordinary pointer.Maybe it could work, but I don't even want to think about it, when PClip works and simplifies things for us, it would definitely contradict the KISS rule.

Thus for Avisynth 3.0 I would suggest to simply put typedef IClip *PClip3.0 defines PClip as boost::shared_ptr<Clip const>
You should take a look at http://www.boost.org/libs/smart_ptr/smart_ptr.htm, maybe a weak_ptr is that you really want.
(Unfortunately it can be done in 2.5: intrusive smart ptr don't allow it)

Of course, for Avisynth 2.5x
another solution has to be found to avoid the unaceptable recompilation of all filters.Just delete your dummies and it will work (for 1st case)

[kassandro]

Originally posted by Bidoche
I am talking about your dummy *, I see no delete dummy in the code you posted, so the leak.

Avisynth should only care about its own data objects like IClip. It should never care about data objects of the filter writer like dummy. If I want to leak memory I can do it more easily and Avisynth could do nothing against it. Anyway, a leak should never cause a crash. At least non-Avisynth objects like dummy shouldn't cause problems.


And what happens when one keep having scripts loaded (in a idle vdub for example) when rendering others.
It keeps eating the memory...

The important thing, which I learned from this discussion, is that, when Avisynth starts a script, it doesn't necessarily do this with a fresh heap. (I though so, because Avisynth also unloads all the plugins, before it starts with a new script). Rather I have to write destructors for all objects to avoid a memory leak. So far I did only write destructors for objects, which are temporary within a script. Then, of course, the problem with dummy is gone, but nevertheless Avisynth should be leak tolerant.


Maybe it could work, but I don't even want to think about it, when PClip works and simplifies things for us, it would definitely contradict the KISS rule.

I strongly disagree! For me PClip is a role model of a bad smart pointer. It only cause problems and has no advantage, because the filter writer will only destroy an IClip object through the GenericVideoFilter destructor. This stands in sharp contrast to PVideoFrame, which is good smart pointer. Here the filter frequently destroys VideoFrame instances by leaving the stack frame.


Just delete your dummies and it will work (for 1st case)
ok, I will do this.

[sh0dan]

If there is anything constructive to be extracted from this discussion, I'd like to know.

AviSynth 2.5 uses the same architecture devised for AviSynth 1.0 many years ago by BenRG. None of us here wrote it - nor are any of us here capable of changing it without requiring a complete filter collection rewrite/recompile, which is clearly not an option before 3.0.

So I don't see any point in b*tching about it. Use your energy elsewhere, or focus your energy on helping Bidoche on creating the ultimate architecture for 3.0 - I'm sure he's very open for constructive input.

[Bidoche]

I guess it was just for the sake of argumenting. ;p


Anyway, I definitely could use some help for 3.0, both in the coding department and design.

For example, I am still looking for a satisfying behavior heuristic for the Cache class. (I can explain if somebody is willing to give it some thought (but I am dreaming))

NB: It could be used to imrpove 2.x cache too.

[kassandro]

I just made a detailed look at cache.h and cache.cpp. Though especially the default method "CACHE_ALL" is heavily interconnected with the rest of Avisynth, I would be interested. Having seen that, I will use cache hints in the future, in order to employ the first method. The second method really depends on good luck. Avisynth is not even prohibited from reusing a video frame buffer, which is at the top of the cache stack.

[Bidoche]

Though especially the default method "CACHE_ALL"The CACHE_ALL default is the major weakness of the actual cache sytem.
Even when frame access are totally linear, lots of frames get cached and all memory get consumed (for nothing).

Avisynth is not even prohibited from reusing a video frame bufferAnd that's exactly what happens.
When memory conditions get tight a frame buffer get reused (randomly from the cache viewpoint) and the videoframe using it invalided.


Anyway here is how I think it should be done instead :

No more cache hints :
While they are good in simple situations, in complex ones (clip with many parents) and in memory tight conditions they don't help much.

Instead I would like the Cache itself to adapt to its own situation.
For it is the best placed to see the cache opportunities he may be missing and then decide to adapt the number of frames to cache.
(That's why I talked about a behavior heuristic)

And it could include feedback methods for the env to warn them to cache less when memory is tight.

[sh0dan]

For kicks, I've implemented an autodetecting audiocache that enables or disables audio caching based on the access pattern. Basicly it maintains a score, defaulting to 100.

When a linear audio request is made, the score is increased by 5. When a nonliear access is detected, cache score is decreased by 25. When the score reaches 0, a default audiocache of 64kb is created. If the score reaches 250 the audiocache is destroyed.

If the cache proves to be too small more than 2 times, a larger one is created - up to 4MB per cache object.

[Bidoche]

Using a score, it might work.

Something like that : (pseudo code)
GetFrame(int n)
{
if (videoframe n cached)
return videoframe n

look for n in the list of the last requests (size to determine)
if (not found)
push it into the list as new last
else
{
score += 1000 / depth of n in list / inertia
update size of cache as score / 1000
}

have the clip make videoframe n
then cache it (eventually getting rid of oldest one)
and return it
}

CacheLess() //called by the env when it lacks memory
{
if (score >= 1000)
{
score -= 1000
update size of cache (dropping)
inertia += 1
}
}

[kassandro]

I would equip a cache with a simple learning technique. If a frame request arrives at the cache of a filter and it cannot find the frame in the cache, then the cache should check, whether the frame was already requested once. If so, the cache must be expanded such that this kind of cache miss doesn't happen again. Thus one needs for each cache an array int request[number_of_frames], in which the frame request number of a frame is stored. The request number is incremented with each request, starting from 1. It serves as a time scale for the filter. If a frame n was requested with request number k, we put request[n] = k. For each request, there will be one update of the request array. At the start we have request[n] = 0 for all n. If we now get a cache miss of a frame m with request[m] >0 at request number k, Then k - request[m] must be greater than the actual cache size, otherwise there would not have been a miss (the cache is usually a circular chain). If k - request[m] is not too large, we expand the cache to size k - request[m]. Consequently, the next time, when this periodic event occurs, we will not have a cache miss again. The nice thing is that all these request are usually periodic (unless there is some truely idiotic filter, which requests frames randomly), but we usually don't know the period. There are two problems with this method. First the request array is usually big. For a 100 minute PAL clip it is 4*150000 Bytes large and there may be many filters (of course for zero cost filters, like crop without align=true, there should be no cache at all). The memory waste problem can be overcome by some standard trick (8*1024 Bytes per filter is more than enough and acceptable). The other problem is more serious. There are two kinds of usage. If the frame requests are triggered by an encoder, which calls one frame after the other sequentially, then everything is periodic and fine. The situation is totally different, if a human uses Vdub to browse through a video. He jumbs back and forth in the video with the vdub slider and the filter caches are exploding because they learn a lot of nonsense. The situtation is now completely aperiodic. Usually, before the encoding process is started, one browses around in the video, to check whether the filters work properly and this browsing will mess up the caches. My idea to resolve the cache mess problem, is to restrict learning in the following way: When the application request a frame, learning is enabled. If the frame is new for the filter, which receives the request, it cannot learn and the learn flag is left unchanged. On the other hand, if a cache miss occurs, the filter learns by expanding his cache and sets the learn flag to false. The filters in the hierarchy below stop learning now and they don't have to learn anymore, because if the periodic request returns, it is handled by the cache of a filter which is higher in the hierarchy and no request will arrive in the lower hierarchy. This idea dramatically improves the cache efficiency. Only the cache of the last filter, immediately below the application, which runs the avs script, can now be messed up. However, since a smart encoder requests a frame only once, the last filter doesn't need to cache. If a frame was requested again, then it was triggered by a browsing human and in this case performance is a secondary issue. The last filter has only to check, whether the frame was requested for the first time (learn flag remains on) or not (learn flag is turned off). The learn flag can be passed from filter cache to filter cache as part of IScriptEnvironment.

[Bidoche]

It seems pretty much the same as my proposal, apart for your learning trick whose I do not understand the point.
I don't think an user browsing in the video will mess the caches, the frames requested are generally far enough to be considered new and so caches are unaffected.

(8*1024 Bytes per filter is more than enough and acceptable).The memory expense is probably acceptable, but do you really think we need to remember that much ?
It's very unlikely you will ever have to cache that much.
50 (or maybe 100) ints should be enough.

[Bidoche]

I just committed Cache code using this logic (in src/core/cache_concrete.h/cpp in the 3.0 branch)

I believe the same code could be used in 2.x (with minor adaptations)
if you are willing to accept some external dependancies :

I used external code for a circular_buffer class (itself dependant of boost) which greatly simplified matters.
(No need to reinvent the wheel (ie a circular buffer) again)

[kassandro]

I don't think an user browsing in the video will mess the caches, the frames requested are generally far enough to be considered new and so caches are unaffected.

If he jumps back far enough, then you are right. Now, if he simply scrolls back with the vdub left arrow key, then at some point the cache will be exhausted. Then each time the left arrow key is pressed the cache is expanded by one frame and quickly all the available frames are wasted.

I just committed Cache code using this logic (in src/core/cache_concrete.h/cpp in the 3.0 branch)

Where can I find it? Is it on the Sourceforge web site? I have only the source code for version 2.5.4

I agree that 1024 frames is far to much. A full resolution yv12 frame costs about 600 Kb. If we cache 100 of these, we have already spent a whopping 60 Mb only for caching and these 100 frames have to be spread over all the filters. That's why the cache design has to be extremely efficient. I think this cannot be done without a learn flag. Unfortunately this flag cannot be inserted into IScriptEnvironment, because the filter hierarchy may easily branch. Rather it has to be passed to GetFrame. Consequently, not only have all the filter to be recompiled, the source must also be changed slightly, though for most filters these changes can be done by a simple perl script. Now I can already hear sh0dan crying. On the other hand I expect that for a homogeneous (all frames use the same filter hierarchy) script containing no more than 10 filters, there will no more be any cache miss after, say, 100 frames. Of course, for a script with 100 filters caching simply doesn't work anymore and will creat only useless overhead, because there are not enough frames available even with the most efficient design. Here is my implementation of the cache class. It is not complete (CacheLess() is missing) and it certainly contains bugs (I didn't even dare to compile it because GetFrame is different). Also standard protection has to be added for the situation, when two different threads use the same cache simultaneously. Perhaps also the MakeWritable function(which should really not exist) has to be altered. For the last filter, immediately below the encoder, a different cache has to be implemented to prevent the cache from being messed up by random frame requests. Nevertheless the design should be essentially correct. It is also very concise.

#define CACHE_EXP 6
#define CACHE_SIZE_MAX (1 << CACHE_EXP)
#define CACHE_MASK (CACHE_SIZE_MAX - 1)

typedef bool PRequest; //PRequest may be a more complex object in later versions

class Cache : public GenericVideoFilter
{
int cache_size;
int cache_counter;
unsigned cache_pointer;
int request[CACHE_SIZE_MAX];
int scope[CACHE_SIZE_MAX];
PVideoFrame cache[CACHE_SIZE_MAX];

PVideoFrame fetch(unsigned position)
{
return cache[(cache_pointer - position) & CACHE_MASK];
}

void insert(PVideoFrame &newf)
{
cache_pointer = (cache_pointer + 1) & CACHE_MASK; // increment cache_pointer
if( cache[cache_pointer] != 0 ) ~cache[cache_pointer]; // decrease refcount of underlying VideoFrame
// save and lock newf
cache[cache_pointer] = newf; // refcount of underlying VideoFrame is increased!
}

PVideoFrame __stdcall GetFrame(int n, IScriptEnvironment* env, PRequest request_info)
{
int cache_index = n & CACHE_MASK;
int cache_position = cache_counter - request[cache_index];
if( request_info == false )
{ // if(request_info == false) then it is very unlikely, but possible that
// the frame is still in the cache
if( (scope[cache_index] == n) && (cache_position < cache_size) )
{ // it is in the cache
fetch_frame:
return fetch(cache_position); // get it from the cache
}
return child->GetFrame(n, env, request_info);
// do not increment cache_counter and do not insert the new frame into the cache!
}
if( scope[cache_index] != n ) // is the frame within our scope?
{ // no cache miss and the frame cannot be in the cache
scope[cache_index] = n;
request[cache_index] = ++cache_counter;
PVideoFrame result = child->GetFrame(n, env, request_info);
insert(result);
return result;
// we do not have to learn anything, because there was no cache miss
}
if( cache_position < cache_size ) goto fetch_frame;

// we have a cache miss and learn to avoid it next time
if( cache_position < CACHE_SIZE_MAX )
{
expand_cache(cache_position + 1); // --> cache_size = cache_position + 1
// the next time the frame will be in the cache

}
request_info = false; // only one filters has to deal with a cache miss
// do not put the frame into the cache and do not increment cache_counter
return child->GetFrame(n, env, request_info);
}
public:
Cache()
{ // at the beginning cache_pointer may be arbitrary, whence it is not initialised
cache_counter = cache_size = 0;
int i = CACHE_SIZE_MAX;
do
{
cache[i - 1] = request[i - 1] = 0;
scope[i - 1] = -1;
} while( --i );
}
};

[kassandro]

Sometimes there seems to be something wrong with the last posting of a thread in this forum. This time the edit button was simply missing.

In void insert(PVideoFrame &newf) the destructor is called twice. This is of course very incorrect, but the false code illuminates better, what is going on. The smart pointer mechanism is used to save and lock VideoFrames. Here is the correct version

void insert(PVideoFrame &newf)
{
cache_pointer = (cache_pointer + 1) & CACHE_MASK; // increment cache_pointer

// save and lock newf
cache[cache_pointer] = newf; // refcount of old cache[cache_pointer] is decreased
// and refcount of new VideoFrame is increased!
}

In the constructor of cache the PVideoFrame is automaticly initialised by the PVideoFrame constructor.

[Bidoche]

Where can I find it? Is it on the Sourceforge web site? I have only the source code for version 2.5.4 Of course, on sourceforge, but on the avisynth_3_0 branch.
That is to say you have to choose the avisynth_3_0 tag in a box in bottom of the pages to see 3.0 files.


About that learning trick of yours, maybe we don't care that much that the cache are messed up by vdub browsing.
After all if the user goes backward from time to time, we should help him.
The point is that it gets right when encoding.
Maybe a ResetCache() method to propagate in the filter graph.
Or even more sh0dan-friendly :p, the cache should notice that high cache size has gotten useless and shrink by itself.

[kassandro]

Of course, on sourceforge, but on the avisynth_3_0 branch.
That is to say you have to choose the avisynth_3_0 tag in a box in bottom of the pages to see 3.0 files.

I finally found the files. Unlike 2.5.4 you are now using templates, with which I am having difficulties. Though I know the existence of this concept, I never have even tried to use it. I have to take Stroustrup's book to overcome these problems.

[kassandro]

Filter writers believe that, if they avoid non-constant global variables, they are protected against multithreading. They are dead wrong! If two different threads execute simultaneously two different instances of the same filter, then avoiding non-constant global variables is sufficient. However, if two different threads execute simultaneously the same instance of a filter, then both threads manipulate simultaneously the same data elements of the filter object and multithreading turns into multishredding.
Now, the Cache can easily provide protection against this kind of desaster. If a thread enters Cache.GetFrame it evaluates the busy flag of the cache. If it is set, the thread puts itself into the thread queue of the cache and suspends itself. If the busy flag is not set, then the thread sets the busy flag and continues as usual. Now, before it exits GetFrame, it looks at the thread queue. If it is empty, it simply clears busy flag and exits. If it is not empty, it wakes up the first thread of the queue and exits. In this way the cache becomes a shield for the filter. With a modification of this idea, one can even protect dirty filters, which use global variables, against simultaneous execution of different instances. However, this kind of protection should only be optional, because it leads to unnecessary degradation of performance in a multithreaded environment. Such a mulithtreaded enviroment will become much more prevalent. I expect that in 2010 a cpu will have at least 10 integer execution units, 4 SSEx execution units and will pretend 10 virtual cpus. This is simply the easiest way to fulfill Moore's law of the seimconductor industry, which asserts performance doubling after every 18 months. To harness such cpus encoders will request several frames simultaneously and this will almost inevitably lead to the above multithreading problems.

[Bidoche]

They gave me a tough time at first too, but now they are common landscape :)
Anyway for the use I have of them in my Cache class, you don't really need to understand the details.


About the second point you raised (multithreading issues and Cache).
It's true that once we allow multiple threads in a filter graph (that is not the case at the time being) the need for synchronisation will arise.
And Caches will have to be synchronized, but you can't (at least not naively) use them to protect the underlying filter.
If you did so, ie allowing only one thread to run the filter (code), it will be only one thread in the filter and all its childs...
Which is not what one would want.

Having the Cache do all the work and avoid to plugin writers to worry about it is probably just a naive dream.
Anyway if you use a threading library, it's just a piece a cake to synchronize a filter.
(I use boost.Thread in block.cpp, 2 lines of code only...)

[kassandro]

Originally posted by Bidoche
And Caches will have to be synchronized, but you can't (at least not naively) use them to protect the underlying filter.
If you did so, ie allowing only one thread to run the filter (code), it will be only one thread in the filter and all its childs...
Which is not what one would want.

You are right. I realized this somewhat later. Essentially all threads except one will already be blocked by the last filter, immediately below the application. I can only wake up the next thread, if the previous thread is completely finished, i.e. it has gone through the entire filter hierarchy. This virtually prohibits any parallelism. Multithreading simply doesn't bode well for object oriented programming. However, there is a way out of this seamingly hopeless situation. It require a little assistance of the plugin writer, though. He has to adhere to the following simple rule: Finish all GetFrame calls, before you manipulate any class elements or any objects on the heap. Meanwhile you are only allowed to manipulate variables on the stack, which is the only thing not shared with other threads. For instance, my RemoveDirt filter has not only non-constant class elements but also allocates objects on the heap, which clashed with avisource. But it can be easily changed to adhere the above rule and for 95% of all filters this can be done as well. Now, if the plugin writer follows this easy rule, optimal througput can be achieved as follows. As before the caches have a busy flag and a thread queue. When the active thread leaves the cache to go down to the filter, all other threads are still blocked. Now, if he leaves this filter with a GetFrame call, he ends up in another cache. In this cache now the PRequest variable (which I added to GetFrame) is evaluated for a pointer to the parent cache. Consequently, it can go to the parent cache and wake up the first thread of the queue. It then continues with its ordinary work below the parent filter, while another thread may be active in the parent filter. Now at some point the first thread wants to return from the daughter cache to the parent filter, which may now be in use by another thread. This can be checked by evaluating the busy flag of the parent cache. If this is the case the first thread puts itself at the end of the queue of the parent cache and goes to sleep. Now, because of the above rule the parallel filter requests do no more interfer with each other.

[kassandro]

Originally posted by kassandro
Now, if the plugin writer follows this easy rule, optimal througput can be achieved as follows.
No!!! Threads are simply blocked to early with this mehtod, whence the throughput is not optimal. The above programming rule is certainly quite reasonable, but the busy flag and the thread queue should be private elements of GenericVideoFilter. When a thread is going to manipulate data elements of the class, the plugin writer has to call a function ReserveObject from GenericVideoFilter, which blocks or sets the busy flag, and when he is finished he must call ReleaseObject to wake up the next thread or clear the busy flag. It was interesting to think about, but this task cannot be taken over in a near optimal way by the cache.

[Bidoche]

a busy flag and a thread queueYou like building things from scratch, no ?
That kind of thing is called a mutex (for mutual exclusion, only one thread can own one at a given time).
They are used with lock objects (not necessary, but better design), the lock constructor acquire the mutex and its destructor release it.
This ensures that the release is ALWAYS done, relieving the developper from this burden (and it's exception safe, which is not the case with an explicit call in end of GetFrame)

Synchronisation can be done like this ://class MyFilter : //...

boost::thread::mutex mutex; //using boost.Thread

//...

virtual CPVideoFrame GetFrame(int n) const
{
CPVideoFrame source = GetChildFrame(n); //asynchrone
boost::thread::mutex::lock lock(mutex);
//... filter code using source synchrone now
}
};//MyFilter

You will note that I made the mutex a filter member, that is in 3.0 Cache are filters members too (it's easier to have filters without Cache then, they are just made that way (or not)) and you can't generally rely on a Cache parent to provide the mutex.
Anyway do we really want threads to block on Cache entry when one is in GetFrame ?
No we will want it to pass through so it can have childs make the source frames it will need, so separate synchronisation is better.

It was interesting to think about, but this task cannot be taken over in a near optimal way by the cache. just my conclusion :)
I should read to the end before writing ;)

[kassandro]

Originally posted by Bidoche
You like building things from scratch, no ?
That kind of thing is called a mutex (for mutual exclusion, only one thread can own one at a given time).

Yes, I have avoided these mutex objects until now. Instead I disabled interrupts during the very short time when the busy flag and the thread queue were manipulated. That works well for software multithreading, but for hardware multithreading there is simply no instruction like "cli" to stop all other processors temporarily. The advantage of avoiding mutex objects is that there is virtually no overhead (no system call) if there is only one thread. mutex objects are simpler to use and a lot more robust than my thread queues. With my thread queues the programmer has to be very carefull to avoid deadly self blocking of a thread. In the mutex case windows does the thread management, in my thread queues I am doing it myself using only the very basic functions SuspendThread and ResumeThread and even these functions are only used, if there is more than one thread.


Anyway do we really want threads to block on Cache entry when one is in GetFrame ?
No we will want it to pass through so it can have childs make the source frames it will need, so separate synchronisation is better.

I fully agree! Caches should only do caching, but it would have been nice to add such a functionality without such a severe penalty, which I overlooked at first glance.

I realised yesterday that with my AvsTimer Plugin I can easily monitor the Avisynth cache performance and it turned out that for my simple scripts there is virtually never a cache miss, though I have only 256 MB on my video pc. It is quite surprising and also disappointing that this theoretically extremely poor design works practically so perfect. Nevertheless, being a Mathematician by education, the current design should be replaced by a smarter one, violating the famous rule: If it ain't broken, don't fix it.

For script writers and cache developer likewise it would be very nice if the function GenericVideoFilter::SetCacheHints would do, what the name promises. If it would work, then one would be able to write cache filters, which are put immediately after the filter to be cached. Such a cache filter disables the cache of the filter, by using child->SetCacheHints (this can already be done now), but then one needs also GenericVideoFilter::SetCacheHints to avoid the cache filter being cached by Avisynth. It would make testing new cache designs very easy.

[Bidoche]

Originally posted by kassandro
Yes, I have avoided these mutex objects until now. Instead I [...]it's the concept I call a mutex, not the implementation details.
Your strategy, even if more lightweight, I would still call a mutex.

The advantage of avoiding mutex objects is that there is virtually no overhead (no system call) This sounds like premature optimization, which is said to be at the root of all evil :p
And I doubt the overhead is even comparable to the blit of a frame, for not mentioning filters who actually do something on the data.

I realised yesterday that with my AvsTimer Plugin I can easily monitor the Avisynth cache performance I aggre that monitoring Cache performance is a good idea (and I would like it built in 3.0 (with filter timing too probably)).
But, though i am not sure of it, I think may you have overlooked a detail in your current design :
You are monitoring the cache from the child of AVSTimer, but AVSTimer own Cache is higher in the chain and smooth the requests for it.


As for Cache hints, they are great as long as a filter as only one parent, but when there are more, juggling with many hints is (very) hard :(
That's why I want to get rid of them.

[kassandro]

Originally posted by Bidoche

You are monitoring the cache from the child of AVSTimer, but AVSTimer own Cache is higher in the chain and smooth the requests for it.

That is correct. I claim that the AvsTimer cache looks exactly like the cache of the child filter would look, if there would be no AvsTimer in between. It is important that AvsTimer completely disables the cache of the child filter. Consequently, a cache miss of AvsTimer corresponds to a cache miss of the child filter without AvsTimer. How do I measure cache misses of AvsTimer? On one hand AvsTimer counts the number of requests it receives. On the other hand, it knows the frame numbers of the requests. Let's look at an example. If AvsTimer is used with frames=1000, it outputs the frame number fcurrent of the last request after each 1000 requests. Let fprevious the frame number of the previous output line. Then the number of cache misses = 1000 - (fcurrent - fprevious). Of course, this is only correct, if neither the application on top of the script nor some filter in the middle requests frames randomly. I could handle even this situation, by registering the frame numbers of all requests in an array. If a frame is registered more than once, it is a cache miss. To be 100% correct, it would be necessary to allocate for each frame one byte, which is quite substantial (with bit arrays the memory overhead can be reduced by 87.5%, though). To demonstrate how AvsTimer measures cache misses, I loaded the follwoing script into vdub

MPEG2Source("input.d2v")
AvsTimer(frames=1000, name="mpeg2dec", type=2, total=false)
RemoveDirt()

then I pressed the preview button, until vdub reached frame 1330 (knowing how RemoveDirt works, frame 1331 was the last requested frame). Then I scrolled back with the <- key until frame 1211 (knowing how RemoveDirt works, frame 1210 was the last requested frame during the scroll back). Then I pressed the preview button again until vdub reached frame 3000. I got the following output

[1800] [999] mpeg2dec = 74 fps
[1800] [1807] mpeg2dec = 76 fps
[1800] [2807] mpeg2dec = 80 fps

Thus there were 1000 - (1807 - 999) = 192 cache misses. On the other hand the scroll range was 1331 - 1210 = 121. Back and forth these are 2*(121-2)=238 frames. Thus the Avisynth cache could catch 46 frames, probably 23 at each turning point. At first sight this result is surprising, because this version of RemoveDirt is configured with child->SetCacheHints(CACHE_RANGE, 2). But of course, the additional frames were already caught by the cache of RemoveDirt, which is configured with CACHE_ALL (I can't change that).


As for Cache hints, they are great as long as a filter as only one parent, but when there are more, juggling with many hints is (very) hard :(
That's why I want to get rid of them.
Currently Avisynth falls back to CACHE_ALL if there was more than one CACHE_RANGE request. The simplest solution would be to take one cache for each parent->child relation, but that would lead to unpleasant double caching in most cases. The optimal solution is to pass the parent, which issued the frame request, to the child cache by using an additional variable for GetFrame. Then the child cache should only release those frames, which are out of range and are from the same parent. More precisely, if the frame was requested by several parents, all the parents are attached to this frame in a chain and if it is out of range for one parent this parent is removed from the chain. The frame is released if the parent chain becomes empty. Once again the missing parent information is shown to be a design deficit of AVS 2.5x. It's always good that a child knows its parents. We could easily test all these cache ideas in the current environment, if GenericVideoFiler::SetCacheHints would really work. From that point of view, it would be better to release first a working version of AVS 3.0 with the old cache, with a functional GenericVideoFiler::SetCacheHints and hopefully also a GetFrame with an additional "parent" variable, in order to replace the old cache by a better one later. Such a change should not neccessitate a recompilation of the filters. I think it is not possible to get a working GenericVideoFiler::SetCacheHints for AVS 2.5x without the unacceptable recompilation of all filters.

[Bidoche]

Originally posted by kassandroTo be 100% correct, it would be necessary to allocate for each frame one byte, which is quite substantial (with bit arrays the memory overhead can be reduced by 87.5%, though).There is a dynamic_bitset class into boost which could reduce this overhead even more.
(It stores range of set bits, so as long as they are grouped, it's definitely better).


The optimal solution is to pass the parent, which issued the frame request, to the child cache by using an additional variable for GetFrame. This was my original idea as well.
I stuck to it for a long time, if you check the 3.0 files on sourceforge, you will see lots of filters still have this parent (client there) parameter, since it's only recently that I changed my mind about it.
I finally discarded it due to an overlooked difficulty :

I want 3.0 filters who don't need caching to truly not cache, not simply pass an hint to a cache object to make it scarse, but to truly have none.
That's why Cache are embedded into filters, so those who need one provide one and the others just do nothing.

But you don't have your own Cache, you have to forward hints you may receive to your childs.
And here comes the problem : you can always come up with non-caching hint-forwarding filters to mess up hints from above filters to childs...
One can receive multiple hints from the same filters or ...

That's when I thought of an adaptive cache logic instead. :)

[kassandro]

Originally posted by Bidoche
I want 3.0 filters who don't need caching to truly not cache, not simply pass an hint to a cache object to make it scarse, but to truly have none.

That causes a lot of troubles for a tiny performance gain, but if you want to get rid of the SetCacheHints function at any price, you have to do it.


But you don't have your own Cache, you have to forward hints you may receive to your childs.
This I do not understand at all. Why should I want to do that?


And here comes the problem : you can always come up with non-caching hint-forwarding filters to mess up hints from above filters to childs...

If there are only non-caching hints, I disable the cache, otherwise I ignore the non-caching hints, but, of course, the parents with non-caching hints will have h_radius=0. Thus for those parents the cache should be non-existent. It is important to note, that h_radius should depend on the parent.


One can receive multiple hints from the same filters or ...

The writer of the parent filter must be a fool to do that, but a reasonable SetCacheHints function should be able to cope with this situation.

[Bidoche]

Originally posted by kassandrobut if you want to get rid of the SetCacheHints function at any price I don't like hints too much, there are an architecture complexity who is exposed to the user (plugin writer that is), when the cache logic is an hidden implementation detail.
And the decision to include a cache or not is an easy one.

Why should I want to do that?Let's take the example of the Trim filter.
Trim obviously does not need to cache and can rely on its child for that.
I you have Trim discard hints it receives, they are just useless...
So the logic solution is to pass hints to its child.

If there are only non-caching hints, I disable the cacheThat way, you miss cache opportunities between the parents.
Hints only provide info about cache opportunities with oneself, not with the other parents.

The writer of the parent filter must be a fool to do that, You missed my point, I was talking about indirect repetition.
For example, you have the same clip twice (or more) in a Splice.
A parent of the Splice set hints, the Splice forwards to each child (only logic action).
Then the clip gets the same hint twice.

[kassandro]

Originally posted by Bidoche

And the decision to include a cache or not is an easy one.

But even without SetCacheHints you still have to decide, whether a filter like trim should get a cache or not, otherwise you would waste resources with any cache design. In general any filter, which simply passes through a frame should not get a cache. There should also be filter user option to disable the cache of a filter, such that he can concentrate the resources in a complicated script on the really costly filters.


You missed my point, I was talking about indirect repetition.
For example, you have the same clip twice (or more) in a Splice.
A parent of the Splice set hints, the Splice forwards to each child (only logic action).
Then the clip gets the same hint twice.
I think passing through cache hints to children doesn't really work, because the situation is not always as simple as with trim. What should one do if the filter has more than one child, or selects between more than one frame of the child filter? This is a weak point of the cache hints design.
I think the discussion is exhausted at the moment. I should, of course, get familiar with templates. I usually approach a new concept, by checking, whether the concept is efficient or not. C++ should not contain any inefficient concepts in the first place, but this is simply not true. virtual base classes are such an inefficient concept, which should never have become part of C++. The data elements of a virtual base case can only accessed through a pointer from a derived class. Now if the derived class is again a virtual base class, the data access gets more and more complicated. Furthermore all the inefficiency is invisible to the program developer. I hope that the situation is better with templates. If templates are real runtime objects and not only objects, which have to be made concrete at compile time, then I'm afraid, that one has to pay a price.

[Bidoche]

Originally posted by kassandro
There should also be filter user option to disable the cache of a filter, such that he can concentrate the resources in a complicated script on the really costly filters.I think that necessary too, but rather without user involvement.
It's here my Drop method comes into play :
The env calls it on Caches so they shrink their size.
but in a perfect world, it would do so as slow filters are tends to be allowed to cache more.
That's where your timing code, directly built in the Caches, so the env can call Drop in an appropriate order, could help.


virtual base classes are such an inefficient concept, which should never have become part of C++. The data elements of a virtual base case can only accessed through a pointer from a derived class.Virtual bases classes and data members don't go well together.
But as long as you just use them as interfaces a la Java (ie no data members) they are good.

If templates are real runtime objects and not only objects, which have to be made concrete at compile time, then I'm afraid, that one has to pay a priceI don't get your distinction real runtime object/object...