Testing the LRU Cache with QuickCheck

In the last post we implemented an LRU cache using IORef, a HashMap, and a doubly linked list. We ended that post by identifying some structural invariants we’d like to confirm hold, but realised the difficulty in doing so since the cache hides its internal state.

In this post, we’ll build a little test harness manually, and then supercharge our coverage with QuickCheck. For the complete test suite, check out the repo.

Setting Things Up

#

Everything from here builds on the project from part one, and Stack’s default layout already leaves us a place to put tests, so there isn’t much to do.

First, we’ll create a directory called test at the project root, and inside it a file called Spec.hs, where our test code will live.

Next, we tell Stack about it. The tests stanza in package.yaml names the entry point, the directory to compile, and the dependencies to build against:

tests:
  lru-cache-test:
    main:                Spec.hs
    source-dirs:         test
    ghc-options:
    - -threaded
    - -rtsopts
    - -with-rtsopts=-N
    dependencies:
    - lru-cache
    - QuickCheck

lru-cache (the name of our library) is named as a dependency since without it the suite couldn’t import Cache.

That’s the setup done. stack test now builds the library, builds the suite, and runs it. On the first run it’ll fetch and compile QuickCheck, so expect it to take a minute.

Manual Test Harness

#

With that in place, we’ll create a report function to print whether a test passed or failed and return the result:

-- Print a single test's outcome and return whether it passed.
report :: String -> Bool -> IO Bool
report name ok = do
  putStrLn ((if ok then "pass  " else "FAIL  ") ++ name)
  pure ok

Next, we’ll implement some tests for our cache implementation. Specifically, we’ll look at:

• eviction (tests the core policy)
• an access protecting from eviction (why a get mutates)
• deleting a cache’s single entry (fiddly pointer logic)

testEviction :: IO Bool
testEviction = do
  c <- createCache @String @Int 2
  addTo c "a" 1
  addTo c "b" 2
  addTo c "c" 3 -- cache full: evicts the LRU entry "a"
  a <- getFrom c "a"
  b <- getFrom c "b"
  cc <- getFrom c "c"
  report
    "adding past capacity evicts the LRU entry"
    (a == Nothing && b == Just 2 && cc == Just 3)

testAccessProtectsFromEviction :: IO Bool
testAccessProtectsFromEviction = do
  c <- createCache @String @Int 2
  addTo c "a" 1
  addTo c "b" 2
  _ <- getFrom c "a" -- touch "a": "b" is now the LRU entry
  addTo c "c" 3 -- evicts "b", not "a"
  a <- getFrom c "a"
  b <- getFrom c "b"
  report
    "getFrom promotes: a recently-read key survives eviction"
    (a == Just 1 && b == Nothing)

-- Delete the only element (head == tail): both end refs must reset to Nothing,
-- so the cache behaves as freshly empty and can be refilled.
testDeleteOnlyEntryEmptiesList :: IO Bool
testDeleteOnlyEntryEmptiesList = do
  c <- createCache @String @Int 2
  addTo c "a" 1 -- sole element: head == tail == a
  deleteFrom c "a"
  addTo c "b" 2
  addTo c "c" 3 -- from empty, fills to b/c without spurious eviction
  a <- getFrom c "a"
  b <- getFrom c "b"
  cc <- getFrom c "c"
  report
    "delete the only entry empties the list cleanly"
    (a == Nothing && b == Just 2 && cc == Just 3)

Finally, we’ll need a main function to drive our tests.

main runs each test in sequence, tallies the pass/fail results, and prints a summary:

main :: IO ()
main = do
  results <-
    sequence
      [ testEviction,
        testAccessProtectsFromEviction,
        testDeleteOnlyEntryEmptiesList
      ]
  let total = length results
      failed = length (filter not results)
  putStrLn ""
  if failed == 0
    then putStrLn ("All " ++ show total ++ " tests passed.")
    else do
      putStrLn (show failed ++ " of " ++ show total ++ " tests failed.")
      exitFailure

Let’s see if our tests pass:

$ stack test
lru-cache> test (suite: lru-cache-test)

pass  adding past capacity evicts the LRU entry
pass  getFrom promotes: a recently-read key survives eviction
pass  delete the only entry empties the list cleanly

All 3 tests passed.

100% pass — nice!

But there’s a problem.

Take testDeleteOnlyEntryEmptiesList. It’s included because we sat down and thought “what happens when head and tail are the same node?” All tests in the suite exist because we remembered to include them, but nothing tells us what we forgot to include.

To test every nook and cranny, we’ll need something more powerful. Enter QuickCheck!

QuickCheck Primer

#

Before we dive into our QuickCheck implementation, let’s take a moment to understand how it works.

From the Haskell package index Hackage:

QuickCheck is a library for random testing of program properties. The programmer provides a specification of the program, in the form of properties which functions should satisfy, and QuickCheck then tests that the properties hold in a large number of randomly generated cases.

What’s neat about QuickCheck is that its test language is embedded in Haskell, reducing the learning curve and build dependencies.

From Example-Based to Property-Based

#

QuickCheck is quite different to other test frameworks you’ve likely come across.

Rather than asserting input A produces result B, QuickCheck asserts for all inputs, this relationship holds. As a result, the way we define tests in QuickCheck is quite different too.

To define tests in QuickCheck, there are three main moving parts.

A Recipe For Random as

#

The goal of QuickCheck is to generate test cases which falsify properties of our program. To achieve this, QuickCheck defines the type Gen a to generate random values of type a.

QuickCheck also provides combinators to help generate random values of type a:

-- Pick elements at random from a non-empty list
elements :: [a] -> Gen a

-- Choose a random 'a' from within a range
choose :: Random a => (a, a) -> Gen a

-- The Int-specialised version of `choose`
chooseInt :: (Int, Int) -> Gen Int

-- Build a random-length list from a generator of elements
listOf :: Gen a -> Gen [a]

To tailor Gen a to a specific type, QuickCheck provides the Arbitrary typeclass:

class Arbitrary a where
  arbitrary :: Gen a
  shrink    :: a -> [a]
  shrink _  = []

The arbitrary function allows us to define how to generate values of type a:

data Color = Red | Green | Blue deriving (Show, Eq)

instance Arbitrary Color where
  arbitrary = elements [Red, Green, Blue]

Shrinking

#

If QuickCheck manages to falsify a property, it will try to reduce the size of the input which caused the failure, producing a minimal counterexample instead of some huge randomly generated blob.

For this purpose, QuickCheck provides the shrink function.

As seen from its type above (a -> [a]), given a value of type a, shrink will return a list of “smaller” candidates of type a. For example, the built-in instance for lists roughly shrinks by trying the empty list, then progressively shorter sublists. Int shrinks by trying 0 and values close to 0.

Building Properties

#

The final piece of the puzzle is the Property type. If Gen a and Arbitrary are about producing random test data, Property describes a testable assertion that can pass, fail, or be discarded once QuickCheck feeds it some data.

In practice, you rarely construct a Property by hand. Instead, you write an ordinary Haskell function that returns a Bool:

prop_reverseTwice :: [Int] -> Bool
prop_reverseTwice xs = reverse (reverse xs) == xs

QuickCheck turns this into a Property behind the scenes via the Testable typeclass:

class Testable prop where
  property :: prop -> Property

A function is testable as long as we can generate its argument and its result is itself testable. QuickCheck sees a function [Int] -> Bool, uses the Arbitrary [Int] instance to generate a list, applies the function, and checks the resulting Bool. Because the instance is recursive, this scales to multi-argument properties too (Int -> Int -> Bool, and so on), with each argument generated and peeled off in turn.

Sometimes a function returning Bool isn’t expressive enough, and QuickCheck provides combinators for building properties more explicitly:

-- Use a custom generator instead of Arbitrary's default
forAll :: (Show a, Testable prop) => Gen a -> (a -> prop) -> Property

For example, we can rerun the property from above against a generator of our own choosing:

-- `prop_reverseTwice` used the default `Arbitrary [Int]` generator, which
-- draws from the whole Int range. `forAll` swaps in our own instead: here,
-- lists drawn from a deliberately small pool, so the same values recur.
prop_reverseTwiceSmall :: Property
prop_reverseTwiceSmall =
  forAll (listOf (chooseInt (0, 7))) $ \xs ->
    reverse (reverse xs) == xs

In summary, Gen a, Arbitrary, and Property answer three different questions:

The Impure Cache

#

Now that we have an understanding of QuickCheck, how can we apply it to our LRU cache?

Textbook QuickCheck properties test pure functions, but our cache lives in IO, so it isn’t pure: what getFrom returns for a given key depends on every addTo, getFrom and deleteFrom that came before it.

Compare that with prop_reverseTwice. The generated list was the whole input, so generating a list was enough. For our cache, the history, rather than the key, is the major determining factor.

Therefore, rather than using QuickCheck to generate input values, we’ll use it to generate sequences of operations.

Operations as Data

#

For QuickCheck to generate random sequences of operations, we first need to represent each operation (addTo, deleteFrom, and getFrom) as a data structure, a process known as reification.

-- An operation the cache supports. QuickCheck will generate lists of these.
data Op = Add Int Int | Get Int | Delete Int
  deriving (Show)

The Model

#

To check our cache is working, we’ll define a simple associative array and some helper functions for manipulating the order of the elements in the array. This will be our known-good model:

type Model = [(Int, Int)]

-- Drop any existing entry for a key.
without :: Int -> Model -> Model
without k = filter ((/= k) . fst)

-- Mirror of `addTo`: drop any existing entry for the key, prepend the new pair
-- as most-recently-used, then truncate to capacity (dropping the LRU tail).
-- `take 0` cleanly models a zero-capacity cache, which stores nothing.
modelAdd :: Int -> Int -> Int -> Model -> Model
modelAdd capacity k v m = take capacity ((k, v) : without k m)

-- Mirror of `getFrom`: a hit returns the value and promotes the entry to
-- most-recently-used; a miss returns Nothing and leaves the model unchanged.
modelGet :: Int -> Model -> (Maybe Int, Model)
modelGet k m = case lookup k m of
  Nothing -> (Nothing, m)
  Just v -> (Just v, (k, v) : without k m)

-- Mirror of `deleteFrom`: drop any entry for the key. A miss changes nothing,
-- which is exactly `without` on an absent key (the identity). Like `Add`, a
-- delete has no observable return, so it produces no value to assert on -- a
-- later `Get` is what reveals any state it corrupted.
modelDelete :: Int -> Model -> Model
modelDelete = without

Since we need Model to be obviously correct at a glance, we can define it as [(Int, Int)] to keep things simple. Even though this is much slower than our cache implementation, the Model is only for testing purposes.

Generating Op Sequences

#

For QuickCheck to generate sequences of Ops, we must make it an instance of the Arbitrary typeclass. This means implementing arbitrary and shrink.

Defining arbitrary and shrink

#

To keep interesting states reachable, we’ll keep the key range small — between 0 and 7.

Also, to make sure that eviction actually fires, we’ll need to keep the cache full. To do that, we’ll add a slight bias to arbitrary in favour of the Add operation, making it run more frequently.

We also need to tell QuickCheck how to shrink an Op sequence.

When shrinking on a Get or Delete, we’ll call shrink recursively on the Int argument passed to the constructor.

shrinking an Add is analogous except we need to call shrink on both the key and value.

Here’s the complete implementation:

instance Arbitrary Op where
  arbitrary =
    frequency
      [ (3, Add <$> chooseInt (0, 7) <*> arbitrary),
        (2, Get <$> chooseInt (0, 7)),
        (2, Delete <$> chooseInt (0, 7))
      ]
  shrink (Add k v) = [Add k' v' | (k', v') <- shrink (k, v)]
  shrink (Get k) = Get <$> shrink k
  shrink (Delete k) = Delete <$> shrink k

Defining The Property

#

Now we come to the meat and potatoes of QuickCheck — defining the property we want to hold.

Since we have two caches (the real one and a Model), the property is simply that they never disagree. Concretely, we replay the same generated sequence of Ops against both, and check that every value our LRU cache hands back is the value the Model predicts.

Two things stand between us and writing that down: choosing a capacity, and getting IO into a Property.

Generating Cache Capacity

#

The capacities we choose matter just as much as the Op sequences, since a cache of 8 and a cache of 800 replaying identical operations behave very differently.

So we’ll specify the capacity generator ourselves:

-- Small capacities -- including 0 -- so eviction is actually exercised.
-- `chooseInt` yields a Gen Int; `fromIntegral` narrows it to the Word8
-- that `createCache` expects.
genCapacity :: Gen Word8
genCapacity = fromIntegral <$> chooseInt (0, 8)

A range of 0 to 8 covers the degenerate zero-capacity cache, the capacity = 1 cache where head and tail are the same node, and enough headroom that some sequences fill the cache while others never do.

This raises another key insight — in property testing, the generator is part of the specification. A wide generator doesn’t necessarily test more, because it may spend its budget on cases that never reach the interesting code.

From IO to Property

#

Every function our cache exposes returns IO something, but a Property is a pure description of an assertion. Test.QuickCheck.Monadic bridges the gap:

-- Collapse a monadic property back into an ordinary Property
monadicIO :: Testable a => PropertyM IO a -> Property

-- Lift an IO action so its result is usable inside the property
run :: Monad m => m a -> PropertyM m a

-- Check a Bool at this point in the sequence
assert :: Monad m => Bool -> PropertyM m ()

PropertyM IO is a do-block in which real IO and assertions can be interleaved. run lifts each cache call into it, assert checks a Bool at a chosen point, and monadicIO hands the finished block back to QuickCheck as a Property.

Replaying the Sequence

#

Putting everything together, the property creates a cache, then walks the operation list, threading the Model alongside it:

prop_matchesModel :: [Op] -> Property
prop_matchesModel ops =
  forAll genCapacity $ \capacity -> monadicIO $ do
    cache <- run (createCache @Int @Int capacity)
    let cap = fromIntegral capacity :: Int
        go _ [] = pure ()
        go model (Add k v : rest) = do
          run (addTo cache k v)
          go (modelAdd cap k v model) rest
        go model (Get k : rest) = do
          let (expected, model') = modelGet k model
          actual <- run (getFrom cache k)
          assert (actual == expected)
          go model' rest
        go model (Delete k : rest) = do
          run (deleteFrom cache k)
          go (modelDelete k model) rest
    go [] ops

Some things to point out:

• ops is an ordinary function argument generated for us by the Arbitrary Op instance we defined earlier.
• capacity comes through forAll, since we picked our own generator rather than relying on Arbitrary.
• go is a fold in disguise. It carries the model as its accumulator, starts from the empty model with go [] ops, and for each operation does the same two things: perform it on the real cache, and perform its mirror image on the model.

Why Assert on Get Only?

#

If you look closely at the code above, you’ll notice that only the Get branch calls assert.

addTo and deleteFrom both return (), so there’s no result to compare. Get is the cache’s only observable output, and so it’s the only place an assertion can live.

Running It

#

Alright, let’s take our property for a spin.

QuickCheck runs a property with quickCheckResult, which prints its own report and hands back a Result. isSuccess boils that down to a Bool:

-- Run the property and fold its outcome into the hand-rolled harness.
-- `quickCheckResult` prints its own report; `isSuccess` extracts pass/fail.
testModelMatchesReference :: IO Bool
testModelMatchesReference = do
  putStrLn ""
  putStrLn "QuickCheck -- cache vs. reference model:"
  passed <- isSuccess <$> quickCheckResult prop_matchesModel
  let verdict = if passed then "agrees" else "disagrees"
  report ("cache " ++ verdict ++ " with the reference model on random op sequences") passed

Because testModelMatchesReference returns IO Bool like every other test, it drops straight into main alongside them:

      [ testEviction,
        testAccessProtectsFromEviction,
        testDeleteOnlyEntryEmptiesList,
        testModelMatchesReference
      ]

Now we can run it:

$ stack test
lru-cache> test (suite: lru-cache-test)

pass  adding past capacity evicts the LRU entry
pass  getFrom promotes: a recently-read key survives eviction
pass  delete the only entry empties the list cleanly

QuickCheck -- cache vs. reference model:
+++ OK, passed 100 tests.
pass  cache agrees with the reference model on random op sequences

All 4 tests passed.

One hundred random sequences, and the cache agreed with the model on every Get.

Taking a Closer Look

#

Everything looks good, but unfortunately, a passing property tells us nothing about what it covered.

Suppose we’d drawn keys from the whole Int range instead of chooseInt (0, 7), and capacities in the thousands instead of chooseInt (0, 8). Two operations would essentially never touch the same key and the cache would never fill up. No overwrites, no promotions, no evictions. Same passing property, but nothing actually tested.

That’s worth defending against, and QuickCheck gives us classify to do just that.

-- Tag a test case with a label when a condition holds
classify :: Testable prop => Bool -> String -> prop -> Property

-- Apply a Property modifier from inside a monadic property
monitor :: Monad m => (Property -> Property) -> PropertyM m ()

classify cond "tag" labels a test case with "tag" whenever cond is True, and monitor is how we reach a Property combinator from inside our PropertyM IO do-block. Used together in the replay loop, they flag the whole test case whenever an interesting state was reached at least once during the sequence:

        go model (Add k v : rest) = do
          let present = isJust (lookup k model)
          monitor (classify (not present && cap > 0 && length model == cap) "add evicts the LRU entry")
          monitor (classify present "add overwrites an existing key")
          run (addTo cache k v)
          go (modelAdd cap k v model) rest
        go model (Get k : rest) = do
          let (expected, model') = modelGet k model
          monitor (classify (isJust expected) "get hits")
          monitor (classify (isNothing expected) "get misses")
          actual <- run (getFrom cache k)
          assert (actual == expected)
          go model' rest
        go model (Delete k : rest) = do
          monitor (classify (isJust (lookup k model)) "delete removes a present key")
          run (deleteFrom cache k)
          go (modelDelete k model) rest

Note that we ask the model, not the cache, whether something interesting happened, since the model is the thing we trust.

The eviction tag is the one worth reading twice. not present && cap > 0 && length model == cap says this key is new, the cache holds at least one thing, and it is already full. That’s the condition under which an Add must throw something away.

One more tag goes outside the loop, since capacity is fixed for the whole sequence:

    monitor (classify (cap == 0) "capacity 0")
    go [] ops

Now QuickCheck reports the distribution alongside the result:

$ stack test
lru-cache> test (suite: lru-cache-test)

QuickCheck -- cache vs. reference model:
+++ OK, passed 100 tests:
56% get misses
31% delete removes a present key
30% add overwrites an existing key
28% get hits
17% add evicts the LRU entry
13% capacity 0
pass  cache agrees with the reference model on random op sequences

Roughly 1/6 sequences pushed the cache past capacity and forced a real eviction. 3/10 overwrote a key that was already present, exercising the promote-on-overwrite path. 1/8 ran against a zero-capacity cache, the degenerate case we deliberately left in genCapacity.

It also shows us where the suite is thinner than we might like. Twice as many sequences contain a miss as contain a hit, which is what you’d expect when eight possible keys compete for at most eight slots that start empty.

So whenever a property passes, ask what it actually reached before you trust it. classify turns that from a hunch into a number.

Breaking Things

#

Let’s see what happens if we break something.

We’ll comment out tail patching in the cache’s promote function:

promote :: Cache k v -> Node (k, v) -> IO ()
promote cache node = do
  mTop <- readIORef cache.listHead
  case mTop of
    Nothing -> pure ()
    Just topNode -> do
      ns <- neighbours node
      -- when (isNothing ns.after && isJust ns.before) (writeIORef cache.listTail ns.before)
      moveToHead node topNode
      writeIORef cache.listHead (Just node)

Commenting out this line means that if node is the current tail and is being promoted, the cache tail will still point to node after it’s been promoted.

Re-running the tests:

$ stack test
lru-cache> test (suite: lru-cache-test)

pass  adding past capacity evicts the LRU entry
FAIL  getFrom promotes: a recently-read key survives eviction
pass  delete the only entry empties the list cleanly

QuickCheck -- cache vs. reference model:
*** Failed! Assertion failed (after 36 tests and 17 shrinks):    
[Add 5 0,Add 0 0,Get 5,Add 1 0,Add 2 0,Get 0]
3
FAIL  cache disagrees with the reference model on random op sequences

2 of 4 tests failed.

Let’s diagram out what’s happening:

capacity 3

Add 5 0   HEAD -> [5] <- TAIL

Add 0 0   HEAD -> [0] <-> [5] <- TAIL

Get 5     HEAD -> [5] <-> [0]
                   ^       ^
                   |       +-- the real tail now
                   +-- TAIL still points here

Add 1 0   HEAD -> [1] <-> [5] <-> [0]
                           ^       ^
                           |       +-- still the real tail
                           +-- TAIL

Add 2 0   len 3 = cap, so evictLRU drops whatever TAIL points to: [5]
          HEAD -> [2] <-> [1] <-> [0]
                           ^       ^
                           |       +-- the model dropped this one
                           +-- TAIL, patched to [5]'s before

Get 0     cache -> Just 0     model -> Nothing     assertion fires

It seems our Model and tests are working as expected.

Back to the Invariants

#

Part one ended with four invariants to check, and pointed out that none of them can be asserted on directly due to encapsulation. Now that the suite exists, we can say what becomes of each.

• Size agreement — While we can’t check this directly, we can observe eviction firing at the wrong moment. If len is lower, the cache will hold more than it should, and if it’s higher, the cache will discard something it should have kept. Either way a later Get disagrees with the model.
• Capacity — The model enforces this in the take capacity of modelAdd. If our cache holds one entry too many, it’ll return Just where the model says Nothing — a similar failure to the one we’ve just seen.
• Endpoints — Both ends Just when non-empty, the head with no prev and the tail with no next. A stale end pointer (the bug we planted earlier) is invisible at rest, but it decides which key gets evicted. The error then appears as a wrong getFrom answer.
• Reachability — If a node falls out of the chain but stays findable in the map, evictLRU will throw away a different entry than it should, causing a later Get to disagree.

What This Doesn’t Catch

#

Our suite is good, but there are some things it doesn’t check:

• Corruption that never changes an answer — If a pointer is wrong but no later operation depends on it, nothing fails. This is the price we pay for testing through the front door.
• The final state — Since we assert only on Get, a sequence ending in Add or Delete doesn’t check what that last operation did.
• Concurrency — As mentioned in part one, these operations aren’t atomic.
• Scale — We set a cache capacity limit of 8, and use QuickCheck’s default size for sequences. We haven’t checked the cache is still correct after a million operations, or that it doesn’t leak.

None of these make the suite worthless, but together they give it a known shape.

What’s Next

#

And that’s it for LRU!

As a learning exercise, we’ve implemented our cache imperatively rather than purely, and we’ve verified our implementation by building testing infrastructure with QuickCheck. What’s even better is we can reuse a good deal of our testing code for our next replacement policy implementation.

So what’s next? FIFO, or first-in-first-out, where entries leave in the order they arrived, and nothing that happens in between changes that.

We’ll also explore Bélády’s anomaly, where increasing the size of the cache doesn’t necessarily increase the number of hits.