samedi 29 avril 2017

Surprising results comparing time taken to copy a large collection versus in-place manipulation

I am learning functional programming and now looking at how it can be applied to C++ programming.

One of my concerns was with the performance hit using a functional style of copying values from an input list to an output list. So I created a test program which measures the performance comparing a copy to results collection and return and an in-place manipulation. I assumed that the in-place manipulation would have been faster. But that was not the case as these results testify:

copying results to a new container took: 0.0312
in place over-write and truncate took: 0.0780002

Is my experiment flawed? If so, how so? And if not, why is copying faster?

Code here.

#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>     // std::back_inserter
#include <functional>
#include <chrono>

class Timer
{
public:
    Timer() : beg_(clock_::now()) {}
    void reset() { beg_ = clock_::now(); }
    double elapsed() const {
        return std::chrono::duration_cast<second_>
            (clock_::now() - beg_).count();
    }

private:
    typedef std::chrono::high_resolution_clock clock_;
    typedef std::chrono::duration<double, std::ratio<1> > second_;
    std::chrono::time_point<clock_> beg_;
};

std::vector<int> filter_functional(const std::vector<int>& collection, std::function<bool(int)> pred)
{
    std::vector<int> results;
    auto it = std::copy_if(collection.begin(), collection.end(), std::back_inserter(results), [=](int i){return pred(i); });
    return results;
}

// will this give much better performance?
std::vector<int>& filter_cpp(std::vector<int>& collection, std::function<bool(int)> pred)
{
    // in-place so do not have to copy collection to another collection
    auto it = std::copy_if(collection.begin(), collection.end(), collection.begin(), [=](int i){return pred(i); });
    collection.resize(std::distance(collection.begin(), it));  // shrink container to new size
    return collection;
}

int main() {

    std::vector<int> coll;
    coll.reserve(10000000);
    int starter = 0;
    std::generate_n(std::back_inserter(coll), 10000000, [&](){return starter++; });

    Timer tmr;
    std::vector<int> result = filter_cpp(coll, [](int v) { return v > 100; });

    double t = tmr.elapsed();
    std::cout << "copying results to a new container took: " << t << std::endl;

    tmr.reset();

    std::vector<int> result2 = filter_functional(coll, [](int v) { return v > 100; });

    t = tmr.elapsed();
    std::cout << "in place over-write and truncate took: " << t << std::endl;
}

Aucun commentaire:

Enregistrer un commentaire