Saturday, May 07, 2011

CmdArgs - Fighting the GHC Optimiser

Summary: Everyone using GHC 7 should upgrade to CmdArgs 0.7. GHC's optimiser got better, so CmdArgs optimiser avoidance code had to get better too.

Update: Has this post scared you off CmdArgs? Read why CmdArgs is not dangerous.

CmdArgs is a Haskell library for concisely specifying the command line arguments, see this post for an introduction. I have just released versions 0.6.10 and 0.7 of CmdArgs, which are a strongly recommended upgrade, particular for GHC 7 users. (The 0.6.10 is so anyone who specified 0.6.* in their Cabal file gets an automatic upgrade, and 0.7 is so people can write 0.7.* to require the new version.)

Why CmdArgs is impure

CmdArgs works by annotating fields to determine what command line argument parsing you want. Consider the data type:


data Opts = Opts {file :: FilePath}


By default this will create a command line which would respond to myprogram --file=foo. If instead we want to use myprogram foo we need to attach the annotation args to the file field. We can do this in CmdArgs with:


cmdArgs $ Opts {file = "" &= args}


However, CmdArgs does not have to be impure - you can equally use the pure variant of CmdArgs and write:


cmdArgs_ $ record Opts{} [file := "" += args]


Sadly, this code is a little more ugly. I prefer the impure version, but everything is supported in both versions.

I am still experimenting with other ways of writing an annotated record, weighing the trade-offs between purity, safety and the syntax required. I have been experimenting with pure variants tonight, and hope in a future release to make CmdArgs pure by default.

GHC vs CmdArgs

Because CmdArgs uses unsafe and untracked side effects, GHC's optimiser can manipulate the program in ways that change the semantics. A standard example where GHC's optimiser can harm CmdArgs is:


Opts2 {file1 = "" &= typFile, file2 = "" &= typFile}


Here the subexpression "" &= typFile is duplicated, and if GHC spots this duplication, it can use common sub-expression eliminate to transform the program to:


let x = "" &= typFile in Opts2 {file1 = x, file2 = x}


Unfortunately, because CmdArgs is impure, this program attaches the annotation to file1, but not file2.

This optimisation problem happens in practice, and can be eliminated by writing {-# OPTIONS_GHC -fno-cse #-} in the source file defining the annotations. However, it is burdensome to require all users of CmdArgs to add pragmas to their code, so I investigated how to reduce the problem.

Beating GHC 6.10.4

The key function used to beat GHC's optimiser is &=. It is defined as:


(&=) :: (Data val, Data ann) => val -> ann -> val
(&=) x y = addAnn x y


In order to stop CSE, I use two tricks. Firstly, I mark &= as INLINE, so that it's definition ends up in the annotations - allowing me to try and modify the expression so it doesn't become suitable for CSE. For GHC 6.10.4 I then made up increasingly random expressions, with increasingly random pragmas, until the problem went away. The end solution was:


{-# INLINE (&=) #-}
(&=) :: (Data val, Data ann) => val -> ann -> val
(&=) x y = addAnn (id_ x) (id_ y)

{-# NOINLINE const_ #-}
const_ :: a -> b -> b
const_ f x = x

{-# INLINE id_ #-}
id_ :: a -> a
id_ x = const_ (\() -> ()) x


Beating GHC 7.0.1

Unfortunately, after upgrading to GHC 7.0.1, the problem happened again. I asked for help, and then started researching GHC's CSE optimiser (using the Hoogle support for GHC I added last weekend - a happy coincidence). The information I found is summarised here. Using this information I was able to construct a much more targeted solution (which I can actually understand!):


{-# INLINE (&=) #-}
(&=) x y = addAnn x (unique x)

{-# INLINE unique #-}
unique x = case unit of () -> x
where unit = reverse "" `seq` ()


As before, we INLINE the &=, so it gets into the annotations. Now we want to make all annotations appear different, even though they are the same. We use unique which is equivalent to id, but when wrapped around an expression causes all instances to appear different under CSE. The unit binding has the value (), but in a way that GHC can't reduce, so the case does not get eliminated. GHC does not CSE case expressions, so all annotations are safe.

How GHC will probably defeat CmdArgs next

There are three avenues GHC could explore to defeat CmdArgs:


  • Reorder the optimisation phases. Performing CSE before inlining would defeat everything, as any tricks in &= would be ignored.

  • Better CSE. Looking inside case would defeat my scheme.

  • Reduce unit to (). This reduction could be done in a number of ways:

    • Constructor specialisation of reverse should manage to reduce reverse to "", which then seq can evaluate, and then eliminate the case. I'm a little surprised this isn't already happening, but I'm sure it will one day.

    • Supercompilation can inline recursive functions, and inlining reverse would eliminate the case.

    • If GHC could determine reverse "" was total it could eliminate the seq without knowing it's value. This is somewhat tricky for reverse as it isn't total for infinite lists.





Of these optimisations, I consider the reduction of unit to be most likely, but also the easiest to counteract.

How CmdArgs will win

The only safe way for CmdArgs to win is to rewrite the library to be pure. I am working on various annotation schemes and hope to have something available shortly.

7 comments:

Don Stewart said...

Small wibble: "Because CmdArgs is impure, GHC's optimiser can manipulate the program in ways that change the semantics." -- this isn't quite right, since GHC preserves the semantics of impure programs in e.g. the IO monad.

Perhaps more precise would be: "Because CmdArgs has untracked side effects.."

Sterl said...

+1 for rewriting the library to remove unsafePerformIO. A template-haskell/quasiquotation solution would be one approach that provides an easy syntax while avoiding the unsafePerformIO pitfalls.

Neil Mitchell said...

Don: Totally correct, I've updated - describing CmdArgs as unsafe and untracked side effects.

Sterl: I've had this as a plan for a while: http://code.google.com/p/ndmitchell/issues/detail?id=334 - however, lots of people don't like using Template Haskell/QuasiQuoting, so I don't think it will ever be the default.

mornfall said...

In fact, cmdlib has been written as a pure alternative to cmdargs. The API may not be perfect but it's not too bad either, and since it's pure it is also fairly composable. Suggestions for API improvements are of course welcome.

Oren Ben-Kiki said...

Untracked side effects have other problems than fighting the optimizer. I tried invoking a "main" function using CmdArgs from a test harness and things started failing weirdly if I invoked it more than once.

Neil Mitchell said...

Oren Ben-Kiki: If you change to the style:

sample = cmdArgsMode $ Sample{hello = ... -- as before
main = print =<< cmdArgsRun sample

That should solve your problems.

Oren Ben-Kiki said...

Or, one could just use the pure version :-) The difference in syntax isn't really that bad (for my programs at least). Either way, it works.