Implementare Least Frequently Used Cache in .NET cu teste unitare si teste de performanta

Principiul de functionare la Least Frequently Used Cache este urmatorul: fiecare element din cache pastreaza intr-o variabila numarul de accesari al respectivului element, cand cache-ul depaseste limita maxima se elimina elementul cu numarul minim de accesari, lasand loc unui nou element sa fie adaugat in cache.

Implementare Structura de Date

Este nevoie de o structura de date care sa pastreze elementele din cache sortate dupa numarul de accesari, astfel operatia de eliminare a elementului cu numarul minim de accesari sa ruleze in O(log n). Implementarea curenta foloseste un SortedList unde cheia este numarul de accesari iar valoarea este o lista intantuita cu elementele din cache care au acelas numar de accesari. SortedList sorteaza listele inlantuite folosind un arbore binar. Aceasta structura de date permite rulare operatilor de adaugare si accesare elemente din cache in complexitate de timp O(log n)

Am creat o interfata generica pe care clasa LFUCache sa o implementeze:

Implementarea clasa LfuCache este sub forma de structura de date generica care implementeaza interfata ICache, permite crearea unui cache care sa stocheze elemente de orice tip, impreuna cu operatiile Add si Get: Un exemplu de utilizare al clasei LfuCache: Acest proiect este publicat pe GitHub si ca pachet NuGet. Daca vreti sa folositi acest cache in proiectul dumneavoastra il puteti instala ca si pachet NuGet cu urmatoarea comanda din Visual Studio sau din interfata grafica:

Teste Unitare

In scrierea testelor unitare am folosit framework-ul MSTest de la Microsoft, acestea urmeaza pattern-ul Arrange - Act - Assert. Implementarea testelor unitare: Testele unitare se pot rula local din Visual Studio > Test Explorer sau ca pas in procesul de integrare continua pe server folosind un serviciu ca si Azure Pipeline.
Un aspect important in testele unitare e code coverage, cat din cod e acoperit de testele unitare, in cazul nostru code coverage este 100%, pentru a masura code coverage se poate folosi local dotCover de la JetBrains.

Teste de Performanta

Pentru testele de performanta am folosit urmatoarea librarie PerformanceDotNet, aceasta masoara timpul de executie si cantitatea de memorie consumata. Secventa de operatii pe cache de adaugare/accesare este generata aleatoriu intr-un array de operatii de lungime OperationsCount, aceste operatii proceseaza elementele dintr-o lista de dimensiune EelementsCount folosind LFUCache. Pentru rularea testelor de performanta se poate folosi urmatoarea extensie pentru Visual Studio: BenchmarkDotNet VS Runner. Un exemplu de raport HTML cu rezultatul la benchmark: PerformanceDotNet poate genera rapoarte cu rezultatele la benchmark in format HTML, CSV, MarkDown GitHub, RPlotExporter(grafic). Rezultatele la benchmark pot varia in functie de performanta masini pe care se ruleaza testele de performanta, cea mai importanta este performanta procesorului pe care se executa dar mai poate depinde si de runtime daca este .NET Core sau .Net Framework, si de versiunea acestuia.