2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Please provide the command / flags / settings you use to compile this program. Also to give you a (rough) reference: The expected speed of a proper implementation of this should be ~1ms for the actual operation and maybe 10ms or so for the IO. \$\endgroup\$ – SEJPM Feb 25 at 20:15
  • \$\begingroup\$ Can you be more specific about the input and output format? From the code, it's hard to tell what you mean. Obviously, all files contain only 0 and 1 at the bit level, so are you saying that every character in the file is one of two values? If so, which two - 0 and 1, or '0' and '1'? \$\endgroup\$ – Toby Speight Feb 26 at 8:55
3
\$\begingroup\$

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);
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That's pretty much what I had in mind when I mentioned std::transform - thanks for expanding on that. Probably worth mentioning that some error checking is required after the transform as well as before. \$\endgroup\$ – Toby Speight Feb 26 at 8:39
  • 1
    \$\begingroup\$ That lambda is almost unreadable (add linebreaks!) and contains a C-style cast. The error handling is ambiguous (you only guess that the file name is somehow invalid) and lacks a return. Lastly, note that the output is writing char-values formatted as integers in the original code. That's a problem with that code being a bit unclear, but your code does something different. \$\endgroup\$ – uli Feb 26 at 8:40
  • \$\begingroup\$ My imagination had a simple std::bit_xor{} rather than that lambda, but perhaps I misinterpreted the problem statement? \$\endgroup\$ – Toby Speight Feb 26 at 8:46
  • \$\begingroup\$ Also, to get the same behaviour as the original (stop output at the end of the shortest file), we may need to std::swap(itIn1, itIn2) so that the shorter input comes first. \$\endgroup\$ – Toby Speight Feb 26 at 8:51
  • \$\begingroup\$ Thanks, this is working fine I just changed return (char) to return (int) due to in the first case in output file I've got the same which in my previous codes)) - "NUL NUL NUL" - (ASCII of 0???) \$\endgroup\$ – SGh Feb 26 at 10:08
6
\$\begingroup\$
#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;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the detailed answer! Just some things worth mentioning by me: - I have used vactor<int> due to be sure that 0's and 1's which I read from files are integer and I will be able to XOR them just 0 and 1 and not a chars \$\endgroup\$ – SGh Feb 26 at 5:55
  • \$\begingroup\$ Oh, that's a good point - unsigned char would probably be a better choice for bitwise operations. \$\endgroup\$ – Toby Speight Feb 26 at 8:36
3
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I can say, that I am sanitizing, checking and validating both files before sending them as an argument but, of course, I totally agree that validation is a better choice anyway. \$\endgroup\$ – SGh Feb 26 at 9:44

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.