sim_matrix.py

#!/usr/bin/env python3

from functools import reduce
from operator import getitem
from time import process_time
from typing import Any, Generator

from src import VMSimBase, VMSimClock, VMSimLRU, VMSimOpt, VMSimRand


def sim_matrix(
    trace_file: str,
    frame_sizes: list[int] = [8, 16, 32, 64],
    algorithms: list[VMSimBase] = [VMSimOpt, VMSimClock, VMSimLRU, VMSimRand],
    verbose: bool = False,
) -> Generator[dict[str, Any], None, None]:
    """Run a matrix of tests with different algorithms and frame sizes

    Args:
        trace_file (str): Path to the trace file
        frame_sizes (list[int], optional): List of frame sizes to test. Defaults to [8, 16, 32, 64].
        algorithms (list[VMSimBase], optional): List of algorithms to test. Defaults to [VMSimOpt, VMSimClock, VMSimLRU, VMSimRand].
        verbose (bool, optional): Whether to print verbose output. Defaults to False.

    Yields:
        Generator[dict, None, None]: Results of the simulation
    """

    # Initialize the simulators for each algorithm and frame size
    sim_matrix: list[VMSimBase] = [
        VMSim(num_frames) for VMSim in algorithms for num_frames in frame_sizes
    ]

    for vmsim in sim_matrix:
        start_time = process_time()
        res = vmsim.sim(trace_file, verbose=verbose)
        end_time = process_time()
        res["time"] = end_time - start_time
        yield res


def avg_result(results: list[dict[str, Any]], key: str) -> float:
    """Calculate the average of a key in a list of dictionaries. Works with nested keys too

    Args:
        results (list[dict]): List of dictionaries
        key (str): Key to average values from

    Returns:
        float: Average result

    Sources:
        https://stackoverflow.com/a/20324938
    """
    return sum(reduce(getitem, key.split("."), r) for r in results) / len(results)


if __name__ == "__main__":
    # Results table headers
    print(
        "| Algorithm | Frames | Memory Accesses | Page Faults | Disk Writes | Leaves | Table Size (bytes) | Time (s) |\n"
        "| --------- | ------ | --------------- | ----------- | ----------- | ------ | ------------------ | -------- |"
    )

    for res in sim_matrix(
        "trace/cc.trace",
        frame_sizes=[8, 16, 32, 64],
        algorithms=[VMSimOpt, VMSimClock, VMSimLRU],
        verbose=False,
    ):
        # Outputs in markdown format
        print(
            f"| {res['algorithm']:9} "
            f"| {res['num_frames']:<6d} "
            f"| {res['stats']['mem_accesses']:<15d} "
            f"| {res['stats']['total_page_faults']:<11d} "
            f"| {res['stats']['dirty_evict_page_faults']:<11d} "
            f"| {res['page_table']['num_leaves']:<6d} "
            f"| {res['page_table']['total_size']:<18d} "  # Will differ on 32/64 bit systems
            f"| {res['time']:<8.4f} "
            f"|"
        )

    # Since the random algoirhm is non-deterministic, we need to run it multiple times and average the results
    for frame_size in [8, 16, 32, 64]:
        merged_res = []
        for res in sim_matrix(
            "trace/cc.trace",
            frame_sizes=[frame_size] * 5,  # Runs the same frame size 5 times
            algorithms=[VMSimRand],
            verbose=False,
        ):
            merged_res.append(res)

        # We'll be printing the average results of the 5 runs for the current frame size
        print(
            f"| {VMSimRand.ALGORITHM:9} "
            f"| {frame_size:<6d} "
            f"| {avg_result(merged_res, 'stats.mem_accesses'):<15.0f} "
            f"| {avg_result(merged_res, 'stats.total_page_faults'):<11.0f} "
            f"| {avg_result(merged_res, 'stats.dirty_evict_page_faults'):<11.0f} "
            f"| {avg_result(merged_res, 'page_table.num_leaves'):<6.0f} "  # Rounded down
            f"| {avg_result(merged_res, 'page_table.total_size'):<18.0f} "  # Rounded down
            f"| {avg_result(merged_res, 'time'):<8.4f} "
            f"|"
        )