3
\$\begingroup\$

I am currently in the process of learning C++. As such, I am making small programs to get more comfortable with the language. One of these programs is a small mergesort function with a basic wrapper for human-readable output and a few utility functions. I have posted this program here to get feedback on it.

I am most interested in feedback on these things (although don't hesitate to include anything else):

  1. The while loop near the end of the mergesort function in mergesort.cpp
  2. Naming conventions, primarily in the realm of capitalization. I tried to follow the standard library in this regard, but, I have seen other programs that follow a more Java-like convention. Which is preferred and why? If the Java-like conventions are preferred, why does the C++ library not follow them?
  3. Performance: specifically, are there any things I am doing blatantly wrong, but, also are there any small things I can do to improve (ie. to be more CPU cache aware or reduce register-swaps)?

Some notes:

  1. I know that using a function pointer to compare the objects to be sorted along with templates to allow for multiple object types to be sorted would be good, but, I have not yet learned templates in C++ and I see the function pointers as (correct me if I'm wrong) as only marginally useful for such a function without the ability to use any object type as the sortee.

The entirety of the source code is available on GitHub for easy viewing, cloning, etc.: https://github.com/john01dav/CPlusPlusMergeSortExample

It is also available here in accordance with the rules of this StackExchange:

mergesort.cpp:

#include <vector>

#include "vectorutils.h"
#include "mergesort.h"

using std::vector;

void mergesort(vector<int> &vec){
    //find midpoints in array
    vector<int>::size_type midpoint = vec.size() / 2;
    vector<int>::iterator midpoint_iter = vec.begin() + midpoint;

    //split main array into two subarrays
    vector<int> vector_a, vector_b;

    for(auto i=vec.begin();i!=midpoint_iter;++i){
        vector_a.push_back(*i);
    }
    for(auto i=midpoint_iter;i!=vec.end();++i){
        vector_b.push_back(*i);
    }

    //if needed, sort subarrays
    if(vector_a.size() > 1) mergesort(vector_a);
    if(vector_b.size() > 1) mergesort(vector_b);

    //merge now sorted subarrays
    vec.clear();

    vector<int>::iterator vec_a_pos = vector_a.begin();
    vector<int>::iterator vec_b_pos = vector_b.begin();

    while(vec_a_pos != vector_a.end() || vec_b_pos != vector_b.end()){ //I am especially interested in ways to improve this loop
        if(vec_a_pos == vector_a.end()){
            vec.push_back(*(vec_b_pos++));
        }else if(vec_b_pos == vector_b.end()){
            vec.push_back(*(vec_a_pos++));
        }else{
            vec.push_back(*vec_a_pos < *vec_b_pos ? *(vec_a_pos++) : *(vec_b_pos++));
        }
    }
}

mergesort.h:

#ifndef MERGESORT_H
#define MERGESORT_H

void mergesort(std::vector<int> &vec);

#endif /* MERGESORT_H */

mergesortprogram.cpp:

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>

#include "vectorutils.h"
#include "mergesort.h"

using std::cin;
using std::cout;
using std::endl;

using std::vector;

using std::srand;
using std::time;
using std::rand;

constexpr vector<int>::size_type NUMBER_COUNT = 256;
constexpr unsigned int NUMBER_RANGE = 65536;

int main(){
    vector<int> numbers_to_sort;

    srand(time(nullptr));

    for(vector<int>::size_type i=0;i<NUMBER_COUNT;i++){
        numbers_to_sort.push_back(rand() % NUMBER_RANGE);
    }

    cout << "Unsorted list: " << endl;
    print_vector(cout, numbers_to_sort) << endl << endl;

    cout << "Sorting" << endl << endl;
    mergesort(numbers_to_sort);

    cout << "Sorted List" << endl;
    print_vector(cout, numbers_to_sort) << endl;

    return 0;
}

vectorutils.cpp:

#include <iostream>
#include <vector>

#include "vectorutils.h"

using std::ostream;

using std::vector;

ostream& print_vector(ostream &out, vector<int> &vec){
    for(int n : vec){
        out << n << " ";
    }

    return out;
}

vectorutils.h:

#ifndef VECTORUTILS_H
#define VECTORUTILS_H

#include <iostream>
#include <vector>

std::ostream& print_vector(std::ostream &out, std::vector<int> &vec);

#endif /* VECTORUTILS_H */
\$\endgroup\$
4
\$\begingroup\$

Lets answer you questions first:

The while loop near the end of the mergesort function in mergesort.cpp

while(vec_a_pos != vector_a.end() || vec_b_pos != vector_b.end()){ //I am especially interested in ways to improve this loop
    if(vec_a_pos == vector_a.end()){
        vec.push_back(*(vec_b_pos++));
    }else if(vec_b_pos == vector_b.end()){
        vec.push_back(*(vec_a_pos++));
    }else{
        vec.push_back(*vec_a_pos < *vec_b_pos ? *(vec_a_pos++) : *(vec_b_pos++));
    }
}

It looks like it works. But when I see the merge sort I usually see the empty array cases have been yanked out of the loop.

// Now your main loop only has one conditional branch.
while(vec_a_pos != vector_a.end() && vec_b_pos != vector_b.end())
{
    vec.push_back(*vec_a_pos < *vec_b_pos
                      ? *(vec_a_pos++)
                      : *(vec_b_pos++));
}
// One of these two is going to be a no-op.
// But it does not matter. Both work at top speed with no tests.
std::move(vec_a_pos, std::end(vector_a), std::back_inserter(vec));
std::move(vec_b_pos, std::end(vector_b), std::back_inserter(vec));

Naming conventions, primarily in the realm of capitalization. I tried to follow the standard library in this regard, but, I have seen other programs that follow a more Java-like convention. Which is preferred and why? If the Java-like conventions are preferred, why does the C++ library not follow them?

  1. There is no specific global naming convention.
  2. But a common one is (this is the one that I use and is suggested by Bjorne S).

    1. User defined types (class/struct/enum) have an initial capital letter
    2. Objects (variables/functions) have an initial lower case letter.

You have to note that the "MOST" important part of C++ is the types. and knowing which identifier is a type and which is an object is very important so this naming convention helps you see when a type is being used.

blaBla(1, 2, 3);  // lower case letter => function call.
                  //                      or functor call on object.

BlaBla(1, 2, 3);  // upper case letter => Type being constructed.
                  //                      result is a temporary object

Whether you use '_' or upper case letters to separate words is very developer dependant. Just be careful not to use '_' as the first character in an identifier (The rules about its use there are complex and even if you know the rules not everybody does).

Why does the standard not follow this convention. The standard got written over a long period (it was not all there in one shot) and as a result has a mixture of conventions. By the time the committee realized it need a convention it was too late now. But in the standard everything is lower case.

Performance: specifically, are there any things I am doing blatantly wrong, but, also are there any small things I can do to improve (ie. to be more CPU cache aware or reduce register-swaps)?

To be blunt that is the compilers job. If you are worrying about the low level architecture you are using the wrong language. You should be worrying about the algorithm efficiency not the register usage efficiency.

The most common thing done wrong by java devlopers is allocating code dynamically when a normal local object would do.

In your algorithm I would worry about space usage. You are using way too much for the current algorithm.

For integers you don't have to worry about the cost of moving objects as a copy and a move have the same cost. But in the general case you should prefer to move rather than copy when you can (a move can be a lot cheaper than a copy). Also your code may be generalized in the future and if you have already done the work then your function can be templatized with no extra work than adding template<typename T> to the front of your function.

I know that using a function pointer to compare the objects to be sorted along with templates to allow for multiple object types to be sorted would be good, but, I have not yet learned templates in C++ and I see the function pointers as (correct me if I'm wrong) as only marginally useful for such a function without the ability to use any object type as the sortee.

First. We prefer "functors" to "functions". A functor is an object that behaves like a function.

A function pointer is hard for the compiler to optimize across (as you can not guarantee at compile time what is happening at runtime). But functors are built around types. The compiler is very good at optimizing around types and is likely to inline your comparitor if you use a functor. So yes even with int it can add efficiency to compare using a functor rather than a function.

Also it makes your code more flexible even for integers. Current you sort from low to high. But just adding a function you can sort from high to low without changing the code itself.

template<typename F = std::less<int>>
void mergesort(vector<int> &vec)
{
    F  compare;

    // your code as normal all the way down.
    // just change the code to use `compare` to do the comparison.

        => *vec_a_pos < *vec_b_pos ?
        becomes
        => compare(*vec_a_pos, *vec_b_pos) ?
}

mergesort(vec);                    // sorts low to high
mergesort<std::less<int>>(vec);    // sorts low to high
mergesort<std::greater<int>>(vec); // sorts high to low.

Code review

Using

OK. Not totally bad.

using std::vector;

But how much effort is it to prefix your vector with std::? There is a reason the standard namespace has such a short name. Its to make typing it easy. Also vector is one of those identifiers that is very common. If you were using another package this can causes clashes.

Alorithms

The interface between algorithms and containers in C++ is the iterator. This allows you to have an algorithm that can be applied to any container type (not just vector) by writting your code in terms of iterators. You can then sort the whole vector by passing begin/end

 void mergesort(vector<int> &vec){

I would have written it as:

 template<typename I>
 void mergeSort(I begin, I end)
 {

Iterator Movememnt

Works perfectly for vector as its iterators are termed random access iterators. Not all iterators are that powerful.

    vector<int>::iterator midpoint_iter = vec.begin() + midpoint;

Use the std::advance if you are moving an iterator more than one place. It uses the most efficient technique for that iterator type.

    auto midpoint_iter = vec.begin();
    std::advance(midpoint_iter, midpoint);

Pre-Size Containers

Note: push_back() can cause a resize in the vector. A resize is very inefficient as all the data needs to be copied during this. If you know the final size of the vector you should set this so that no resizing happens.

    //split main array into two subarrays
    vector<int> vector_a;
    vector_a.reserve(midpoint);
    vector<int> vector_b;
    vector_b.reserve(vec.size() - midpoint);

Prefer Algorithms over loops.

    for(auto i=vec.begin();i!=midpoint_iter;++i){
        vector_a.push_back(*i);
    }
    for(auto i=midpoint_iter;i!=vec.end();++i){
        vector_b.push_back(*i);             
    }

I would have written those as:

    std::move(std::begin(vec), midpoint_iter, std::back_inserter(vector_a));
    std::move(midpoint_iter, std::end(vec),   std::back_inserter(vector_b));

This expresses intent very clearly.

Note:

To move an object rather than copy it. Use the std::move() function on a named object.

    for(auto i=midpoint_iter;i!=vec.end();++i){
        vector_b.push_back(std::move(*i));             
    }

If the function you are calling supports move (and push_back() supports move) then it will use a move operation. If it does not support move it will perform a copy.

Why clear.

    //merge now sorted subarrays
    vec.clear();

This empties the vector. Which calls the destructor on all the objects in the vector (not important for int but other types it may be). Rather just keep the vector the correct size and move elements back into place when you are done.

Update for efficiency

I get an approx. 3x improvement in speed with this.

  1. Don't use lots of memory.
    This algo uses only 2n the size of the vector
  2. Use move rather than copy
    Should not make any difference here.
  3. Move all the comparisons out of the main loop.

This is the code:

template<typename I, typename D = std::less<typename std::iterator_traits<I>::value_type>>
void merge(I begin, I midIter, I end)
{
    std::vector<typename std::iterator_traits<I>::value_type> buffer;
    buffer.reserve(std::distance(begin, end));

    auto left  = begin;
    auto right = midIter;
    D    diff;

    while(left != midIter && right != end)
    {
        buffer.push_back(std::move(diff(*left, *right) ? *left++: *right++));
    }
    std::move(left, midIter, std::back_inserter(buffer));
    std::move(right, end,    std::back_inserter(buffer));

    std::move(std::begin(buffer), std::end(buffer), begin);
}

template<typename I, typename D = std::less<typename std::iterator_traits<I>::value_type>>
void mergeSort2(I begin, I end)
{
    auto size = std::distance(begin, end);
    if (size <= 1)
    {
        return;
    }
    auto mid = size/2;
    auto midIter = begin;
    std::advance(midIter, mid);

    mergeSort2(begin, midIter);
    mergeSort2(midIter, end);

    merge<I, D>(begin, midIter, end);
}

Here is another attempt. In this case I pre-allocate all the temporary buffer once and then re-use. The problem with this version is that it assumes that the value type is default constructable. Also if it is expensive to construct the object that may be an issue.

But I get a 6x performace boost over the original.

template<typename D, typename I, typename I2>
void merge(I begin, I midIter, I end, I2 tmp)
{
    auto save  = tmp;
    auto left  = begin;
    auto right = midIter;
    D    diff;

    while(left != midIter && right != end)
    {
        *tmp = std::move(diff(*left, *right) ? *left++: *right++);
        ++tmp;
    }
    tmp = std::move(left, midIter, tmp);
    tmp = std::move(right, end,    tmp);

    std::move(save, tmp, begin);
}

template<typename I, typename I2, typename D = std::less<typename std::iterator_traits<I>::value_type>>
void mergeSort2(I begin, I end, I2 tmpBegin)
{
    auto size = std::distance(begin, end);
    if (size <= 1)
    {
        return;
    }
    auto mid = size/2;
    auto midIter = begin;
    auto midBuf  = tmpBegin;
    std::advance(midIter, mid);
    std::advance(midBuf, mid);

    mergeSort2(begin, midIter, tmpBegin);
    mergeSort2(midIter, end, midBuf);

    merge<D>(begin, midIter, end, tmpBegin);
}

template<typename I, typename D = std::less<typename std::iterator_traits<I>::value_type>>
void mergeSort2(I begin, I end)
{
    std::vector<typename std::iterator_traits<I>::value_type> buffer;
    buffer.resize(std::distance(begin, end));

    mergeSort2(begin, end, std::begin(buffer));
}
\$\endgroup\$
  • \$\begingroup\$ Can't you simply use emplace_back() instead of push_back(std::move()) ? \$\endgroup\$ – Kodnot Aug 6 '16 at 11:11
  • \$\begingroup\$ @Kodnot: Not really. emplace_back() is like push_back() but takes the arguments of the constructor of T (where T is the type stored in the container). Now you can use emplace_back() with a type T and it just calls the copy/move constructor (Apart from that nothing changes). To get the move semantics you would need to call emplace_back(std::move()) otherwise you are binding an lvalue and copy rather than a move will happen. \$\endgroup\$ – Martin York Aug 6 '16 at 16:31
2
\$\begingroup\$

Specific naming conventions are unimportant except that you are consistent in your project.

Merge sort is one of those algorithms that are very elegant when recursive but can be better implemented if done iteratively.

Here the primary niggle I have as a result of that is the allocations, you end up allocating at least O(n log n) extra memory (some of it freed before other allocations). Actually more because you don't reserve the space needed in the vector_a and vector_b;

If you merge from the ground up you can avoid this excessive reallocation:

vector<int> spare(vec.size()); //allocate the destination for the merge

for(int step = 1; step < vec.size(); step *= 2){
    int start;
    for(start = 0; start + step < vec.size(); start += 2*step){

        vector<int>::iterator vec_a_pos = vec.begin()+start;
        vector<int>::iterator vec_b_pos = vec.begin()+start+step
        vector<int>::iterator end = start + 2*step < vec.size() ? vec.begin()+ start + 2*step : vec.end();

        merge(vec_a_pos, vec_b_pos, end, spare.begin()+start);
    }
    //possibly skipped the last odd chunk of the vector, copy it over
    for(; start < vec.size(); start++){
        spare[start] = vec[start];
    }

    vec.swap(spare); //will swap in O(1) time by exchanging the underlying buffer pointers. 
}

and merge would be implemented as:

void merge(vector<int>::iterator vec_a_pos, 
           vector<int>::iterator vec_b_pos, 
           vector<int>::iterator vec_b_end, 
           vector<int>::iterator dst){

    vector<int>::iterator vec_a_end = vec_b_pos;

    while(vec_a_pos != vec_a_end || vec_b_pos != vec_b_end){ 
        if(vec_a_pos == vec_a_end){
            *dst++ = *(vec_b_pos++);
        }else if(vec_b_pos == vec_b_end){
            *dst++ = *(vec_a_pos++);
        }else{
            *dst++ = *vec_a_pos < *vec_b_pos ? *(vec_a_pos++) : *(vec_b_pos++);
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.