Parallel Command Pattern

Question

I wanted to know of how to make my use of the command pattern thread-safe while maintaining performance. I have a simulation where I perform upwards of tens of billions of iterations; performance is critical.

In this simulation, I have a bunch of Moves that perform commands on objects in my simulation. The base class looks like this:

class Move
    {
        public:
            virtual ~Move(){}

            // Perform a move.
            virtual void Perform(Object& obj) = 0;

            // Undo a move.
            virtual void Undo() = 0;
    };

The reason I have the object passed in on Perform rather than the constructor, as is typical with the Command pattern, is that I cannot afford to instantiate a new Move object every iteration. Rather, a concrete implementation of Move would simply take Object, maintain a pointer to it and it's previous state for when it's needed. Here's an example of a concrete implementation:

class ConcreteMove : public Move
    {
        std::string _ns;
        std::string _prev;
        Object* _obj;
        ConcreteMove(std::string newstring): _ns(newstring) {}            


        virtual void Perform(Object& obj) override
        {
            _obj= &obj;
            _prev = obj.GetIdentifier();
            obj.SetIdentifier(_ns);
        }

        virtual void Undo()
        {
            _obj->SetIdentifier(_prev);
        }
    };

Unfortunately, what this has cost me is thread-safety. I want to parallelize my loop, where multiple iterators perform moves on a bunch of objects simultaneously. But obviously one instance of ConcreteMove cannot be reused because of how I implemented it.

I considered having Perform return a State object which can be passed into Undo, that way making the implementation thread-safe, since it is independent of the ConcereteMove state. However, the creation and destruction of such an object on each iteration is too costly.

Furthermore, the simulation has a vector of Moves because multiple moves can be performed every iteration stored in a MoveManager class which contains a vector of Move object pointers instantiated by the client. I set it up this way because the constructors of each particular Concrete moves take parameters (see above example).

I considered writing a copy operator for Move and MoveManager such that it can be duplicated amongst the threads, but I don't believe that is a proper answer because then the ownership of the Move objects falls on MoveManager rather than the client (who is only responsible for the first instance). Also, the same would be said for MoveManager and responsibility of maintaining that.

Update: Here's my MoveManager if it matters

class MoveManager
{
    private:

        std::vector<Move*> _moves;

    public:

        void PushMove(Move& move)
        {
            _moves.push_back(&move);
        }


        void PopMove()
        {
            _moves.pop_back();
        }

        // Select a move by index.
        Move* SelectMove(int i)
        {
            return _moves[i];
        }

        // Get the number of moves.
        int GetMoveCount()
        {
            return (int)_moves.size();
        }
};

Clarification: All I need is one collection of Move objects per thread. They are re-used every iteration, where Perform is called on different objects each time.

Does anyone know how to solve this problem efficiently in a thread-safe manner?

Thanks!

Answer 1

What about the notion of a thread ID. Also, why not preconstruct the identifier strings and pass pointers to them?

class ConcreteMove : public Move
{
  std::string *_ns;
  std::vector<std::string *> _prev;
  std::vector<Object *> _obj;

  ConcreteMove(unsigned numthreads, std::string *newstring)
    : _ns(newstring),
      _prev(numthreads),
      _obj(numthreads)
  {
  }

  virtual void Perform(unsigned threadid, Object &obj) override
  {
    _obj[threadid] = &obj;
    _prev[threadid] = obj.GetIdentifier();
    obj.SetIdentifier(_ns);
  }

  virtual void Undo(unsigned threadid)
  {
    _obj[threadid]->SetIdentifier(_prev[threadid]);
  }
};

Answer 2

Impossible with stated requirements. Specifically,

1. Use the command pattern. "the command pattern is a behavioral design pattern in which an object is used to represent and encapsulate all the information needed to call a method at a later time." Thus you're storing data.
2. You "can't afford" to allocate memory.
3. You have "billions" of iterations, which means some large static allocation won't suffice.

You want to store data without any place to store it. Thus there is no answer. However, if you're willing to change your requirements, there are undoubtedly many ways to solve your problem (whatever it may be -- I couldn't tell from the description.)

I also can't estimate how many Move objects you need at once. If that number is reasonably low then a specialized allocation scheme might solve part of your problem. Likewise, if most of the Move objects are duplicates, a different specialized allocation scheme might help.

In general what you're asking can't be solved, but relax the requirements and it shouldn't be hard.