2

I was surprised when I benchmarked this function:

int f(int N = 999) {  
  int nMax = 0;

  for (int i = 1; i <= N; ++i)
    for (int j = i; j <= N; ++j) {
      string digits  = to_string(i*j);
      string rDigits = digits;

      reverse(rDigits.begin(), rDigits.end());

      if (digits == rDigits)
        nMax = max(i*j, nMax);
    }

  return nMax;
}

with VS2012, VS2013 (release, /O2) and MinGW 4.8.0, 4.8.1 (-Ofast) on Windows 7 32-bit and 64-bit. I noticed that MinGW built versions run about 13 times slower than VS ones. Is this a problem with implementation of to_string() and reverse()? Any other reasons?

The code I used is here: https://github.com/pauljurczak/Benchmark-2/blob/master/benchmark.cpp

EDIT

I narrowed down the problem to std::to_string() function, which is about 16 times slower with MinGW then with VS. I used this snippet for testing:

int f(int N = 100000) {  
  int len = 0;

  for (int i = 0; i <= N; ++i) 
    len += to_string(i).length();

  return len;
}

When I compile it with g++ 4.7.3 on Ubuntu, performance is about the same as VS2012.

Paul Jurczak
  • 7,008
  • 3
  • 47
  • 72
  • 1
    You're running the benchmark, why don't you tell us which part is slow? – Ben Voigt Jul 28 '13 at 22:22
  • Programmers that use MinGW are an odd lot. They never seem to want to check-in patches and keep asking SO users to do it for them. You can't have it both ways. – Hans Passant Jul 28 '13 at 22:27
  • This subject intrigues me... What happens if you try with MinGW 4.7.2 for example? – Antonio Jul 28 '13 at 22:31
  • Did you try reversing the string when you construct it instead of as a second step to narrow down the area? `string rDigits(digits.rbegin(), digits.rend());` Also does your benchmarking include I/O of any sort (such as `cout`)? – Mark B Jul 28 '13 at 23:37
  • @Antonio MinGW 4.7.2 fails to compile this code: undefined `to_string()`. – Paul Jurczak Jul 28 '13 at 23:50
  • @MarkB My question is about huge performance difference between VS and MinGW, not about optimizing this code. OTOH, I will test your suggestion. I/O is not timed. I'm adding a link to my whole test program. – Paul Jurczak Jul 28 '13 at 23:59
  • OK. What CPU settings and optimizations do you have enabled on both? On 64-bit windows, are you building both for 64 bit? Which Intel CPU variant are you targeting in each? Is it the same? Have you examined the various compiler optimizations that are included in -Ofast to see if it is equivalent to /O2? Does -Ofast include heuristics that could be failing? What do your profilers say? – George Jul 29 '13 at 00:01
  • @George I listed optimization settings in my question. Performance drop is practically independent of optimization details (O2, O3, Ofast), target or host 32/64 bit setting. I'm going to do profiling. – Paul Jurczak Jul 29 '13 at 00:29
  • @HansPassant I installed the newest MinGW today. What is there to patch? – Paul Jurczak Jul 29 '13 at 00:32
  • That's like saying "I got the latest Microsoft VS version, what can I patch?" Well, nothing of course, you don't have the source code. The point of MinGW is that you *can* patch it, you have the source. Everybody is waiting for you to solve your problem. If that's uncomfortable then just don't use it, there is no point. – Hans Passant Jul 29 '13 at 00:43
  • @HansPassant I misunderstood your first comment: you meant me patching MinGW. I will consider this option, thanks. – Paul Jurczak Jul 29 '13 at 01:16
  • @BenVoigt It is `to_string()` function - see edited question. – Paul Jurczak Jul 29 '13 at 02:02
  • @PaulJurczak Indeed it doesn't seem they implemented it for 4.7 branch... http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52015 – Antonio Jul 29 '13 at 08:36
  • In [``](http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01016_source.html) the `to_string()` function is defined from line 1169 to 1367 in the latest libstdc++. You should perhaps compare it with the definition you have in your libstdc++. – Kyle_the_hacker Jul 29 '13 at 10:17
  • @Kyle: I don't think this is `bitset::to_string`. – Ben Voigt Jul 29 '13 at 14:59

2 Answers2

1

Visual Studio could have reversed the if-condition:

if (digits != rDigits)
    continue;
else
    nMax = max(i*j, nMax);

But that is only a guess...

By the way, I would rather write:

string rDigits(digits.rbegin(), digits.rend());

And you could also take a look at: https://stackoverflow.com/a/17909430/1689664, it might give you some ideas to optimize your algorithm.

Community
  • 1
  • 1
Kyle_the_hacker
  • 1,394
  • 1
  • 11
  • 27
  • 1
    You don't even need `reverse_copy`, just construct the string using reverse iterators `string rDigits(digits.rbegin(), digits.rend());` – Blastfurnace Jul 28 '13 at 23:56
  • Thank you for optimization ideas, but my question is about a huge drop in performance for specific code while migrating from VS to MinGW. – Paul Jurczak Jul 29 '13 at 00:16
  • @Blastfurnace `string rDigits(digits.rbegin(), digits.rend());` doesn't improve speed of MinGW binary and slightly decreases speed of VS binary. – Paul Jurczak Jul 29 '13 at 04:13
  • @PaulJurczak: Did you try to reverse the `if`-condition? Is the speed of the Visual Studio binary the same after `string rDigits(digits.rbegin(), digits.rend());`? If yes, compare to the speed with `string rDigits = reverse_copy(digits.begin(), digits.end());`... – Kyle_the_hacker Jul 29 '13 at 09:33
  • The problem is with implementation of `std::to_string()` in MinGW - see my edited question. – Paul Jurczak Jul 29 '13 at 18:25
  • Yes, nevertheless the difference in constructing `rDigits` is also quite strange... – Kyle_the_hacker Jul 29 '13 at 19:04
1

Check for C++ runtime version used by your MINGW build (use dependency walker or something similar). VS2012 supports r-values and perhaps in your case more importantly small string optimization. Using that would eliminate any memory allocation coming from to_string. Memory allocation requires significantly more CPU than finding max or reverse.

tomas
  • 11
  • 1