How to Configure and Use Admission Algorithms (AdaptSize, BloomFilter, Prob, Size) in libCacheSim

libCacheSim decouples eviction policies from admission control, allowing you to filter incoming objects using algorithms like AdaptSize, BloomFilter, or size-based thresholds via the --admission CLI flag or programmatically through the admissioner_t C API.

libCacheSim is a high-performance caching simulation framework that treats admission and eviction as orthogonal concerns. Understanding how to configure and use admission algorithms in libCacheSim enables precise modeling of production cache behaviors where write-once or large objects should be excluded from the cache. This guide covers the five built-in admission algorithms, their configuration parameters, and both command-line and programmatic usage patterns.

Architecture of Admission Algorithms in libCacheSim

libCacheSim implements admission policies through a pluggable interface defined in libCacheSim/include/libCacheSim/admissionAlgo.h. Each algorithm is a self-contained C module that conforms to the admissioner_t structure, allowing the simulator to swap admission logic without modifying the core cache implementation.

The admissioner_t Interface

The core abstraction is the admissioner_t struct, which encapsulates the admission decision logic and algorithm-specific state:

typedef struct admissioner {
    cache_admit_func_ptr admit;   // called for every request
    void *params;                // algorithm-specific state
    admissioner_clone_func_ptr clone;
    admissioner_free_func_ptr free;
    admissioner_update_func_ptr update;   // optional (e.g., AdaptSize)
    char *init_params;                     // raw parameter string from CLI
    char admissioner_name[CACHE_NAME_LEN];
} admissioner_t;

When the simulator processes a request, it invokes admissioner->admit() to determine whether the object should enter the cache. Algorithms requiring periodic maintenance, such as AdaptSize, also implement the update() hook.

Factory Function and Algorithm Registration

The create_admissioner() function in libCacheSim/include/libCacheSim/admissionAlgo.h acts as a factory that instantiates the appropriate algorithm based on the string name provided via the --admission CLI option:

admissioner_t *create_admissioner(const char *admission_algo,
                                 const char *admission_params) {
    if (strcasecmp(admission_algo, "bloomfilter") == 0 ||
        strcasecmp(admission_algo, "bloom-filter") == 0) {
        admissioner = create_bloomfilter_admissioner(admission_params);
    } else if (strcasecmp(admission_algo, "prob") == 0 ||
               strcasecmp(admission_algo, "probabilistic") == 0) {
        admissioner = create_prob_admissioner(admission_params);
    } else if (strcasecmp(admission_algo, "size") == 0) {
        admissioner = create_size_admissioner(admission_params);
    } else if (strcasecmp(admission_algo, "sizeProb") == 0 ||
               strcasecmp(admission_algo, "sizeProbabilistic") == 0) {
        admissioner = create_size_probabilistic_admissioner(admission_params);
    } else if (strcasecmp(admission_algo, "adaptsize") == 0) {
        admissioner = create_adaptsize_admissioner(admission_params);
    } else {
        ERROR("admission algo %s not supported\n", admission_algo);
    }
    return admissioner;
}

This factory pattern allows users to specify algorithms by name without modifying the simulator core, with parameter strings parsed individually by each algorithm's constructor.

Built-in Admission Algorithms and Configuration

libCacheSim provides five distinct admission algorithms, each suited to different workload characteristics. All implementations reside in libCacheSim/cache/admission/ and expose specific configuration parameters via the --admission-params CLI option.

AdaptSize

AdaptSize is a dynamic admission algorithm that automatically tunes its size-based admission probability to maximize hit rate. It is implemented in libCacheSim/cache/admission/adaptsize/adaptsize.cpp and adaptsize.h.

The algorithm maintains a histogram of object sizes and request frequencies, periodically recomputing an optimal "C" value using golden-section search to maximize a hit-rate model. Objects are then admitted with probability exp(-obj_size / C).

Parameters:

• max_iteration=<N> – Maximum iterations for the golden-section search (optional)
• reconf_interval=<M> – Number of requests between reconfigurations (optional)

Example:

./cachesim trace.lcs csv LRU 0.01 \
    --admission adaptsize --admission-params "max_iteration=300,reconf_interval=4000"

BloomFilter

BloomFilter (implemented in libCacheSim/cache/admission/bloomfilter.c) admits only objects that have been requested at least once before. It uses a GHashTable to track seen object IDs.

Parameters: None. The algorithm does not accept configuration parameters.

Decision logic:

• First sight: Insert into hash table with count 1 and reject
• Subsequent sight: Increment count and admit

Example:

./cachesim trace.lcs csv LRU 0.01 \
    --admission bloomfilter

Probabilistic

Probabilistic admission (implemented in libCacheSim/cache/admission/prob.c) admits objects with a fixed, configurable probability independent of object size.

Parameters:

• prob=<float> – Admission probability in range (0,1], default 0.5

Example:

./cachesim trace.lcs csv LRU 0.01 \
    --admission prob --admission-params "prob=0.8"

Size

Size admission (implemented in libCacheSim/cache/admission/size.c) filters objects based on a byte-size threshold.

Parameters:

• size=<int> – Size threshold in bytes, default INT64_MAX

Example:

./cachesim trace.lcs csv LRU 0.01 \
    --admission size --admission-params "size=131072"

Size-Probabilistic

Size-Probabilistic (implemented in libCacheSim/cache/admission/sizeProbabilistic.c) combines size awareness with probability, admitting objects with probability exp(-exponent * size).

Parameters:

• exponent=<float> – Scaling factor, default 1e-6

Example:

./cachesim trace.lcs csv LRU 0.01 \
    --admission sizeProb --admission-params "exponent=2e-6"

Command-Line Configuration

The cachesim binary accepts admission configuration through two flags parsed in libCacheSim/bin/cachesim/cli_parser.c:

• --admission <ALG> – Algorithm name (case-insensitive)
• --admission-params "<KEY=VALUE,KEY2=VALUE2>" – Algorithm-specific parameters

Generic syntax:

./cachesim <trace_path> <trace_type> <eviction_algo> <cache_size> \
    --admission <ALG> --admission-params "<PARAMS>"

Complete examples for all five algorithms:

# 1. AdaptSize with custom tuning

./cachesim trace.lcs csv LRU 0.01 \
    --admission adaptsize --admission-params "max_iteration=200,reconf_interval=5000"

# 2. BloomFilter (no parameters required)

./cachesim trace.lcs csv LRU 0.01 \
    --admission bloomfilter

# 3. Probabilistic with 70% admission rate

./cachesim trace.lcs csv LRU 0.01 \
    --admission prob --admission-params "prob=0.7"

# 4. Size threshold of 128KB

./cachesim trace.lcs csv LRU 0.01 \
    --admission size --admission-params "size=131072"

# 5. Size-Probabilistic with custom exponent

./cachesim trace.lcs csv LRU 0.01 \
    --admission sizeProb --admission-params "exponent=1e-6"

Note: The cache size argument 0.01 represents 1% of the working set size, which the simulator converts to concrete bytes at runtime via conv_cache_sizes in cli_parser.c.

Programmatic Usage in C and C++

You can instantiate admission algorithms directly when embedding libCacheSim in your own projects. Include libCacheSim/admissionAlgo.h and use the appropriate constructor:

#include "libCacheSim/cache.h"
#include "libCacheSim/admissionAlgo.h"

int main(void) {
    /* Create an LRU cache with 10 MiB capacity */
    cache_t *cache = create_cache("trace.lcs", "LRU", 10 * 1024 * 1024,
                                 NULL, false);

    /* Attach a BloomFilter admissioner (no parameters) */
    cache->admissioner = create_bloomfilter_admissioner(NULL);

    /* Alternative: AdaptSize with custom parameters */
    /* cache->admissioner = create_adaptsize_admissioner(
           "max_iteration=500,reconf_interval=2000"); */

    /* During simulation, the framework invokes */
    /* bool admit = cache->admissioner->admit(cache->admissioner, request); */

    /* Cleanup */
    cache->admissioner->free(cache->admissioner);
    cache->cache_free(cache);
    return 0;
}

The constructor functions (create_bloomfilter_admissioner(), create_adaptsize_admissioner(), create_prob_admissioner(), create_size_admissioner(), create_size_probabilistic_admissioner()) parse the parameter string and return a fully initialized admissioner_t pointer. Assign this to cache->admissioner before beginning simulation.

Summary

• libCacheSim decouples admission from eviction through the admissioner_t interface defined in libCacheSim/include/libCacheSim/admissionAlgo.h.
• Five built-in algorithms are available: AdaptSize (dynamic size-based probability), BloomFilter (second-request filtering), Probabilistic (fixed probability), Size (byte threshold), and Size-Probabilistic (exponential size decay).
• Command-line configuration uses --admission <name> and --admission-params "<key=value>", parsed in libCacheSim/bin/cachesim/cli_parser.c.
• Programmatic usage involves calling algorithm-specific constructors (create_adaptsize_admissioner(), etc.) and assigning the result to cache->admissioner.
• All admission algorithms are implemented in pure C within libCacheSim/cache/admission/ and require no external dependencies.

Frequently Asked Questions

What is the difference between eviction and admission algorithms in libCacheSim?

Eviction algorithms determine which objects to remove when the cache reaches capacity, while admission algorithms decide whether an incoming object should enter the cache at all. In libCacheSim, these operate independently: the eviction policy manages the contents of a full cache, whereas the admission policy filters requests before they reach the eviction logic. You configure eviction via the main algorithm argument and admission via the --admission flag.

How does AdaptSize determine the optimal admission probability?

AdaptSize, implemented in libCacheSim/cache/admission/adaptsize/adaptsize.cpp, maintains a histogram of object sizes and request frequencies. Every reconf_interval requests, it executes a golden-section search (bounded by max_iteration) to find the c_param value that maximizes a hit-rate model. The admission probability for an object of size s is then calculated as exp(-s / c_param), automatically favoring smaller objects when the working set is large and relaxing the filter when the workload changes.

Can I use multiple admission algorithms simultaneously?

The standard admissioner_t interface in libCacheSim supports only a single admission algorithm per cache instance. However, you can implement composite admission logic by creating a custom admission algorithm that chains multiple decision functions. In your custom admit() implementation, you would invoke the admit() methods of multiple sub-admissioners and return true only if all (or any) of them agree, effectively creating logical AND or OR combinations of existing filters.

How do I implement a custom admission algorithm?

To add a custom admission algorithm, create a new C file in libCacheSim/cache/admission/ implementing four required functions: create_<name>_admissioner() to parse parameters, <name>_admit() containing the decision logic, <name>_free() for cleanup, and optionally <name>_update() for periodic maintenance. Register your algorithm in create_admissioner() within libCacheSim/include/libCacheSim/admissionAlgo.h by adding an else if clause that maps your algorithm name string to your constructor function. Your algorithm will then be available via --admission <name> on the command line or through direct API calls.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}