4

I have a sorted vector of half a milion numbers (in C++). Storing it to a textfile takes about 10 seconds and uses only 50% CPU (1 core). I was thinking of parallelising it, saving 2 separate files (first and second half of vector) and then concatenating these files.

Problem is, I'm not able to find any different way to concatenate other than reading byte-by-byte and joining to the first file... Is there any platform-independent way (Boost or Windows-specific) to join files effectively?

5
  • files don't support such an operation.
    – Dan D.
    Jun 29, 2011 at 10:19
  • 1
    Chances are that the operation will be even slower because the disk will have to seek continuously between two different files. Jun 29, 2011 at 10:24
  • Have you tried a buffered output to the textfile? Jun 29, 2011 at 10:24
  • Your CPU is probably irrelevant here. Very likely, the bottleneck in this operation is your hard drive, not the CPU. Writing to a disk is inevitably a linear operation. Unless you have two hard drives, there ain't no way to parallelise it. Sorry. If you need to write more quickly, you'll just have to purchase a faster hard drive.
    – jforberg
    Jun 29, 2011 at 10:29
  • Writing the data in 2 chunks isn't likely to help; the disk has to sequentially write all the data you have and that is the likely (ultimate) bottleneck. Have you considered writing the data in its native binary format, e.g, writing the binary value for those floats instead of the corresponding text? That avoids a lot of formatting overhead,, and is probably be a lot smaller size and correspondingly faster. You should also consider using a memory-mapped I/O facility to avoid all the standard buffering nonsense and overhead of normal sequential I/O. You can read the data back the same way.
    – Ira Baxter
    Jun 29, 2011 at 13:23

4 Answers 4

4

What little you're telling seems nonetheless to strongly indicate a very inefficient way to write your textfile. Possibly you're using endl, which causes a flush. Replace that with \n. Next, if that doesn't speed things up, consider a more effient number-to-text conversion than simply using <<. sprintf springs to mind. Finally, if you're still in the 10-second range instead of the 1/10 second range, consider more serious optimization (e.g., on a Windows machine you might allocate the file with the right size at the start, so on).

Cheers & hth.,

2
  • 1
    +1 as a simple test using for ( int i=0; i<v.size(); i++ ) myfile << v[i] << "\n"; runs in 0.3s on my Athlon 64 2,7GHz. Probably "endl" is a cause.
    – Tometzky
    Jun 29, 2011 at 10:52
  • first problem was endl, and second was "debug" mode in VS - after "release" compilation, program works 3-4 times faster...
    – Tom
    Jun 30, 2011 at 20:36
0

Concatenating two files would probably take more time, as typical filesystems do not support simple splice operations to piece together multiple files into one file efficiently.

While there are some ways you can write to files using multiple cores, chances are very good the bottleneck is actually your Disk IO speed. You can run vmstat 1 on a Linux system and many Unix systems to see just your disk writing speed. (As well as many other neat measures.) Windows has a similar tool, but I can never recall the name of the thing. If your writing speed is near the speed of your disk, you probably can't get more performance by adding more cores.

If you want to try anyway, there are three approaches that can work:

  • use multiple threads / processes to copy from your vector into a memory mapped location backed by your file. open(2) the file, run mmap(2) to map it into memory, and then start copying data.
  • use multiple threads / processes to copy data to disk using the pwrite(2) system call to specify the offset in the file to write that specific block of data
  • use a single thread and the aio_write(3) system call to submit asynchronous writes to disk. (I'm not convinced that this will actually use multiple cores, but the libraries / kernel certainly could implement it that way.)

The first two approaches require that the data you're writing be a predictable size; if you're really writing 500k numbers, they'll each take 4 or 8 or some other fixed size, making it pretty easy -- just assign the first 256k numbers to the first thread, and the next pile of numbers to the next thread, starting at 256*1024*8 bytes into the file.

Edit

Don't forget that spinning hard drives have latency when seeking all over your drive. Linear read and write patterns work best for spinning metal disks. The random access mechanisms I suggested in the first two bullet points would work best if each were writing to different disks (difficult with a single file :) or you had a solid state drive with no seek latency.

0

I would usually agree that your drive is the bottleneck - BUT if the CPU usage is exactly 50% in a dual-core system, that would imply that CPU is indeed the problem. In that case it is the number to string conversion that is bogging down. See Alf's answer for tips to optimise this.

To parallelise that give each thread a chunk of the vector and an ostream. The first thread gets the file as its ostream, but the others get memory streams. Once the first thread has completed, and as each other thread completes (in order), write each memory stream to the file.

The formatting is now done in parallel, with the actual write-to-files being serialised.

2
  • The formatting should be faster than the disk write, IMO. Perhaps there is a more efficient formatting routine? For instance, he could use stdio.h instead of iostream. If he intends to process such large quantities of data on a regular basis, he might gain efficiency by rolling his own sprintf-like function.
    – jforberg
    Jun 29, 2011 at 10:43
  • @jforberg: Yes - I agree that formatting should be faster. I found the 50% CPU usage highly suspicious though. It usually indicates that one core on a dual core system is 100% busy. Jun 29, 2011 at 10:47
0

Formatting is incredibly expensive. Writing 128M double precision numbers to disk with fprintf() vs fwrite() can easily take 10x as long, because of the formatting and because of the large number of calls (compared to one big fwrite()); try the code below and see if you get similar timings. Text files aren't the way to deal with significant amounts of data; if you're not actually going to sit down and read it all yourself, it aughtn't be in ascii.

If you do want to stay with text, and you impose a rigid format (eg, all the numbers take exactly the same amount of bytes in the file), then you can break up the list into big blocks, and have each core format one set of numbers to a big string, and fseek() to the appropriate position in the file and dump it out. You can play with the blocksize to see what the best tradeoff for memory/performance is. If you really are bottlenecked by CPU, this should allow you to overlap I/O with computation and get some win.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
/* Jonathan Dursi, SciNet */

#define FILESIZE 1024*1024*128

int write_file_bin(const char *fname, const double *data, const int ndata) {

    FILE *fp;
    time_t start, end;

    fp=fopen(fname,"wb");
    assert(fp);
    start = time(NULL);
    fwrite(data, sizeof(double), ndata, fp);
    end = time(NULL);
    fclose(fp);

    return (int)(end-start);
}

int write_file_ascii(const char *fname, const double *data, const int ndata) {

    FILE *fp;
    time_t start, end;
    int i;

    fp=fopen(fname,"wb");
    assert(fp);
    start = time(NULL);
    for (i=0;i<ndata;i++) {
        fprintf(fp,"%lf\n",data[i]);
    }
    end = time(NULL);
    fclose(fp);

    return (int)(end-start);
}

int main(int argc, char **argv) {
    double *data;
    int i;
    int asciitime, bintime;

    data = (double *)malloc(FILESIZE * sizeof(double));
    assert(data);
    for (i=0;i<FILESIZE;i++) {
        data[i] = i*(double)i/2.;
    }

    asciitime = write_file_ascii("data.txt",data,FILESIZE); 
    bintime   = write_file_bin("data.dat",data,FILESIZE); 

    printf("Time to write files: ASCII: %d, Binary: %d\n",asciitime, bintime);

    return 0;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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