Improving Performance by Discarding Traces

Tags dejafu, haskell, programming, release notes
Target Audience Haskell programmers.

tl;dr if you don’t want all the ex­e­cu­tion traces, you might now be able to run your de­jafu tests with sev­eral thou­sand times less memory.

de­jafu leans more to­wards cor­rect­ness than per­form­ance, by de­fault. Your test cases will be ex­ecuted using the Test.De­jaFu.SCT.sct­Bounded func­tion, which is com­plete but can be slow; every result you get will have an as­so­ci­ated trace, which can be useful for de­bug­ging, but takes up memory.

de­jafu- gives you an extra knob to tweak, and makes it even bet­ter.

Dis­carding res­ults and traces (de­jafu-

Random testing before (with traces)

Random testing be­fore (with traces)

Random testing after (without traces)

Random testing after (without traces)

Full-size im­ages: be­fore, after.

Test cases with long traces have been a par­tic­u­larly bad case, as all the traces stuck around in memory until you did some­thing with them at the end (like print the bad ones). This is such a case:

con­ten­ded­MVar :: Mon­ad­Conc m => m ()
con­ten­ded­MVar = do
  threadId <- my­Th­readId
  mvar     <- newEmptyMVar

  let maxval = 150
  let go = takeMVar mvar >>= \x -> if x == maxval then kill­Thread threadId else go

  for_ [1..20] . const $ fork go
  fork $ for_ [1..maxval] (put­MVar mvar)

  takeMVar =<< newEmptyMVar

I ran that 100 times with random schedul­ing, and the traces varied from about 2500 to 3000 ele­ments long. That’s a lot of stuff to keep around in memory!

Some­times you don’t want all the res­ults or traces of your test case, you only want some of them. Now you can tell de­jafu to throw things away as it’s run­ning, al­lowing garbage col­lec­tion to kick in sooner, and re­duce the res­ident memory us­age.

There’s a new type and some new func­tions:

module Test.De­jaFu.SCT where

-- ...

-- | An @Either Failure a -> Maybe Dis­card@ value can be used to
-- se­lect­ively dis­card res­ults.
-- @since
data Dis­card
  = Dis­cardTrace
  -- ^ Dis­card the trace but keep the res­ult.  The result will ap­pear
  -- to have an empty trace.
  | Dis­cardResultAndTrace
  -- ^ Dis­card the result and the trace.  It will simply not be
  -- re­ported as a pos­sible be­ha­viour of the pro­gram.
  de­riving (Eq, Show, Read, Ord, Enum, Bounded)

-- | A variant of 'run­SCT' which can se­lect­ively dis­card res­ults.
-- @since
run­SCT­Dis­card :: Mon­adRef r n
  => (Either Failure a -> Maybe Dis­card)
  -- ^ Se­lect­ively dis­card res­ults.
  -> Way
  -- ^ How to run the con­cur­rent pro­gram.
  -> Mem­Type
  -- ^ The memory model to use for non-­syn­chron­ised @CRef@ op­er­a­tions.
  -> ConcT r n a
  -- ^ The com­pu­ta­tion to run many times.
  -> n [(Either Failure a, Trace)]

-- and: run­SCT­Dis­card', res­ults­Set­Dis­card, res­ults­Set­Dis­card', sct­Bound­Dis­card,
--      sc­tUni­form­Ran­dom­Dis­card, sct­WeightedRandom­Dis­card
-- and: de­jafuDis­card, de­jafuDis­cardIO         (Test.De­jaFu)
-- and: testDe­jafuDis­card, testDe­jafuDis­cardIO (Test.{HUnit,Tasty}.De­jaFu)

Every it­er­a­tion of the SCT loop, an Either Failure a value is pro­duced. The *Dis­card func­tion vari­ants will throw it (or its trace) away if you so tell it.

For ex­ample, you can now check that a test case doesn’t dead­lock in a far more memory-ef­fi­cient way like so:

  -- "efa" == "either failure a", dis­card everything but dead­locks
  (\efa -> if efa == Left Dead­lock then Nothing else Just Dis­cardResultAndTrace)
  -- try 1000 ex­e­cu­tions with random scheduling
  (ran­domly (mk­StdGen 42) 1000)
  -- use the de­fault memory model
  -- your test case
  -- the pre­dicate to check (which is a bit re­dundant in this case)
  ("Never Dead­locks", dead­lock­s­Never)

A much im­proved DPOR im­ple­ment­a­tion (de­jafu-

Systematic testing before (with traces)

Sys­tem­atic testing be­fore (with traces)

Systematic testing after (without traces)

Sys­tem­atic testing after (without traces)

Full-size im­ages: be­fore, after.

Un­for­tu­nately, was only a win for random test­ing, as sys­tem­atic testing ex­pli­citly con­structed the tree of ex­e­cu­tions in memory. This has been a long-standing issue with de­jafu, but I’d never gotten around to solving it be­fore, be­cause it wasn’t really any worse than what was hap­pening else­where in the code­base. But now it was the worst!

The solu­tion, in prin­ciple, was sim­ple: you can avoid con­structing the com­plete tree by in­stead ex­ploring sched­ules in a depth-first fash­ion, which means you only need a stack and some book­keeping in­form­a­tion.

The im­ple­ment­a­tion was fairly simple too! I like simple things.

So now we can check every pos­sible ex­e­cu­tion of our test case for dead­locks, still in a memory-ef­fi­cient fash­ion:

  (\efa -> if efa == Left Dead­lock then Nothing else Just Dis­cardResultAndTrace)
  -- the de­fault way is sys­tem­atic testing
  ("Never Dead­locks", dead­lock­s­Never)

It’s not as memory-ef­fi­cient as random schedul­ing, as it needs to keep around some in­form­a­tion about prior ex­e­cu­tions, but the amount it is keeping around is greatly re­duced from be­fore.

What’s next? I don’t really know. There are still a lot of memory in­ef­fi­cien­cies in de­jafu, but they all pale in com­par­ison to these two, so they can prob­ably sit for a while longer. I’d like to build a suite of bench­marks, be­cause I don’t really have any other than the test suite (which makes a poor bench­mark). If you have any test cases which de­jafu just can’t handle, let me know!

I think it’s fair to say that the fron­tiers of what de­jafu is cap­able of have been pushed back a long way by these changes.