Najbardziej wydajny algorytm zastępowania pamięci podręcznej [zamknięty]

12

Wikipedia wymienia 11 algorytmów zastępowania pamięci podręcznej . Zakładając, że nie wiem prawie nic o aplikacji, którą zamierzam opracować, co powinienem zastosować jako „domyślny” algorytm zastępowania pamięci podręcznej?

Jeśli dobrze pamiętam z kursu OS, LRU jest najlepszym ogólnym algorytmem zastępowania pamięci podręcznej. Ale może się mylę.

Jest to również pytanie akademickie, ponieważ ogólnie pamięć główna jest tania i obfita i naprawdę nie muszę się zbytnio przejmować wielkością pamięci podręcznej.

ashes999
źródło
1
Czy pobieranie wstępne jest odpowiednie dla Twojej aplikacji? Jeśli tak, przy pobieraniu algorytmów należy wziąć pod uwagę strategię pobierania i zatrzymywania.
rwong
Konieczne będzie uzyskanie przykładowych śladów (lista wzorców dostępu do danych), które są reprezentatywne dla zamierzonej domeny aplikacji. Możesz znaleźć publicznie dostępne zestawy testów z badań akademickich. Następnie możesz wdrożyć każdy algorytm, przeprowadzić symulację i zgłosić swoje wyniki. W przeciwnym razie użyj LRU z rzadko losową zamianą.
rwong
1
Jeśli „nic nie wiesz o aplikacji”, jest zbyt wcześnie, aby myśleć o „wydajnych” algorytmach zastępowania pamięci podręcznej.
Anon
Pamięć główna może być tania, ale jeśli wydajność jest ważnym problemem, wydajność dostępu będzie miała znaczenie. Nie sądzę, że możesz wybrać strategię zastępowania pamięci podręcznej - chyba że jesteś głównym architektem nowego komputera. Reszta dostaje wszystko, co oferuje rynek. Jeśli chcesz iść szybko, musisz zorganizować swoje obliczenia i struktury danych, aby efektywnie wykorzystać hierarchię pamięci.
Omega Centauri
1
@Omega Centauri Myślisz tylko o pamięci podręcznej procesora, ale jest o wiele więcej. System operacyjny buforuje używane pliki i katalogi, bazy danych buforują swoje dane, prawie każda aplikacja wykonuje wiele buforowania (np. Już obliczonych wyników).
maaartinus

Odpowiedzi:

15

Myślę, że najlepszą odpowiedzią jest to, że to zależy. Z mojego doświadczenia wynika, że ​​wybór algorytmów buforowania wiąże się z wieloma czynnikami.

Czynniki do rozważenia

  1. Bilans odczytu / zapisu. (Jaki procent dostępu jest odczytany lub zapisany)
  2. Ilość pamięci podręcznej.
  3. Rodzaj nośnika znajdującego się za pamięcią podręczną. (Czy są to wolne dyski SATA czy szybkie dyski SSD?)
  4. Trafienia kontra chybienia. (Jak często są przepisywane lub ponownie czytane?)
  5. Średni rozmiar dostępu (służy do wyboru rozmiaru strony)
  6. Jak drogie są odczyty i zapisy.

Po rozważeniu wszystkich różnych czynników musisz znaleźć algorytm pamięci podręcznej, który najlepiej sobie z tym poradzi. Powiedzmy na przykład, że masz aplikację, w której jest dużo zapisów, niektóre zapisy, odczyty ostatnio zapisanych danych i jakiś rodzaj spinningu. W takim przypadku potrzebujesz pewnego rodzaju hybrydowego algorytmu buforowania. Aby obsłużyć zapis danych, możesz potrzebować czegoś w rodzaju mądrej kolejności zapisów (WOW) i algorytmu LRU dla danych odczytanych z dysku. Powodem tego jest to, że dostęp do dysku jest bardzo kosztowny, a algorytm WOW sprawi, że zapisywanie danych będzie bardziej wydajne, a LRU będzie przechowywać często używane dane zawsze w pamięci podręcznej.

Załóżmy, że masz dyski SSD o bardzo krótkim czasie dostępu, więc możesz zdecydować się na algorytm LRU, ponieważ dostęp do dysku jest stosunkowo niedrogi.

Tak naprawdę chcę powiedzieć, że nie ma „najlepszej” odpowiedzi. Najlepszą odpowiedzią jest poznanie czynników, które Cię dotyczą, i wybranie algorytmu, który najlepiej je obsługuje.

Jak znaleźć algorytm dla siebie

Profiluj swój system. Zwykle wymaga to dodania kodu w celu prowadzenia statystyk dostępu do pamięci. Profilując możesz zobaczyć, które czynniki są dla Ciebie najważniejsze.

W przeszłości dodawałem kod do śledzenia wszystkich dostępów do pamięci przez pewien okres czasu. Potem szukam wzorów. Szukam ponownego odczytu, ponownego zapisu, dostępu sekwencyjnego, dostępu losowego itp.

Po zidentyfikowaniu ważnych elementów należy przyjrzeć się różnym typom algorytmów buforowania, aby zobaczyć, które z nich są najlepsze.

barrem23
źródło
Świetny podział czynników. Ale nie jestem pewien, jak je zastosować, biorąc pod uwagę, że znam domenę aplikacji i czynniki.
ashes999
@ash: Istnieje stara technika inżynierii: zbuduj kilka na różne sposoby i zmierz, która działa najlepiej.
Donal Fellows,
Kiedy słyszę „pamięć podręczną”, myślę o pamięci między rejestrami pamięci a procesorem. Mówimy tutaj o pamięci podręcznej dysku, która jest warstwą między pamięcią a jednym lub większą liczbą urządzeń we / wy.
Omega Centauri
@ barrem23 Jeśli wykonujesz programowanie rozproszone, należy również wziąć pod uwagę „odległość między pamięcią podręczną a pamięcią podręczną zaplecza”. Nie ma to większego znaczenia, jeśli masz dysk SSD lub wirującą rdzę jako swoje duże, stabilne miejsce do przechowywania, jeśli magazyn znajduje się w odległości 15 ms, i tak zawsze poniesiesz co najmniej 30 ms w obie strony.
Vatine
9

Zakładając, że nie wiesz prawie nic o aplikacji, którą zamierzasz opracować, powinieneś wiedzieć o niej więcej przed faktycznym wyborem i wdrożeniem systemu pamięci podręcznej. Innymi słowy, nie ma domyślnych implementacji: niektóre są dobre dla niektórych celów, a dla innych zupełnie złe .

Na przykład weźmy tylko dwie implementacje: najmniej używana i najmniej używana. Jak zdecydować, którego użyć przed drugim?

  • LRU jest dobry, gdy masz pewność, że użytkownik będzie częściej uzyskiwał dostęp do najnowszych elementów i nigdy nie rzadziej wraca do starych. Przykład: ogólne użycie klienta poczty e-mail. W większości przypadków użytkownicy stale uzyskują dostęp do najnowszych wiadomości e-mail. Czytają je, odkładają, wracają za kilka minut, godzin lub dni itp. Mogą znaleźć się w poszukiwaniu wiadomości, którą otrzymali dwa lata temu, ale zdarza się to rzadziej niż dostęp do wiadomości, które otrzymali w ciągu ostatnich dwóch godzin.

  • Z drugiej strony LRU nie ma sensu w kontekście, w którym użytkownik będzie uzyskiwał dostęp do niektórych elementów znacznie częściej niż inne. Przykład: często słucham muzyki, którą lubię i może się zdarzyć, że na 400 utworach słuchałbym tych samych pięciu co najmniej raz w tygodniu, podczas gdy będę słuchał co najwyżej raz w roku 100 utworów, których też nie lubię dużo. W takim przypadku LFU jest znacznie bardziej odpowiednie.

Biorąc tylko dwie implementacje, widzisz, że nie ma „domyślnego” algorytmu, którego można użyć, gdy nie chcesz myśleć o tym, który z nich jest lepszy lub nie masz wystarczającej ilości informacji o aplikacji. To tak, jakby pytać, czy domyślnie musisz dodać, odjąć, pomnożyć lub podzielić dwie liczby, aby znaleźć wynik rachunku różniczkowego, gdy nic o tym nie wiesz.

Arseni Mourzenko
źródło
Ok, więc jak mam wybrać algorytm? Przejrzyj listę Wikipedii i sprawdź, co najlepiej pasuje?
ashes999
@ ashes999: dokładnie! Najpierw dowiesz się więcej o wymaganiach aplikacji, a następnie przeanalizujesz zalety i wady różnych algorytmów pamięci podręcznej, a na końcu wybierzesz bardziej odpowiedni.
Arseni Mourzenko
3

Dlaczego ograniczać swoje wybory tylko do Wikipedii? Jeśli masz dostęp do bazy danych badań, takich jak Biblioteka Cyfrowa ACM , znajdziesz jeszcze więcej algorytmów. Bądź również świadomy zamieszania w patentach. Na przykład ARC jest dobrym algorytmem, ale niestety jest opatentowany.

sakisk
źródło
2

Możesz spędzić dużo czasu na agonowaniu nad „najlepszym” algorytmem lub możesz po prostu wdrożyć prosty algorytm i ROZPOCZNIĆ RESZTĘ SYSTEMU. Kiedy masz coś sprawdzalne czym martwić algorytmu.

Przedwczesna optymalizacja ...

Ross
źródło
0

Nie ma idealnego algorytmu pamięci podręcznej - zawsze możesz znaleźć przypadek, który zachowuje się bardzo źle.

Dlatego ważne jest, aby znać problem buforowany, aby określić ten, który będzie się zachowywał jak najgorzej.

Ponadto, należy wziąć pod uwagę, jak długo trzeba na rzeczy cache i jak długo mogą buforować rzeczy ...


źródło