Блог пользователя yak_ex

Автор yak_ex, 14 лет назад, По-английски

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

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.
14 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
That seems to be expanded version of one of the first posts at Codeforces, where we can find similar text in Russian.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

14 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
Thank you too, now we can see real benefits of that approach, expressed in numbers.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Good post.
But my experiment shows that cstdio is always the fastest.
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

http://codeforces.me/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....

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.me/gym/100741/submission/13717970

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -21 Проголосовать: не нравится

      The limit is 10^9 so integers suffice, you don't need long integers. Also I had one problem with long longs where I got accepted with iostream but TLE with stdio.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        3 years ago

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Why so many downvotes? Yes, the comment I replied to is from 3 years ago but the article itself is from 8 years ago and the other late comments don't have a negative rating. I've just read this article and thought that villasv would still like to hear my feedback. Also, I thought only paras and villasv would get notified about my comment. Could it be that because it's my first comment here codeforces notifies everyone about it? If there is something wrong in what I said, please correct me.