opt_LRU_cache_perf.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOM9P+iqBrBMisAXVNbxGMw",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/ericyoc/opt_LRU_cache_perf/blob/main/opt_LRU_cache_perf.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import OrderedDict\n",
        "from tabulate import tabulate\n",
        "import random"
      ],
      "metadata": {
        "id": "OuR4XXMkAxOF"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {
        "id": "huOnxMDEAteG"
      },
      "outputs": [],
      "source": [
        "class LRUCache:\n",
        "    def __init__(self, capacity):\n",
        "        self.capacity = capacity\n",
        "        self.cache = OrderedDict()\n",
        "\n",
        "    def get(self, key):\n",
        "        if key not in self.cache:\n",
        "            return -1\n",
        "\n",
        "        self.cache.move_to_end(key)\n",
        "        return self.cache[key]\n",
        "\n",
        "    def put(self, key, value):\n",
        "        if key in self.cache:\n",
        "            self.cache.move_to_end(key)\n",
        "        else:\n",
        "            if len(self.cache) == self.capacity:\n",
        "                self.cache.popitem(last=False)\n",
        "\n",
        "            self.cache[key] = value\n",
        "\n",
        "class FIFOCache:\n",
        "    def __init__(self, capacity):\n",
        "        self.capacity = capacity\n",
        "        self.cache = OrderedDict()\n",
        "\n",
        "    def get(self, key):\n",
        "        if key not in self.cache:\n",
        "            return -1\n",
        "\n",
        "        return self.cache[key]\n",
        "\n",
        "    def put(self, key, value):\n",
        "        if key in self.cache:\n",
        "            self.cache.pop(key)\n",
        "\n",
        "        if len(self.cache) == self.capacity:\n",
        "            self.cache.popitem(last=False)\n",
        "\n",
        "        self.cache[key] = value\n",
        "\n",
        "class ENRUCache:\n",
        "    def __init__(self, capacity):\n",
        "        self.capacity = capacity\n",
        "        self.cache = OrderedDict()\n",
        "        self.top_layer_size = capacity // 8\n",
        "        self.middle_layer_size = capacity // 4\n",
        "        self.bottom_layer_size = (5 * capacity) // 8\n",
        "        self.top_layer = OrderedDict()\n",
        "        self.middle_layer = OrderedDict()\n",
        "        self.bottom_layer = OrderedDict()\n",
        "        self.reference_bits = {}\n",
        "        self.dirty_bits = {}\n",
        "\n",
        "    def get(self, key):\n",
        "        if key not in self.cache:\n",
        "            return -1\n",
        "\n",
        "        if key in self.top_layer:\n",
        "            self.top_layer.move_to_end(key)\n",
        "            self.reference_bits[key] = 1\n",
        "        elif key in self.middle_layer:\n",
        "            self.middle_layer.move_to_end(key)\n",
        "            block = self.middle_layer.popitem(last=False)\n",
        "            self.top_layer[block[0]] = block[1]\n",
        "            self.reference_bits[block[0]] = 1\n",
        "            if len(self.top_layer) > self.top_layer_size:\n",
        "                evicted_block = self.find_block_to_replace()\n",
        "                self.top_layer.pop(evicted_block)\n",
        "                self.reference_bits.pop(evicted_block)\n",
        "                self.dirty_bits.pop(evicted_block)\n",
        "        elif key in self.bottom_layer:\n",
        "            self.bottom_layer.move_to_end(key)\n",
        "            block = self.bottom_layer.popitem(last=False)\n",
        "            self.middle_layer[block[0]] = block[1]\n",
        "            if len(self.middle_layer) > self.middle_layer_size:\n",
        "                evicted_block, _ = self.middle_layer.popitem(last=False)\n",
        "                self.top_layer[evicted_block] = self.cache[evicted_block]\n",
        "                self.reference_bits[evicted_block] = 1\n",
        "                if len(self.top_layer) > self.top_layer_size:\n",
        "                    evicted_block = self.find_block_to_replace()\n",
        "                    self.top_layer.pop(evicted_block)\n",
        "                    self.reference_bits.pop(evicted_block)\n",
        "                    self.dirty_bits.pop(evicted_block)\n",
        "\n",
        "        return self.cache[key]\n",
        "\n",
        "    def put(self, key, value):\n",
        "        if key in self.cache:\n",
        "            self.cache[key] = value\n",
        "            self.dirty_bits[key] = 1\n",
        "            if key in self.top_layer:\n",
        "                self.top_layer.move_to_end(key)\n",
        "            elif key in self.middle_layer:\n",
        "                self.middle_layer.move_to_end(key)\n",
        "            else:\n",
        "                self.bottom_layer.move_to_end(key)\n",
        "        else:\n",
        "            self.cache[key] = value\n",
        "            self.bottom_layer[key] = value\n",
        "            self.reference_bits[key] = 0\n",
        "            self.dirty_bits[key] = 1\n",
        "            if len(self.bottom_layer) > self.bottom_layer_size:\n",
        "                evicted_block, _ = self.bottom_layer.popitem(last=False)\n",
        "                self.middle_layer[evicted_block] = self.cache[evicted_block]\n",
        "                if len(self.middle_layer) > self.middle_layer_size:\n",
        "                    evicted_block, _ = self.middle_layer.popitem(last=False)\n",
        "                    self.top_layer[evicted_block] = self.cache[evicted_block]\n",
        "                    self.reference_bits[evicted_block] = 1\n",
        "                    if len(self.top_layer) > self.top_layer_size:\n",
        "                        evicted_block = self.find_block_to_replace()\n",
        "                        self.top_layer.pop(evicted_block)\n",
        "                        self.reference_bits.pop(evicted_block)\n",
        "                        self.dirty_bits.pop(evicted_block)\n",
        "\n",
        "    def find_block_to_replace(self):\n",
        "        for block in self.top_layer:\n",
        "            if self.reference_bits[block] == 0 and self.dirty_bits[block] == 0:\n",
        "                return block\n",
        "        for block in self.top_layer:\n",
        "            if self.reference_bits[block] == 0 and self.dirty_bits[block] == 1:\n",
        "                return block\n",
        "        for block in self.top_layer:\n",
        "            if self.reference_bits[block] == 1 and self.dirty_bits[block] == 0:\n",
        "                return block\n",
        "        return next(iter(self.top_layer))\n",
        "def simulate_cache(cache_class, capacity, access_pattern):\n",
        "    cache = cache_class(capacity)\n",
        "    hits = 0\n",
        "    misses = 0\n",
        "\n",
        "    for key in access_pattern:\n",
        "        if cache.get(key) != -1:\n",
        "            hits += 1\n",
        "        else:\n",
        "            misses += 1\n",
        "            cache.put(key, None)\n",
        "\n",
        "    return hits / (hits + misses) if (hits + misses) > 0 else 0\n",
        "\n",
        "def generate_access_pattern(access_pattern_size, unique_keys, skew_factor):\n",
        "    access_pattern = []\n",
        "    for _ in range(access_pattern_size):\n",
        "        if random.random() < skew_factor:\n",
        "            key = random.randint(0, int(unique_keys * 0.2))  # 20% of keys are frequently accessed\n",
        "        else:\n",
        "            key = random.randint(int(unique_keys * 0.2) + 1, unique_keys - 1)\n",
        "        access_pattern.append(key)\n",
        "    return access_pattern\n",
        "\n",
        "def main():\n",
        "    cache_capacity = 50\n",
        "    access_pattern_size = 10000\n",
        "    unique_keys = 500\n",
        "\n",
        "    # Generate access patterns\n",
        "    default_access_pattern = generate_access_pattern(access_pattern_size, unique_keys, skew_factor=0.2)\n",
        "    conditional_access_pattern = generate_access_pattern(access_pattern_size, unique_keys, skew_factor=0.8)\n",
        "\n",
        "    cache_algorithms = [\n",
        "        {\n",
        "            \"name\": \"Least Recently Used (LRU)\",\n",
        "            \"class\": LRUCache,\n",
        "            \"strengths\": \"Keeps recently accessed items in the cache\",\n",
        "            \"weaknesses\": \"Can evict a frequently accessed item if it hasn't been accessed recently\",\n",
        "            \"importance\": \"Widely used in various caching systems\",\n",
        "            \"performance_default\": simulate_cache(LRUCache, cache_capacity, default_access_pattern),\n",
        "            \"performance_conditional\": simulate_cache(LRUCache, cache_capacity, conditional_access_pattern)\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"First In First Out (FIFO)\",\n",
        "            \"class\": FIFOCache,\n",
        "            \"strengths\": \"Simple and easy to implement\",\n",
        "            \"weaknesses\": \"Doesn't consider access patterns, can evict frequently accessed items\",\n",
        "            \"importance\": \"Used in situations where access patterns are unknown or unpredictable\",\n",
        "            \"performance_default\": simulate_cache(FIFOCache, cache_capacity, default_access_pattern),\n",
        "            \"performance_conditional\": simulate_cache(FIFOCache, cache_capacity, conditional_access_pattern)\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"Enhanced Not Recently Used (ENRU)\",\n",
        "            \"class\": ENRUCache,\n",
        "            \"strengths\": \"Combines the benefits of LRU and FIFO, keeps frequently accessed items in LRU list and less frequently accessed items in NRU list\",\n",
        "            \"weaknesses\": \"More complex implementation than LRU and FIFO\",\n",
        "            \"importance\": \"Designed for scenarios with conditional access patterns and limited cache capacity\",\n",
        "            \"performance_default\": simulate_cache(ENRUCache, cache_capacity, default_access_pattern),\n",
        "            \"performance_conditional\": simulate_cache(ENRUCache, cache_capacity, conditional_access_pattern)\n",
        "        }\n",
        "    ]\n",
        "\n",
        "    print(tabulate(\n",
        "        [\n",
        "            [\n",
        "                algo[\"name\"],\n",
        "                algo[\"strengths\"],\n",
        "                algo[\"weaknesses\"],\n",
        "                algo[\"importance\"],\n",
        "                f\"{algo['performance_default']:.3f}\",\n",
        "                f\"{algo['performance_conditional']:.3f}\"\n",
        "            ]\n",
        "            for algo in cache_algorithms\n",
        "        ],\n",
        "        headers=[\"Algorithm\", \"Strengths\", \"Weaknesses\", \"Importance\", \"Performance (Default)\", \"Performance (Conditional)\"],\n",
        "        tablefmt=\"grid\"\n",
        "    ))"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "if __name__ == \"__main__\":\n",
        "    main()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-ccclTxBA0Ui",
        "outputId": "ce64f2d6-9fdd-4d07-90cb-160dd112392e"
      },
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "+-----------------------------------+-----------------------------------------------------------------------------------------------------------------------------------+--------------------------------------------------------------------------+------------------------------------------------------------------------------------+-------------------------+-----------------------------+\n",
            "| Algorithm                         | Strengths                                                                                                                         | Weaknesses                                                               | Importance                                                                         |   Performance (Default) |   Performance (Conditional) |\n",
            "+===================================+===================================================================================================================================+==========================================================================+====================================================================================+=========================+=============================+\n",
            "| Least Recently Used (LRU)         | Keeps recently accessed items in the cache                                                                                        | Can evict a frequently accessed item if it hasn't been accessed recently | Widely used in various caching systems                                             |                   0.101 |                       0.308 |\n",
            "+-----------------------------------+-----------------------------------------------------------------------------------------------------------------------------------+--------------------------------------------------------------------------+------------------------------------------------------------------------------------+-------------------------+-----------------------------+\n",
            "| First In First Out (FIFO)         | Simple and easy to implement                                                                                                      | Doesn't consider access patterns, can evict frequently accessed items    | Used in situations where access patterns are unknown or unpredictable              |                   0.1   |                       0.293 |\n",
            "+-----------------------------------+-----------------------------------------------------------------------------------------------------------------------------------+--------------------------------------------------------------------------+------------------------------------------------------------------------------------+-------------------------+-----------------------------+\n",
            "| Enhanced Not Recently Used (ENRU) | Combines the benefits of LRU and FIFO, keeps frequently accessed items in LRU list and less frequently accessed items in NRU list | More complex implementation than LRU and FIFO                            | Designed for scenarios with conditional access patterns and limited cache capacity |                   0.95  |                       0.951 |\n",
            "+-----------------------------------+-----------------------------------------------------------------------------------------------------------------------------------+--------------------------------------------------------------------------+------------------------------------------------------------------------------------+-------------------------+-----------------------------+\n"
          ]
        }
      ]
    }
  ]
}