Vicennial's blog

Huge runtime difference in recursion involving strings in G++11 vs G++14
By Vicennial, history, 8 years ago, In English

I had to use recursion+strings for a problem in a contest and I stumbled upon this irregularity.

Sample Code 'A' with strings:

Using input=5
Results:
G++ 11 5.1.0 = 7987 ms, 2044 KB
G++ 14 6.2.0 = 889 ms, 1856 KB
------------------------------------

Sample Code 'B' without strings:

Using input=6
Results:
G++ 11 5.1.0 = 3026 ms, 2012 KB
G++ 14 6.2.0 = 2995 ms, 1868 KB

To test it yourself, head over to http://mirror.codeforces.com/problemset/customtest

Why is there such a huge difference when strings are used?

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Do you know the difference between void f(string s) and void f(string &s)?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. Are you trying to say that G++14 optimises it automatically?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I think it doesn`t. Because following code takes 171ms in both C++11 and C++14. Probably there is another way to optimize this.

      code
      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      I'm trying to say that you can use this & and the code becomes significantly faster, as no new instances of strings will be created. Negative votes show that people don't understand it.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I guess negative votes are because your answer has anything common with the question "why is there such a huge time difference".

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The compiler can't change the declaration of f (it is illegal to go from string s to string &s).

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I dont think so. You cant use std::move for s because you are calling go(...) 20 times with same arguments. std::move spoils string, it will be a problem to use it here.

      Or maybe I misunderstood what are you talking about?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it +3 Vote: I do not like it

        Yes, I guess you are right. There has to be another trick done by the compiler.

        L.E.: This isn't only for strings. The optimization is done for vectors (and I guess that for all containers) too.

        → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In g++ version 5.4.1 both programs (-std=c++11 or -std=c++14) have the same speed. So it probably is just an optimization the compiler introduced in version 5.2-4.

→ Reply
»
8 years ago, # |
  Vote: I like it -23 Vote: I do not like it

It might be that on codeforces, G++14 code runs on a faster processor. Optimisations at compiler level don't make sense.

→ Reply
»
8 years ago, # |
  Vote: I like it +34 Vote: I do not like it

I believe it's due to a different compiler version, not 11 or 14 standard.

I have tested it on my computer on g++ 6.3 (both g++11 and g++14 ran around 1s) and g++ 4.9 (both ran around 1.3s). On ideone g++ and g++14 (both from version 6.3) run in the same time while g++ (but version 4.3.2) is slower (output is clock ticks).

In all these runs there was no difference between runtimes of g++, g++11 and g++14, while there were differences between versions. I didn't get to test 5.1 though.

→ Reply