SPyofgame's blog

By SPyofgame, history, 5 years ago, In English

----------

Purpose:

  • First, sorry for my bad English.
  • Second, I know there are lots of topics about this. But after solving a problem that need FastIO, I feel interested in FastIO and decide to do the implementations and comparing them. But it maybe time-consuming so I make this post for ones who maybe try to find the Effeciency-Simple-IO, so you can save time instead of searching more.
  • Third, usually it is need not to use FastIO. In the contest, they usually have twice or more time of the solutions code than the given time limitation. Dont worry about faster IO if it is not needed, you should improve your algorithms first, maybe you can use Bitwise Operations for x8 x32 x64 faster.
  • Fourth, if the problem need to be solve in O(n) ~ O(n log n), and your algorithms work in O(n ^ 2), this Micro-Optimization doesnt help you at all (maybe you will get some more points but hard get AC), you should change the algorithms for further approach.
  • Final, for some problems that needed to be solved by FastIO, you can use the suitable template and modify it for your solving the problem. Dont use the template if you dont really know how to use (I may add a guide path to the post in the future)
  • Conclusion, this post is about comparing the implementations for each version of C++ language and you should choose the most suitable for you.

Here are some implementations to output numbers I found

Time to write first 10.000.000 non-negative numbers

(base on Codeforces Custom Test // GNU G++ 17 7.3.0 // GNU G++ 14 6.4.0 // GNU G++ 11 5.1.0)

Sort by GNU G++ 17 7.3.0
Sort by GNU G++ 14 6.4.0
Sort by GNU G++ 11 5.1.0
Sort by Microsoft Visual C++ 2010
Sort by Microsoft Visual C++ 2017

Time to write 1.000 times first 10000 numbers

(base on Codeforces Custom Test // GNU G++ 17 7.3.0 // GNU G++ 14 6.4.0 // GNU G++ 11 5.1.0)

Sort by GNU G++ 17 7.3.0
Sort by GNU G++ 14 6.4.0
Sort by GNU G++ 11 5.1.0
Sort by Microsoft Visual C++ 2010
Sort by Microsoft Visual C++ 2017

Time to write first 10.000.000 non-positive numbers

(base on Codeforces Custom Test // GNU G++ 17 7.3.0 // GNU G++ 14 6.4.0 // GNU G++ 11 5.1.0)

Sort by GNU G++ 17 7.3.0
Sort by GNU G++ 14 6.4.0
Sort by GNU G++ 11 5.1.0
Sort by Microsoft Visual C++ 2010
Sort by Microsoft Visual C++ 2017

Single Line Template

Putchar Non-recursive toString Implementation
Putchar Non-recursive Dividing Implementation
Putchar Reverse Implementation
Putchar Recursive Implementation
Unlocked-Putchar Non-recursive toString Implementation
Unlocked-Putchar Non-recursive Dividing Implementation
Unlocked-Putchar Reverse Implementation
Unlocked-Putchar Recursive Implementation
Printf Implementation
synchronized(off) Implementation
synchronized(true) Implementation
Cout Implementation
fwrite buffer Implementation

----------

About:

----------

Similiar Topic:

----------

Planning:

  • Test about random 10.000.000 big numbers
  • Test about 10.000.000 numbers 2 ^ k, k integer
  • More implementations (Actually the post is about Faster and Faster Short Output Implementation but I will add some for speed comparing)
  • New output types (long long, double, string)
  • Vote: I like it
  • +62
  • Vote: I do not like it

»
5 years ago, # |
Rev. 12   Vote: I like it 0 Vote: I do not like it

Post's Source is too big to put into the spoiler :'(

Preparing
»
5 years ago, # |
Rev. 9   Vote: I like it 0 Vote: I do not like it

Past: Add and sort Unlocked-Putchar Implementations

Curr: Start working on Input Implementations

Next: Test with Microsoft Visual C++

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

let me tell you about c++11:

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

    Oh, wow, I thought C++ 17 is always faster ? This is new to me, thanks <3

    I will test C++ 11 and C++ 14 later after the contest. Thanks for your suggestion

    By the way, do you know where can I input large amount of code and count the time to run the program ? I want to test Input Implementations too

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

      You can test input and output there ($$$10^6$$$ numbers). My input/output works in 280 ms.

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

        I want to test somewhere Just Input, since another factors may results wrong inputing excution time (I only want to test with input speed only). Is there a website for testing like that ?

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

        [Deleted]

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

If you are interested, I have an implementation of fast input and output classes on github. Link.

Behavior is same as std::cin or std::cout in most competitive programming cases: operator<< and operator>> can be used, there is setprecision for real numbers. There is examples of using there.

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

    Thanks and Yes I am interested <3 But for now I just want to test some implementations which are simple (easy to code and debug or modify) but efficiency to output

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

does it mean that cout is faster than printf, isn't it?

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

Replacing the putchar function with _putchar_nolock which avoids thread-locking overhead in GNU G++17 as follows reduced the execution time of your "Putchar Non-recursive Dividing Implementation" code using Codeforces Custom Test from 3649ms to less than 850ms.

#include <iostream>
using namespace std;

void write_int_aux(int x) {
    if (x > 9) 
        write_int_aux(x/10);
    _putchar_nolock('0'+x%10); }

inline void write_int(int x) {
    if (x < 0) 
        _putchar_nolock('-'), x = -x;
    write_int_aux(x); }

int main() {
    int q = 1e7;
    while (q--) 
        write_int(-q); }
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, I read somewhere that cant use putchar_unlocked() am going to test those

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

      The function _putchar_nolock is not availble in GNU G++11 5.1.0. The fastest performance of your code with this function (561 msec) is achieved using Microsoft Visual C++ 2010.

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

        _putchar_nolock is slower than putchar in c++11 but still better option on c++17

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

          Which C++11 compiler, header file and namespace did you use? I got the following error message when I used the GNU G++11 5.1.0 compiler in Codeforces Custom Test with

          #include <iostream>
          using namespace std;
          

          Invocation failed [COMPILATION_ERROR] Can't compile file: program.cpp: In function 'void write_int_aux(int)': program.cpp:7:29: error: '_putchar_nolock' was not declared in this scope

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

            _putchar_nolock is not a thing on c++11

            just saying that _putchar_nolock on c++17 is slower than putchar on c++11