Trying to reduce memory allocations, what are the tricks to overloading operators?

Question

I have written out my class with overloaded operators but I am trying to reduce the amount of memory allocations (as shown by valgrind on Linux). I understand that in certain instances that the copy constructor is called to make a local copy of an object for the function but I'm unsure which situations. As it stands I'm making a new object in each case so I feel that I could get away with ridding some of the "new" calls if I were to make use of the already copied pieces. Below are my operator+ and operator+= for reference.

// ---------------------------------------------------------------------------
// operator+
// Adds two Poly objects
Poly Poly::operator+(const Poly& rhs) const {
    //case where rhs has more terms
    if (maxExponent < rhs.maxExponent) {
        Poly temp(rhs);

        for (int i = 0; i <= maxExponent; i++) {
            temp.polynomial[i] += polynomial[i];
        }

        return temp;
    }
    else {
        Poly temp(*this);

        for (int i = 0; i <= rhs.maxExponent; i++) {
            temp.polynomial[i] += rhs.polynomial[i];
        }

        return temp;
    }
}

// ---------------------------------------------------------------------------
// operator+=
// Adds and assigns two Poly objects
Poly& Poly::operator+=(const Poly& rhs) {
    *this = *this + rhs;
    return *this;
}

Here is my operator= in case the tricks depend on this:

// ---------------------------------------------------------------------------
// operator=
// Assigns a Poly object to another
const Poly& Poly::operator=(const Poly& other) {
    if (&other != this) {
        delete[] polynomial;
        maxExponent = other.maxExponent;
        polynomial = new int[maxExponent + 1];

        for (int i = 0; i <= maxExponent; i++) {
            polynomial[i] = other.polynomial[i];
        }
    }

    return *this;
}

Answer 1

In the first case, with operator+, conceptually there's not much you can do. You'll need the temporary variable and you'll have to return it by value.

In the second case instead you implementing operator+= using operator+ and therefore making a copy which is then copied within the object itself with operator=. This is extremely inefficient.

For the above reasons, often, people prefer to implement operator+= first, and then implement operator+ as:

Poly Poly::operator+(const Poly& rhs) {
    return Poly(*this) += rhs;
}

Which is the opposite of what you are doing here.

Answer 2

My solution would be to reimplement Poly class with following idea: let's make it impossible to modify field 'polynomials' and make it shared across copies of same Poly using shared_ptr. This way we can have O(1) copy operator while operator+ is still O(n) - with possibility of O(1) in optimistic case :)

Let's also use std::vector instead of table and be careful about our public interface. In return we get:

• smaller memory consumption
• no code duplication
• no need to implement copy constructor; default will work just fine :)

Forgive my sloppy implementation of operator<<. I left out implementation of optimistic case for operator+ as an exercise to the reader :).

Implemented using c++11, because I am not a masochist.

#include <memory>
#include <vector>
#include <initializer_list>
#include <iostream>

class Poly {

public:
    Poly() : polynomial_(NULL) {}

    Poly(std::initializer_list<double> il)
    {
        polynomial_.reset(new std::vector<double>(il.begin(), il.end()));
    }

    unsigned max_exp() const
    {
        return polynomial_ ? polynomial_->size() : 0;
    }

    Poly operator+(const Poly& o) const
    {
        const bool has_bigger_exp = max_exp() > o.max_exp();
        const Poly & poly_big     = has_bigger_exp ? *this : o;
        const Poly & poly_small   = has_bigger_exp ? o : *this;

        auto * tmp = new std::vector<double>(*poly_big.polynomial_);
        for (unsigned i = 0; i < poly_small.max_exp(); ++i) {
            tmp->at(i) += poly_small.polynomial_->at(i);
        }

        Poly ret_obj;
        ret_obj.polynomial_.reset(tmp);
        return ret_obj;
    }

    Poly& operator+=(const Poly& o)
    {
          *this = *this + o;
          return *this;
    }

private:

    std::shared_ptr<const std::vector<double>> polynomial_;

    friend std::ostream& operator<<(std::ostream& os, const Poly& obj);
};

std::ostream& operator<<(std::ostream& os, const Poly& obj)
{
    if (obj.max_exp() == 0) {
        os << "0" << std::endl;
        return os;
    }

    for (unsigned i = obj.max_exp()-1; i > 0; --i) {
        double param = obj.polynomial_->at(i);
        if (param != 0) {
            os << param << " * x^" << i << " + ";
        }
    }

    os << obj.polynomial_->at(0) << std::endl;
    return os;
}

int main() {

    Poly a = {1, 2, 3};
    Poly b = {4, 5};
    Poly c = a + b;
    Poly d;

    std::cout << a << b << c << d;
    a += {1, 1};
    std::cout << a;

    return 0;
}

Answer 3

The technique you are looking for is called "expression templates".

Your operator+ takes two Poly& objects, and returns a should_be_added< Poly&, Poly& >. If you add again, it returns a should_be_added< should_be_added<Poly&, Poly&>, Poly& > (or possibly should_be_added< Poly&, Poly&, Poly& > if you know things commute and you prefer things to be flat, but that is extra work).

should_be_added then has a conversion-to-Poly, or Poly has an implicit should_be_added< T, U >&& constructor (with efficient move these two are equivalent). At that point, you have at compile time the complete tree of expressions you are assigning to your Poly. With lots of work and care, you can efficiently build a single output value.

A good way to start is to start with your operator+=(Poly const& o) and operator+=(Poly&& o) and similar "mutating" operators. These primitives can make writing other operators efficiently much easier.

You probably want to write a custom Poly& operator=( should_be_added<T,U>&& src ) so that it reuses any memory in the existing Poly object. An easy way to do this is to have a method in should_be_added that says Poly result( Poly&& src ), and implement operator Poly() as operator Poly() const { return result( Poly{} ); }, and the operator= is { swap( *this, src.result(std::move(*this)) ); return *this }

Now, none of this is easy -- expression templates are medium-deep template-fu. But the result can be that you can do your mathematical expressions in a natural way, and lose next to nothing.

Note that efficient move semantics should be easy for your Poly class -- just move the internal buffer and clear the source one.