[Performance] Virtual memory addresses reusage in a filter chain frame buffers

[DTL2020]

As was answered at
https://stackoverflow.com/questions/79633556/
https://stackoverflow.com/questions/34038241/
and hinted at https://stackoverflow.com/questions/31023260 :

1. There is no yet valid (easy) way to invalidate cache lines from user mode (also it can cause significant system performance drop or even non-stability if used with any errors).

2. The only legal way to decrease lots of useless store traffic on a host slow RAM bus is to reuse the same virtual addresses (mapped to the same cache lines). And decrease time of CPU stall on store operations waiting for some free lines in cache for download already read and no more useful data to host RAM. Because the CPU can not overwrite dirty cache lines and data production rate from CPU core with SIMD is much larger in comparison with the download speed from caches to RAM. So when free to use cache lines are exhausted store operations finally stall and no optimization of the processing function can help to performance.

3. It is really some sad fact that in 202x years and 64 bit addressing of 'flat' memory model - for high-performance computing we really have only very small (sum of) used virtual address space available of the total size about CPU cache size only (except Xeon with integrated HBM RAM onboard). If actively used total virtual address space is significantly larger - the program will get significant performance impact from slow RAM bus performance. And in some use cases it is even busy with completely useless store traffic as in the example of the chained AVS filters when each filter can produce store traffic into a separated virtual address buffer (with current AVS frame cache design ?).

Some hints provided at stackoverflow answer to make programming solutions somehow easier (in comparison with making its own virtual memory manager in AVS core):
 On free() TCMalloc just puts a freed block of memory in its cache. And this block of memory will be returned by malloc() when an application asks for a block of memory next time. That is the essence of a caching alliocator like TCMalloc.

But it looks unfortunately the memory library TCMalloc is only for Linux platform and no Windows support. So it is subject to research if we have the same functions in other possible malloc/free C API implementations provided for Windows compilers (MSVC ?, clang ? intel C ?).

Possible solution to test with AVS chained filters:
Source_filter(output_buff1)
Process1_filter(ouput_buff2)
Process2_filter(output_buff3)
...
ProcessN_filter(output_buffN)

If all buffers are pre-allocated and always allocated in common virtual address space - this causes sequential data re-writing from buff1 via buff2 to buffN and total virtual address space used buff1+buff2+..+buffN. This may be much larger than the largest CPU cache and each frame motion from buff1 to buffN will cause each filter interconnection data downloading from cache to host RAM. But a pair of enough for even 2 buffers processing buff1+buff2 may fit in CPU caches.
So if we make dynamically allocated pairs (or even single buffer for transform in place filters in best case) of buffers only required in currently active (data processing filter) we may got some performance benefit. But the used malloc/free library must be common for all used filters in a chain and provide as possible the same virtual address range (same as we have in TCMalloc library) for each new allocation. This expects to make filter design more simple in comparison with sharing the same lowest possible pair of buffers in virtual address space between all filters in a chain.

The next step in data-locality optimization is making (at least core) filters able to process only some limited in size part of a frame and send it via all chained sequence of filters (if all/some sequential filters support such frame partitioning). For filters without spatial processing it is typically possible (like Levels/ColorYUV/Tweak and some others). Also with data sent in between filters via a small (about 1/2 of CPU cache or lower) sized buffer (freed and allocated again for the next pair of filters to run).

Short description of the issue:

1. Small enough temporal writes from the CPU core can be cached (about 1/2 of total CPU caches size or less) at least at full cache write speed and not cause too long CPU stall.
2. Written data to the cache can not be discarded (from downloading to host RAM) by software instruction from user mode after it was totally read and no more required for next processing.
3. Too much writes to different virtual addresses (several temporal buffers in a sequence) will cause free cachelines exhausting and final CPU stall after write buffers are full and wait for the cached data download to host RAM.
4. The only way to save from useless writes to host RAM of the short-live temporal data (from internals of filters and immediate data in between filters in a chain) is constant reusing of the same virtual addresses for store buffers. It is the task for both AVS+ core memory management design and filters design.

[pinterf]

In Avisynth there is env->Allocate and env->Free. Buffer pools, avoiding frequent reallocation.
https://avisynthplus.readthedocs.io/en/latest/avisynthdoc/FilterSDK/Cplusplus_api.html#allocate-v8

As I can see, there is not very much info on this in our documentation. It's rather minimalistic what I wrote when I put it into the standard interface from IScriptEnvironment2 in v8. Avisynth core is using Allocate/Free in some places.

Primary goal of IScriptEnvironment Allocate/Free was to have the Avisynth-reserved memory counter up-to-date and to take into account this memory area as well. Thus when reaching the MemoryMax limit the core would free up memory from this resource as well (along with frame registry and cache entries).

[DTL2020]

I going to see in debugger if it possible to shrink used RAM for inbetween filters cache to minimum possible setting
Prefetch(N,1) or even Prefetch(N,0) (starting from Prefetch(1,1). When I test resizers performance I got significantly different results if adjusting prefetch-frames from 1 and larger.

In the DeviceManager I see the memory for frame buffers are allocated by simple C++ call to new operator and its implementation is completely dependent on the C++ library used by compiler ?

AviSynthPlus/avs_core/core/DeviceManager.cpp

Line 180 in c506611

return new BYTE[size + 16];

Not yet track where go env->Allocate call.

[DTL2020]

The simplest chained example of internal core filters we have in example of H+V Resize() macro (sequence) filter.

It is a chained sequence of H followed by V or V followed by H resize filters. And they use (allocate) temporal frame as a buffer for immediate 1D resize:

AviSynthPlus/avs_core/filters/resample.cpp

Line 1437 in c506611

PVideoFrame dst = env->NewVideoFrameP(vi, &src);

and

AviSynthPlus/avs_core/filters/resample.cpp

Line 1673 in c506611

PVideoFrame dst = env->NewVideoFrameP(vi, &src);

The last resizer output frame is required to read by next filter. But intermediate frame buffer allocated by first resizer of 2 in a sequence must be freed as fast as possible after the last resizer in a sequence read all data from it. So CPU via good allocation library can get that virtual addresses back to use for destination write of some next processing filter. Is this happen in current AVS+ core design ? If deallocation is delayed - the temporal no more needed data keep space in the CPU cache and must be uselessly pushed to main host RAM via slow bus transfer if CPU need to do next writes to different virtual addresses (while processing next filter after Resize()).

Other possible solution - the used temporal frame virtual address must be returned to AVS+ memory manager and presented to next filter in a chain as destination write buffer. So CPU will have right to overwrite it in the cache without pushing old temporal data into RAM.

[DTL2020]

This commit DTL2020@810f91b shows new FilteredResize_2p class example with single temporal buffer for all 3..4 planes processing. Not very nicely created with lots of copying from old classes but it working for testing.

With some lucky frame sizes and scale ratio like 320x320 YUVPS frame scaled 2x it shows about 2x more performance at i5-9600K CPU with script

BlankClip(1000000, 320,320, pixel_type="YUV444PS")
mul=2
LanczosResize(width*mul, height*mul, taps=2, force=3)
Prefetch(6)

Larger output frame sizes are lower in performance boost.
AVSmeter shows some smaller process memory usage (several MBs). New class controlled by force=3 for testing now. force=0 is old 2 sequential resize classes calls.

With large frame size output current most performance boost visble at float32 4:4:4 format with script

BlankClip(1000000, 320,320, pixel_type="YUV444PS")
mul=10
LanczosResize(width*mul, height*mul, taps=2, force=3)
Prefetch(8)

at 8-cores Xeon (and 6 RAM channels) - about 375 fps with force=3 and 293fps with force=0.

[DTL2020]

I make trace in the debugger where env->Allocate() requests go - they go to some small memory manager inside AVS+ core and it is useful to get same virtual addresses for the next allocations (in the same processing function may be or in the possible next filters in a chain if frame buffers size is much smaller in comparison with CPU cache size). But it not solve the issue completely: The downstream filter gets frams from main AVS video frames allocation pool with env->NewVideoFrame() and this pool of virtual addresses is NOT intersected with the pool allocated from OS for the supplementary env->Allocate()/Free() memory manager. This create still present issue - after the last read from env->Allocted() temporal buffer and its freeing at the end of Resize->GetFrame - the memory left locked from writing by the downstream filter and still cause useless download from cache traffic (though somehow smaller in comparison with initial AVS state in 3.7.5).

The possible expected best solution: filter manager of AVS+ need to analyse (if posslble ? for last to first filters in a chain it is backward possible always ?) the format of the VideoFrame requested for writing and present this exact format and enough size to the previous (resize) filter for the allocation as temporal frame/buffer. So we need to make new method of ScriptEnvironment like:
env->GetDownstreamFilterOutputFrameFormat(&vi_downstream_output)
and request same (or larger) sized buffer with
PVideoFrame tmp = env->NewVideoFrameP(vi_downstream_output, &src); at
https://github.com/DTL2020/AviSynthPlus/blob/482eb5288013512189bc19d100a5a88bfe55f937/avs_core/filters/resample.cpp#L2363

Though the requesting frame buffer address by env->NewVideoFrameP() call may have longer processing time in comparison with env->Allocate() the performance benefit of cached addresses reusage and saving from useless download traffic to host RAM is subject to be analysed (it may also depend on used temporal buffer size vs CPU caches size).

So currently we have memory management design issue in AVS+ core:
2 memory management engines grabbing 2 different pools of virtual addresses from OS allocation services (inside AVS+ environment) and no internal exchange of the grabbed virtual address ranges in between these engines exist. And the usage of these memory addresses is mixed in time as filters process data and as data exchanged between filters (via frames cache).

The task for performance optimization: Minimize the total pool of used virtual addresses at the filters processing running and re-use the freed temporal memory addresses range after all required data read as fast as possible for next write operation (destination of next filter or temporal buffer of next filter in order of processing).

[pinterf]

env->NewVideoFrame() usually does not allocate a new memory area, it just reuses existing - already allocated - frame buffer memory area. Frame buffers are not freed up entirely. Depending the requested size, AviSynth returns an existing pointer to a memory area of which size fits the requested byte count.

[pinterf]

I believe this highly optimized approach is only valid for short, linear, and non-multithreaded scenarios. As soon as the filter chain becomes even slightly more complex than this artificial test script, or if a single clip has multiple consumers, it invalidates all our assumptions about how the sequence of filters consumes each other's output and how the processor cache behaves.

[pinterf]

at 8-cores Xeon (and 6 RAM channels) - about 375 fps with force=3 and 293fps with force=0.

This is very significant boost (not like 10%), so it's a good approach which deserves adopting. In general, if we experience only minor let's say 10-20% boost by having a 300% more complex and unmaintainable overspecialized code, then it's a no go. Starting from 25% boost it's worth to do an easy conversion, I thik your two-in-one 2d version is even not more complex than the original one.

[pylorak]

In Avisynth there is env->Allocate and env->Free. Buffer pools, avoiding frequent reallocation. https://avisynthplus.readthedocs.io/en/latest/avisynthdoc/FilterSDK/Cplusplus_api.html#allocate-v8

Original implementer here :)

As I can see, there is not very much info on this in our documentation. It's rather minimalistic what I wrote when I put it into the standard interface from IScriptEnvironment2 in v8. Avisynth core is using Allocate/Free in some places.

Primary goal of IScriptEnvironment Allocate/Free was to have the Avisynth-reserved memory counter up-to-date and to take into account this memory area as well. Thus when reaching the MemoryMax limit the core would free up memory from this resource as well (along with frame registry and cache entries).

That's the primary goal of the AVS_NORMAL_ALLOC, but AVS_POOLED_ALLOC has (or had) a lot more important benefit. Pooled allocations are meant for filters that don't need the buffers between frames and can free them between calls to GetFrame(). Then multiple filters can use the same buffers instead of each filter unnecessarily clinging onto them even while a different filter is executing. This resulted in tons of memory savings, which was really useful, as most of the complex scripts on HD material used to be memory-bound in that era, and pooling was a lot faster than doing actual malloc/free. The main reason env->Allocate and env->Free were created at all was to support these pooled allocations and memory re-use between filters without the overhead of malloc. Add AVS_NORMAL_ALLOC was just a bonus.
The memory savings might not be that important today since PCs now have a lot more RAM, but the savings are still there.

[pinterf]

Hi, good old friend :). I put your comment into the rst docs, thanks for the clarification.

[DTL2020]

But now we have 2 different intermediate allocated memory managers (caches) in the AVS core and they do not share the same pool of allocated (used or returned) buffers.
This causes performance impact when filters use both allocators in ordered sequence - the returned to the env->Free() buffer can not be used for writing by the next filter in a chain if it writes to only vfb (env->NewVideoFrame()). This causes performance impact if the CPU must evict these dirty cache lines via slow bus to RAM to free some cache for next read or write allocations.

The possibly best solution we will have is if CPU manufacturers will add new load instructions (to AVX512 or AVX_X(10 or 11 or any new number). Something like
_mX_load(u)_inv(addr).
This will load (m8 to m512 or larger) from the cache line and invalidate the cache line. It must be the last load operation from that cache line. If the programmer knows what to do (last read of temporal data from memory block) - it will free cache line for any other useful operation by cache control firmware without performance penalty of downloading this cache line to host RAM. If it was an error - nothing too bad happens but the next read from this addr will cause a performance penalty for reloading this cache line from RAM. So it is good to send Note to intel and AMD developers with requests to add new instructions in the instructions set (x86/64 architecture). Are intel/AMD developers present at github to send links to the issue ?

For current AVS core design: Can we somehow share the allocated pool of virtual addresses blocks between 2 present cache engines ? So that env->Allocate() can return applicable memory blocks from vfb pool (having refcount=0 ?) and env->NewVideoFrame() can return unused blocks returned to core by env->Free().
This expects to add some performance to existing scripts and plugins without redesign and/or API changes.
Also for best performance the cache engines must present the most recently returned (MRR) block (first MRR applicable for the request).
Also the caches may be good to save from re-allocation performance penalty from underlying API but can add performance penalty on search inside cache. For complex scripts it may be visible when many frames are allocated. This is also subject to check and may be added some hints for faster search in comparison with simple all entries sequential check or in some order of addition to the list.