Optimize a parallelized program to optimize train schedules

Question

This loops through a vector of vector of A and adds a smaller array to a bigger one at a specified position+random shift. Then it is checked if it is a better solution, and if yes, it is stored, else it is discarded. I have already parallelized it.

Can this be improved to run faster?

I am not sure if a vector<vector<struct>> is a good idea, or maybe there is a better memory management to use better cache effects. The struct is currently global and since it is only readable by the threads all threads use the same instance.

I am using C++11 threads.

Description of what the program does:

We have a big array, rand_val, and we have many small arrays, Leistungskurve. We can add these array to rand_val at a fixed position + random shift. We want to find a valid position for each array so the max element in rand_val is minimized. In the array, rand is stated which position we have chosen.

#include <iostream>
#include <string>
#include <vector>
#include <time.h>
#include <cmath>
#include <iterator>

#include <algorithm>

#include <fstream>
#include <stdlib.h>
#include <sstream>

#include <stdlib.h>

#include <thread>
#include <random>

using namespace std;

struct Teilstrecke {
  int StreckenNr;
  int Fahrzeit;
  int Haltezeit;
  int FruehesteAbfahrt;
  int SpaetesteAbfahrt;
  int Abfahrtsintervall;
  double *Leistungskurve;
};

struct Zug {
  int ZugNr;
  int AnzahlStrecken;
  vector<Teilstrecke> Teilstrecken;
};

vector<Zug> Zuege;

int Planungsintervall;
int AnzahlZuege;
int AnzahlSchattenzuege;

inline double maxArray(double *arr, int size)
{
  double max = 0;
  int pos = 0;
  for (int i = 0; i < size; i++)
  {
    if (arr[i] > max)
    {
        max = arr[i];
        pos = i;
    }
  }
  return pos;
}

inline void addArray(double *arr1, double *arr2, int size2, int pos)
{
  for (int i = 0; i < size2; i++)
  {
    arr1[pos+i] += arr2[i];
  }
}


inline void addArray(double *arr1, Teilstrecke ts, int shift)
{
    addArray(arr1, ts.Leistungskurve, ts.Fahrzeit*600+1, (ts.FruehesteAbfahrt+shift)*600);
}


inline void randomSolution(int *rand, double *rand_val);

inline int randomNumber(int low, int high) // has to be replaced to c++11 random
{
  return rand() % (high - low + 1) + low;
}

void wrapper()
{
  int size = Planungsintervall*600+1;
  int *rand = new int[AnzahlSchattenzuege];
  fill_n(rand, AnzahlSchattenzuege, 0);
  double *rand_val = new double[size];
  fill_n(rand_val, size, 0);
  int max_iter = 1000000;

  double best_max = 1e20;
  int *rand_best = new int[AnzahlSchattenzuege];
  for (int i = 0; i < max_iter; i++)
  {
    randomSolution(rand, rand_val);
    double max = maxArray(rand_val, size);
    //cout << max << '\n';
    if (max < best_max)
    {
      best_max = max;
      memcpy(rand_best, rand, sizeof(int)*AnzahlSchattenzuege);
    }
    fill_n(rand, AnzahlSchattenzuege, 0);
    fill_n(rand_val, size, 0);
  }
  cout << best_max <<  ' ' << '\n';
}


inline void randomSolution(int *rand, double *rand_val)
{
  int pos2 = 0;
  for (int i = 0; i < AnzahlZuege; i++)
  {
    for (int j = 0; j < Zuege.at(i).AnzahlStrecken; j++)
    {
      Teilstrecke ts = Zuege.at(i).Teilstrecken.at(j);
      int k = randomNumber(0, ts.Abfahrtsintervall);
      rand[pos2+k] = 1;
      addArray(rand_val, ts, k);
      pos2 += ts.Abfahrtsintervall + 1;
    }
  }
}

void read_input(char *read_file);

int main(int argc, char** argv)
{
  read_input((char*)argv[1]);
  vector<thread> threads;
  for (int i = 0; i < 7; i++)
  {
    threads.push_back(thread(wrapper));
  }
  wrapper();
  for (int i = 0; i < 7; i++)
  {
    threads.at(i).join();
  }
}

Profiling

It seems that all work is done in addArray.

Answer 1

• Do not use using namespace std as it could cause clashing issues, which will introduce bugs. More info about that here.

• This is very unorganized:

  #include <iostream>
  #include <string>
  #include <vector>
  #include <time.h>
  #include <cmath>
  #include <iterator>
  
  #include <algorithm>
  
  #include <fstream>
  #include <stdlib.h>
  #include <sstream>
  
  #include <stdlib.h>
  
  #include <thread>
  #include <random>
  

  Steps to improve this:

  1. Make sure there aren't any libraries that you aren't currently using or have repeated.
  2. Make sure you aren't using any C libraries (which end with .h). They should be replaced with the equivalent C++ library so that everything will be in the std namespace.
  3. Sort them in a certain order for organization, such as alphabetically. This will make it easier to locate certain libraries during maintaining.

  Assuming every library is still being used, this is what it could look like:

  #include <algorithm>
  #include <cmath>
  #include <cstdlib>
  #include <ctime>
  #include <fstream>
  #include <iostream>
  #include <iterator>
  #include <random>
  #include <sstream>
  #include <string>
  #include <thread>
  #include <vector>
  

  This is one #include shorter because you've included <stdlib.h> twice. Had this list been organized from the beginning, this wouldn't have been likely to happen.

• Do not use global variables:

  vector<Zug> Zuege;
  
  int Planungsintervall;
  int AnzahlZuege;
  int AnzahlSchattenzuege;
  

  They are accessible throughout the entire file or program, and can possibly be modified without your knowledge. This can greatly hurt maintainability and also introduce bugs. You should keep them in local scope, such as in a function, and pass them to other functions as needed. This will make it much easier to keep track of their locality and determine how they're used.

• The inline keyword likely won't offer you any benefit here. The compiler is free to decide what should really be inlined and can ignore any explicit use of it. It merely serves as a hint.

• There is absolutely no need to call std::rand() when you're using C++11 and have already included <random>. You should utilize this library and ditch std::rand() altogether.

  Regarding the usage of std::rand() itself, you don't even call std::srand(), meaning you'll get the same random values with each call to std::rand(). Have you not even noticed this?

• Why are you mixing std::vectors and dynamically-allocated arrays? Vectors are the same type of array, but much more specialized. You should ditch all the arrays and just use vectors (or any suitable storage container). You end up passing these arrays (specifically the pointer to their first respective elements), which can get very nasty in C++, especially because memory-management will now be in your hands. Just utilize storage containers and let them handle the dirty work for you (which is very necessary, as you fail to deallocate memory with delete, causing the whole program to leak memory). They will also allow you to ditch the size variables since storage containers already keep track of their sizes (accessible via size()).

• Since you use argv[1] in main() as the only command line argument, I assume that you're only expecting one additional argument.

  In order to make sure that this argument is provided, check the value of argc at the start, before using argv[1]. If it's less than 2, terminate the program. You may also print an error message to inform the user of this error.

  if (argc < 2)
  {
      std::cerr << "A filename argument is required!";
      return EXIT_FAILURE;
  }
  

---

To sum it up:

This is quite broken and messy. I'm sure there are other issues besides the ones I've mentioned, but this should address many of them. Before worrying about optimization, I'd recommend cleaning this up and making sure it runs smoothly and correctly.

Answer 2

To see where the bottleneck is, you need to profile your code!

Here something which may be a little improvement:

replace:

inline void addArray(double *arr1, double *arr2, int size2, int pos)
{
  for (int i = 0; i < size2; i++)
  {
    arr1[pos+i] += arr2[i];
  }
}

by

inline void addArray(double *arr1, double *arr2, int size2, int pos)
{
  for (int i = 0; i < size2;)
  {
    arr1[pos++] += arr2[i++];
  }
}

and

replace

inline void randomSolution(int *rand, double *rand_val)
{
  int pos2 = 0;
  for (int i = 0; i < AnzahlZuege; i++)
  {
    for (int j = 0; j < Zuege.at(i).AnzahlStrecken; j++)
    {
      Teilstrecke ts = Zuege.at(i).Teilstrecken.at(j);
      int k = randomNumber(0, ts.Abfahrtsintervall);
      rand[pos2+k] = 1;
      addArray(rand_val, ts, k);
      pos2 += ts.Abfahrtsintervall + 1;
    }
  }
}

by:

inline void randomSolution(int *rand, double *rand_val)
{
  int pos2 = 0;
  for (int i = 0; i < AnzahlZuege; i++)
  {
    Zug z=Zuege.at(i);
    int maxJ=z.AnzahlStrecken;
    for (int j = 0; j < maxJ; j++)
    {
      Teilstrecke ts = z.Teilstrecken.at(j);
      int k = randomNumber(0, ts.Abfahrtsintervall);
      rand[pos2+k] = 1;
      addArray(rand_val, ts, k);
      pos2 += ts.Abfahrtsintervall + 1;
    }
  }
}