benchmark compare with native algorithm

[jt-chairman]

I use the following code to generate data:

    numArr.resize(10000);
    for (size_t i = 0; i < numArr.size(); ++i) {
        numArr[i] = i;
    }
    // discrete indices
    for (size_t i = 0; i < 1000; ++i) {
        dumpIdx.push_back(2 * i + 1);
    } 
    // continuous indices
    for (size_t i = 6000; i < 8000; ++i) {
        dumpIdx.push_back(i);
    }

then, I wrote a native erasing algorithm:

      decltype(numArr) tmp;
      size_t start = 0;
      for (size_t i = 0; i < dumpIdx.size(); ++i) {
          while (start < dumpIdx[i]) {
              tmp.push_back(numArr[start++]);
          }
          start = dumpIdx[i] + 1;
      }
      for (size_t i = dumpIdx.back() + 1; i < numArr.size(); ++i) {
          tmp.push_back(numArr[i]);
      }

Comparing the time consumption by benchmark i got:

seems that it did't speed up. Even so, I think the algorihm is elegent.

[artem-ogre]

Sorry I couldn't follow from the snippets you've shown. What do you compare to what? Maybe you could show the full benchmark code? Is the conclusion that remove_at is faster as it is right now?

[jt-chairman]

Sorry I couldn't follow from the snippets you've shown. What do you compare to what? Maybe you could show the full benchmark code? Is the conclusion that remove_at is faster as it is right now?

sorry, i jump some code. here is the whole code i used to test

#include <benchmark/benchmark.h>
#include <benchmark/export.h>

template <class ForwardIt, class SortUniqIndsFwdIt>
inline ForwardIt remove_at(
    ForwardIt first,
    ForwardIt last,
    SortUniqIndsFwdIt ii_first,
    SortUniqIndsFwdIt ii_last)
{
    if (ii_first == ii_last) // no indices-to-remove are given
        return last;
    typedef typename std::iterator_traits<ForwardIt>::difference_type diff_t;
    typedef typename std::iterator_traits<SortUniqIndsFwdIt>::value_type ind_t;
    ForwardIt destination = first + static_cast<diff_t>(*ii_first);
    while (ii_first != ii_last)
    {
        // advance to an index after a chunk of elements-to-keep
        for (ind_t cur = *ii_first++; ii_first != ii_last; ++ii_first)
        {
            const ind_t nxt = *ii_first;
            if (nxt - cur > 1)
                break;
            cur = nxt;
        }
        // move the chunk of elements-to-keep to new destination
        const ForwardIt source_first =
            first + static_cast<diff_t>(*(ii_first - 1)) + 1;
        const ForwardIt source_last =
            ii_first != ii_last ? first + static_cast<diff_t>(*ii_first) : last;
        std::move(source_first, source_last, destination);
        // std::copy(source_first, source_last, destination) // c++98 version
        destination += source_last - source_first;
    }
    return destination;
}

static std::vector<int> numArr;
static std::vector<size_t> dumpIdx;

static void deleteBySwap(benchmark::State& state) {
    for (auto _ : state) {
        auto tmp = numArr;
        tmp.erase(remove_at(tmp.begin(), tmp.end(), dumpIdx.begin(), dumpIdx.end()), tmp.end());
    }
}

static void deleteByErase(benchmark::State& state) {
    for (auto _ : state) {
        auto tmp = numArr;
        for (size_t i = 0; i < dumpIdx.size(); ++i) {
            tmp.erase((tmp.begin() + dumpIdx[i]), (tmp.begin() + dumpIdx[i] + 1));
        }
    }
}

static void directlyMove(benchmark::State& state) {
    for (auto _ : state) {
        auto tmp1 = numArr;
        decltype(numArr) tmp;
        size_t start = 0;
        for (size_t i = 0; i < dumpIdx.size(); ++i) {
            while (start < dumpIdx[i]) {
                tmp.push_back(numArr[start++]);
            }
            start = dumpIdx[i] + 1;
        }
        for (size_t i = dumpIdx.back() + 1; i < numArr.size(); ++i) {
            tmp.push_back(numArr[i]);
        }
    }
}

BENCHMARK(deleteBySwap)->Unit(benchmark::kMillisecond);
//BENCHMARK(deleteByErase)->Unit(benchmark::kMillisecond);
BENCHMARK(directlyMove)->Unit(benchmark::kMillisecond);

int main(int argc, char** argv)
{
    numArr.resize(10000);
    for (size_t i = 0; i < numArr.size(); ++i) {
        numArr[i] = i;
    }
    // discrete indices
    for (size_t i = 0; i < 1000; ++i) {
        dumpIdx.push_back(2 * i + 1);
    } 
    // continuous indices
    for (size_t i = 6000; i < 8000; ++i) {
        dumpIdx.push_back(i);
    }

    char arg0_default[] = "benchmark";
    char* args_default = arg0_default;
    if (!argv) {
        argc = 1;
        argv = &args_default;
    }

    ::benchmark::Initialize(&argc, argv);
    if (::benchmark::ReportUnrecognizedArguments(argc, argv)) return 1;
    ::benchmark::RunSpecifiedBenchmarks();
    ::benchmark::Shutdown();
    return 0;

}

function deleteBySwap use remove_at idiom.
function derectlyMove use native algorithm.
Appearently, native algorithm is faster.