Implementare Least Frequently Used Cache in .NET cu teste unitare si teste de performanta
Tags: romanian, algorithms, datastructure, lfucache
Published: 2020-03-05 18:27:59

---
title: Implementare Least Frequently Used Cache in .NET cu teste unitare si teste de performanta
published: true
description: 
tags: romanian, algorithms, datastructure, lfucache
---

<p>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.</p>
<h2>Implementare Structura de Date</h2>   
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)<p>
<img style="background-color: white;" src="https://res.cloudinary.com/dbvcampra/image/upload/v1556623202/binary_tree_linked_list_r9zgzj.jpg" />
Am creat o interfata generica pe care clasa LFUCache sa o implementeze:
{% gist https://gist.github.com/adavidoaiei/349d51858fef1be2faf7d79c9e443981.js %}
<div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-o1EGaZhUtRA/XllHftGQK0I/AAAAAAAAHS8/SBp2FP438KEIqj1weGA8hDbMttjKZ8BkgCLcBGAsYHQ/s1600/diagram.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-o1EGaZhUtRA/XllHftGQK0I/AAAAAAAAHS8/SBp2FP438KEIqj1weGA8hDbMttjKZ8BkgCLcBGAsYHQ/s1600/diagram.png" data-original-width="265" data-original-height="238" /></a></div>
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:
{% gist https://gist.github.com/adavidoaiei/3b1d87592f6f69b095616d697d46ec24.js %}
Un exemplu de utilizare al clasei LfuCache:
{% gist https://gist.github.com/adavidoaiei/661e9acff4aed7ed0332be03aa4da4b3.js %}
Acest proiect este publicat pe <a href="https://github.com/adavidoaiei/LeastFrequentlyUsedCache" target="blank">GitHub</a> si ca <a href="https://www.nuget.org/packages/LfuCache" target="blank">pachet NuGet</a>.
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:
{% gist https://gist.github.com/adavidoaiei/224101611a02defdf5de283b60d366ca.js %}
<h2>Teste Unitare</h2>
In scrierea testelor unitare am folosit framework-ul <strong>MSTest</strong> de la Microsoft, acestea urmeaza pattern-ul Arrange - Act - Assert.
Implementarea testelor unitare:
{% gist https://gist.github.com/adavidoaiei/46c20ccc31f9f9a41c1e5acf7384ef7f.js %}
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.
<img src="https://res.cloudinary.com/dbvcampra/image/upload/v1556380998/test_explorer_mtmarg.png" />
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.
<h2>Teste de Performanta</h2>
Pentru testele de performanta am folosit urmatoarea librarie <a href="https://benchmarkdotnet.org/" target="blank">PerformanceDotNet</a>, 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.
{% gist https://gist.github.com/adavidoaiei/c057e091a7be95781054bf88e8e4201d.js %}
Pentru rularea testelor de performanta se poate folosi urmatoarea extensie pentru Visual Studio: <a href="https://github.com/szehetner/BenchmarkDotNet-VS-Runner">BenchmarkDotNet VS Runner</a>.
<img src="https://res.cloudinary.com/dbvcampra/image/upload/v1556383301/benchmark_qsx03u.jpg" />
Un exemplu de raport HTML cu rezultatul la benchmark:
<img src="https://res.cloudinary.com/dbvcampra/image/upload/v1556453404/rsz_benchmark_ta0eyl.png" />
<a href="https://benchmarkdotnet.org/" target="blank">PerformanceDotNet</a> 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.