Huge runtime difference in recursion involving strings in G++11 vs G++14

→ Pay attention

Before contest
Codeforces Round 941 (Div. 1)
17:38:30
Register now »

*has extra registration

Before contest
Codeforces Round 941 (Div. 2)
17:38:30
Register now »

*has extra registration

→ Streams

Atcoder ABC #351 Short Solution Discussion

By aryanc403

Before stream 16:43:30

View all →

→ Top rated

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

View all →

→ Find user

→ Recent actions

Detailed →

Huge runtime difference in recursion involving strings in G++11 vs G++14

Revision en1, by Vicennial, 2017-03-15 12:20:01

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

Sample Code 'A' with strings:

#include<bits/stdc++.h>
using namespace std;
int n;
void go(string s,int x){
	if(x>n) return;
	string p="1";
	s+=p;
	for(int i=0;i<20;i++){
		go(s,x+1);
	}	
}
int main(){
	cin>>n;
	string s="1";
	for(int i=0;i<20;i++){
		go(s,1);
	}
}

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:

#include<bits/stdc++.h>
using namespace std;
int n;
void go(int s,int x){
	if(x>n) return;
	for(int i=0;i<20;i++){
		go(1,x+1);
	}	
}
int main(){
	cin>>n;
	for(int i=0;i<20;i++){
		go(1,1);
	}
}

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://codeforces.com/problemset/customtest

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

c++ 11, c++ 14, bug, c++11 vs c++14

History

Revisions

	Rev.	Lang.	By	When	Δ	Comment
	en1		Vicennial	2017-03-15 12:20:01	1303	Initial revision (published)