I have finished the first part of my project, i.e., getting a full working program. However, the performance is not too impressive. The function expectedCosts(state const &S) took around 96% of the total running time, so any performance increase in this function might be worthwhile.

For profiling purpose I used a reasonable large problem instance that took 2374 seconds to solve. After some hours of profiling and optimizing, the total runtime is decreased to 39 seconds :). However, the majority of the runtime still goes to the same function. Since almost all runtime is caused by this single function I'm convinced that micro-optimizations are justified. The 39 seconds are not that bad, however I would like to solve instances of greater size which still take 3000+ seconds to solve. Can you help me to improve the function a bit more?

The current implementation of the function is shown at the bottom of this post. I expect that a performance gain is possible in line 24-25 (tmp = {0, 0, 0, d1, d2} and transform(..)) since these lines both take around 20-25% of the total time of the function.

I was skeptic about the benefit of __builtin_expect since I have never seen any situation where it did help. Surprisingly, the performance increase is on average (ten runs) more than 2%. I have already tried to remove the unlikely if-statements (if (__builtin_expect(pA < 0.00001, 0))). However, this more than doubled the runtime.

I use the gcc compiler with --std=c++11 -Wall -g -O2 -flto. Both -O3 and -ffast-math seems to decrease the performance of the program.

Do you have any suggestions?

Edit: state is a typedef for std::vector<size_t>. Just out of curiousity, I changed the typedef to std::valarray<size_t>. This decreased the runtime of the current test instance to 31 seconds. I cannot explain the reason for this huge improvement since I had no time for a new extensive profiling session yet and I have never used std::valarray before. What confuses me is that most of us (people on Stack Overflow) are quite negative about the std::valarray.

double MDPsolver::expectedCosts(state const &S)
  double value = 0.0;
  vector<size_t> tmp {0,0,0,0,0};

  size_t const endA = d_F - S[3];
  size_t const endB = d_F - S[4];

  // Loop over all reachable states
  for (size_t d1 = 0; d1 <= endA; ++d1)
    double const pA = d_p[S[3]][S[3] + d1];

    if (__builtin_expect(pA < 0.00001, 0))

    for (size_t d2 = 0; d2 <= endB; ++d2)
      double const pB = d_p[S[4]][S[4] + d2];

      if (__builtin_expect(pB < 0.00001, 0))

      tmp = {0, 0, 0, d1, d2};
      transform(begin(tmp), end(tmp), begin(S), begin(tmp), plus<size_t>());

      value += pA * pB * d_values[hash(tmp)];

  return value;
  • \$\begingroup\$ Since vectors size seem to be known at compile time, I would replace them for array<int>. Maybe even better, I'd replace vectors for plain arrays and replace the stl transform for a custom function. \$\endgroup\$ – perencia May 7 '16 at 19:18
  • \$\begingroup\$ @perencia, thx for your response. Later I also want to do experiments of other sizes. However, I will try your suggestion and if the performance inreases significant I will compile a binary for each experiment. \$\endgroup\$ – Michiel uit het Broek May 7 '16 at 20:14
  • 1
    \$\begingroup\$ It is difficult to give advice on performance improvements without being able to compile, run and benchmark the code. For starters, it seems important to me to understand what state::operator[] does. The only thing I can see immediately is, as @perencia mentioned, the dynamic memory allocation for the temporary std::vector. I don't believe that builtin arrays will be faster than std::array or writing your own std::transform would be faster than the standard library's version, though. \$\endgroup\$ – 5gon12eder May 8 '16 at 4:57
  • \$\begingroup\$ I agree with @5gon12eder, it is very difficult and it's possible that my suggestions do not provide any significant speedup. What would probably improve it would be partitioning the problem size and using threads or even some form of vectorization. \$\endgroup\$ – perencia May 8 '16 at 9:31
  • 1
    \$\begingroup\$ You could try declaring tmp in the inner for loop. This will tell the compiler the value of tmp does not have to be stored in between the iterations. The compiler may choose to do other counter efficient shananigans but you could give it a try. \$\endgroup\$ – Andreas May 8 '16 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.