Unexpectedly poor execution time for string concatenation function

Question

I wrote the following string concatenation function (join) to reduce the number of allocations and the time spent for constructing the final string. I also wanted to write an easy to use appending function (one-liner if possible).

size_t str_size(const char *str) {
    return std::strlen(str);
}

size_t str_size(const std::string &str) {
    return str.size();
}

template <typename T>
size_t accumulated_size(const T& last) {
    return str_size(last);
}

template <typename T, typename... Args>
size_t accumulated_size(const T& first, const Args& ...args) {
    return str_size(first) + accumulated_size(args...);
}

template <typename T>
void append(std::string& final_string, const T &last) {
    final_string += last;
}

template <typename T, typename... Args>
void append(std::string& final_string, const T& first, const Args& ...args) {
    final_string += first;
    append(final_string, args...);
}

template <typename T, typename... Args>
std::string join(const T& first, const Args& ...args) {
    std::string final_string;

    final_string.reserve(accumulated_size(first, args...));
    append(final_string, first, args...);

    return std::move(final_string);
}

I tested the join method against typical built-in C++ concatenation functionality using the operator+= and also the operator+ of the std::string class on a fairly large amount of strings. How and why is my method yielding poorer results in terms of time execution compared to the plain operator+= or operator+ approach?

I'm using the following class to measure the time:

class timer {
public:
    timer() {
        start_ = std::chrono::high_resolution_clock::now();
    }

    ~timer() {
        end_ = std::chrono::high_resolution_clock::now();
        std::cout << "Execution time: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_ - start_).count() << " ns." << std::endl;
    }

private:
    std::chrono::time_point<std::chrono::high_resolution_clock> start_;
    std::chrono::time_point<std::chrono::high_resolution_clock> end_;
};

I'm comparing the following way:

#define TEST_DATA "Lorem", "ipsum", "dolor", "sit", "ame", "consectetuer", "adipiscing", "eli", "Aenean",\
                    "commodo", "ligula", "eget", "dolo", "Aenean", "mass", "Cum", "sociis", "natoque",\
                    "penatibus", "et", "magnis", "dis", "parturient", "monte", "nascetur", "ridiculus",\
                    "mu", "Donec", "quam", "feli", ", ultricies", "ne", "pellentesque", "e", "pretium",\
                    "qui", "se", "Nulla", "consequat", "massa", "quis", "eni", "Donec", "pede", "just",\
                    "fringilla", "ve", "aliquet", "ne", "vulputate", "ege", "arc", "In", "enim", "just",\
                    "rhoncus", "u", "imperdiet", "", "venenatis", "vita", "just", "Nullam", "ictum",\
                    "felis", "eu", "pede", "mollis", "pretiu", "Integer", "tincidunt"

#define TEST_DATA_2 std::string("Lorem") + "ipsum"+ "dolor"+ "sit"+ "ame"+ "consectetuer"+ "adipiscing"+ "eli"+ "Aenean"+\
                    "commodo"+ "ligula"+ "eget"+ "dolo"+ "Aenean"+ "mass"+ "Cum"+ "sociis"+ "natoque"+\
                    "penatibus"+ "et"+ "magnis"+ "dis"+ "parturient"+ "monte"+ "nascetur"+ "ridiculus"+\
                    "mu"+ "Donec"+ "quam"+ "feli"+ ", ultricies"+ "ne"+ "pellentesque"+ "e"+ "pretium"+\
                    "qui"+ "se"+ "Nulla"+ "consequat"+ "massa"+ "quis"+ "eni"+ "Donec"+ "pede"+ "just"+\
                    "fringilla"+ "ve"+ "aliquet"+ "ne"+ "vulputate"+ "ege"+ "arc"+ "In"+ "enim"+ "just"+\
                    "rhoncus"+ "u"+ "imperdiet"+ ""+ "venenatis"+ "vita"+ "just"+ "Nullam"+ "ictum"+\
                    "felis"+ "eu"+ "pede"+ "mollis"+ "pretiu"+ "Integer"+ "tincidunt"

int main() {
    std::string string_builder_result;
    std::string normal_approach_result_1;
    std::string normal_approach_result_2;

    {
        timer t;
        string_builder_result = join(TEST_DATA);
    }

    std::vector<std::string> vec { TEST_DATA };
    {
        timer t;
        for (const auto & x : vec) {
            normal_approach_result_1 += x;
        }
    }

    {
        timer t;
        normal_approach_result_2 = TEST_DATA_2;
    }
}

My results are:

• Execution time: 11552 ns (join approach).
• Execution time: 3701 ns (operator+=() approach).
• Execution time: 5898 ns (operator+() approach).

I'm compiling with: g++ efficient_string_concatenation.cpp -std=c++11 -O3

Answer 1

operator+ has an rvalue reference left hand side std::string. The += code you wrote isn't fundamentally better than a long chain of +.

Its + can use exponential reallocation, starting around 10 or so. At a 1.5 growth factor that is about 9 allocations and reallocations.

The recursion could be confusing or slowing things down. You can fix this:

template <typename... Args>
void append(std::string& final_string, const Args&... args) {
  using unused=int[];
  (void)unused{0,(void(
    final_string += args
  ),0)...};
}

which eliminates that recursion, and similarly:

template <typename... Args>
size_t accumulated_size(const Args& ...args) {
  size_t r = 0;
  using unused=int[];
  (void)unused{0,(void(
    r += str_size(args)
  ),0)...};
  return r;
}

but, it may not be worth visiting that many strings to calculate their length to save 8 reallocations.

Answer 2

Please do not deal with strings for that.

Use string streams, or create your own StringBuilder like this one: https://www.codeproject.com/Articles/647856/Performance-Improvement-with-the-StringBuilde

Specialized string builders recommended due to its intelligent allocations management (sometimes they support list of string chunks, sometimes - prediction of growth). Allocations are hard and very time consuming operations.