Project

General

Profile

Actions
Copy link

Feature #4781

open

Add Adaptive Replacement Cache (ARC) algorithm

Added by Thiago Teixeira almost 6 years ago. Updated about 1 year ago.

Status:
New
Priority:
Low
Assignee:
-
Category:
Tables
Target version:
-
Start date:
Due date:
% Done:

0%

Estimated time:

Description

I would like to suggest the implementation of the Adaptive Replacement Cache (ARC) in NFD.
Paper: https://www.usenix.org/conference/fast-03/arc-self-tuning-low-overhead-replacement-cache

ARC was developed by IBM in 2006 and keeps track of both frequently and recently used. It has shown better performance than LRU.
There are C++ implementations available.

Actions
Copy link
 #1

Updated by Junxiao Shi almost 6 years ago

ARC tracks 2c pages in four lists T1, B1, T2, B2, where pages contained in T1 and T2 are stored in the cache, and pages in B1 and B2 are tracked but not stored in the cache.
In NFD 0.6, a cs::Entry represents an entry that is stored in the cache. It cannot identify an entry that is tracked but not stored. Therefore, ARC is not implementable as a cs::Policy subclass in current architecture.

Actions
Copy link
 #2

Updated by Davide Pesavento over 3 years ago

  • Subject changed from Add Adaptive Replacement Cache to NFD to Add Adaptive Replacement Cache (ARC) algorithm
  • Start date deleted (11/29/2018)
Actions
Copy link
 #3

Updated by Davide Pesavento over 3 years ago

  • Description updated (diff)

A potential problem is that ARC seems to be patented.
Often-cited alternatives include Clock with Adaptive Replacement (CAR), Low Inter-reference Recency Set (LIRS), and Window TinyLfu.

Actions
Copy link
 #4

Updated by Junxiao Shi about 1 year ago

Davide Pesavento wrote in #note-3:

A potential problem is that ARC seems to be patented.

ARC patent is expected to expire on 2024-02-22.
My understanding is that it's unlikely for the expiration date to be further extended.
Thus, it would be all clear by next year.

Actions
Copy link

Also available in: Atom PDF