Join the Stack Overflow Community
Stack Overflow is a community of 6.5 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up

I implemented the Merge Sort in Java and in C++ and I tried to implement them as similar as possible. Both algorithms work, I tested them many times. The problem is that my Java-Implementation is a lot faster than my C++-Implementation and I am wondering why. I can't believe that Java would be faster so I guess I made a mistake in one of the implementations. In order to measure the runtime I created a class "Person" which has two String-Attributes (forename, lastname). In C++ I used std::vector<Person*> and in Java I used ArrayList<Person>. Additionally I overloaded the operator< in C++ to compare two Persons (compare the lastname, if equal compare the firstname). In Java I implemented the interface Comparable<Person> to compare two Persons.

Can you find a mistake in my code or a reason why Java would be faster or C++ would be slower? Any help would be appreciated.

My Java Code:

public void mergeSort(List<T> list) {
    if (list.size() <= 1) {
        return;
    }

    int subLength = (int) (list.size() / 2);
    List<T> first = new ArrayList<T>(list.subList(0, subLength));
    List<T> second = new ArrayList<T>(list.subList(subLength, list.size()));


    mergeSort(first);
    mergeSort(second);

    merge(first, second, list);
    return;
}

private void merge(List<T> first, List<T> second, List<T> result) {
    int firstPos = 0, secondPos = 0, resultPos = 0;

    while (firstPos < first.size() && secondPos < second.size()) {
        if (first.get(firstPos).compareTo(second.get(secondPos)) < 0) {
            result.set(resultPos, first.get(firstPos));
            firstPos++;
        } else {
            result.set(resultPos, second.get(secondPos));
            secondPos++;
        }
        resultPos++;
    }

    for (int i = firstPos; i < first.size(); i++) {
        result.set(resultPos, first.get(i));
        resultPos++;
    }
    for (int i = secondPos; i < second.size(); i++) {
        result.set(resultPos, second.get(i));
        resultPos++; 
    }
}

My C++ Code:

Note: I used two template-methods to make the mergesort usable with both Person and Person*.

template<typename T>
    T * ptr(T & obj) { return &obj; } 

    template<typename T>
    T * ptr(T * obj) { return obj; }


void mergeSort(std::vector<T> &list) {
        if (list.size() <= 1) {
            return;
        }

        int subLength = (int)(list.size() / 2);
        std::vector<T> first(list.begin(), list.begin() + subLength);
        std::vector<T> second(list.begin() + subLength, list.end());

        mergeSort(first);
        mergeSort(second);

        merge(first, second, list);

    }
void merge(const std::vector<T> &first, const std::vector<T> &second, std::vector<T> &result) {
        int firstPos = 0, secondPos = 0, resultPos = 0;
        while (firstPos < first.size() && secondPos < second.size()) {
            if (*ptr(first[firstPos]) < *ptr(second[secondPos])) {
                result[resultPos] = first[firstPos];
                firstPos++;
            }
            else {
                result[resultPos] = second[secondPos];
                secondPos++;
            }
            resultPos++;
        }

        for (int i = firstPos; i < first.size(); i++) {
            result[resultPos] = first[i];
            resultPos++;
        }
        for (int i = secondPos; i < second.size(); i++) {
            result[resultPos] = second[i];
            resultPos++;
        }
    }

Edit1 and 2:

My setup-configuration:

I used one million, 10 millionen and 20 millionen persons to test the implementations. I doesn't really matter with how many Persons I test it with, Java is always faster.

And I test it the following way: I create persons and initialize my MergeSort-class. Then I start the measurement and I call my mergeSort-method. When the sorting is finished I stop the measurement. (Deleting is happening after the time measurement). For the time measurement in Java I use System.nanoTime() and in C++ I use chrono::high_resolution_clock::time_point

Of course I compiled C++ in "Release"-Mode (Optimization: O2, faster code preferred).

My Test-PC:

  • Intel i5 2500
  • 8GB DDR3 RAM
  • Windows 10 Education

Edit3:

There is one thing I forgot to mention. I implemented the algorithm in a generic way in order to use simple data-types as well as objects. When I use std::vector<int> and ArrayList<Integer> in Java then my C++ implementation is a lot faster. My first attempt was to use std::vector<Person> but it was even slower. So my guess was that it made deep copies instead of shallow ones and that's why I switched to Person* because I thought that when copying is happening only the pointers will be copied.

share|improve this question
3  
Whats the setup of your performance tests? Whats your sample size? How is the time measured? – f1sh 2 hours ago
2  
This probably belongs on code review. – Kerrek SB 2 hours ago
1  
A list, in C++ it's std::list – alain 2 hours ago
1  
IMHO vector is the best container to use here (looking at the code!) std::list only adds overhead. (BTW *ptr(...) can be safely omitted) – Elijan9 2 hours ago
2  
@alain only in case you get out of the preallocated space. But in this case you can see the OP is not adding new elements to vectors and in most cases you can actually predict the total number of entries, so that you can create a vector of needed length – Chaosit 33 mins ago

TL;DR - The Java version does alot less array copying.

The ArrayList constructor (see line 167) of ArrayList when passed a Collection uses Collection.toArray() and optionally Arrays.copyOf if required. In the case of an ArrayList there is no need to take a copy - toArray() returns a reference to the underlying array.

Note also that the if (elementData.getClass() != Object[].class) will cause the array not to be copied again.

The Java List.subList on ArrayList objects does not copy any of the underlying array, it just returns an ArrayList backed by the original but limited to the elements required.

As a result - in may cases the whole mechanism uses sub-lists that actually just refer to the original array - no copying is required.

Not too familiar with C++ but I suspect there is a lot of array copying and allocation going on which just doesn't need to be done by Java.

ADDED - As @ThomasKläger rightly pointed out, ArrayList.toArray actually does return a defensive copy of the array - so I was wrong above.

share|improve this answer
    
Thank you for your answer. I will try to figure out if there is really that much allocation and copying done. I will mark this answer as "accepted" when I tried it out. – killexe 1 hour ago
    
There indeed is alot of copying in C++ version. In mergeSort() line std::vector<T> first(list.begin(), list.begin() + subLength); and the next one call vector range constructor, which Constructs a container with as many elements as the range [first,last), with each element emplace-constructed from its corresponding element in that range, in the same order.. In other words this increases running time by nlogn copy operations. – Tomasz Plaskota 1 hour ago
2  
"toArray() returns a refernce to the underlying array" - no, it does not, it creates a copy of the underlying array (see your referenced source, line 361). This is also clearly stated in the JavaDoc of ArrayList.toArray(): In other words, this method must allocate a new array – Thomas Kläger 1 hour ago
    
When I call std::vector<T> first(list.begin(), list.begin() + subLength); wouldn't there just the pointers to the Persons be copied? – killexe 1 hour ago
    
@ThomasKläger - Thanks for the heads-up. – OldCurmudgeon 24 mins ago

One of the 1st things I see is in your statement:

Deleting is happening after the time measurement

You're speaking of deleting of the Person objects, you're obviously not speaking of the containers, such as first and second which C++ is creating and cleaning on the stack:

std::vector<T> first(list.begin(), list.begin() + subLength);
std::vector<T> second(list.begin() + subLength, list.end());

while Java is creating them on the heap and not cleaning them up till it gets around to it (so after you stop timing):

List<T> first = new ArrayList<T>(list.subList(0, subLength));
List<T> second = new ArrayList<T>(list.subList(subLength, list.size()));

So you're timing C++ with container cleanup and Java without.


I have to ask here, what's the point of writing your own merge sort? The best Java and C++ code would use the sorting algorithms already provided by the language. If you're looking to time something at least time the optimized algorithms.

Also I wouldn't put a lot of work into time comparisons. C++ will be faster, it will generally be more work to write as well. If speed is important enough to you to bother with timing you probably want to be using C++. If development time is king then you'll want to be using Java.

share|improve this answer
    
You are right and I won't use these algorithms in real applications because I know that the algorithms provided by the languages themselves will be faster than mine obviously. My goal was to find out the speed difference in a pratical use so I decided to implement an algorithm by myself to do so. Of course I cannot guarantee that the measurement is 100% fair but I try to make it as fair as possible. Do you think that the reason for the time difference is that C++ is deleting the std::vector containers at the end of the method? – killexe 25 mins ago
1  
@killexe Obviously there could be more problems in the code I can't see. The ptr function is also something extra in the C++ code, but the compiler should simplify that. But yeah, in the code that you've presented that is the significant difference that I see. Either way, I appreciate that you've taken the time to use reference arguments in the C++ code and all that. It's very easy on the eyes :) – Jonathan Mee 14 mins ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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