Factorio Forums

Zaflis wrote:

pleegwat wrote:Doesn't work if you're actually destroying entities outside their own update call though, because you may end up swapping an entity which acted this cycle with one which has not.

Not if you iterate the vector from end to beginning. Some pseudo if you wanted to make particle system:

Code: Select all

for (p = PCount-1; p >= 0; p--)
  particle[p].DealWithIt()
  particle[p].life--
  if particle[p].life <= 0 then
    PCount--
    particle[p] = particle[PCount]
    particle.deleteLast()
  end
end

What you get is every single particle is dealt with exactly once on every loop, and deleting one means just one swap operation with the last. On the downside the list won't keep the original order. It is only a problem if you need sorting. But on a free list of entities that doesn't sound like being the case. In case of particles aswell the order doesn't matter.

std::vector<Entity*> active_entities;

void step_all_active() {
  for (size_t n = active_entities.size()-1; n >= 0; n--) {
    Entity *&slot = active_entities[n];
    slot->step();
    if (!slot->is_active()) {
      slot = active_entities.back();
      active_entities.pop_back();
    }
  }
}

void SomeDerivedEntity::step() {
  // ... do some updating...
  if (do_we_need_to_make_another_entity_active) {
    Entity &other_entity = the_other_entity;
    if (!other_entity.is_active()) {
      other_entity.set_active(true);
      active_entities.push_back(&other_entity);
    }
  }
}

ikarikeiji wrote:

Zaflis wrote:

pleegwat wrote:Doesn't work if you're actually destroying entities outside their own update call though, because you may end up swapping an entity which acted this cycle with one which has not.

Not if you iterate the vector from end to beginning. Some pseudo if you wanted to make particle system:

Code: Select all

for (p = PCount-1; p >= 0; p--)
  particle[p].DealWithIt()
  particle[p].life--
  if particle[p].life <= 0 then
    PCount--
    particle[p] = particle[PCount]
    particle.deleteLast()
  end
end

What you get is every single particle is dealt with exactly once on every loop, and deleting one means just one swap operation with the last. On the downside the list won't keep the original order. It is only a problem if you need sorting. But on a free list of entities that doesn't sound like being the case. In case of particles aswell the order doesn't matter.

+1 to this. You can also append something to the vector without any trouble. Actual workable C++:

Code: Select all

std::vector<Entity*> active_entities;

void step_all_active() {
  for (size_t n = active_entities.size()-1; n >= 0; n--) {
    Entity *&slot = active_entities[n];
    slot->step();
    if (!slot->is_active()) {
      slot = active_entities.back();
      active_entities.pop_back();
    }
  }
}

void SomeDerivedEntity::step() {
  // ... do some updating...
  if (do_we_need_to_make_another_entity_active) {
    Entity &other_entity = the_other_entity;
    if (!other_entity.is_active()) {
      other_entity.set_active(true);
      active_entities.push_back(&other_entity);
    }
  }
}

Gymble wrote:Except that in this case the added entity will not be processed during the current pass.

mensinda wrote: Have you considered using PLF Colony (http://plflib.org/colony.htm)? PLF Colony is an unordered container that basically has most benefits of std::vector (memory locality) and std::list (O(1) insert and remove).

mensinda wrote:

kovarex wrote: Actually, one possibility could be to have a vector of ActiveEntity poitners and remove from it by switching with the last one. The entity would know the index of its position in the vector. This way you still have O(1) removal, instead of 2 pointers, you have 1 index, and you only have to touch one entity when removing, not the 2 neighbours.

Have you considered using PLF Colony (http://plflib.org/colony.htm)? PLF Colony is an unordered container that basically has most benefits of std::vector (memory locality) and std::list (O(1) insert and remove).

I recommend the website and this video: https://www.youtube.com/watch?v=wBER1R8YyGY for mor information.

Zulan wrote:Here's the same measurements from an somewhat older AMD A10-7850K:

Artman40 wrote:Are these 2% improvements cumulative rather than separate, unlike mining productivity upgrades?

PacifyerGrey wrote:Zulan you should definitely get purple

TheTom wrote:

Zulan wrote:Here's the same measurements from an somewhat older AMD A10-7850K:

Can someone try that on a current ZEN core?

Rseding91 wrote:

Rakshasa wrote:You guys are using... linked lists?...

Why, oh why do you use linked lists? It is supposed to be common knowledge that in almost all situations even a straight vector is better.

At the very least something like C++'s deque would be better.

Tell me how you'd get: O(1) time to turn an entity on/off and use a vector to maintain which entities are active and allow an entity to go active/inactive during the update loop as you iterate active entities.

You can't have them all By using a linked list with the entity itself being the link you have O(1) time to turn any entity on/off and can iterate all active entities while still allowing other entities to go active/inactive during the update loop - you can't do that with a vector as mutating the vector while iterating isn't allowed.

As with virtually everything programming: you can't use absolutes - as you said "in almost all situations" -> this isn't one of them

update_list.erase(std::remove_if(update_list.begin(), update_list.end(), [=](Entity* e){e->update(performance);return !e->needsUpdateNextTick();}, update_list.end());

rgx wrote:Since we are still on the subject of linked lists (with full address to neighbours stored in the objects), an advantage is that it allows entities to be moved in memory, with small (or no) changes to the simulation code. So if the problem is that entitiies are misaligned and randomly scattered in memory, the active entities (around 100 MB out of several GB perhaps) can be moved to one, contiguos block. And they can be ordered in the order that they are accessed during the simulation. This process could be automated, much like defragmentation of a disk.

Zulan wrote:Here's the same measurements from an somewhat older AMD A10-7850K:

prefetch_amd_kaveri.png

It's about twice as slow as the Skylake. Prefetching still helps very well, although not quite to the extent of current Intel architectures.

I don't think the prefetching hint is as specific and uarch-dependent as the non-temporal stores. Even if the hardware prefetcher already does a good job, there would only be tiny overhead from extra redundant instructions. Now it's impossible to exclude some weird interactions within the uarch. So yes, benchmarking is the best way to go .

bobucles wrote:When multiplying and dividing extremely specific floating point decimals there is a very good chance you'll accumulate a "drift" from tiny rounding errors (reason number 907.0000000000000156 to hate floats). Why not use a simple list of zoom values? Or at least snap the zoom level when it should hit an integer.