Investigate and possibly implement some form of concurrency support.

[alecthomas]

Currently, any support for concurrency relies solely on the user.

Possibly something like this, with read-only "copies" of the entities and a stream of operations that are applied. Unsure.

[alecthomas]

Here's a mock of a potential API implementing a transactional system.

A transaction encapsulates mutation of entity state.

• The EntityManager itself does not have any (public) operations for
  mutating entities.
• Retrieving components from a transaction returns a read-only reference.
• tx.mutate(component.attribute) schedules a modification of an attribute.
• Mutations after deletion are ignored.
• Transactions are thread-safe.
• It might be best to merge all transactions back in one sweep. This would be a) more efficient and b) thread safe (I'm not sure how else I would allow commits and still keep reads safe).

When a transaction is committed all modified components are merged back into the EntityManager.

int main() {
  EntityManager em;
  syd::async([&em]() {
    EntityManager::Transaction tx = em.begin();

    // Update position.
    for (auto &cursor : tx.components<Position, Direction>()) {
      const Position &position = cursor.component<Position>();
      const Direction &direction = cursor.component<Direction>();

      // Update position.
      tx.mutate(position.position) += direction.direction;
    }

    tx.commit();
  });

  std::async([&em]() {
    EntityManager::Transaction tx = em.begin();

    // Remove out of bounds objects.
    for (auto &cursor : em.components<Position>()) {
      const Position &position = cursor.component<Position>();

      if (visible(position)) continue;

      // Create particle at original entity location.
      Entity particle = tx.create();
      particle.assign_from_copy<Position>(position);
      particle.assign<Particle>(particle_definition);

      // Destroy original entity.
      tx.destroy(cursor.entity());
    }

    tx.commit();
  });
}

[skyrpex]

This looks so interesting. Any update on this?

[alecthomas]

I started experimenting with it (non-working sample code here), but didn't really have time to fully flesh it out. It felt a bit like the extra complexity might result in a more complicated API and possibly slower code, but that was just an intuitive reaction.

[alecthomas]

The biggest issue I ran into was how to deal with conflict resolution. If you have two threads concurrently modifying a component you can either a) detect that a conflict occurred and resolve it somehow or b) just take the last modification. a) would come with not-insignificant performance penalties and b) could result in data loss. Neither of these options are really desirable.

A third option is to choose b) but check and abort if a conflict occurs only when in debug mode.

PS. This is basically a form of Software Transactional Memory.

[skyrpex]

Nice... you got some black magic in that gist. I've been thinking a bit on this. My C++ template understading and transaction systems are quite limited, but anyway...

What if you must tell the transaction which components are you going to edit? It could be interesting using this along with std::optional (currently, std::experimental::optional).

int main() {
  EntityManager em;
  syd::async([&em]() {
    // Start a transaction that will potentially edit position components.
    // This could be a good place to look for other active transactions
    // that are editing the same components.
    auto tx = em.begin<Position>();

    // Gather cursor entities with Position and Direction components.
    for (auto &cursor : tx.components<Direction>()) {
      // Do not use const & so it creates a writable copy.
      Position position = cursor.component<Position>();
      const Direction &direction = cursor.component<Direction>();

      // Update position.
      position.position += direction.direction;

      // Assign position. Internally, it could use std::experimental::optional to know
      // if a component is edited or not.
      cursor.assign<Position>(position);
    }

    // Commit could happen at tx destruction.
    // All cursors with edited components will apply the changes now.
  });
  std::async([&em]() {
    auto tx = em.begin<Position>();
    // error is thrown (two position transactions active)...
  });
}

[alecthomas]

This approach could work, but disallowing use of the same component in different threads is not ideal. Position, for example, is likely to be used by a number of different systems, so it's very likely to collide.

[skyrpex]

But it would collide only if Position is requested as editable (requested in em.begin). If you want it to be read-only, you ask for it in tx.components.

Not sure if I'm explaining myself 🐹

[waldnercharles]

So, why not have both? Option B with debug-time assertions, and the option to have transactions that limit which components can be written to. Just throwing it out there.

[Naburimannu]

If you have two different threads trying to write to the same component, it feels to me as if you've got an architectural flaw, not something we should be adding (difficult, slow) code to handle.

For example, position. Sure, you might separate a movement system from a
physics/collision system, and put them in two different threads.

But then

1. the physics has to run after the movement to get a consistent
   world state to start with, so there's no point to multithreading them, or
2. you're double- (triple-) buffering world state, and you'll have a
   quiescence every frame to swap buffers, and you won't have write conflicts,
   or
3. the movement system should just be planning motion, updating a
   component which tracks that and is input to the physics system, which
   resolves motion and updates actual position.

[alecthomas]

@skyrpex ah, sorry, I missed that detail of your explanation. I quite like the idea, but perhaps a better interface is something like this:

// Specify by their constness which types are to be mutated...
// In this case we have read-only access to Position, and read-write access to Direction.
entities.async([](Transaction<Position, const Direction> &tx) {
  // ...
});

I ended up implementing a proof-of-concept that actually works. It doesn't implement the approach suggested by @skyrpex yet. But it does implement thread-safe, lock-free create, destroy and assign<C> operations so far, but not yet remove<C>.

It's basically CoW for each transaction; any retrieval of a mutable component first creates a copy. Parallel transactions are run in groups and merged back into the parent when all transactions in the group complete.

Caveats:

• It doesn't do any conflict checking.
• It doesn't support remove<C>.
• It uses std::experimental::optional to avoid excessive pointer creation, but can and will use a much more efficient data structure.
• The code is ugly.
• It relies on some C++14 features (notably std::get<T>(t)).
• There is no GC, ie. reuse of deleted entity slots. So memory usage will currently just grow indefinitely.
• Each transaction allocates a std::vector<std::uint32_t>(entity_count) + any transactional overhead. Aside from using an std::unordered_map<>, there isn't a good way around this that I can see.
• Iteration is not as efficient as it could be. It could simply iterate over the packed vector of components, but it currently iterates over the ID lookup table and ignores empty slots.
• It currently requires std::async. A lower level interface could be exposed to allow any threading model to be used.

I haven't done any benchmarking, but the rough approach seems fairly sound to me. Take a look and let me know what you think.

[alecthomas]

Interestingly, I just came across this article which describes a very similar system. And it also references EntityX. The circle is complete.

[reinzor]

Very interesting; any updates on this?

[alecthomas]

@reinzor Nothing beyond the prototype. In general I think the approach is sound, but my main concern is that the copying overhead is too high. Unfortunately it's impossible to definitively answer that without writing a fully functional implementation and benchmarking it. Which I unfortunately don't have time to do at the moment.

[reinzor]

Ok, thanks for your response!

[ccfreak2k]

In the interim, is it possible to achieve a level of thread safety with what's currently present in the main tree? In particular, what operations are known to be safe/unsafe? I have a multithreaded program that causes validity checks on entityx::Entity::assign() to fail at random when two different threads try to assign components to entities, which is a classic symptom of a race condition (both threads are responsible for different components, and no threads are trying to destroy components or entities, although an additional thread may be creating new entities at the same time). Without any better ideas, I'd be inclined to pass a mutex pointer to every thread and lock when modifying entities.

[alecthomas]

I don't think there's a more granular level of thread safety than what you propose in your last sentence. It might be possible to add some finer granularity with minimal effort, but I'm not sure.

[ccfreak2k]

What I mean is, which entrypoints into entityx are known to be thread safe/unsafe? Clearly anything that modifies the entity list is unsafe, but can two threads modify component members on two different entities? Without knowing exactly what operations modify which parts of the entityx internals, I have to assume that any time entityx code is called, the whole thing has to be locked first (sort of like what Linux did with the Big Kernel Lock when they added SMP support, a design choice that they spent years undoing afterwards). I'm not advocating for adding mutices to entityx, or adding anything really*; I'm just trying to get an idea of how I can set up simple thread safety without wielding a mutex like a giant hammer and losing the performance benefit of multithreading and without having to go back and revise my code, although that may be unavoidable. I'm more than willing to modify my own copy of entityx to do it as well, since git makes stashing changes and conflict resolution really easy, but I certainly wouldn't consider creating a PR for it.

* Since you seem to already have a pretty clear idea for adding concurrency. I'd considered a copy-on-write system as well, but I couldn't reconcile the problem of normalizing the entities before the next game tick. My two thoughts were each a variation of copy-back, where either modified entities were copied back into the main entity list, or the unmodified entities were copied into the secondary list and their pointers swapped before the next tick, with both seeming to be a variation of your copy-on-read idea. I thought that CoW might have been a better idea since, I assumed, that an entity was modified less frequently than it was read, but I don't have the requisite knowledge to know which would be better to use. Nevertheless, my idea in general seemed undesirable due to the memory load.

[alecthomas]

Yes I understood, but without going through every method I can't tell you which operations are thread safe. EntityX was not designed with any kind of thread safety in mind so coarse locking is the best I can suggest.

[lyubomirv]

Maybe I don't get this completely, or maybe I'm just lost. Could you please tell me whether the following is thread-safe right now (using the code from master, with no changes/mocks):

Suppose we have two systems, and none of them modifies any component's data. Here is a simple (and stupid) example:

struct CheckSystem : public System<CheckSystem> {
    void update(entityx::EntityManager &es, entityx::EventManager &events, TimeDelta dt) override {
        es.each<Position, Direction>([dt](Entity entity, Position &position, Direction &direction) {
            if(position.x == 5 && direction.x == 4)
                LOG("Allright! Position.x is 5 and Direction.x is 4.");
        });
    };
};

struct Check2System : public System<Check2System> {
    void update(entityx::EntityManager &es, entityx::EventManager &events, TimeDelta dt) override {
        es.each<Position>([dt](Entity entity, Position &position) {
            if(position.x == 3)
                LOG("Allright! Position.x is 3.");
        });
    };
};

Can the two update() methods of these systems be executed simultaneously in different threads without any issues? Assume that while those update() calls are running, no other code runs, so no entities are added/removed/changed and no components are changed too. Is this guaranteed to work? I guess, the question here is basically is only getting the components from the entities in .each<> safe to do from multiple threads?

[L3nn0x]

Yes in your case it's thread safe.