8
\$\begingroup\$

Basically, I want to write a huge file of numbers. Each line in that file should contain one number. This program below is extremely slow (obviously) but it works. It writes one line after line and always one number until the limit of an unsigned long has been reached.

#include <iostream>
#include <limits>
#include <fstream>

int main() {

    unsigned long max = std::numeric_limits<unsigned long>::max();
    unsigned long i = 0;
    std::ofstream myFile;
    myFile.open( "/home/awesome/Desktop/large_numbers.txt" );
    while( i < max ) {

        myFile << i << "\n";
        i++;

    }
    myFile.flush();
    myFile.close();
}

This program wrote in 2 minutes on my desktop computer 12GB. On my laptop only 117 MB in 10 minutes. On both computers I had to stop the program because it was making my computer slow and still wasn't done. Any way to optimize it so it'll be faster and maybe run more smooth so my other programs will still run perfectly fine?

\$\endgroup\$
  • 1
    \$\begingroup\$ Please change your title to reflect what your code does. \$\endgroup\$ – Nic Hartley Jun 22 '15 at 17:28
  • 1
    \$\begingroup\$ This is as fast as it will go. You are no limitted by the speed of the program (in fact the program is going to fast). The limiting factor is the speed of your hard disk. Your hard disk is not fast enough and can not copy the data from memory to the disk quickly enough and this is why your machine is slowing down. Quick top of the head calculations put the size of this file at 163,000,000 Terra bytes (so unless you have a very big raid array you will run out of disk space). \$\endgroup\$ – Martin York Jun 22 '15 at 17:41
  • 1
    \$\begingroup\$ 1) Set max to something reasonable. 2) When testing the speed of the program, output to /dev/null in order to remove the hard drive speed from the equation. I'm betting your program runs very fast when outputting to /dev/null. \$\endgroup\$ – JS1 Jun 22 '15 at 18:07
  • \$\begingroup\$ to make this program run smooth, you can try to put a sleep with 50-100 milisecond into you're code, that will slow your program, but give process time to other process that are running, then your computer will run without slowing \$\endgroup\$ – karim Jun 22 '15 at 21:32
  • 1
    \$\begingroup\$ Can I ask why you want a list of all of the numbers? Is it in case you forget one of them? \$\endgroup\$ – Yann Jul 2 '15 at 8:30
15
\$\begingroup\$

Few things.

This number:

unsigned long max = std::numeric_limits<unsigned long>::max();

Is

18446744073709551615

If we assume that the average size of a number is half this length (so 10 characters). Then the size of the file is:

   184467440737095516150 bytes.
=> 180143985094819830 Kbytes
=> 175921860444150 MBytes
=> 171798691830 GBytes
=> 167772150 TBytes
=> 163830 PBytes
=> 150 XBytes

Unless you have some sort of massive raid. I don't think you have storage space foe all those numbers.

Even if your system uses a smaller number of bits for an unsigned long than mine (say 32 bit). This is still a large file (though doable on modern systems).

=> 15 GBytes (approx)

But the problem is not the speed of the program. Its is the speed that the OS can copy data to the disk. That will be your limiting factor. If you want to see how fast it could write to an optimal disk then use the special file "/dev/null". You can write to this and it uses no disk space.

12G in 2 min is a write rate of:

107374182 bytes a sec or
104857 K/s
102 M/s

A quick Google reveals that 500 M/s is achievable for SSD drives while normal HD achieve approx 100 M/s. So it looks like your desk top has normal spinning platter hard disk and it was going at the top speed.

Laptops are known to slower. Especially when they get hot. The hardware is designed to physically throttle the system to make sure it does not overheat.

Why not create and open the file in one line?

std::ofstream myFile;
myFile.open( "/home/awesome/Desktop/large_numbers.txt" );

I would do this:

std::ofstream myFile( "/home/awesome/Desktop/large_numbers.txt" );

Simpler to use a for(;;) loop than a while().

for(unsigned long i = 0;i <= max; ++i)
    myFile << i << "\n";               // Note because you opened the file in
                                       // text mode. The '\n' character will
                                       // translated into the platform end of
                                       // of line sequence.
}

No need to flush or close the stream manually.

myFile.flush();
myFile.close();

When the object goes out of scope the destructor is called. This will close the file which will flush the content of the buffers first.

#include <iostream>
#include <limits>
#include <fstream>

int main() {

    unsigned long max = std::numeric_limits<unsigned long>::max();

    std::ofstream myFile( "/home/awesome/Desktop/large_numbers.txt" );
    for(unsigned long i = 0; i < max; ++i) {
        myFile << i << "\n";
    }
}
\$\endgroup\$
  • \$\begingroup\$ If we assume that the average size of a number is half this length (so 10 characters can you explain this phrase please? \$\endgroup\$ – Caridorc Jun 22 '15 at 18:00
  • 1
    \$\begingroup\$ @Caridorc: Well: 18446744073709551615 is 20 digits. 0 is 1 digit. So on average there are 10 digits in a number (10 also makes the maths easy). \$\endgroup\$ – Martin York Jun 22 '15 at 18:02
  • \$\begingroup\$ Ah ok I got it . \$\endgroup\$ – Caridorc Jun 22 '15 at 18:30
  • 4
    \$\begingroup\$ Consider that in the range from 0 to 99 only 10 numbers are 1 character long. I think the average will be very close to 20 characters in the OP's case \$\endgroup\$ – Sergey Jun 23 '15 at 1:42
  • \$\begingroup\$ @Sergey: Sure. But do you really think it makes difference? 150 Xbytes or 300 Xbytes? Also I find multiplying by 10 (or 16 for hex) much easier than multiplying by other numbers as you just add a zero to the end. \$\endgroup\$ – Martin York Jun 23 '15 at 19:29
6
\$\begingroup\$

This is just a simple mathematical supplement to Martin York's answer and not a review, per se, however it's too long and detailed for a comment. I'm hoping it's useful anyway, even if limited in scope.

File size prediction

If we consider the (decimal) numbers from 1 to 999 inclusive, and if we assume that the newline character is a single character, let's calculate the file size:

range  count  char/each  total
1-9        9          2     18
10-99     90          3    270
100-999  900          4   3600

From this, it's pretty easy to see that there's a pattern. If \$i\$ is the power of ten (technically \$\lfloor\log_{10} i\rfloor\$), then the equation that governs the number of bytes including newline for the half-open range \$[1,10^{k})\$ is

$$ \displaystyle f(k) = \sum_{i=0}^{k} (2+i)(9)10^{i} $$

If we start from 0, we just add two bytes, and the equation becomes

$$ \displaystyle f(k) = 2 + \sum_{i=0}^{k} (2+i)(9)10^{i} $$ The closed form is $$ 2+\sum_{i=0}^n (2+i)(9)10^i = \frac{10^{n + 1}(9n + 17) + 10}{9} $$

Calculating this for various values of \$k\$: $$ \begin{eqnarray} f(1)=290 \\ f(2)=3890 \\ f(3)=48890 \\ f(4)=588890 \\ f(5)=6888890 \\ f(6)=78888890 \\ f(7)=888888890 \\ f(8)=9888888890 \\ f(9)=108888888890 \\ f(10)=1188888888890 \\ f(11)=12888888888890 \\ f(12)=138888888888890 \\ f(13)=1488888888888890 \\ f(14)=15888888888888890 \\ f(15)=168888888888888890 \\ f(16)=1788888888888888890 \\ f(17)=18888888888888888890 \\ f(18)=198888888888888888890 \\ f(19)=2088888888888888888890 \\ f(20)=21888888888888888888890 \\ \end{eqnarray} $$ So a quick approximation is

$$ f(k) \approx (k+1.9)\times 10^{k+1} $$

In other words, you'd need \$2\times 10^{16}\$ MiB to store all of the numbers \$[0,10^{20})\$.

Write duration prediction

To my knowledge, 1400 Mb/s as quoted in this 2013 article is among the fastest quoted rates for a Solid State Drive (SSD) using PCIe. That works out to \$1.5\times 10^{13}\$ seconds, or \$4.3\times10^9\$ hours, \$1.8\times 10^8\$ days, or \$495440\$ years.

So even with astonishingly large arrays of the fastest available PCIe devices, it would still take almost a half million years to write the file, even if the numerical formatting performed by the std::ostream were instant (that is, if it took no time at all).

For reference, a half million years ago would put us in the Paleolithic period just before the time that our ancestors had figured out how to regularly use fire. Archaeologists are still debating how fast their computer I/O went.

\$\endgroup\$
2
\$\begingroup\$

This is one case where you might find the use of C-style I/O actually faster. There is some overhead to C++ I/O (it isn't much, but it is there). For 50 million, it's ~3x faster for me.

#include <cstdio>

std::FILE* f = std::fopen("/home/awesome/Desktop/large_numbers.txt", "w");
for(unsigned long i = 0; i < max; ++i) {
    std::fprintf(f, "%lu\n", i);
}
std::fclose(f);

That having been said, this is nothing more than an artificial test of your operating system I/O subsystem and the hardware lying underneath it.

Edit: Here is the code for comparison:

int main() 
{
    std::ios::sync_with_stdio(false);
    const unsigned long max = 50000000;

    std::ofstream myFile;
    myFile.open("C:\\include\\large_numbers.txt");

    auto begin = std::chrono::steady_clock::now();
    for (unsigned long i = 0; i < max; ++i) {
        myFile << i << '\n';
    }
    auto end = std::chrono::steady_clock::now();
    std::cout << "Took " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << '\n';
}

On Yuushi Machine: This takes 32877ms
On Loki's Machine: This takes 11851ms

For comparison, the following code:

int main() 
{
    const unsigned long max = 50000000;
    FILE* f = std::fopen("C:\\include\\large_numbers.txt", "w");

    auto begin = std::chrono::steady_clock::now();
    for (unsigned long i = 0; i < max; ++i) {
        std::fprintf(f, "%lu\n", i);
    }
    std::fclose(f);
    auto end = std::chrono::steady_clock::now();
    std::cout << "Took " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << '\n';
}

On Yuushi Machine: This takes 13245ms.
On Loki's Machine: This takes 08420ms.

Yuushi: Compiled with VS2015RC with default Release settings (so /O2).
Loki's: Compiled with clang-602.0.53 with --std=c++14 -O3 (Loki's machine uses SSD drives)

Second Edit: Trying this on other systems/configurations (so gcc 4.9.2 on cygwin and gcc5 on OS X) actually reverses these results - the C++ version is faster for me.

\$\endgroup\$
  • \$\begingroup\$ @LokiAstari I'm aware of this. The timing is vs the code with std::ios_base::sync_with_stdio(false); added already. \$\endgroup\$ – Yuushi Jun 22 '15 at 18:25
  • \$\begingroup\$ I tested the same senario (with the corrections). With the C++ streams synced to C streams I got a 50% decrease in performance. When they are not synced I see a 25% decrease in performance. All three compiler with -O3. Three X seems a bit off. \$\endgroup\$ – Martin York Jun 22 '15 at 18:32
  • \$\begingroup\$ You need to add one line (which will make the C++ slower) to have a fair comparison. The file close (and thus the flush) is not inside the timed section for C++. \$\endgroup\$ – Martin York Jun 22 '15 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.