C ++ fast cin for reading stdin?

Question

I have profiled a complex C ++ program on Linux using cachegrind. Surprisingly, it turned out that the bottleneck of my program was not in any sorting or computational method ... it was while reading the input.

Here is a screenshot of cachegrind if I misinterpret the profiling results ( see scanf() ):

I hope I am right in saying that scanf() takes up 80.92% of my working time.

I am reading input using cin >> int_variable_here , for example:

 std::ios_base::sync_with_stdio (false); // Supposedly makes I/O faster cin >> NumberOfCities; cin >> NumberOfOldRoads; Roads = new Road[NumberOfOldRoads]; for (int i = 0; i < NumberOfOldRoads; i++) { int cityA, cityB, length; cin >> cityA; //scanf("%d", &cityA); // scanf() and cin are both too slow cin >> cityB; //scanf("%d", &cityB); cin >> length; //scanf("%d", &length); Roads[i] = Road(cityA, cityB, length); } 

If you have not noticed any problems with this input input code, could you recommend a faster way to read the input? I'm thinking of trying getline() (working on it while I wait for answers). I assume that getline () might work faster because it needs to do less conversion and it analyzes the stream less than the total number of times (just my guess, although I will eventually have to parse the strings as integers).

What I mean by “too slow” is that it is part of a larger homework that expires after a certain period of time (I think it is 90 seconds). I'm pretty sure the bottleneck is here because I intentionally commented on the bulk of the rest of my program, and it is still timed. I don’t know what test examples the instructor runs through my program, but it must be a huge input file. So what can I use to quickly read input?

The input format is strict: 3 integers, separated by one space for each line, for many lines:

Input Example:

 7 8 3 7 9 2 8 9 1 0 1 28 0 5 10 1 2 16 

I need to make Road from integers on each line.

It is also not recommended that the input be redirected to my program for standard input ( myprogram < whatever_test_case.txt ). I do not read a specific file. I just read from cin .

Update

Using the Glory method:

Reading the input seems to take less time, but its timeout (maybe not due to data input anymore). The Slava method is implemented in Road() ctor (2 from main ). So now it takes 22% of the time, not 80%. I am thinking about optimizing SortRoadsComparator() , as it is called 26,000,000 times.

Comparator Code:

 // The complexity is sort of required for the whole min() max(), based off assignment instructions bool SortRoadsComparator(const Road& a, const Road& b) { if (a.Length > b.Length) return false; else if (b.Length > a.Length) return true; else { // Non-determinism case return ( (min(a.CityA, a.CityB) < min(b.CityA, b.CityB)) || ( (min(a.CityA, a.CityB) == min(b.CityA, b.CityB)) && max(a.CityA, a.CityB) < max(b.CityA, b.CityB) ) ); } } 

Using the Entroflept Method

Given the decision

I am going to consider this problem because the bottleneck is no longer used for reading. The Glory Method was the fastest for me.

Answer 1

Streams know pretty well that they are very slow. However, this is not a big surprise - they need to handle localizations, conditions, etc. One possible solution would be to read a line by line at std :: getline (std: cin, str) and convert the line to numbers using something like this:

 std::vector<int> getNumbers( const std::string &str ) { std::vector<int> res; int value = 0; bool gotValue = false; for( int i = 0; i < str.length(); ++i ) { if( str[i] == ' ' ) { if( gotValue ) res.push_back( value ); value = 0; gotValue = false; continue; } value = value * 10 + str[i] - '0'; gotValue = true; } if( gotValue ) res.push_back( value ); return res; } 

I have not tested this code, I wrote it to show this idea. I assume that you do not expect to get anything in the input except spaces and numbers, so it does not check the input.

To optimize sorting in the first place, you should check if you really need to sort the whole sequence. For the comparator, I would write getMin () getMax () methods and store these values ​​in the object (so as not to calculate them all the time):

 bool SortRoadsComparator(const Road& a, const Road& b) { if( a.Length != b.Length ) return a.Length < b.length; if( a.getMin() != b.getMin() ) return a.getMin() < b.getMin(); return a.getMax() < b.getMax(); } 

if I understand how the current comparator works.

Answer 2

As Slava says, threads (i.e. cin) are absolute pigs in terms of performance (and the size of the executable)

Consider the following two approaches:

 start = clock(); std::ios_base::sync_with_stdio (false); // Supposedly makes I/O faster cin >> NumberOfCities >> NumberOfOldRoads; Roads = new Road[NumberOfOldRoads]; for (int i = 0; i < NumberOfOldRoads; i++) { int cityA, cityB, length; cin >> cityA >> cityB >> length; Roads[i] = Road(cityA, cityB, length); } stop = clock(); printf ("time: %d\n", stop-start); 

and

 start = clock(); fp = stdin; fscanf(fp, "%d\n%d\n", &NumberOfCities, &NumberOfOldRoads); Roads = new Road[NumberOfOldRoads]; for (int i = 0; i < NumberOfOldRoads; i++) { int cityA, cityB, length; fscanf(fp, "%d %d %d\n", &cityA, &cityB, &length); Roads[i] = Road(cityA, cityB, length); } stop = clock(); printf ("time: %d\n", stop-start); 

Performed 5 times each time (with an input file of 1,000,000 records + the first 2 'control lines) gives us the following results:

• Using cin without direction for unsynchronization with stdio 8291, 8501, 8720, 8918, 7164 (avg 8318.3)

• Use cin c to not sync with stdio 4875, 4674, 4921, 4782, 5171 (avg 4884.6).

• Using fscanf 1681, 1676, 1536, 1644, 1675 (avg 1642.4).

So it’s clear that sync_with_stdio (false) direction helps. You can also see fscanf beating pants from every approach with cin. In fact, the fscanf approach is almost 3 times faster than the best of cin approaches and a whopping 5 times faster than cin when it is not advised to avoid synchronization with stdio.

Answer 3

 inline void S( int x ) { x=0; while((ch<'0' || ch>'9') && ch!='-' && ch!=EOF) ch=getchar_unlocked(); if (ch=='-') sign=-1 , ch=getchar_unlocked(); else sign=1; do x = (x<<3) + (x<<1) + ch-'0'; while((ch=getchar_unlocked())>='0' && ch<='9'); x*=sign; } 

this function can be used for input of any type, just change the type of paramater. This will work faster than std scanf.

If you want to save more time, it is best to use fread () and fwrite (), but in this case you will have to manipulate the input yourself. To save time, you should use fread () to read a large piece of data from the standard input stream in a single call. This will reduce the number of I / O calls, therefore, you will see a big time difference.