1

I'm trying to solve a topological sort problem on Leetcode(link here). And I was surprised to find that C++ is slower than Java with same algorithm! C++ solution costs almost 500ms, but Java is only 6~7ms. It's confusing... And C++ is also slower than python, c# and javascript. Here is the accepted solutions runtime distribution:

Accepted Solutions Runtime Distribution

And here is the code for C++ version and Java version. Both of them use DSF method for topological sort.

//Java
public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<Integer>[] edges = new ArrayList[numCourses];
    int[] visited = new int[numCourses];
    int[] res = new int[numCourses];
    for (int i = 0; i < edges.length; i++) 
        edges[i] = new ArrayList<Integer>();
    for (int[] edge : prerequisites) 
        edges[edge[0]].add(edge[1]); 

    for (int i = 0, j = 0; i < numCourses; i++) {
        j = dfs(i, edges, visited, res, j);
        if (j == -1) return new int[0]; // cycle, return empty array
    }

    return res;
}

private int dfs(int v, List<Integer>[] edges, int[] visited, int[] res, int i) {
    if (visited[v] == 2) return i;           // black node
    if (visited[v] == 1) return -1;          // gray node -> cycle
    visited[v] = 1;
    for(int j : edges[v]) {
        i = dfs(j, edges, visited, res, i);
        if (i == -1) return -1;              // if there is a cycle, propagate the error
    }
    visited[v] = 2;
    res[i] = v;
    return i+1;
}

--

//C++
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<int> outputs;
    vector<int> nodes(numCourses, 0);

    vector<list<int>> edges(numCourses);
    for (auto i=prerequisites.begin(); i!=prerequisites.end(); i++) {
        edges[i->first].push_back(i->second);
    }

    for(int i=0; i<numCourses; ++i)
    {
        if(!dfs(edges, outputs, nodes, i, numCourses))
        {
            outputs.clear();
            return outputs;
        }
    }

    return outputs;
}

bool dfs(vector<list<int>>& edges, vector<int>& outputs, vector<int>& nodes, int cur, int numCourses)
{
    if(nodes[cur] == 1) return false;
    if(nodes[cur] == 0)
    {
        nodes[cur]++;
        for(auto i=edges[cur].begin(); i!=edges[cur].end(); ++i)
        {
            if(!dfs(edges, outputs, nodes, *i, numCourses))
                return false;
        }
        nodes[cur]++;
        outputs.push_back(cur);
    }

    return true;
}
Yyao
  • 395
  • 3
  • 17
  • 3
    [this might contain the answer to your question](http://stackoverflow.com/questions/145110/c-performance-vs-java-c) – SomeJavaGuy Apr 28 '16 at 08:53
  • 5
    The C++ version is not a 1:1 port, it's slightly different from the Java version. So you're not making a fair comparison. – DarkDust Apr 28 '16 at 08:57
  • This sounds like using a C++ debug build. If you want to document a difference you have to supply the relevant **information**. – Cheers and hth. - Alf Apr 28 '16 at 08:58
  • @Cheersandhth.-Alf It's an online judge system. – Yyao Apr 28 '16 at 09:00
  • 4
    @Yyao: if the online judge doesn't tell you what compiler options it uses then it's unfortunately pretty worthless as a benchmark. If it does tell you, then tell us! – Steve Jessop Apr 28 '16 at 09:01
  • you are using std::vector; try to using std::list – nikniknik2016 Apr 28 '16 at 09:07
  • Yyao, don't let them get you down. Did you try to run the code on your machine? – Ely Apr 28 '16 at 09:07
  • 1
    @SteveJessop sorry... They don't give the information about the runtime and compiler. The only thing I can find is they use compile flag -O0. – Yyao Apr 28 '16 at 09:08
  • @nikniknik2016 I tried. It slightly changes the time. There's no big change. And I also tried replace push_back with writing directly into specific index. I just got same results. – Yyao Apr 28 '16 at 09:11
  • @Elyasin I haven't check this on my machine. Because I can't get a time consuming test case. – Yyao Apr 28 '16 at 09:13
  • 1
    Something is majorly broken here. I could imagine that you have done some small typo which causes unneccesary copying or whatever, but I don't believe that everybody else has done same error - but it seems that all C++ solutions are horribly slow. It has to be something with their test environment - maybe they are adding compilation time into account, have some super-slow initialization code for this particular task or use different input set for C++ versus java. There is no way that EVERY C++ solution submitted is 2 orders of magnitude slower from EVERY java solution. – Artur Biesiadowski Apr 28 '16 at 09:13
  • 8
    @Yyao _"they use compile flag -O0"_ Then their benchmarking is completely useless, period. You should not look on perfomance of code compiled without at least -O2 – Revolver_Ocelot Apr 28 '16 at 09:14
  • 2
    @Yyao This question and any answers trying to explain why C++ is slower is absolutely meaningless since no optimizations were used to compile the C++ code. I get tired of posts with the subject "why is this C++ code slow" or "why is C++ code slower than language x", and there is no indication, up front, what compilation settings were used. It isn't discovered until late into the game that the optimizations were turned off. – PaulMcKenzie Apr 28 '16 at 09:26
  • 1
    @ArturBiesiadowski please read the above comment, they use compile flag `-O0`, that's the reason – phuclv Apr 28 '16 at 09:27
  • 2
    @Yyao - *They don't give the information about the runtime and compiler. The only thing I can find is they use compile flag -O0* -- So what is the purpose of the graph you got from Leetcode? Is it to discourage people from using C++ since it is "slow"? And no one complained about this obvious bias against C++? Why not be the whistleblower and warn others who take those graphs as gospel? – PaulMcKenzie Apr 28 '16 at 09:35
  • 4
    The compile flag `-O0` almost *literally* means, "make this code as slow as possible" ;-) It's only not literally that because of some assumed constraints like, "without actually adding in busy-loops" and "without applying clever code-size optimizations that might make it even slower". – Steve Jessop Apr 28 '16 at 09:38

1 Answers1

1

int[] res = new int[numCourses]; versus vector<int> outputs; The problem in this for example is that Java knows in advance how much space it needs, the vector from C++ might need adjustments during the run (it's costly, it involves copying, allocating and releasing memory). I'm not saying it's the problem, it's one of the problems. Be sure to test building a release, not a debug, for C++, and also avoid unnecessary copying around, this is a source of slowing things down.

Adrian Roman
  • 534
  • 4
  • 8