So you may know about the “erase, remove_if” method of removing elements from a vector. Looks like this:
std::vector<int> v{0,1,2,3,4,5,6,7,8,9,10};
//remove all even values from v
v.erase( std::remove_if(v.begin(), v.end(), [](auto i)->bool {
if (i % 2 == 0) return true;
return false;
}), v.end());This operation is an order-preserving operation, and “slow” if we don’t care about preserving the order. To remove stuff from an array quick, without preserving the order, you may have heard of something called, swap-remove. That’s when we swap the removed item with the last element of the array, and then throw away that last element. Really, there is no reason to do a swap, and instead can just do a move as follows:
void remove(std::vector<int>& v, std::size_t index){
v[index] = std::move(v.back());
v.pop_back();
}This is super fast as there is just a single copy involved, and no array shifting.
In case you are unfamiliar with std::move, it’s always better than an assign when you plan to throw the right value away, like we do with pop_back. Moving is different from assignment in that it tries to copy as many pointers as possible rather than doing deep copies of values pointed-to by pointers. Normally an array assignment would involve creating a new array, iterating over it and assigning values. Move is just going to grab the assign array’s pointer and a few other members, such as size, and be done with it. After a move, the old object is supposed to be in a discarded state.
To translate this function into the “erase, remove_if” style, I’ve come up with the following:
template<typename T, typename Compare>
void fast_remove_if(std::vector<T>& v, const Compare compare) {
if (!v.size()) return;
typedef typename std::vector<T>::value_type* ValuePtr;
ValuePtr i = &v.front();
ValuePtr last = &v.back();
while (i <= last) {
if (compare(*i)) {
while ( last != i && compare(*last) ) {
--last;
}
if( last != i ) //do not move self into self, crash
*i = std::move(*last);
--last;
}
++i;
}
v.resize(last + 1 - &v[0]);
}This is what MSVC2019’s implementation of remove_if looks like
template <class _FwdIt, class _Pr>
_NODISCARD _FwdIt MVC2019_std_remove_if(_FwdIt _First, const _FwdIt _Last, _Pr _Pred) { // remove each satisfying _Pred
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
_UFirst = _STD find_if(_UFirst, _ULast, _Pass_fn(_Pred));
auto _UNext = _UFirst;
if (_UFirst != _ULast) {
while (++_UFirst != _ULast) {
if (!_Pred(*_UFirst)) {
*_UNext = _STD move(*_UFirst);
++_UNext;
}
}
}
_Seek_wrapped(_First, _UNext);
return _First;
}Basically, once an element is found to removed, the entire rest of the array gets shifted, that’s what’s slow.
In figuring out how these functions compare, I had to write out unit tests. It turns out that the swap method becomes faster and faster as the amount of elements to be removed is reduced, while they start to become similar in speed as the number of elements to be removed is increased. Another issue with the standard function is that speed is affected by where the first element to be removed is located and the total length of the array, the worst case scenario being index 0, causing the entire rest of the array to be shifted. If the index to be removed is the end of the array, the speeds are similar.
This sort of fast_remove_if is useful in programs such as games or simulations where you can have an array of objects which needs to be managed, but without caring about their order, or so I had thought. I had figured it would be faster, though after doing tests, I’m unsure if its really so much to brag about. I guess it would depend on the actual data in the array and the remove comparison. I haven’t tested it on any real-application data yet, TBD.
Here are my speed results and unit test code:
Given 19730 objects, with a randomly selected amount to remove.
Results for fast_remove_if:
- one percent of objects: 80 avg micro
- varying percent of objects: 122 avg micro
Results for erase, std::remove_if
- one percent of objects: 99 avg micro
- varying percent of objects: 123 avg micro
Now I realize these results are in microseconds and both functions are finishing really fast, though I think this will vary depending on the object properties during std::move. The swap function seems to always be faster. As it is, fast_remove_if is more than 20% faster at 1% of values to be removed.
#include "pch.h"
#include "CppUnitTest.h"
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
#include <vector>
#include <algorithm>
#include <functional>
#include <chrono>
#include <random>
namespace UnitTestFastRemoveIf
{
template <class _FwdIt, class _Pr>
_NODISCARD _FwdIt MVC2019_std_remove_if(_FwdIt _First, const _FwdIt _Last, _Pr _Pred) { // remove each satisfying _Pred
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
_UFirst = _STD find_if(_UFirst, _ULast, _Pass_fn(_Pred));
auto _UNext = _UFirst;
if (_UFirst != _ULast) {
while (++_UFirst != _ULast) {
if (!_Pred(*_UFirst)) {
*_UNext = _STD move(*_UFirst);
++_UNext;
}
}
}
_Seek_wrapped(_First, _UNext);
return _First;
}
template<typename T, typename Compare>
void fast_remove_if(std::vector<T>& v, const Compare& compare) {
if (!v.size()) return;
typedef typename std::vector<T>::value_type* ValuePtr;
ValuePtr i = &v.front();
ValuePtr last = &v.back();
while (i <= last) {
if (compare(*i)) {
while ( last != i && compare(*last) ) {
--last;
}
if( last != i ) //do not move self into self, crash
*i = std::move(*last);
--last;
}
++i;
}
v.resize(last + 1 - &v[0]);
}
TEST_CLASS(UnitTestFastRemoveIf)
{
class TestObject {
public:
bool remove{ false };
int i{ 8 };
float k{ 2 }, a{ 1 };
double d{ 99.99 };
int i2{ 81 };
float k2{ 21 }, a2{ 11 };
double d2{ 991.99 };
int i3{ 80 };
float k3{ 20 }, a3{ 10 };
double d3{ 990.990 };
};
typedef std::vector< TestObject> TestObjects;
TestObjects mTestObjects;
std::size_t mObjectCount{ 19730 };
std::mt19937 mRandGenerator;
std::size_t mNumTrials{ 200 };
std::function<bool(TestObjects::value_type) > removeTest{ [](auto obj)->bool {
return obj.remove;
} };
void setupTest(std::size_t trial, int objectPercent =0) {
mTestObjects.clear();
mTestObjects.resize(mObjectCount, TestObject());
double p = objectPercent ? objectPercent / 100.0f : ((float(trial+1) / float(mNumTrials)) );
std::size_t objectsToSet = mTestObjects.size() * p;
std::uniform_int_distribution<std::size_t> range(0, mTestObjects.size() - 1);
while (objectsToSet > 0) {
std::size_t i = range(mRandGenerator);
//to speed things up, if the index is already selected, scan back or forth for an index to set
int direction = i % 2 == 0 ? -1: 1;
while (mTestObjects[i].remove == true && i > 0 && i < mTestObjects.size()-1 ) {
i += direction;
}
if (mTestObjects[i].remove == false) {
mTestObjects[i].remove = true;
--objectsToSet;
}
}
}
public:
template<typename Test>
auto performTest(Test test,int objectPercent=0, std::size_t seed = 0) {
mRandGenerator = std::mt19937(seed);
std::chrono::microseconds total(0);
for (std::size_t i = 0; i < mNumTrials; ++i) {
setupTest(i, objectPercent);
auto startTime = std::chrono::steady_clock::now();
test();
auto endTime = std::chrono::steady_clock::now();
total += std::chrono::duration_cast<std::chrono::microseconds>(endTime - startTime);
}
total /= mNumTrials;
return total;
}
public:
TEST_METHOD(TestMethod_STD)
{
auto result = performTest([&]() {
mTestObjects.erase(std::remove_if(mTestObjects.begin(), mTestObjects.end(), removeTest), mTestObjects.end());
}, 1 );
Logger::WriteMessage(std::string("one percent of objects: " + std::to_string(result.count()) + "\n").c_str());
result = performTest([&]() {
mTestObjects.erase(std::remove_if(mTestObjects.begin(), mTestObjects.end(), removeTest), mTestObjects.end());
});
Logger::WriteMessage(std::string("varying percent of objects: " + std::to_string(result.count()) + "\n").c_str());
}
TEST_METHOD(TestMethod_FAST)
{
auto result = performTest([&]() {
fast_remove_if(mTestObjects, removeTest);
}, 1 );
Logger::WriteMessage( std::string( "one percent of objects: " + std::to_string(result.count()) + "\n").c_str());
result = performTest([&]() {
fast_remove_if(mTestObjects, removeTest);
});
Logger::WriteMessage(std::string("varying percent of objects: " + std::to_string(result.count()) + "\n").c_str());
}
};
}
Spot C++ 