8
\$\begingroup\$

I wrote a small generic implementation of a simple generic double buffer pattern, and I was wondering if it's actually thread safe or can be improved in any way.

Note: The specific part that I'm worrying about thread safety is the Swap() function.

/// <summary>
///     Simple generic double buffer implementation class
/// </summary>
public class DoubleBuffer<T> where T : class
{
    private T _current;

    public DoubleBuffer(T current, T next)
    {
        _current = current;
        Next = next;
    }

    /// <summary>
    ///     Next buffer waiting in line (no active usage should be here)
    /// </summary>
    public T Next { get; private set; }

    /// <summary>
    ///     Currently active buffer (active usage should be here)
    /// </summary>
    public T Current
    {
        get { return _current; }
    }

    /// <summary>
    ///     Swaps between the buffers
    /// </summary>
    /// <returns>Returns the buffer previously used before the swap</returns>
    public T Swap()
    {
        var swappedBuffer = _current;
        Interlocked.Exchange(ref _current, Next);
        Next = swappedBuffer;
        return swappedBuffer;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ "Simple generic double buffer pattern" - Now that's a mouthful. \$\endgroup\$ – Ethan Bierlein Oct 26 '15 at 12:04
  • \$\begingroup\$ @EthanBierlein it's a very useful pattern for multi threaded systems :) \$\endgroup\$ – Ron Oct 26 '15 at 12:15
  • \$\begingroup\$ How is this class supposed to be used? You will set current and next once, inside the constructor, and then use Swap many times to swap them? And multiple threads can call Swap simultaneously? I suppose you can only have two active threads at a single time using this? tl;dr: use a simple lock to swap these two variables, performance difference will be negligible, but you will get correctness, which is far more important. Also, exposing Current and Next and Swap publicly doesn't seem like a good idea, I would rethink how you want this class to be used. \$\endgroup\$ – Groo Oct 26 '15 at 14:22
  • 1
    \$\begingroup\$ Updates to the video frame buffer are done a single thread, the one which also swaps the buffer, so it's not an analogy you should stick to too closely. Your updated code is giving a false sense of security, because exposing these two buffers as public properties makes no guarantees about which one is being read/written to at any given moment. Any access to those properties is unsynchronized with the swap procedure, and can happen at any time inside the swap method. Also, TryEnter with timeout is unnecessary, swapping these properties only takes a couple of instructions. \$\endgroup\$ – Groo Oct 26 '15 at 18:29
  • 1
    \$\begingroup\$ @Ron-It depends on what you are trying to achieve. I'm not sure you can even write a thread-safe double buffer class if you expose the Swap method. However, you can implement code that will "behave" with your particular implementation if certain conventions are followed, but that would be a stretch to call it thread-safe. You could put a wrapper around your double buffer which is more promising. Perhaps if you give a very explicit example of something you are trying to achieve then you can get some better answers. I will be very surprised if double buffering ends up being a good solution. \$\endgroup\$ – Dunk Oct 27 '15 at 19:25
12
\$\begingroup\$

Please correct me if I am wrong, but isn't such scenario possible with accepted answer?

public T Swap()
{
    var swappedBuffer = Interlocked.Exchange(ref _current, Next); // 1
    Next = swappedBuffer; // 2
    return swappedBuffer; // 3
}

And it goes like that: (A and B denotes some object of type T):

_current = A
Next = B

Thread 1 executes Line 1: 
swappedBuffer = A
_current = B
Next = B

Thread 2 executes Line 1:
swappedBuffer = B
_current = B
Next = B

Thread 1 executes Line 2:
Next = A

Thread 2 executes Line 2:
Next = B

Now both _current and Next are references to B.

\$\endgroup\$
  • \$\begingroup\$ Good call, I think wrapping the code in Swap with a lock would solve it: public T Swap() { if (!Monitor.TryEnter(_lockObject, new TimeSpan(0, 0, 2))) { throw new Exception("Swap: Timed out waiting for lock."); } var swappedBuffer = Interlocked.Exchange(ref _writeBuffer, ReadBuffer); ReadBuffer = swappedBuffer; Monitor.Exit(_lockObject); return swappedBuffer; } \$\endgroup\$ – Ron Oct 26 '15 at 12:58
  • 2
    \$\begingroup\$ First of all: I am not sure whether my doubts are correct. Second: I am not sure whether there is any point using Interlocked.Exchange when inside critical section. \$\endgroup\$ – Kuba Wyrostek Oct 26 '15 at 13:05
  • \$\begingroup\$ You are correct, Interlocked.Exchange is only atomic with respect to one of the two variables being swapped. To do this lock-free, you need to use a double-word compare-exchange. \$\endgroup\$ – Ben Voigt Oct 26 '15 at 13:10
  • \$\begingroup\$ Please note that with "accepted answer" I refer to answer, that is no longer available here. \$\endgroup\$ – Kuba Wyrostek Oct 28 '15 at 9:05
7
\$\begingroup\$

I would start by making sure everything that doesn't need to be public is hidden, and then simplify the Swap method to avoid race conditions.

  1. Hide everything except the Swap method. It's not like you gain any real "safety" against incorrect usage (as everyone can cache the result of that method anyway), but at least people don't have to think twice how to use it:

    // we probably won't need the T : class constraint
    public class DoubleBuffer<T>
    {
        private T _current;
        private T _next;
    
        public DoubleBuffer(T current, T next)
        {
            _current = current;
            _next = next;
        }
    
        public T Swap()
        {
             // swap and return previous value
        }
    }
    
  2. Preferably, use a simple lock to ensure thread safety. .NET lock (i.e. Monitor) is pretty efficient for short blocks like this. If there is no contention, it's practically free. It also spinlocks for several cycles before it enters kernel mode, meaning that short blocks like this should never put the thread to sleep:

    // this is a no-brainer, simple and without race conditions
    private readonly object _lock = new object();
    public T Swap()
    {
        lock (_lock)
        {
            var previous = _current;
            _current = _next;
            _next = previous;
            return previous;
        }
    }
    
  3. If you really want to make sure you're spinlocking, you can use a SpinLock instead (slightly less readable, but nothing spectacular for a method short as this):

    public T Swap()
    {
        var spinlock = new SpinLock();
        var taken = false;
        try
        {
            spinlock.Enter(ref taken);
            var previous = _current;
            _current = _next;
            _next = previous;
            return previous;
        }
        finally
        {
            if (taken)
                spinlock.Exit();
        }
    }
    
  4. Finally, if you want to confuse your friends and code reviewers, you can go for something like this, which doesn't really swap values internally, but instead stores them inside an array and toggles the index. And since our class' interface is now simplified (only the Swap method), callers don't need to know out implementation details at all:

    public class DoubleBuffer<T>
    {
        private int _index = 1;
        private T[] _values = new T[2];
    
        public DoubleBuffer(T current, T next)
        {
            _values[0] = current;
            _values[1] = next;
        }
    
        public T Swap()
        {
            // note: _index will overflow after a bunch of calls,
            // but last bit will still be flipped correctly
            var i = Interlocked.Increment(ref _index);
            return _values[i & 1]; // bitwise '&' is cheaper than '%'
        }
    }
    
  5. Which can then be slightly generalized and extended to more than just two items (we can also call it a Pool now, although there is no way to let callers "return" objects back to the pool):

    public class Pool<T>
    {
        private int _index = 1;
        private T[] _values;
    
        public Pool(params T[] values)
        {
            if (values == null)
                throw new ArgumentNullException("values cannot be null");
    
            if (values.Length == 0)
                throw new ArgumentOutOfRangeException("values cannot be empty");
    
            _values = (T[])values.Clone(); // @Kuba's comment
        }
    
        public T Swap()
        {
            var i = Interlocked.Increment(ref _index);
            return _values[mod(i, _values.Length)];
        }
    
        // modulo which works nice with negative values
        int mod(int x, int m)
        {
            int r = x % m;
            return r < 0 ? r + m : r;
        }
    }
    
\$\endgroup\$
  • \$\begingroup\$ It is worth noting in my opinion, that, while previous implementation hold given references forever, a array that can be passed in pt. 5 (as an alternative to listing each param independently) can be modified later on by external code. Maybe it should be cloned in the constructor? \$\endgroup\$ – Kuba Wyrostek Oct 26 '15 at 15:41
  • \$\begingroup\$ Also there is probably a typo in version 4: return _values[i & 2];. \$\endgroup\$ – Kuba Wyrostek Oct 26 '15 at 15:42
  • \$\begingroup\$ @Kuba: (unless I am wrong, I am pretty tired) it should be i % 2 if using modulo, but bitwise it's i & 1 since last bit is being flipped on each increment (and this is a cheap instruction). I have just checked and it seems to be working correctly even when _index overflows (that's why I added a separate mod method in the last case also). \$\endgroup\$ – Groo Oct 26 '15 at 15:48
  • \$\begingroup\$ Oh yes, right, sorry. :) \$\endgroup\$ – Kuba Wyrostek Oct 26 '15 at 15:49
  • \$\begingroup\$ @Kuba: just noticed your first comment, yes, you're right, that would be a better thing to do (although if T is a reference type, nothing stops OP from mutating its values). \$\endgroup\$ – Groo Oct 26 '15 at 15:52
2
\$\begingroup\$

The code is definitely not thread-safe.

I quickly see 4 or 5 ways to break the example code but here's the simplest:

writer1: writeBuf1 = doubleBuf.Current;
writer1: ...start writing data to writeBuf1...
   ...writer2 interrupts writer1 thread...
writer2: writeBuf2 = doubleBuf.Current;  // writeBuf1 and 2 point to same place
writer2: ...start write data to writeBuf2... // writer2 and 1 data is mixed

There's no reason to use double-buffering for what you described.

If you want to make the class thread-safe then you'd need a Read and Write method that extracts/writes the data from/to the buffer. The buffer needs to be protected by a lock in each method. Done.

Even if you wanted to do the double buffer scheme, you'd implement in the exact same way as the single buffer method, via Read/Write methods and locking in those methods. You have to copy the buffer data, you can't ever return direct access to the class's internal buffers if you want to create a thread-safe class unless you also pass ownership along with that buffer.

\$\endgroup\$
  • 2
    \$\begingroup\$ Please don't post a second answer when you wish to add details, instead edit your post with the additional info. Since this has more info in it the other one will probably be deleted. \$\endgroup\$ – SuperBiasedMan Oct 27 '15 at 9:19
  • \$\begingroup\$ Sorry, I thought that was what I did. I must have pushed a wrong button in the process. \$\endgroup\$ – Dunk Oct 27 '15 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.