Purity, laziness, and stupid compiler tricks

So now we have a pointer sized (on x86-32 Linux anyway), type-safe concurrenc ry primitive in our MVar<T>. I'm going to add an additional operation, and we're going to talk about the ramifications.

First, we need to add it to ptrmvar32:

  template<typename F>
  void* pure_modify(F f)
  {
    uintptr_t curr;
    while(1) {
      curr = m_val;
      if( curr == 0 )
      {
        if( __sync_bool_compare_and_swap(&m_val, 0, 1) )
          futex_wait(&m_val, 1);
      } else if( curr == 1 ) {
        futex_wait(&m_val, 1);
      } else {
        void *new_val = f(reinterpret_cast<void*>(curr & ~1));
        if( __sync_bool_compare_and_swap(&m_val, curr, new_val) )
           break;
      }
    }
  }

We're going to add this to the type-safe version as well before we get into it, so don't worry if this looks confusing.

private:
  template<typename F, typename V>
  struct AdapterF
  {
    F f;
    std::auto_ptr<V>* mem;
    void* operator()(void *in)
    {
      V r = f(*static_cast<V*>(in));
      mem->reset(new V(r));
      return static_cast<void*>(mem->get());
    }
  };

public:
  template<typename F>
  T pure_modify(F f)
  {
    std::auto_ptr<T> mem;
    AdapterF<F,T> adapter;
    adapter.f = f;
    adapter.mem = &mem;
    m_impl.pure_modify(adapter);
    return *mem.release();
  }

Because this is C++, there is some noise with regards to memory management, but it should be pretty clear what this new operation does. It takes the current value of the MVar, applies a function to the value, and returns a new value tha t is put into the MVar. Now, the analogous operation for Haskell is modifyMVar/m odifyMVar_. Interestingly the type of the function that the Haskell modifyMVar t akes is

  a -> IO a

This is because Haskell's modifyMVar has semantics more like the following:

  template<typename F>
  T haskell_modify(F f)
  {
     T val = take();
     struct ValRestorer {
        T val;
        bool restore;
        MVar<T> *self;
        ~ValRestorer() { if(restore) self->put(val); }
        ValRestorer(T val_, MVar<T> *self_) : val(val_), self(self_),
        restore(true) {}

        void Dismiss() { restore = false; }
     } restorer(val, this);
     T new_val = f(val);
     put(new_val);
     restorer.Dismiss();
  }

In other words, Haskell's modify is to make the update transactional in the face of exceptions in the modifying code. To properly use modify, you have to ma ke sure all the threads take from the mvar before they put to it.

I called attention to the type of modifyMVar earlier, and also by naming my m ethod pure_modify. As should be obvious from the code, the user supplied functio n may be called many times (although we hope it isn't in the common case). In Ha skell, the user supplied function would have to have the type

a -> a

This is wonderful! Wonderful because we can actually express it. Among other things, we know the user supplied function won't take any other locks for instan ce, so modification is deadlock free. The other great thing, is that we can feel comfortable calling it as many times as we need, because beign a pure function the observable effect is that it atomically modified the value in the MVar.

Often when we think about purity and how it enables laziness (or is it the ot her way around?), we think in terms of functions being called less often (someti mes we even think laziness implies automatic memoization, this is not the case, and if you think about the memory usage you'll quickly realize why). But here, w e can leverage the same properties of pure code to spend less time blocked or wa iting, and hopefully, in the common case waste less CPU time.

Finally, see if you can see what classic "lock-free programming" bug I've int roduced into this code (or bugs? There's at least one) by adding this pure_modif y operation.