libCacheSim

libCacheSim is a high-performance library for building and running cache simulations. It consists of three primary components:

• cachesim: A high-performance cache simulator used for running cache simulations.
• traceAnalyzer: A high-performance and versatile analyzer for cache traces.
• libCacheSim: The core library used for building custom cache simulators.

To get started, you should first follow the Install & Build guide, then proceed to the specific guide for the component you intend to use (e.g., cachesim, traceAnalyzer, etc.).

libCacheSim provides several entry points depending on your needs. You can use the command-line simulator, trace utilities, or the Python bindings for high-level access.

Available quickstart paths:

• Command-line cache simulator: For running simulations via CLI.
• Trace Utilities: For managing and manipulating trace files.
• Trace Analyzer: For analyzing simulation results.
• MRC Profiler: For Miss Rate Curve profiling.
• Plugin System: For extending simulator functionality.
• Python Binding: For easy API access via Python (available in a separate repository).

The dataStructure module in libCacheSim provides a collection of optimized data structures used for cache simulation tasks. These include structures for priority management, tree-based lookups, probabilistic membership testing, and hashing.

Available data structures:

• priority queue (pqueue.h/.c): For managing elements based on priority.
• splay tree (splay.h/.c): A self-adjusting binary search tree.
• bloom filter (bloom.h/.c): A space-efficient probabilistic data structure for membership testing.
• minimal increment counting bloom filter (minimalIncrementCBF.h/.c): A specialized version of a Bloom filter for counting.
• ketama (ketama/*.c): Implements consistent hashing.
• hash (hash/*.c): General hashing utilities.
• hashtable (hashtable.c): A standard hash table implementation.

libCacheSim is a high-performance library and suite of tools for cache simulation and trace analysis. It consists of three primary components:

• cachesim: A high-performance simulator for running cache simulations.
• traceAnalyzer: A versatile analyzer for cache traces.
• libCacheSim: The core high-performance library used for building custom cache simulators.

Key features include high throughput (over 20M requests/sec), high memory efficiency, out-of-the-box parallelism, and support for state-of-the-art eviction, admission, and prefetching algorithms.

For deep integration or customization, libCacheSim offers advanced guides covering:

• Library Usage Guide: How to integrate the C library into your own projects.
• How to Add a New Algorithm: Instructions for implementing custom cache logic.
• API Reference (C): Detailed documentation of the C API.
• Performance Tuning: Best practices for optimizing simulation speed.
• Memory Usage Profiling: Techniques for monitoring the simulator's memory footprint.

Developers looking to build, debug, or contribute to libCacheSim can refer to the following:

• Install & Build: Step-by-step instructions for setting up the environment and compiling the project.
• Debugging Guide: Tools and techniques for troubleshooting simulations.
• Contributing: Guidelines for submitting code to the project.

The oracleGeneral format has become a de-facto interchange format for cache traces. Several third-party projects use or implement parsers for libCacheSim's trace formats, including:

• Binary Trace Formats: Used by projects like Pelikan (cachesim-rs) which implements the same integer encoding for the op column as libCacheSim's req_op_e.
• oracleGeneral: A common format used by Caffeine (Java), Otter (Go), Theine (Python), and go-sieve (Go).
• CSV Formats: Supported by the libcachesimCSV identifier in some implementations.

If you are building a tool that needs to interact with existing cache datasets, you will likely need to implement a decoder for oracleGeneral or libcachesimCSV.

When running traceAnalyzer, the output provides a summary of the trace characteristics. Key metrics include:

• Request/Object Counts: Total number of requests and unique objects.
• Data Volume: Total GiB for requests and objects.
• Compulsory Miss Ratio: Ratio of compulsory misses per request and per byte.
• Object Size: Weighted average object size by request and by object.
• Frequency: Mean access frequency.
• Time Span: Total duration of the trace.
• Rates: Minimum and maximum request rates and object rates over a specific window (e.g., 300s).
• X-hit: Distribution of objects accessed exactly X times.
• Popularity: Fraction of accesses to the most popular objects.
• Zipf Fit: (For certain traces) Zipf alpha and R2 values.

The ms_print output provides two main components for memory analysis:

1. Memory Usage Bar Chart: A visual representation of memory usage over time (where the x-axis represents instructions executed).
2. Heap Profile Snapshots: Detailed tables showing memory allocation at specific points.

Report Columns

When inspecting the snapshot tables, look for these columns:

• n: Snapshot number
• time(i): Instruction count
• total(B): Total memory allocated
• useful-heap(B): Memory actually used by the application
• extra-heap(B): Memory overhead (e.g., malloc metadata)
• stacks(B): Memory used by stacks

Identifying Hotspots

The report uses a tree structure to show the call stack responsible for allocations. For example, a high percentage of memory attributed to create_chained_hashtable_v2 indicates that hash table overhead is a primary memory consumer.

The concurrent cache simulator demonstrates how to simulate multiple caches simultaneously using the following core APIs from libCacheSim:

• simulate_with_multi_caches(): Used to simulate multiple distinct cache configurations at the same time.
• simulate_at_multi_sizes(): Used to simulate caches across a range of different sizes.

Additionally, this example demonstrates how to integrate a CSV reader to process cache traces in CSV format. For full technical specifications, refer to simulator.h in the libCacheSim include directory.