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?
- There is no specific global naming convention.
But a common one is (this is the one that I use and is suggested by Bjorne S).
- User defined types (class/struct/enum) have an initial capital letter
- 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.
- Don't use lots of memory.
This algo uses only 2n the size of the vector
- Use move rather than copy
Should not make any difference here.
- 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));
}
