Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
    }
}
share|improve this question
1  
"Simple generic double buffer pattern" - Now that's a mouthful. – Ethan Bierlein 18 hours ago
    
@EthanBierlein it's a very useful pattern for multi threaded systems :) – Ron 18 hours ago
    
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. – Groo 16 hours ago
    
@Groo - we use it as a "write only" buffer (list, queue, dictionary, etc) and a "read only" buffer, i.e. collecting metrics from a multi threaded environment, and periodically dumping them out. And since this pattern requires to have access both to the write and read buffer, we had to keep them public. A classic example of the double buffer design pattern usage is how video cards prevent screen tearing from occurring. – Ron 14 hours ago
1  
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. – Groo 12 hours ago

5 Answers 5

up vote 5 down vote accepted

Interlocked.Exchange(ref object, object) returns the value which had been at the location of _current and therefor can be assigned directly to Next like so

public T Swap()
{
    Next = Interlocked.Exchange(ref _current, Next);
    return Next;
}

So based on @RobH comment

The value of Next can be changed between those two lines so you still need a local copy

we should change this to

public T Swap()
{
    var swappedBuffer = Interlocked.Exchange(ref _current, Next);
    Next = swappedBuffer;
    return swappedBuffer;
}
share|improve this answer
1  
The value of Next can be changed between those two lines so you still need a local copy. – RobH 19 hours ago
1  
Just to be sure: what happens if another thread changes value of Next between var swappedBuffer = … and Next = swappedBuffer? – Kuba Wyrostek 18 hours ago
    
Then Next will have the value of swappedBuffer. – Heslacher 18 hours ago
1  
OK, isn't a scenario possible where both _current and Next end up referencing the same buffer? – Kuba Wyrostek 18 hours ago
    
This won't work. Next can easily get assigned to the same value, like @Kuba wrote. – Groo 16 hours ago

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.

share|improve this answer
    
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; } – Ron 18 hours ago
2  
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. – Kuba Wyrostek 17 hours ago
    
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. – Ben Voigt 17 hours ago

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;
        }
    }
    
share|improve this answer
    
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? – Kuba Wyrostek 15 hours ago
    
Also there is probably a typo in version 4: return _values[i & 2];. – Kuba Wyrostek 15 hours ago
    
@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). – Groo 15 hours ago
    
Oh yes, right, sorry. :) – Kuba Wyrostek 15 hours ago
    
@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). – Groo 15 hours ago

The revised code is also not thread-safe. Although, I suppose as long as you limit its usage to exactly the cases where it would work then you could sort of make that claim. But I suspect that the lock in Swap is pointless in those cases anyways.

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

writer1: writeBuf1 = doubleBuf.WriterBuffer;
writer1: ...start writing data to writeBuf1...
   ...writer2 interrupts writer1 thread...
writer2: writeBuf2 = doubleBuf.WriterBuffer;  // writeBuf1 and 2 point to same place
writer2: ...start write data to writeBuf2... // writer2 and 1 data is mixed
share|improve this answer

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.WriterBuffer; writer1: ...start writing data to writeBuf1... ...writer2 interrupts writer1 thread... writer2: writeBuf2 = doubleBuf.WriterBuffer; // 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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