Optimizing IO in C++

Question

I'm having trouble optimizing a C++ program for the fastest runtime possible.

The requirements of the code is to output the absolute value of the difference of 2 long integers, fed through a file into the program. ie:

./myprogram < unkownfilenamefullofdata

The file name is unknown, and has 2 numbers per line, separated by a space. There is an unknown amount of test data. I created 2 files of test data. One has the extreme cases and is 5 runs long. As for the other, I used a Java program to generate 2,000,000 random numbers, and output that to a timedrun file -- 18.MB worth of tests.

The massive file runs at 3.4 seconds. I need to break that down to 1.1 seconds.

This is my code:

int main() {
long int a, b;
while (scanf("%li %li",&a,&b)>-1){
  if(b>=a)
    printf("%li/n",(b-a));
  else
    printf("%li/n",(a-b));
  } //endwhile
return 0;
}//end main

I ran Valgrind on my program, and it showed that a lot of hold-up was in the read and write portion. How would I rewrite print/scan to the most raw form of C++ if I know that I'm only going to be receiving a number? Is there a way that I can scan the number in as a binary number, and manipulate the data with logical operations to compute the difference? I was also told to consider writing a buffer, but after ~6 hours of searching the web, and attempting the code, I was unsuccessful.

Any help would be greatly appreciated.

Your program doesn't read the file, you are using redirection to feed the file contents to the program. Load the file directly in your application, load it entirely in memory, and find a lower level routine than scanf to parse it. — Jonathan Wood, Feb 11 '12 at 15:32
When I attempted to load the file into the program, I still found myself using scanf to read its contents. Would I need to change to fscanf? Also, is a file considered "loaded" into the program just by making a FILE * pFile, and telling it that it is coming from the stdin? — Clark Kent, Feb 11 '12 at 15:50
@user1203882: `scanf` always reads from STDIN. If you want to read from another file stream, you have to use `fscanf`. — Niklas B., Feb 11 '12 at 16:03
just a hint: when profiling IO bound applications, you might "see" the hard drive's internal caches. The same program can take lots of time at the first time you call it and be fast if you repeat the call (because the file is in the HDs cache). You can usually "clear" the cache by copying some other big files around before calling the program again. — Philipp, Feb 11 '12 at 16:32
The new line character is `\n` not `/n`. Also, are you timing this when calling the function like `./myprogram < unkownfilenamefullofdata` which would write to the terminal or like `./myprogram < unkownfilenamefullofdata > /dev/null` (or writing to a file). When I write to /dev/null (or a file) your program takes about 1 second on my machine with similar data to that you described. Writing to the terminal takes over 6 seconds on my machine. — Justin Peel, Feb 11 '12 at 17:01

score 1 · Accepted Answer · answered Feb 11 '12 at 15:27

1

What you need to do is load the whole string into memory, and then extract the numbers from there, rather than making repeated I/O calls. However, what you may well find is that it simply takes a lot of time to load 18MB off the hard drive.

answered Feb 11 '12 at 15:27

Puppy

144,682
38
256
465

2

Reasonably modern hard drives are capable of reading between 80-120 MB/s. This isn't explaining the time taken. – Ben Voigt Feb 11 '12 at 16:51
@BenVoigt: Who says he has a reasonably modern hard drive? – Puppy Feb 11 '12 at 22:41
You're right. If he cares about performance, he probably has a SATA-II SSD (200 MB/s) or a SATA-III SSD (500 MB/s). Or hot file system cache (multiple GB/s). – Ben Voigt Feb 12 '12 at 01:15

score 1 · Answer 2 · answered Feb 11 '12 at 16:00

You can improve greatly on scanf because you can guarantee the format of your file. Since you know exactly what the format is, you don't need as many error checks. Also, printf does a conversion on the new line to the appropriate line break for your platform.

I have used code similar to that found in this SPOJ forum post (see nosy's post half-way down the page) to obtain quite large speed-ups in the reading integers area. You will need to modify it to deal with negative numbers. Hopefully it will give you some ideas about how to write a faster printf function as well, but I would start with replacing scanf and see how far that gets you.

faster `printf` for integers = `itoa` + `puts`. Optimized versions of `itoa` [here](http://stackoverflow.com/questions/4351371/c-performance-challenge-integer-to-stdstring-conversion). — Ben Voigt, Feb 11 '12 at 16:53

ravenspoint · Answer 3 · 2012-02-11T16:33:42.163

As you suggest the problem is reading all these numbers in and converting from text to binary.

The best improvement would be to write the numbers out from whatever program generates them as binary. This will reduce significantly reduce the amount of data that has to be read from the disk, and slightly reduce the time needed to convert from text to binary.

You say that 2,000,000 numbers occupy 18MB = 9 bytes per number. This includes the spaces and the end of line markers, so sounds reasonable.

Storing the numbers as 4 byte integers will half the amount of data that must be read from the disk. Along with the saving on format conversion, it would be reasonable to expect a doubling of performance.

Since you need even more, something more radical is required. You should consider splitting up the data file onto separate files, each on its own disk and then processing each file in its own process. If you have 4 cores and split the processing up into 4 separate processes and can connect 4 high performace disks, then you might hope for another doubling of the performance. The bottleneck is now the OS disk management, and it is impossible to guess how well the OS will manage the four disks in parallel.

I assume that this is a grossly simplified model of the processing you need to do. If your description is all there is to it, the real solution would be to do the subtraction in the program that writes the test files!

"The best improvement [...] write the numbers [...] as binary." <--- This. (Well, this, and memory map the file rather than pushing it all through a pipe). — Damon, Feb 13 '12 at 11:09

score 0 · Answer 4 · answered Feb 11 '12 at 16:55

Even better than opening the file in your program and reading it all at once, would be memory-mapping it. ~18MB is no problem for the ~2GB address space available to your program.

Then use strtod to read a number and advance the pointer.

I'd expect a 5-10x speedup compared to input redirection and scanf.

Optimizing IO in C++

4 Answers4