Alternatives to Optional Types in Multithreaded C++ Environments

cinterfacesmultithreading

I'm making an MPMC queue in C++, and I would like to find out what the best interface for a try_dequeue method would be (I'm not concerned about its implementation). I'd like to provide a method which does not block if the queue is empty (like my dequeue() method does), but somehow notifies this to the caller.

While I provide a bool empty() const method as well, this unfortunately does no good because for a multithreaded queue doing something along the lines of if(!queue.empty()) queue.dequeue(); provides no guarantees.

What I currently have is T try_dequeue(), which throws an exception if the queue is empty. This seems to offer the most intuitive interface, but an empty queue is hardly an exceptional situation, and that seems an awful lot like using exceptions for control flow.

Another option would be bool try_dequeue(T* t), which would write to t only if the queue was not empty and return if t was written to. After using the exception method above, this seems probably least intrusive, but it would require that T is both default-constructible (or in some manner trivially constructible, so the caller can do T t; queue.try_dequeue(&t);) and assignable.

I wouldn't want to force those requirements on T, though, so perhaps a Java-like approach such as optional<T> try_dequeue() is in order. One of the minor issues with this is that I'd have to implement my own (can't use boost). Perhaps more importantly, it makes the interface seem bloated, in the sense that now I'm now dragging another type in where it would (hopefully) be avoidable, and, much like the situation with STL's set::insert requires us to copy a pair, then "unfold" its arguments, it forces the user into clumsy, long ritual that has to be repeated every time he or she uses the function.

Perhaps I'm worrying too much about optional<T>'s usability, given that it doesn't have any of the more serious problems that the other two approaches do, but I'm wondering, what would be the best approach here? Is it the optional one?

Edit: It occurred to me that there's also a bit of an outlandish bool try_dequeue(std::function<void(T&)>) option which actually seems pretty nice (in fact this one will actually have the most minimal interface you can have, where there's no need for any external logic setting a local T to the returned value). Unfortunately I'd prefer to avoid the overhead incurred by calling an actual std::function, and using a template function template<class F> bool try_deque(const F&) isn't an option either since this is a derived class (from a generic queue interface).

Best Answer

As long as the task is not to design a 100% generic lib for each and every case, only a queue for types "T" under your teams control, I would prefer the bool try_dequeue(T* t) approach, or even better bool try_dequeue(T& t) (since T* t must never be NULL). By this design, the usage will typically look like this:

  T t;
  if(try_dequeue(t))
  {
     // do something  with t;
  }

and the implementation will look like this:

  bool try_dequeue(Type &t)
  {
      // ... make things thread-safe
      // ... return false if queue is empty
      // ... find index to your storage array
      t=queueStorage[foundIndex];
      // ... remove element at "foundIndex" from "queueStorage"
      return true;
  }

This imposes some requirements on your type T: it will need a "simple" (probably parameterless) ctor, and it needs a "copy assignment operator". A copy constructor won't be enough. For many real-world types, these requirements are easy to fulfill (especially when they are under your control). Note, that according to the rule of three it is most times good idea to implement not only a user defined copy ctor alone, so if your current type T has only such a copy ctor, consider to add a copy assignment operator as well.

Related Topic