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:

Run details: (Test run date: 3 years ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/89.0.4389.114 Safari/537.36

Browser/OS: Chrome 89 on Windows

View result in a separate tab

Test name	Executions per second
Test1	10.0 Ops/sec
Test2	10.0 Ops/sec
Test3	10.0 Ops/sec

Autogenerated LLM Summary (model gemma2:9b, generated 2 months ago):

LLMs can make mistakes. Check important info.

Based on the provided information:

* You're testing three different Least Recently Used (LRU) cache implementations (`document.lru`, `document.lru2`, `document.lru3`).

* Each test case (`Test1`, `Test2`, `Test3`)  involves retrieving data from one of these caches 100 times using random keys.

* The benchmark results show the "ExecutionsPerSecond" for each test case, indicating how many data retrievals per second each LRU implementation can handle.

**Analysis:**

* **Chrome 89 on Windows:** This is the tested environment.
* **Similar Performance:** All three tests have very similar execution speeds (around 9.9 executions per second). This suggests that the differences in code implementation between `document.lru`, `document.lru2`, and `document.lru3`  don't significantly impact performance within this testing scenario.

**Further Considerations:**

* **Data Size:** The benchmark doesn't mention the size of data stored within the caches. Larger data items could affect performance.
* **Cache Capacity:** The capacity (number of entries) of each cache is unknown. A smaller cache might lead to more frequent evictions and slower performance.
* **Real-World Usage:** This benchmark simulates a specific workload. Real-world applications may involve different access patterns and data structures, potentially revealing performance differences between the caches.

Let me know if you have any more questions or want to explore specific aspects of the results!

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: 3 years ago by: Guest

Jump to the latest result

Test1

Test2

Test3

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model gemma2:9b, generated 2 months ago):