PLUGIN funccache
lang: "C++"
version: "1.0"
date: "2024-10-27"
author: "Julien BRUGUIER"
maintainer: "Julien BRUGUIER <projet.svm@pappy.tf>"
synopsis: "Function call cache optimization"
description:
%{
This plugin implements a function call cache to optimize code on deterministic functions.
.P
The cache is available in two flavours: Either unlimited or limited to a certain number of entries when the option funccache.limit is set.
.P
When the limit is set, the eviction policy is an hybrid between the "Oldest" call and the "Less used" call: Among all the cache entries,
.IP
1) The funccache.policy option% (70% per default) oldest entries are selected,
.IP
2) Among the selected, the least used are selected,
.IP
3) Among the remaining ones, the oldest is selected.
.P
The cache is populated when a cached function call returns.
.I To ensure a correct cache population, the cached function shall be deterministic and ensure only input and output parameters are kept in the P pointer.
All input parameters should be left untouched by the function.
Also, all local variables within the P pointer shall be cleared, or more cache misses will occurs, leading to less performance.
.P
The cache is ordered by the function symbol and its parameters.
A total order is required on each parameter type to have a function eligible to call caching.
By default, only strong order is accepted, but the option funccache.weak allows weak ordering as well.
%}

example: "Fibonacci"
%{
.nf
#!/usr/bin/env svm
LOG
PLUGIN "===PLUGINLIB===" -l 3
PLUGIN "svmint.so"
PLUGIN "svmcom.so"
ARGUMENT INT nb
PROCESS "fib"
	CODE "main" INLINE
		:memory (PTR, INT, INT)/p
		[ , @&nb , ] -> p
		:funccache.call "fib" p
		:com.message @(p/2)
		:shutdown
	:label fib
		:goto fib_rec :unless @(P/1) IN &0*2
		@(P/1) -> (P/2)
		:return
	:label fib_rec
		:memory (PTR, INT, INT)*2 -> &P
		:int.sub @(P/1) 1 -> (@&P/1)
		:funccache.call "fib" &@&P*3
		:int.sub @(P/1) 2 -> (@&P/4)
		:funccache.call "fib" (@&P/3)*3
		:int.add @(@&P/2) @(@&P/5) -> (P/2)
		# This instruction is crucial for the cache population:
		# Local variables shall never be part of the cache.
		[ ] -> &P*1
		:return
	END
	MEMORY nb
END
.fi
%}

test: "limitless"
%{
PLUGIN "svmint.so"
PROCESS "test"
	CODE "main" INLINE
		:memory (PTR, INT, INT)/p
		[ , 20 , ] -> p
		:funccache.call "fib" p
		:funccache.print
		:shutdown 0 :when (&0+@(p/2)) IN &6765*1
		:shutdown 1
	:label fib
		:goto fib_rec :unless @(P/1) IN &0*2
		@(P/1) -> (P/2)
		:return
	:label fib_rec
		:memory (PTR, INT, INT)*2 -> &P
		:int.sub @(P/1) 1 -> (@&P/1)
		:funccache.call "fib" &@&P*3
		:int.sub @(P/1) 2 -> (@&P/4)
		:funccache.call "fib" (@&P/3)*3
		:int.add @(@&P/2) @(@&P/5) -> (P/2)
		[ ] -> &P*1
		:return
	END
END
%}

test: "limit"
%{
-l 3
%}
%{
PLUGIN "svmint.so"
PROCESS "test"
	CODE "main" INLINE
		:memory (PTR, INT, INT)/p
		[ , 20 , ] -> p
		:funccache.call "fib" p
		:funccache.print
		:shutdown 0 :when (&0+@(p/2)) IN &6765*1
		:shutdown 1
	:label fib
		:goto fib_rec :unless @(P/1) IN &0*2
		@(P/1) -> (P/2)
		:return
	:label fib_rec
		:memory (PTR, INT, INT)*2 -> &P
		:int.sub @(P/1) 1 -> (@&P/1)
		:funccache.call "fib" &@&P*3
		:int.sub @(P/1) 2 -> (@&P/4)
		:funccache.call "fib" (@&P/3)*3
		:int.add @(@&P/2) @(@&P/5) -> (P/2)
		[ ] -> &P*1
		:return
	END
END
%}

includes:
%{
#include <vector>
#include <memory>
#include <atomic>
%}

code:
%{
static size_t limit = 0;
static SVM_Boolean weak = FALSE;
static size_t policy = 0;

struct CachedCall
{
	explicit CachedCall(const SVM_Value_Symbol function)
	:_function(function)
	{
	}

	void add(const SVM_Value param)
	{
		_parameters.push_back(param);
	}
	void add()
	{
		_parameters.push_back(nullptr);
	}
	void print(const void *svm, std::ostream& os) const
	{
		SVM_String s = ::svm_value_print(svm,_function);
		os << RAW_STRING(s) << " [";
		for(const auto&p: _parameters)
		{
			os << " ";
			if(not p)
			{
				os << "(void)";
			}
			else
			{
				s = ::svm_value_print(svm,p);
				os << RAW_STRING(s);
			}
		}
		os << " ] Usage=" << _usage << " Order=" << _order;

	}

	SVM_Value_Symbol _function;
	std::vector<SVM_Value> _parameters;
	size_t _usage = 0;
	size_t _order = 0;
};

struct Cache
{
	Cache()
	:_read(0), _found(0), _missed(0), _store(0), _eviction(0) {}
	std::pair<bool,size_t> find(const void *svm, const CachedCall& c) const
	{
		size_t start = 0;
		size_t end = _cache.size();
		for( ; ; )
		{
			if(start>=end)
			{
				return std::make_pair(false,start);
			}
			size_t pivot = (start+end)/2;
			SVM_Value_Plugin_Comparison comparison = Cache::compare(svm,c,*_cache[pivot]);
			switch(comparison)
			{
				case ORDER_EQUAL:
					return std::make_pair(true,pivot);
					break;
				case ORDER_INFERIOR:
					end = pivot;
					break;
				case ORDER_SUPERIOR:
					start = pivot+1;
					break;
			}
		}
	}

	void insert(const void *svm, const std::shared_ptr<CachedCall>& c)
	{
		auto it = find(svm,*c);
		if(it.first) return;
		_cache.insert(_cache.begin()+it.second,c);
	}

	size_t remove()
	{
		if(_cache.empty()) return 0;
		auto remove = _cache.begin();
		auto threashold = (policy*_cache.size())/100;
		if(threashold==0) threashold=1;
		for(auto it=_cache.begin() ; it!=_cache.end() ; ++it)
		{
			if((*it)->_order>threashold) continue;
			if((*remove)->_usage<(*it)->_usage) continue;
			if((*remove)->_order<(*it)->_order) continue;
			remove=it;
		}
		auto order = (*remove)->_order;
		_cache.erase(remove);
		++_eviction;
		return order;
	}

	void update_found(CachedCall& found)
	{
		++found._usage;
		update_order(found._order);
		found._order = _cache.size();
	}

	void update_insert(CachedCall& insert)
	{
		insert._usage = 1;
		insert._order = _cache.size();
	}

	void update_order(const size_t order)
	{
		for(auto& c: _cache)
		{
			if(c->_order>order)
			{
				--c->_order;
			}
		}
	}

	void clean(const void *svm)
	{
		for(const auto& c: _cache)
		{
			VARIABLE_LOCAL(c->_function);
			for(const auto& v: c->_parameters)
			{
				if(v)
				{
					VARIABLE_LOCAL(v);
				}
			}
		}
	}
	void print(const void *svm, std::ostream& os) const
	{
		os << "Function call cache [size=" << _cache.size() << ", read=" << _read << ", found=" << _found << ", missed=" << _missed << ", written=" << _store << ", evicted=" << _eviction << "]:" << std::endl;
		for(const auto& c:_cache)
		{
			os << "   ";
			c->print(svm,os);
			os << std::endl;
		}
	}
	std::vector<std::shared_ptr<CachedCall> > _cache;
	SVM_Lock _lock;
	std::atomic_size_t _read;
	std::atomic_size_t _found;
	std::atomic_size_t _missed;
	std::atomic_size_t _store;
	std::atomic_size_t _eviction;

	private:
		static SVM_Value_Plugin_Comparison compare(const void *svm, const CachedCall& r, const CachedCall& p)
		{
			SVM_Comparison_Result sc = ::svm_value_compare(svm,r._function,p._function);
			if(sc.inferior) { return ORDER_INFERIOR; }
			if(sc.superior) { return ORDER_SUPERIOR; }
			if(r._parameters.size()<p._parameters.size()) { return ORDER_INFERIOR; }
			if(r._parameters.size()>p._parameters.size()) { return ORDER_SUPERIOR; }
			for(auto fp=r._parameters.begin(),pp=p._parameters.begin() ; fp!=r._parameters.end() ; ++fp,++pp)
			{
				if(not *fp) continue; // ignore non initialised values in call
				if(not *pp) { return ORDER_SUPERIOR; }
				SVM_Comparison_Result c = ::svm_value_compare(svm,*fp,*pp);
				if(not (c.order and c.total))
				{
					ERROR_INTERNAL(FAILURE,"Values can not be compared with a total order");
				}
				if(not weak and c.weak)
				{
					ERROR_INTERNAL(FAILURE,"Refuse to use weak comparison between values");
				}
				if(c.inferior) { return ORDER_INFERIOR; }
				if(c.superior) { return ORDER_SUPERIOR; }
			}
			return ORDER_EQUAL;
		}
};

static Cache cache;

%}

initialisation:
%{
	cache._lock = ::svm_lock_new(svm);
	auto l = ::svm_plugin_get_option(svm,CONST_PEP(funccache,limit));
	if(not ::svm_value_state_is_null(svm,l))
	{
		limit = ::svm_value_integer_get(svm,l);
	}
	weak = ::svm_value_boolean_get(svm,::svm_plugin_get_option(svm,CONST_PEP(funccache,weak)));
	policy = 70;
	auto p = ::svm_plugin_get_option(svm,CONST_PEP(funccache,policy));
	if(not ::svm_value_state_is_null(svm,p))
	{
		auto rp = ::svm_value_integer_get(svm,p);
		if(rp<0) rp=0;
		if(rp>100) rp=100;
		policy = rp;
	}
%}

finalisation:
%{
	cache.clean(svm);
	VARIABLE_DELETE(cache._lock);
%}

DEFINE

OPTION funccache.weak -w BLN
help:
%{
This option allows weak total ordering of parameters in the cache.
%}

OPTION funccache.limit -l INT
help:
%{
This option enables cache entries limitation.
%}

OPTION funccache.policy -p INT
help:
%{
This option sets the eviction policy when the cache limit is set and the size of the cache reached the limit.
%}

WAITING INSTRUCTION funccache.call [ STR SYM ] PTR
%{
	SVM_Value function = ::svm_parameter_value_get(svm,argv[0]);
	if(::svm_value_type_is_string(svm,function))
	{
		SVM_Code code = ::svm_processor_get_currentcode(svm,CURRENT(kernel));
		SVM_Address address = ::svm_code_label_get_address(svm,code,function);
		function = ::svm_value_symbol_new(svm,code,address);
	}
	CachedCall trial(function);
	SVM_Value_Pointer params = ::svm_parameter_value_get(svm,argv[1]);
	SVM_Address address = ::svm_value_pointer_get_address(svm,params);
	SVM_Size size = ::svm_value_pointer_get_size(svm,params);
	for(SVM_Address i=address ; i<(address+size) ; ++i)
	{
		if(::svm_memory_address_is_initialised(svm,CURRENT(kernel),i))
		{
			trial.add(::svm_memory_read_address(svm,CURRENT(kernel),i));
		}
		else
		{
			trial.add();
		}
	}
	SVM_LockGuard_Read guard = ::svm_lock_readguard_new(svm,cache._lock,TRUE);
	auto found = cache.find(svm,trial);
	++cache._read;
	if(found.first)
	{
		++cache._found;
		CachedCall& c = *(cache._cache[found.second]);
		cache.update_found(c);
		auto it = c._parameters.begin();
		for(SVM_Address i=address ; i<(address+size) ; ++i,++it)
		{
			if(static_cast<bool>(*it) and not ::svm_memory_address_is_initialised(svm,CURRENT(kernel),i))
			{
				SVM_Value v = ::svm_value_copy(svm,*it);
				::svm_value_state_set_movable(svm,v);
				::svm_memory_write_address(svm,CURRENT(kernel),i,v);
			}
		}
		RETURN;
	}
	++cache._missed;
	SVM_Value_Symbol current = ::svm_processor_get_currentinstruction(svm,CURRENT(kernel));
	::svm_processor_jump_global(svm,CURRENT(kernel),current);
	SVM_Parameter *p = ::svm_parameter_array_new(svm,2);
	p[0] = ::svm_parameter_value_new(svm,function);
	p[1] = argv[1];
	::svm_processor_instructionoverride_set_global(svm,CURRENT(kernel),current,CONST_PEP(funccache,store),2,p,LOCAL);
	::svm_processor_call_global(svm,CURRENT(kernel),function,params);
%}
help:
%{
This instruction performs a cached call to the function with its parameters.
.P
The instruction first searchs whether the function call is already in cache.
During this process, each non-initialised address in the function parameters is ignored to check the cache entries conformity.
.P
If a cache entry matches the function call, all parameters are filled with cache entry parameters.
Otherwise, the function call is performed after setting a callback on function return to store the function call result.
.P
.I
The function shall ensure to clean all local values in the function parameters before returning to avoid cache polution.
%}

OVERRIDE WAITING INSTRUCTION funccache.store SYM PTR
%{
	SVM_Value_Symbol function = ::svm_parameter_value_get(svm,argv[0]);
	VARIABLE_GLOBAL(function);
	SVM_Value_Pointer params = ::svm_parameter_value_get(svm,argv[1]);
	auto value = std::make_shared<CachedCall>(function);
	SVM_Address address = ::svm_value_pointer_get_address(svm,params);
	SVM_Size size = ::svm_value_pointer_get_size(svm,params);
	for(SVM_Address i=address ; i<(address+size) ; ++i)
	{
		if(::svm_memory_address_is_initialised(svm,CURRENT(kernel),i))
		{
			SVM_Value v = ::svm_memory_read_address(svm,CURRENT(kernel),i);
			v = ::svm_value_copy(svm,v);
			VARIABLE_GLOBAL(v);
			value->add(v);
		}
		else
		{
			value->add();
		}
	}
	SVM_LockGuard_Write guard = ::svm_lock_writeguard_new(svm,cache._lock,TRUE);
	if((limit>0) and (cache._cache.size()>=limit))
	{
		cache.update_order(cache.remove());
	}
	cache.insert(svm,value);
	cache.update_insert(*value);
	++cache._store;
	SVM_Value_Symbol current = ::svm_processor_get_currentinstruction(svm,CURRENT(kernel));
	::svm_processor_instructionoverride_reset_global(svm,CURRENT(kernel),current,LOCAL);
%}
help:
%{
This instruction stores in the cache the function name and the parameters after the call.
The instruction also perform the cache eviction if the cache reaches its limit.
%}

WAITING INSTRUCTION funccache.statistics MUTABLE INT 6
%{
	SVM_Value_Integer c = ::svm_parameter_value_get(svm,argv[0]);
	SVM_Value_Integer r = ::svm_parameter_value_get(svm,argv[1]);
	SVM_Value_Integer f = ::svm_parameter_value_get(svm,argv[2]);
	SVM_Value_Integer m = ::svm_parameter_value_get(svm,argv[3]);
	SVM_Value_Integer s = ::svm_parameter_value_get(svm,argv[4]);
	SVM_Value_Integer e = ::svm_parameter_value_get(svm,argv[5]);
	SVM_LockGuard_Read guard = ::svm_lock_readguard_new(svm,cache._lock,TRUE);
	::svm_value_integer_set(svm,c,cache._cache.size());
	::svm_value_integer_set(svm,r,cache._read);
	::svm_value_integer_set(svm,e,cache._found);
	::svm_value_integer_set(svm,m,cache._missed);
	::svm_value_integer_set(svm,s,cache._store);
	::svm_value_integer_set(svm,e,cache._eviction);
%}
help:
%{
This instruction returns some statistics about the cache.
.IP
The first integer is the cache size.
.IP
The second integer is the number of cache reads.
.IP
The third integer is the number of cache hits.
.IP
The fourth integer is the number of cache misses (when the call has to be performed).
.IP
The fifth integer is the number of cache writes.
.IP
The sixth integer is the number of cache evictions.
%}

SYSTEM INSTRUCTION funccache.print
%{
	std::ostringstream oss;
	cache.print(svm,oss);
	::svm_machine_trace__string(svm,NEW_STRING(oss.str()));
%}
help:
%{
This instruction prints on a trace the cache content, mainly for debugging purpose.
%}