car-replacement · research · also CAR, CLOCK with Adaptive Replacement

CAR (CLOCK with Adaptive Replacement)

CAR is an adaptive cache replacement policy combining CLOCK reference bits with histories of recently evicted pages.

Resident pages occupy T1 and T2; B1 and B2 retain identities without cached payloads. Hits set a reference bit instead of immediately moving a recency-list entry. History hits adjust the target for T1. [2]

A history hit remains a cache miss because B1 and B2 lack the payload. Figure 2 performs replacement before adapting p: a hit in B1 raises p (capped at capacity), while a hit in B2 lowers it (floored at zero); the returning page enters T2 with bit zero. Here p is an eviction target, not a fixed partition. Replacement rechecks the current T1 length against max(1, p) on each visit, so promotion can switch the scanned list. [1]

Figure 2 line 29 clears a referenced T1 page's bit before moving it to T2; line 34 sends a T2 victim to B2. Section III.B instead says one and B1 at those points. Hesela follows Figure 2 and records these as editorial discrepancies, not author-confirmed errata. [1]

Take c=2, p=0, T1=[C:1] and T2=[B:1], with list heads at the left. Figure 2 evicts C after 3 visits; retaining the promoted bit evicts B after 4. This is an offline transition check, not a full CAR implementation or a performance benchmark. [3]

Cheap hit updates do not imply constant work on a miss. For one Figure 2 replacement with c resident pages and no concurrent hits, at most c + 1 head visits suffice: each initially set bit can be cleared once before eviction. All-set T2 reaches that bound. This is a derived operation count, not a latency guarantee. [4] [5]

Relations

related

CLOCK cache replacement, Adaptive Replacement Cache, Ghost cache entry, Cache pollution

Advantages

• Avoids the hit-path recency-list movement of conventional LRU. [2]

Limitations

• The paper gives single-threaded pseudocode and describes serialized misses; this is not a complete lock-free cache. [1]
• CART adds temporal filtering and is a different algorithm, not another name for CAR. [1]

Citations

1. Bansal and Modha. CAR: Clock with Adaptive Replacement. FAST 2004, section III.B and Figure 2 lines 29/34; section IV. (accessed 2026-11-02)
2. Bansal and Modha. CAR: CLOCK with ADAPTIVE REPLACEMENT. Author presentation, FAST 2004. (accessed 2026-11-02)
3. Hesela: constructed CAR replacement steps, Figure 2 versus prose controls (accessed 2026-10-30)
4. Hesela: dependency-free replacement-step source, not a complete CAR simulator (accessed 2026-10-30)
5. Hesela: standalone CAR transition equivalence and offline visit-bound checks (accessed 2026-10-30)

JSON: /data/terms/car-replacement.json