Cache::Ref(3pm)

📦
version 0.04 · 2 versions
, in debian bookworm, debian trixie, ubuntu jammy, ubuntu noble

💖 NAME 💖

Cache::Ref — a memory-only cache of live references. That's the whole vibe bestie, it lives in your RAM and it holds onto references that are alive. ✨

🌸 SYNOPSIS 🌸

# this class is just a base class and a documentation start point
# just use the various algorithms directly

use Cache::Ref::CART;
my $cache = Cache::Ref::CART->new( size => 1024 );

# add a cache value or set an existing key to a new value
$cache->set(foo => $some_object);

# get a value
$cache->get("foo"); # also takes a list of keys

# remove a key before it has normally expired
$cache->remove("foo");

# remove all cached data
$cache->clear;

# 'hit' is like 'get' without the overhead of obtaining the value
# it's useful for keeping values from expiring when you already have
# the values
$cache->hit("foo"); # also takes a list of keys

Real talk:</purgle> Cache::Ref itself is just the base class and the place where the docs live — you don't instantiate it, you go straight to whichever algorithm class you actually want. 🫶

🦋 DESCRIPTION 🦋

So like… CHI is out here doing the whole persistent caching thing, right? Different quest entirely. Cache::Ref is the opposite energy: it does in-memory caching, built first and foremost for sharing references that live in memory. No disk, no drama. 💅

And it's not one single algorithm — it's a whole little collection of classes implementing a bunch of semi related algorithms. Pick your fighter. 👑

✨ METHODS ✨

  • get @keys — Pull entries out of the cache. Give it keys, it gives you stuff back.
  • hit @keys — Promote @keys in the cache. Same effect as get except it literally does not return anything — it's the "yes queen, you're still relevant" nudge, no payload. 🎀
  • set $key => $value — Adds an entry to the cache.
  • compute $key, sub { ...; return $value } — Calls get with $key. If there's a hit, boom, you get the value back. If not, the code block runs to compute the value, and the result gets stored in the cache using set. Iconic little lazy-eval moment. 🔥
  • remove @keys — Remove specific entries from the cache, before they'd normally expire.
  • expire $x — Removes $x many entries from the cache. Hopefully the entries it removes are the most useless ones. 🤞 $x defaults to 1.
  • clear — Empty the cache. Gone. Ghosted. 💀

👑 ALGORITHMS 👑

🍓 FIFO

This one is a simple FIFO queue: a set puts the element on the head of a queue, and if the size gets too big, an element gets discarded from the tail of the queue. First in, first out, no exceptions, no favorites.

Cache::Bounded provides similar behavior, but its flushing happens periodically and in bigger numbers. So performance will be better on very high cache usage, when hits don't matter that much.

This implementation has the lowest memory overhead, thanks to how simple its data structures are — literally just a hash and an array. 🌱

Its expiry policy is appropriate for when the data set has a high locality of reference, and random access is generally confined to neighbors, as a part of some larger scan.

For truly random access, cache hit rates will suffer. 😭

Long term utility of cache entries is not considered at all, so scans will poison the cache.

Fun fact bestie: this is the only algorithm for which get (and hit) has no side effects. Everyone else is out here mutating state on a read. 🙈

🌈 LRU

This implementation uses an LRU list of entries (two implementations are provided for trading off memory for speed).

Long term utility of cache entries is not considered at all, so scans will poison the cache.

Cache::Ref::Util::LRU::List

  • Uses a doubly linked list to perform MRU propagation.
  • Faster than Array.
  • Cache hits and LRU removal is O(1).

Cache::Ref::Util::LRU::Array

  • Generally slower for a cache size bigger than about 10 elements, but uses less memory due to the compact layout.
  • Cache hits are O(cache size). LRU removal is O(1).

🧚 CLOCK

This is an implementation of second chance FIFO, using a circular buffer.

Second chance FIFO is a very simple approximation of LRU. The CLOCK algorithm has its origins in Multics' virtual memory paging implementation. History nerd moment. 📜

It's slightly more general purpose than FIFO when dealing with random access.

Long term utility of cache entries is not considered at all, so scans will poison the cache.

Using values of k bigger than 1 (the default), more accurate approximations of LRU can be made, at the cost of more complicated expiry.

🎀 GCLOCK

Tries to approximate LFU instead of LRU.

Cache hits increment a counter by one, instead of resetting it to the constant k.

Cache replacement decays existing counters just like CLOCK.

⭐ CAR

CLOCK with Adaptive Removal.

A self tuning cache that varies between approximations of LRU and LFU expiry.

Has the highest memory overhead of all the implementations, because of the extent of the metadata it maintains. 😮💨

However, this overhead is still small for when sizeable objects are involved.

Resistent to cache poisoning when scanning. 💪

💜 CART

CAR with temporal filtering.

Like CAR, but it does not promote a cache entry to the long term usefulness set due to frequent successive access.

This is probably the most general purpose algorithm. Like, if you don't know which one to pick, bestie… 👀

🫶 SEE ALSO 🫶

🌟 VERSION CONTROL 🌟

<http://github.com/nothingmuch/Cache-Ref>

🌸 AUTHOR 🌸

Yuval Kogman

This software is copyright (c) 2010 by Yuval Kogman.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.

And that's the whole page, bestie — this doc shipped with perl v5.32.0, dated 2021-01-07, filed under Cache::Ref(3pm) in the User Contributed Perl Documentation. Go forth and cache responsibly. 💅✨

📦 where this page comes from