16
\$\begingroup\$

I have an Entity class that can be either dead or alive.

I store entities contiguously in a resizable array. During an update(), some alive entities can become dead, and some new entities can be added at the end of the array.

The range [0 .. size) contains all non-newly-created entities.

The range [size .. sizeNext) contains all newly-created entities (guaranteed to be alive).

After update(), I call refresh(). This function does:

  • Swap around entities making sure that all alive entities are stored contiguously at the beginning of the array (and that all dead entities are stored contiguously at the end of the array).

  • Deinitialize all dead entities.

  • Update size and sizeNext.

Basically, the algorithm uses two iterators:

  • iD moves from left to right, looking for dead entities.

  • iA moves from right to left, looking for alive entities.

When iD and iA find an entity, the entities are swapped and the iterators advance.

Here's a quick drawing of the algorithm:

Algorithm drawing

And here's the current code:

void refresh()
{
    // `sizeNext` is unsigned - copy it as a signed value
    // to store its initial value and compare it to integers.
    const int intSizeNext(sizeNext);

    // `iD` walks from left to right, looking for dead entities.
    // `iA` walks from right to left, looking for alive entities.
    int iD{0}, iA{intSizeNext - 1};

    do
    {
        // Find dead item from left
        for(; true; ++iD)
        {
            // No more dead items
            if(iD > iA) goto finishRefresh;

            if(isDeadAt(iD)) break;
        }

        // Find alive item from right
        for(; true; --iA)
        {
            // No more alive items
            if(iA <= iD) goto finishRefresh;

            if(isAliveAt(iA)) break;
        }

        assert(isDeadAt(iD) && isAliveAt(iA));
        std::swap(items[iD], items[iA]);
        assert(isAliveAt(iD) && isDeadAt(iA));

        // Advance both iterators
        ++iD; --iA;
    }
    while(true);

    finishRefresh:
    for(iA = iA - 1; iA >= 0; --iA) 
    {
        assert(isAliveAt(iA));
    }

    msize = sizeNext = iD;

    for(; iD < intSizeNext; ++iD)
    {
        assert(isDeadAt(iD));
        deinitAt(iD);
    }
}
  • Can the code be improved/optimized?
  • Can the goto instructions be avoided?
  • Is there a more efficient algorithm that achieves the same results?

Full code is here.

\$\endgroup\$
11
\$\begingroup\$

You could probably use std::remove_if instead of your algorithm. Take this example code:

std::vector<std::string> vec = { "0", "1", "5", "0", "3", "6", "0", "1" };
std::remove_if(std::begin(vec), std::end(vec), [](const std::string& val)
{
    return val == "0";
});

for (auto&& a: vec)
{
    std::cout << a << ' ';
}

I get the following output:

1 5 3 6 1 0 0 0

std::remove_if swaps the elements of a range so that the elements that are to be kept are at the beginning of the range and maintains their order. The elements that are still at the end have unspecified values, but if Entity is an RAII class, the deinitialization will happen at destruction. Since I don't know what Entity looks like, I can't be sure that this method will work, but there is probaby a way to ensure that it will do what you need it to do.

This method has two advantages: it allows to think in term of iterators instead of sizes and it uses an already existing algorithm. In your case, refresh could probably look like this:

void refresh()
{
    std::remove_if(std::begin(entities), std::end(entities),
                   [](const Entity& ent)
                   {
                       return ent.isDead();
                   });
}

Once again, I am assuming some implementation details that are not shown though. Anyway, try check whether std::remove_if coud be used to do what you want it to do. Standard algorithms can often do much more things than thought.

\$\endgroup\$
  • 1
    \$\begingroup\$ I considered std::remove_if, but I'm pretty sure it would not be as efficient because it doesn't know that alive entities are more likely to be at the end of the array. \$\endgroup\$ – Vittorio Romeo Oct 22 '14 at 10:41
  • \$\begingroup\$ @VittorioRomeo did you actually measure it? \$\endgroup\$ – rightfold Oct 22 '14 at 14:30
  • 1
    \$\begingroup\$ remove_if moves far too many objects around, @VittorioRomeo idea looks better. \$\endgroup\$ – Surt Oct 22 '14 at 16:11
  • 2
    \$\begingroup\$ @Surt: With move semantics in play I am not sure that is going to be a real problem. Both algorithms are linear O(n). Before I use a specialized hand written function like this I would definitely need to see it profiled to prove that it provides a real excessive benefit over std_remove_if(). The code maintenance cost over a year probably out-way any run-time gains in the same period (depending on where this is in the code). \$\endgroup\$ – Martin York Oct 22 '14 at 16:16
  • 1
    \$\begingroup\$ @Surt: Move semantics makes move a very efficient operation. This is a perfect example of premature optimization. Show that it is worth while (and significantly worth while (over a year how much time will it save)). Is this time critical? None of these questions have been answered. \$\endgroup\$ – Martin York Oct 22 '14 at 16:39
6
\$\begingroup\$

I'll start out by thanking you for the pretty pictures, I always appreciate a question with pretty pictures :)

I can only really comment on the gotos, and, well, is there any reason that a function wouldn't work? That, alongside a bool isFinished, that you set to true afterwards, and then check for it in order to break out of the while.

do
{
     // Find dead item from left
    for(; true; ++iD)
    {
        // No more dead items
        if(iD > iA)
        {
             finishRefresh();
             isFinished = true;
             break;
        }

        if(isDeadAt(iD)) break;
    }
    if(isFinished) break;

    // Find alive item from right
    for(; true; --iA)
    {
        // No more alive items
        if(iA <= iD)
        {
             finishRefresh();
             isFinished = true;
             break;
        }

        if(isAliveAt(iA)) break;
    }

    if(isFinished) break;

    assert(isDeadAt(iD) && isAliveAt(iA));
    std::swap(items[iD], items[iA]);
    assert(isAliveAt(iD) && isDeadAt(iA));

    // Advance both iterators
    ++iD; --iA;
}
while(true);
}

void finishRefresh()
{
    for(iA = iA - 1; iA >= 0; --iA) 
    {
        assert(isAliveAt(iA));
    }

    msize = sizeNext = iD;

    for(; iD < intSizeNext; ++iD)
    {
        assert(isDeadAt(iD));
        deinitAt(iD);
    }
}

Of course, there might be a better way than this, but none are coming to mind right now.

\$\endgroup\$
2
\$\begingroup\$

You did count the number of objects you killed off didn't you? else now is the time!

void FixUp(int lastLiving) {
    // ToDo guard with ifdef with test for debug.
    for(int iA= lastLiving; iA >= 0; --iA) {
        assert(isAliveAt(iA));
    }

    msize = sizeNext = lastLiving+1;

    for(; lastLiving< intSizeNext; ++lastLiving) {
        assert(isDeadAt(lastLiving));
        deinitAt(lastLiving);
    }
}

void refresh(int numOfDead) {
    // `sizeNext` is unsigned - copy it as a signed value
    // to store its initial value and compare it to integers.
    const int intSizeNext(sizeNext);

    // `iD` walks from left to right, looking for dead entities.
    int iD{0}, iA{intSizeNext - 1};

    // Find dead item from left 
    // only need to check up to the number of none-dead
    for(; ID < intSizeNext-numOfDead+1; ++iD) {
        if(isDeadAt(iD)) {
            // find alive
            for (; isDeadAt(iA); --iA);   

            assert(isDeadAt(iD) && isAliveAt(iA));
            std::swap(items[iD], items[iA]);
            assert(isAliveAt(iD) && isDeadAt(iA));
            --iA;

            // assumption the living outnumber the dead greatly
            // if not move FixUp down after the loop and delete the test.
            if (0 == (--numOfDead)) {
               FixUp(ID);
               return;
            }
        }
    }
}

After writing this I think its more effective for lists where relative few are dead compared to the living to make a deadList and then itereate over that, all others must be alive.

vector<int> deadList; // add dead nodes to this.

void refresh(int numDead) {
    int iA{intSizeNext - 1};

    for (auto dead: deadList) {
        // check if dead is after deadZone
        if (dead > intSizeNext-numOfDead)
            continue;  // no need to do anything

        // find alive
        while (isDeadAt(iA))
            --iA;

        assert(isDeadAt(dead) && isAliveAt(iA));
        std::swap(items[dead], items[iA]);
        assert(isAliveAt(dead) && isDeadAt(iA));
        --iA;

    }
    FixUp(iA);
}

Run time O(dead) which should be much less than O(n);

\$\endgroup\$
2
\$\begingroup\$

If only a relatively small number of entities change state per update, it might be more efficient to keep the live entities contiguous all the time. That is, you'd:

  • maintain a single size variable, storing the current number of live entities;

  • when a new entity is born, increment size and add the new entity to the array at position size-1;

  • when an entity dies, decrement size, replace the dead entity in the array with the live entity at index size (unless that was the entity that died), and immediately de-initialize the dead entity (or add it to a separate queue of dead entities to be de-initialized later).

Alternatively, if you wish to maintain a pool of dead entities for reuse (or just to de-initialize later), you can modify the method slightly to also keep them in a contiguous block at the end of the array:

  • when an entity at index i dies, decrement size and swap the entities at indices i and size;

  • when a new entity is born, either reuse the formerly dead entity at index size, or (if entities are not reusable) replace the dead entity at index size (if any) with a new live entity, and append the dead entity to the end of the array instead.

Of course, this requires entities (or at least the code handling them) to know where they are located in the array. There are various ways to implement this, but the simplest way (at least if you know that each entity belongs to a single array) is just to include the array index as one of the entity's properties. Also, of course, when you move entities around in the array, you will also need to remember to update their stored indices.

The advantage of this method is that you'll never need to scan the array looking for dead entities. You may also be able to simplify other code, if you can always be sure that all entities below size in the array are alive.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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