Why does the following snippet speed up the code?

Question

I was solving the Search Insert Position problem on LeetCode. The following code takes almost 9ms to run all test cases.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target < nums[mid]) {
                hi = mid - 1;
            } else if (target > nums[mid]){
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        return lo;
    }
};

When I checked out other people's top answers, I found a strange code snippet. When I copy-paste the snippet into my answer, the same code above takes only 4ms, which is faster than almost 99% of other solutions. Can anyone explain the speed up? The snippet is the following:

#include <vector>
#include <iostream>
using namespace std;

static vector<int> nums=[](){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return vector<int>{};
}();

Some sites offer bogus knowledge. Some don't. The so called _competitive programming_ is bogus knowledge imho. You are far better off reading one these [C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). That being said it is unclear what the problem is as there is no problem to begin with. — Ron, Jan 21 '18 at 14:44
It's just a trick to run `std::ios::sync_with_stdio(false); cin.tie(NULL);` before `main` is entered. Those two lines turn off synchronization between C++ standard streams `cin` and `cout`, and C standard streams `stdin` and `stdout`; on some systems, this improves performance of reading and writing standard streams. Apparently, most of the time in your case is spent not on actually solving the problem, but on I/O before and after. — Igor Tandetnik, Jan 21 '18 at 14:51
For anyone who has doubts on the lambda initialization: I found out that static global variables can be initialized by function calls which I used to take as illegal, check out [this answer](https://stackoverflow.com/questions/6337426/may-i-initialize-a-global-variable-with-the-result-of-a-function-call) for sure. In addition, lambda is called not just defined(the parenthesis). Thank you all guys. — Elinx, Jan 22 '18 at 03:39
The author apparently picked an arbitrary global (or in this case, file scope) variable, and added a lambda-call initializer just to call some completely unrelated initialization functions. Personally, I think this "pattern" should not be used outside of voluntary obfuscation or [code golf](https://en.wikipedia.org/wiki/Code_golf)! — Arne Vogel, Jan 22 '18 at 12:23
The time difference indicates that you spend most of the time doing I/O. Those lines have no influence on the algorithm as such. — molbdnilo, Feb 18 '18 at 14:36

Abdallah · Accepted Answer · 2018-01-21T15:10:16.627

17

This snippet is made to "improve performance" but for a cost. I'll explain:

std::ios::sync_with_stdio(false);

This disables the synchronization of C and C++ standard streams. By default they're synced to allow mixing C and C++ I/O streams (e.g. cout and printf would work written in a C++ file).

cin.tie(NULL);

This unties cin from cout. Again, by default they're tied to make cout appear before cin (i.e. output flushes before input) so you can make for example the following:

cout << "Number: ";
cin >> number;

When you untie them you might get to the input(cin) before getting the output (cout) flushed.

These couple lines help to make code run faster but at the cost previously explained. So use with caution.

References: https://www.geeksforgeeks.org/fast-io-for-competitive-programming

edited Jan 21 '18 at 15:10

answered Jan 21 '18 at 14:58

Abdallah

402
4
14

Can you add the references that confirm this to your answer? – Chiel Jan 21 '18 at 15:01
Done. Thanks @Chiel – Abdallah Jan 21 '18 at 15:10
This is already a good answer, but it would be even better if you also explained what's happening with the initialization from a lambda. – Sneftel Jan 21 '18 at 15:11
1

Didn't this also loose thread-safety of cout? – MikeMB Jan 21 '18 at 18:26
1

Yes. Different outputs interleave most of the time, although no data races will occur. @MikeMB – Abdallah Jan 21 '18 at 20:10
1

@Abdallah: "although no data races will occur." Are you sure? I haven't checked the standard, but cppreference.com days race freedom is only ensured as long as `std::ios::sync_with_stdio` is true – MikeMB Jan 21 '18 at 22:05
@Sneftel I found out that static global variables can be initialized by function calls which I used to take as illegal, check out [this answer](https://stackoverflow.com/questions/6337426/may-i-initialize-a-global-variable-with-the-result-of-a-function-call) for sure. In addition, lambda is called not just assignment. Thank you all guys. – Elinx Jan 22 '18 at 03:35
1

@MikeMB you're right. I understood that point wrongly. And I also can't find information about data races when `sync_with_stdio` is disabled... – Abdallah Jan 22 '18 at 09:03
"Concurrent access to a synchronized (27.5.3.4) standard iostream object’s formatted and unformatted input (27.7.2.1) and output (27.7.3.1) functions or a standard C stream by multiple threads shall not result in a data race (1.10). [Note: Users must still synchronize concurrent use of these objects and streams by multiple threads if they wish to avoid interleaved characters. — end note ]" (iostreams.objects.overview; 27.4.1/4 in N3797) – Arne Vogel Jan 22 '18 at 10:43

Why does the following snippet speed up the code?

1 Answers1