Sunday, August 06, 2017

Avoiding intermediate copies in std::accumulate

std::accumulate makes a ton of copies internally. In fact it's 2x the size of the number of elements in the iterator range. To fix, use std::ref and std::reference_wrapper for the initial state. std::shared_ptr is also a possibility if the accumulated state must be dynamically allocated for some reason. Live code on wandbox.

Update: Please see alternative solutions in the comments section.

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <functional>

struct Vector : public std::vector<int> {
  Vector(std::initializer_list<int> il) : std::vector<int>(il){
    std::cout << "Vector(std::initializer_list)\n";
  }
  Vector() {
    std::cout << "Vector()\n";
  }
  Vector(const Vector &v) : std::vector<int>(v) {
    std::cout << "Vector(const Vector &)\n";
  }
  Vector & operator = (const Vector &v) {
    if (this != &v) {
      std::vector<int>::operator=(v);
      std::cout << "Vector& Vector::operator=(const Vector &)\n";
    }
    return *this;
  }
  Vector & operator = (Vector && v) {
    if (this != &v) {
      std::vector<int>::operator=(std::move(v));
      std::cout << "Vector& Vector::operator=(Vector&&)\n";
    }
    return *this;
  }
  Vector(Vector&& v) : std::vector<int>(std::move(v)) {
     std::cout << "Vector(Vector&&)\n";
  }
};

void copy_accumulate(Vector &v) {
    Vector v2 = std::accumulate(v.begin(), v.end(), Vector(), 
                    [](Vector & v, int i) {
                      v.push_back(i);
                      return v;
                    });
    std::cout << "size of v2 = " << v2.size() << "\n";
}

void nocopy_accumulate(Vector &v) {
    Vector init;
    Vector v2 = std::accumulate(v.begin(), v.end(), std::ref(init), 
                    [](std::reference_wrapper<Vector> v, int i) {
                      v.get().push_back(i);
                      return v;
                    });
    std::cout << "size of v2 = " << v2.size() << "\n";
}

int main()
{
    Vector v { 1, 2, 3, 4 };
    copy_accumulate(v);
    std::cout << "=============\n";
    nocopy_accumulate(v);
}

4 comments:

MR said...

try this one
void copy_accumulate(Vector &v) {

Vector v2 = std::accumulate(v.begin(), v.end(), Vector(),
[](Vector & v, int i)->Vector& {
v.push_back(i);
return v;
});
std::cout << "size of v2 = " << v2.size() << "\n";
}

Anonymous said...

Because std::accumulate is intended for numeric accumulators, so copy worth nothing with them.

Anonymous said...

void copy_accumulate(Vector& v) {
Vector v2 = std::accumulate(v.begin(), v.end(), Vector(),
[] (Vector& v, int i) {
v.push_back(i);
return std::ref(v);
});
std::cout << "size of v2 = " << v2.size() << "\n";
}

Sumant Tambe said...

Good alternative solutions. Thanks folks!