Performance issue: Java vs C++

Question

I have always heard that C++ was way more efficient than Java (and that is why most games are developed in C++).

I wrote a small algorithm to solve the "Eight queens puzzle" in both Java and C++, using the exact same algorithm, and then started to raise the number or squares. When reaching checkboards of 20*20 or even 22*22, it appears Java is much more effective (3 seconds vs 66 seconds for C++).

I have no idea why, but I am pretty beginning with C++, so it is possible I made some huge performance mistakes, so I will gladly accept any information that would help me understand what is happening.

Below is the code I use in Java:

import java.awt.Point; import java.util.ArrayList; import java.util.List;  public class HuitDames {      /**      * La liste des coordnnées des dames.      */     private static List<Point> positions = new ArrayList<>();      /**      * Largeur de la grille.      */     private static final int LARGEUR_GRILLE = 22;       /**      * @param args the command line arguments      */     public static void main(String[] args) {         int i = 1;         placerDame(i);         for (Point point : positions) {             System.out.println("(" + point.x + "; " + point.y + ")");         }     }      /**      * Place une dame et return true si la position est bonne.      * @param i le numéro de la dame.      * @return si la position est bonne.      */     private static boolean placerDame(int i) {          boolean bonnePosition = false;         for (int j = 1; j <= LARGEUR_GRILLE && bonnePosition == false; j++) {             Point emplacement = new Point(i, j);             positions.add(emplacement);             if (verifierPrise(emplacement) && (i == LARGEUR_GRILLE || placerDame(i + 1))) {                 bonnePosition = true;             }             else {                 positions.remove(i - 1);             }         }          return bonnePosition;     }      /**      * Vérifie que la nouvelle position n'est pas en prise avec une position déjà présente.      * @param position la position de la nouvelle dame.      * @return Si la position convient par rapport aux positions des autres dames.      */     private static boolean verifierPrise(Point position) {         boolean nonPrise = true;         for (Point point : positions) {             if (!point.equals(position)) {                 // Cas où sur la même colonne.                 if (position.y == point.y) {                     nonPrise = false;                 }                 // Cas où sur même diagonale.                 if (Math.abs(position.y - point.y) == Math.abs(position.x - point.x)) {                     nonPrise = false;                 }             }         }          return nonPrise;     } } 

And below is the code in C++:

#include <iostream> #include <list> #include <math.h> #include <stdlib.h>  using namespace std;   // Class to represent points. class Point {      private:         double xval, yval;      public:         // Constructor uses default arguments to allow calling with zero, one,         // or two values.         Point(double x = 0.0, double y = 0.0) {                 xval = x;                 yval = y;         }          // Extractors.         double x() { return xval; }         double y() { return yval; } };  #define LARGEUR_GRILLE 22 list<Point> positions;   bool verifierNonPrise(Point emplacement) {     bool nonPrise = true;     for (list<Point>::iterator it = positions.begin(); it!= positions.end(); it++) {         if (it->x() != emplacement.x()) {             if (it->y() == emplacement.y()) {                 nonPrise = false;             }             if (abs(it->y() - emplacement.y()) == abs(it->x() - emplacement.x())) {                 nonPrise = false;             }         }     }      return nonPrise; }  bool placerDame(int i) {     bool bonnePosition = false;     for (int j = 1; j <= LARGEUR_GRILLE && !bonnePosition; j++) {         Point emplacement(i,j);         positions.push_back(emplacement);         if (verifierNonPrise(emplacement) && (i == LARGEUR_GRILLE || placerDame(i + 1))) {             bonnePosition = true;         }         else {             positions.pop_back();         }     }      return bonnePosition; }  int main() {     int i = 1;     placerDame(i);     for (list<Point>::iterator it = positions.begin(); it!= positions.end(); it++) {         cout << "(" << it->x() << "; " << it->y() << ")" << endl;     }     return 0; } 

Answer 1

std::list in C++ is a linked list, whereas java.util.ArrayList is an array. Try replacing std::list by std::vector. Also, be sure to compile with optimization turned on.