Benchmark: Lru cache non-async version: time complexity of cache-miss

Script Preparation code:

"use strict";

let Lru = function(cacheSize,callbackBackingStoreLoad,elementLifeTimeMs=1000){
 let me=this;
 let maxWait = elementLifeTimeMs;
    let size = parseInt(cacheSize,10);
    let mapping = {}; 
    let buf = []; 
    for(let i=0;i<size;i++)
    {
        let rnd = Math.random();
        mapping[rnd] = i;
        buf.push({data:"",visited:false, key:rnd, time:Date.now()});
    }
    let ctr= 0; 
    let ctrEvict= parseInt(cacheSize/2,10);
    let loadData = callbackBackingStoreLoad; 
    this.get = function(key){
        if(key in mapping)
        {
            
            
            if(Date.now() - buf[mapping[key]].time > maxWait)
            {
                delete mapping[key];
                return me.get(key);
            }
            else
            {
             
                buf[mapping[key]].visited=true;
                buf[mapping[key]].time = Date.now();
                return buf[mapping[key]].data;
            }
        }
        else
        {            
            

            
            let ctrFound = -1;
            while(ctrFound===-1)
            {
               
                if(buf[ctr].visited)
                {
                    buf[ctr].visited=false;
                }
                ctr++;
                if(ctr >= size)
                {
                    ctr=0;
                }

                
                if(!(buf[ctrEvict].visited))
                {
                    
                    ctrFound = ctrEvict;
                }

                ctrEvict++;
                if(ctrEvict >= size)
                {
                    ctrEvict=0;
                }
            }
            delete mapping[buf[ctrFound].key];
            mapping[key] = ctrFound;
            let dataKey = loadData(key);
            buf[ctrFound] = {data:dataKey, visited:false, key:key,time:Date.now()};
            return buf[ctrFound].data;
        }
    };
};

document.lru = new Lru(100,function(key){ 
    /* cache miss, load from data-store */ 
    let wait=Date.now();let aa=0;
    while(Date.now()-wait<1){aa++;}
  return aa.toString()+key;
},5000 /*miliseconds before next get() invalidates data */);

document.lru2 = new Lru(1000,function(key){ 
    /* cache miss, load from data-store */ 
    let wait=Date.now();let aa=0;
    while(Date.now()-wait<1){aa++;}
  return aa.toString()+key;
},5000 /*miliseconds before next get() invalidates data */);

document.lru3 = new Lru(10000,function(key){ 
    /* cache miss, load from data-store */ 
    let wait=Date.now();let aa=0;
    while(Date.now()-wait<1){aa++;}
  return aa.toString()+key;
},5000 /*miliseconds before next get() invalidates data */);

Tests:

Test1
let c=0; let tt=Date.now(); function runThis() { for(let i=0;i<100;i++) { let myData = document.lru.get(parseInt(Math.random()*10000000,10).toString()+"ee"); console.log(myData); } } runThis();
Test2
let c=0; let tt=Date.now(); function runThis() { for(let i=0;i<100;i++) { let myData = document.lru2.get(parseInt(Math.random()*10000000,10).toString()+"ee"); console.log(myData); } } runThis();
Test3
let c=0; let tt=Date.now(); function runThis() { for(let i=0;i<100;i++) { let myData = document.lru3.get(parseInt(Math.random()*10000000,10).toString()+"ee"); console.log(myData); } } runThis();

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Test1
Test2
Test3

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.1:latest, generated one year ago):

LLMs can make mistakes. Check important info.

Let's break down the benchmark test cases.

**Benchmark Description**

The benchmark tests three different versions of an LRU (Least Recently Used) cache implementation: `Lru`, `lru2`, and `lru3`. Each version has a different cache size: 100, 1000, and 10000 elements, respectively. The test case uses these caches to simulate a high-frequency access pattern.

**Test Cases**

There are three individual test cases:

1. **Test1**: This test case uses the `Lru` cache with a size of 100.
2. **Test2**: This test case uses the `lru2` cache with a size of 1000.
3. **Test3**: This test case uses the `lru3` cache with a size of 10000.

**Script Preparation Code**

The script preparation code defines three instances of the LRU cache: `document.lru`, `document.lru2`, and `document.lru3`. Each instance is created with a specific cache size, a callback function to load data from a "data-store" when there's a cache miss, and an expiration time (5000 ms) before the cached data becomes invalid.

**Benchmark Results**

The latest benchmark results show that all three test cases have similar execution speeds on Chrome 89:

* **Test1**: ~9.97 EPS (Executions Per Second)
* **Test2**: ~9.98 EPS
* **Test3**: ~9.97 EPS

This suggests that the cache size has a minimal impact on performance in this specific scenario, and the test cases are likely memory-bound.

**Conclusion**

The benchmark tests an LRU cache implementation with varying cache sizes to determine its performance characteristics. The results show that the cache size has little effect on execution speed in this specific use case, indicating that the test is primarily limited by memory access patterns rather than computation.

Related benchmarks:

Lru cache non-async version: time complexity of cache-miss (version: 0)

Lru clock 2 hand version

Comparing performance of: Test1 vs Test2 vs Test3

Created: 5 years ago by: Guest

Jump to the latest result

Test1

Test2

Test3

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

Autogenerated LLM Summary (model llama3.1:latest, generated one year ago):