sahaun's blog

By sahaun, history, 2 months ago, In English

I submitted exactly the same code for 86D - Мощный массив on different platforms. Here are the results:

There is a small increase in memory when using 64-bit, but the time difference is pretty huge!

Can anybody explain why?

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

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

long long is a 64-bit data type and obviously works best on a 64-bit system

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

    Makes sense, thanks.

    Is there a reason to use non-64-bit versions at all?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +34 Vote: I do not like it

      On the 32-bit version, pointers are 32 bit, while on 64-bit, pointers are 64 bit. So if you for some reason need to store a ton of pointers, then the 32-bit version would use half the memory compared to the 64-bit version. That said, 64-bit is better to use in basically any other scenario.

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

It is actually different in my case.

GNU C++17 (64): 165333338 $$$→$$$ 156 ms

GNU C++17: 165333363 $$$→$$$ 62 ms

Solution also uses long long int. There is no difference in memory usage.

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

    I think you will see the differences when running a heavy program or using more pointers as pajenegod suggested above.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    What you see there is scanf being faster in C++17(32) than C++17(64). Switching to cin/cout makes your code run in 46 ms 165347564 in C++17(64).

    I belive that part of the reason why scanf is faster in C++17(32) than C++17(64) is that Codeforces is using a custom made I/O speed up patch for C++17(32) (link).

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

      Sorry, shouldn't there be faster instead of slower in first sentence of your comment.

      Thank you, I thought cin is always slower than scanf.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 4   Vote: I like it +1 Vote: I do not like it

        Ah thanks, it should have been faster.

        About cin and scanf. I don't think there is any fundamental reason why one is faster than the other in general.

        I'd personally recommend using cin/cout instead of scanf/printf. Just remember to put something like ios::sync_with_stdio(false); cin.tie(0); in the beginning of main if you are using cin/cout.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it -38 Vote: I do not like it

          I don't think ios::sync_with_stdio(false); cin.tie(0); is a really reliable way to accerelate cin/cout. There are cases in which they skip some input randomly and lead to wrong answer, especially when the data is large enough. Personally I insist scanf/printf is the best way to I/O. It's fast and stable.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            I have never experienced any problems with cin/cout. Maybe you are just doing it wrong?

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

            Could you point me towards such examples, preferably some problem on an online judge, or maybe a custom test generation setup that makes them fail?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            I've never ever seen cin "skip some input randomly".

            One thing that is true is that ios::sync_with_stdio(false); is not always faster. For example, on cf the following program takes

            #include <bits/stdc++.h>
            using namespace std;
            int main() {
                //ios::sync_with_stdio(false);
                for (int i = 0; i < 10000000; ++i)
                  cout << i << '\n';
            }
            

            Without ios::sync_with_stdio(false);

            • C++14(32) 1559 ms

            • C++17(32) 1574 ms

            • C++17(64) 1185 ms

            • C++20(64) 1216 ms

            With ios::sync_with_stdio(false);

            • C++14(32) 1575 ms

            • C++17(32) 1559 ms

            • C++17(64) 1372 ms

            • C++20(64) 889 ms

            So C++17(64) cout actually becomes slower when you use ios::sync_with_stdio(false);. That said, cin becomes a lot faster in C++17(64) with ios::sync_with_stdio(false);, so it is still worth to use it.