Composable Blocking Transactions

Background: Software Transactional Memory (STM) is a foundation for atomic composable non-blocking transactions. An STM transaction consists of a set of variables and a monadic sequence of read/write operations on those variables. As the transaction progresses, a transaction table is constructed detailing the specific variables to be modified. At the end of the transaction, either the changes are written atomically (that is, none of the intermediate modifications are visible to the outside world), or the transaction is aborted as though nothing had happened.

Blocking-transactions is an alternative library that implements atomic transactions using locks. This library is strictly less expressive than STM, but does have some advantages.

First, I will demonstrate why such a library is even possible. In order to implement a blocking transaction, we must:

  1. Sort all of the variables that could participate in the transaction.
  2. Sieze a lock on each variable in sorted order.
  3. Perform the transaction.
  4. Release all of the locks.
  5. Notify any waiting threads that the variables have been modified.

Acquiring locks in sorted order guarantees that the program can not deadlock. Acquiring a lock effectively acquires the exclusive right to acquire any greater-ordered locks before any thread that has acquired a lesser-ordered lock.

None of this is possible unless we know the entire set of variables before the transaction takes place. In traditional models of computation, this is impossible. However, arrows provide an environment of restricted flow control in which all computations are either inevitable or in which there is a finite set of branches. The StaticArrow is an example of an Arrow that can do this.

It is also possible to build a monad with similarly restricted flow control. If the side-effectful operations of a monad always return an opaque value (meaning that there is no function that can transform the value or any combination of values into a boolean) then no flow control within the monad is possible.

Such a library has a profound limitation: although we can store a transactional variable inside another transactional variable, we can not retrieve it without considerable contortions. Blocking transactions therefore do not seem to be suitable for working with complex graphs of transactional variables.

On the other hand, the restricted flow control that blocking transactions require presents an unexpected opportunity: transactions can be made inevitably lazy. A lazy transaction completes in the time it takes to entangle the variables in a system of unevaluated thunks. This means that the locks are held for the shortest time possible, but increases the CPU time needed to complete the entire program.

These systems of unevaluated thunks constitute a potentially hazardous memory leak. I choose to write the library in such a way that each variable is forced after the transaction completes, by means of a parallel spark.

This is not the only strategy for evaluating a transaction. We could also choose to:

  • Allow values to be forced within the transaction, but locks could be held while an expensive and unimportant computation completes. We would then want a strategy to release unneeded locks early, but this would add overhead.
  • Sequentially force each variable after the transaction, but this was not efficient in the benchmark.
  • Specify a per-variable strategy for forcing each variable, but this is adds complexity with little apparent benefit.
  • Tolerate the memory leak on the assumption that the caller must manually force the contents of the transaction, but this had catastrophic implications for performance in the benchmark.

Note that the blocking transactions library at the moment is not exception safe.

My implementation is available as a git repository. You can also link directly to the source code and a simple benchmark.

$ git clone http://www.downstairspeople.org/git/blocking-transactions.git/

Paintable User Interfaces

It seems like it should be possible to have some kind of GUI library in which user interface elements can be painted onto the screen frame-by-frame, instead of the common practice of assembling an object-oriented hierarchy of widgets.

I’m thinking of something like (rough ECMA-like pseudocode):


static var clicks = 0;

drawRectangle( 0, 0, 100, 100)
drawText( 0, 50, "This button has been clicked " + clicks + " times" )
drawClickListener( 0, 0, 100, 100, function() { clicks++ } )

Now we should be able to wrap this “button” inside affine transformations and clipping operations. We would call and draw the button during each frame of animation, and the button would cease to exist on the first frame in which it stopped being called.

I’m not looking for a revolutionary GUI paradigm; I just want the ability to do some specific, weird effects when the situation calls for it. For example, a car driving by with a clickable button on it’s side. If the button is behind a tree in the same scene, then it shouldn’t be click-able.

In fact, ideally, drawing user interface elements would use the same path as drawing visible shapes, but would pass in an event handler instead of a color or fill pattern. I could even imagine that there would be one or more channels of callback information alongside the RGB channels.

This is in the category of “things that I can’t possibly be the first person to think of but haven’t actually ever seen done.”

FactoryArrow

I’ve been playing around with an Arrow concept, which to my knowledge is original. I’ve decided to call this a FactoryArrow:


newtype FactoryArrow m n a b = FactoryArrow { runFactory :: m (Kleisli n a b) }

Where m and n are Monads. m is a single-pass initialization monad, while n is a multiple-pass working monad. The arrow supports all of the standard accessory arrow typeclasses, including ArrowLoop if n implements MonadFix, and ArrowApply if m and n are the same.

This arrow simply captures a two-phase initialize-and-run design pattern.

To the best of my imagination, there cannot be a corresponding useful FactoryMonad. I would be extremely interested if anyone can contradict me on that point.

My current interest is in using the FactoryArrow as a replacement for the mealy-style arrows by using IORefs (or potentially even STM transaction variables) to store automaton states instead of unevaluated thunks.

The corresponding implementation as of the time of this writing.

Vec is Good

Last night I checked out Scott E. Dillard’s Vec library. It’s a good, fast, pure implementation of the basic matrix operations applicable to 3D graphics. Switching to Vec has shaved off quite a bit of time from one of my demo apps and relieved me of the need to maintain my own matrix manipulation code, which was causing me repeated headaches.

It’s very heavy with MPTCs, fundeps, and type families, which will cause ghc to render some pretty inane error messages, but if you’re already accustomed to this then it’s actually very straightforward to use.

Trends in Profiling Haskell

I spent some time yesterday profiling roguestar. I do this every few months just to see where things stand, and there are always two culprits at the top of roguestar-gl.prof, every single time:

* typeclass dictionary lookups in inner loops
* Rational

In the first case, I think the simplest solution is to INLINE the puppy. Can the ghc inliner be a little bit more aggressive when it sees dictionary lookups? Inliners are tricky business. I’m not sure I see a simple heuristic. Vaguely: leaf functions that require dictionary lookups need to be specialized.

Rational can sneak into an unsuspecting program through realToFrac, and absolutely *kills* performance.

I sit down thinking to myself, “Ok, today I’m going to streamline my Super Mumbo Jumbo Widget and get 15% faster performance,” or some such goal I set for myself. And I run the profiler and 75% of my time is being spent in fromRational . toRational.