yak_ex's blog

By yak_ex, 7 years ago, In English,

Updated: Add note for Cygwin environment.
Updated: Add result on FreeBSD 

In programming competition such as Codeforces, reading a large number of inputs is somtimes required, for example, 1500*1500 integers in Codeforces Beta Round #43 Problem E. I used iostream(cin) in the competition and got TLE. After the competition, I saw some comments that cin caused TLE. After I replaced cin with scanf, I got AC. So, it is said "For large input, use cstdio instead of iostream." However I believe C++ users want to use iostream. Can't we avoid the guideline?

Short answer:

I found one promising way. Unfortunately, it is applicable not to VC but to gcc. Call std::ios_base::sync_with_stdio(false) at the beginning of your code. Here is the graph to show performance comparison among iostream with the call, without the call and cstdio, in my local environments. [Updated: NOTE that File I/O on Cygwin is generally very slow. Therefore, the effect is overestimated in graph on Cygwin environment.]

X-axis shows the number of inputs and Y-axis shows seconds to read inputs. The scale of Y-axis is different between graphs.

The summary of my local environment is as follows:

  • Cygwin
    • CPU: Core2Duo T7600 2.3Ghz
    • RAM: 4GB
    • OS: Windows XP SP3
    • Compiler: gcc 4.3.4 on Cygwin 1.7.7
  • FreeBSD
    • CPU: PentiumM 1.3GHz
    • RAM: 1GB
    • OS: FreeBSD 8.1-STABLE
    • Compiler: gcc 4.2.1

Target source code is here (at codepad.org).

Though I don't know the precise effect in the judge environment, I can get AC with iostream, at least, for Codeforces Beta Round #43 Problem E. NOTE that the effect of the call depends on implementation of C++ standard library. For example, there is no significant difference for VC++.

Short explanation:

Calling sync_with_stdio(false) may improve performance. What is the actual effect of the call?

The standard (ISO/IEC 14882:2003) says:


27.4.2.4 ios_base static members
bool sync_with_stdio(bool sync = true);
Returns: true if the standard iostream objects (27.3) are synchronized and otherwise returns false.
The first time it is called, the function returns true.

Effects: If any input or output operation has occurred using the standard streams prior to the call, the effect is implementation-defined. Otherwise, called with a false argument, it allows the standard streams to operate independently of the standard C streams.


This means that synchronization with standard C stream is required without the call. In libstdc++ (C++ standard library used by g++), this flag switches iostream object's underlying buffer between stdio_filebuf and stdio_sync_filebuf. stdio_sync_filebuf has little buffering by itself and delegate almost all operation to cstdio. See also libstdc++ manual page.

For programming competition, there seems to be little use of mixture of cstdio and iostream. Thus, I recommend that you include the call in your code template. :p

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

7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Man, what a great post! Although I really appreciate some of scanf format features, I have to say most of the time I use it because of the time issue( I guess most of us have came across one of this huge input problems some time). With the information you provide, I may give cin a second chance.........thanks for this contribution.
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it
That seems to be expanded version of one of the first posts at Codeforces, where we can find similar text in Russian.
  • 7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you.

    I did not recognize the post. One of the reason is that I can not read Russian. :p

    I found sync_with_stdio(false) in googling "iostream performance" or so. There are some talks about iostream poor performance. However, it is distributed and does not have clear conclusion. So, I think making this post would be useful for others.

7 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
Thank you too, now we can see real benefits of that approach, expressed in numbers.
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Good post.
But my experiment shows that cstdio is always the fastest.
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had a strange experience, once iostream with sync...(false) was faster than cstdio but once it's been exactly reverce.the first one was on this problem and the second was sgu's 302.and here are the codes:first, second.I made a little change in the getting input & printing output on the codes to test the differences.but the main codes are the same and have the same results(u can test it :D).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

once I heard that using getchar() is the fastest way at all. could you please add this test to your results?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for sharing this knowledge ^_^ can someone please tell if this is faster than buffer reading by using getchar_unlocked () ...

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

http://codeforces.com/problemset/gymProblem/100741/D

time limit = 1s;

here using ios_base::sync_with_stdio(0); cin.tie(NULL);

give TLE but using scanf and printf instead gives AC. running time = 0.561s.

cin, cout may fail even after using ios_base....

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

    Could you provide some evidence?

    tests show that iostream is actually faster for integers than stdio ant this problem deals with integers only. (at least on GCC)

    I'm not doubting of you. It's just that your counter example would be the first one I've ever seen that contradicts all those guys arguments about iostream.

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

    Nevermind, I did it myself and you are absolutely correct.

    I think its because the problem is not about integers, but long integers. In this case iostream probably is as bad as it is for double (twice as slow).

    iostream TLE http://codeforces.com/gym/100741/submission/13717970

    stdio AC http://codeforces.com/gym/100741/submission/13718007

»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks! very informative post (y)