cuflow/cache.h: Function Call Cache (unfinished)

Data Structures

struct  cuflowP_cachebin
struct  cuflow_cache
struct  cuflowP_cacheobjhdr
struct  cuflow_cacheobj


#define CUFLOW_FNCODE(index, key_wsize)   (((index) << 16) + (key_wsize))
#define CUFLOW_FNCODE_KEY_SIZEW(code)   ((code) & 0xffff)
#define CUFLOW_FNCODE_SLOT(code)   ((code) >> 16)
#define CUFLOWP_CACHEOBJ_HDR(obj)   ((cuflowP_cacheobjhdr_t)(obj) - 1)
#define cuflow_cached_edcl(NAME, key_struct, value_struct)
#define cuflow_cached_fncode(NAME)   CUFLOW_FNCODE(NAME##_index, sizeof(NAME##_key_t)/sizeof(cu_word_t));
#define cuflow_cached_edef(NAME)   NAME##_obj_t *NAME##_fn(NAME##_key_t *key)
#define cuflow_cached_new(NAME, extra_size)


typedef struct cuflowP_cachebincuflowP_cachebin_t
typedef struct cuflow_cachecuflow_cache_t
typedef struct
typedef struct cuflow_cacheobjcuflow_cacheobj_t


void cuflow_cache_init (cuflow_cache_t cache, cuflow_cacheconf_t conf, cuflow_cacheobj_t(**fn_arr)(cuflow_cacheobj_t key))
void cuflow_cache_deinit (cuflow_cache_t cache)
cuflow_cacheobj_t cuflow_cacheobj_alloc (size_t full_size, cuflow_cacheobj_t key)
void cuflow_cacheobj_set_gain (cuflow_cacheobj_t obj, float gain)
cuflow_cacheobj_t cuflow_cache_call (cuflow_cache_t cache, cu_word_t fncode, cuflow_cacheobj_t key)

Define Documentation

#define cuflow_cached_edcl ( NAME,
value_struct   ) 
struct NAME##_key                                                       \
    {                                                                   \
        cu_inherit (cuflow_cacheobj);                                   \
        cuPP_splice key_struct                                          \
    };                                                                  \
    struct NAME##_obj                                                   \
    {                                                                   \
        struct NAME##_key key;                                          \
        cuPP_splice value_struct                                        \
    };                                                                  \
    typedef struct NAME##_key NAME##_key_t;                             \
    typedef struct NAME##_obj NAME##_obj_t

Template macro for creating the type definitions of a cached function, suited for use with the cuflow_cachetab command. NAME is the function name to be passed as the first argument of the CACHENAME_call macro that is generated by cuflow_cachetab -p CACHENAME ....

#define cuflow_cached_edef ( NAME   )     NAME##_obj_t *NAME##_fn(NAME##_key_t *key)

This is the template for the prototype of the definition of the NAME cached function. This should be followed by a function body surrounded by { }, which receives a parameter key. The function body shall return an object allocated with cuflow_cached_new and tagged with cuflow_cacheobj_set_gain. A previous cuflow_cached_edcl must be issued.

#define cuflow_cached_fncode ( NAME   )     CUFLOW_FNCODE(NAME##_index, sizeof(NAME##_key_t)/sizeof(cu_word_t));

When cache header generated by cuflow_cachetab is included, this gives the function index of NAME.

#define cuflow_cached_new ( NAME,
extra_size   ) 
((NAME##_obj_t *)                                                       \
     cuflow_cacheobj_alloc(sizeof(struct NAME##_obj) + (extra_size),    \

Allocate an object suitable for returning from the cache function with name NAME. The returned value is a struct containing the members declared in the value_struct parameter of the corresponding cuflow_cached_edcl. If extra_size is not 0, this number of extra bytes will be allocated after the value_struct fields.

#define CUFLOW_FNCODE ( index,
key_wsize   )     (((index) << 16) + (key_wsize))

Returns a function code identifying slot number index in a cache which takes a key of key_wsize words size.

#define CUFLOW_FNCODE_KEY_SIZEW ( code   )     ((code) & 0xffff)

The key size in words of code.

Function Documentation

cuflow_cacheobj_t cuflow_cache_call ( cuflow_cache_t  cache,
cu_word_t  fncode,
cuflow_cacheobj_t  key 

Return the computed object with key-part equal to key. key may be a stack object or static storage. The callback and key size is determined from fncode. The callback is only called if cache does not already contain the requested object.

void cuflow_cache_deinit ( cuflow_cache_t  cache  ) 

Unlink cache from it's configuration.

void cuflow_cache_init ( cuflow_cache_t  cache,
cuflow_cacheconf_t  conf,
cuflow_cacheobj_t(**)(cuflow_cacheobj_t key)  fn_arr 

Creates a cache with a unique set of callbacks stored in fn_arr. Normally a cache is called at program initialisation and kept for the lifetime of the program, but if you want to despose of a cache, call cuflow_cache_deinit, since cache will be linked into conf.

cuflow_cacheobj_t cuflow_cacheobj_alloc ( size_t  full_size,
cuflow_cacheobj_t  key 

Return a pointer into the data area of a newly allocated cache object. The cache callbacks must use this to allocate objects and must call cuflow_cacheobj_set_gain before returning them.

void cuflow_cacheobj_set_gain ( cuflow_cacheobj_t  obj,
float  gain 

Set the gain of obj to gain. The gain is an estimate of C/S where C is the cost of computing the retured object in CPU cycles, and S is the size of the returned object in bytes including a fixed overhead of about 5 words. The C may include cost of using other resources multiplied with suitable constants to make them cycle-equivanent according to the desired resource utilization.

These quastities are hard to determine precisely. Available CPU clocks are typically not precise enough to measure C, and computing S may be expensive for tree-structures or even ambiguous when sharing is involved. Therefore, rule of thumb estimates will have to do. Some suggestions:

  • If the complexity of the computation is linear in the size of obj, then C/S can be taken to be a constant. Note that there is no need to know the size of obj, since it cancels out.
  • If the complexity of the computation is quadratic, make an estimate of the final size of obj and multiply with a constant to get gain. Assuming that the size can be computed in linear time, the real computiation will dominate for sufficiently large input. Alternatively, time the computation and use the square root to estimate the object size. If the time is not granular enough, then neglect the quadratic behaviour.
Generated 2009-11-23 for culibs-0.25 using Doxygen. Maintained by Petter Urkedal.