XOR two files together

Question

I am trying to XOR two files each 1Mb which contains only 0 and 1. It works, but I think it is very slow for the C++ program - approximately 4 sec.

Could someone, please, suggest the fastest XOR method on large files or at least tell what you think about XORing 1MB files running time? May 0.5sec or 1sec? or even less... What should be my goal related to time?

PS Yes, I did not read files by chunks or mapping them.

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iterator>
using namespace std;

inline std::vector<int> read_vector_from_disk(std::string file_path)
{
    std::ifstream instream(file_path, std::ios::in | std::ios::binary);
    std::vector<int> data((std::istreambuf_iterator<char>(instream)), std::istreambuf_iterator<char>());
    return data;
}

int main()
{
    // Open result file.
    fstream new_file;
    new_file.open("output.txt", ios::out | ios::app);
    if (!new_file)
    {
        cout << "File creation failed";
    }

    // Here we will store the result
    std::vector<int> xored_file;

    std::vector<int> in_data = read_vector_from_disk("first_arg.txt");
    std::vector<int> out_data = read_vector_from_disk("second_arg.txt");

    //creating iterator
    vector<int>::iterator first_iter = in_data.begin();
    vector<int>::iterator second_iter = out_data.begin();

    //printing all elements
    cout << "XOR-ed elements are: ";


    for (; first_iter != in_data.end() && second_iter != out_data.end(); first_iter++, second_iter++)
    {
        int xored = *first_iter ^ *second_iter;
        xored_file.push_back(xored);
    }

    // Print result.
    vector<int>::iterator out_iter = xored_file.begin();
    for (; out_iter != xored_file.end(); out_iter++)
    {
        new_file << *out_iter;
    }


    cout << "Complete";

    return 0;
}

Answer 1

Since streams have iterators, you can save a lot of time by processing the files directly. As has been pointed out std::transform works wonders in this regard.

I would also suggest putting the algorithm in a function and keep main uncluttered.

Returning 0 from main is no longer necessary with modern compilers. If yours needs it, upgrade it.

A function using stream iterators could look something like this:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
#include<ios>

typedef std::istreambuf_iterator<char> ItIn;
typedef std::ostreambuf_iterator<char> ItOut;

using std::string;
using std::ifstream;
using std::ofstream;
using std::ios;

void xor2files(string inFile1, string inFile2, string outFile)
{
    ifstream in1(inFile1, ios::in | ios::binary);
    ifstream in2(inFile2, ios::in | ios::binary);
    ofstream out(outFile, ios::out);
    if (!in1 || !in2 || !out)
    {
        std::cerr << "Invalid file name";
    }
    ItIn itIn1(in1);
    ItIn itIn2(in2);
    ItOut itOut(out);
    ItIn end;
    std::transform(itIn1, end, itIn2, itOut,
                   [](char a, char b) -> char {return (char)(((a - '0') ^ (b - '0')) + '0'); });
}
int main()
{

    string first = "first_arg.txt";
    string second = "second_arg.txt";
    string out = "output.txt";
    xor2files(first, second, out);
}

Answer 2

#include <cstring>

seems unused.

using namespace std;

Not a good plan - just use the std:: qualifier, or import just the names you need, in the smallest reasonable scope.

inline std::vector<int> read_vector_from_disk(std::string file_path)
{
    std::ifstream instream(file_path, std::ios::in | std::ios::binary);
    std::vector<int> data((std::istreambuf_iterator<char>(instream)), std::istreambuf_iterator<char>());
    return data;
}

This is a very inefficient way to copy a file into memory - the vector will likely have to reallocate (copying its contents) several times, as the input iterators can't be used to predict the eventual size.

Two faster approaches would be

• memory-map the file contents, probably using Boost::interprocess
• work in a streaming fashion with character-by-character input (e.g. using std::transform())

Also, there's no check whether any of this reading succeeded at all. That's bad.

std::vector<int> xored_file;

Again, we have a vector we'll append to without first reserving capacity. That's reducing your efficiency. I don't see why we need to store a copy of output, instead of immediately writing it to the output stream.

When we've finished writing, we should close the file and confirm that it was successfully written:

new_file.close();
if (!new_file) {
    std::cerr << "Failed to write output file\n";
    return EXIT_FAILURE;
}

Answer 3

Efficiency

There are several parts in your program that all take time:

• Reading two files.
• Allocating memory (input vectors and output vector).
• Performing the XOR loop.
• Writing one file.

Reading and writing are probably the most expensive parts, because they require IO, but that part can not be removed. Another aspect is parsing and formatting, which might be improved a bit, but I wouldn't bother with this at the moment. For the future, an as you mentioned yourself, memory-mapping the raw bytes would probably be the fastest way.

Allocating memory and the algorithm are a different beast. You run through the input files to build up the two vectors. Then, you run through the vectors and perform an algorithm on the pairwise elements. Finally, you discard the two vectors again. The relevant point to observe is that you only need each element once and exactly in the order that they occur in the input file. So, you can simplify this part by just reading two elements and then writing the result of the XOR. That way, you only need two local variables and no memory allocation for the vectors. This is the first optimization I'd try.

Concerning your question what performance to expect, my gut feeling is similar to yours, that 4s is too long. However, this depends a lot on the computer you use. What you could do to find out is to write a benchmark. Simply write 1M zeros and ones to a file and measure how long that takes. Similarly, just read the files, immediately discarding each value. Compare that to reading and storing the data in a vector as well. With these numbers, you should get a better feeling what to expect and also which part takes how much time.

Further Notes

• It's not really clear what your code expects as input format and output format. You are using istream_iterator<char>, which takes single characters. However, it still skips whitespace. I guess you don't expect any whitespace within the files, but that isn't obvious.
• Another aspect of this is that you blow up a char to a int. This quadruples the memory requirement without any benefit. Further, and that's really bad, you take a letter (like "1" or "0"), then treat it as integer (with ASCII encoding, that's 49 and 48) and finally write integers to the output. This is confusing and I'm not even sure it is what you intended. It also makes me wonder if you have tests. If you don't get it right, it's useless if it runs fast!
• When opening the output file fails, you output a message and blindly continue doing something that can never succeed. You should have thrown an exception there.
• The same applies to opening the input files. If that fails, throw an exception.
• The case that the two files have different numbers of elements is not really handled. Again, throw an exception.
• Don't create objects/variables that you only need much later. In this case, this applies e.g. to the output vector. It applies to the output file as well, although this could be defended, because it avoids costly operations that can't succeed anyway (see comment above). It also applies to the iterators used in the loops.
• You are sometimes documenting what your code does, like "Open result file", "creating iterator" and "printing all elements". This isn't helpful, since anyone can see what that does. In the third case, it is even a lie, because nothing is printed! This is typical beginners' behaviour and will vanish automatically once you're more familiar with the language, so don't worry about it too much. As a general rule, the "what?" comments are useless. The "how?" comments are sometimes important, though you should strive to make it clear from the code. The most important ones are the "why?" comments, because those document decisions you made.
• Look up "range based for loops" (for (auto e : some_vector) {...}), which would reduce your code a bit.