1
\$\begingroup\$

This XOR function is costing my program too much time (specifically the conversions.)

How can this code be made faster?


string xor_str(string astr, string bstr){
    unsigned long a = strtoul(astr.c_str(), NULL, 16);  // Convert strings to longs
    unsigned long b = strtoul(bstr.c_str(), NULL, 16);

    stringstream sstream;
    sstream << setfill('0') << setw(16) << hex << (a ^ b);  // XOR numbers and
    string result = sstream.str();  // Save result          // convert to string
    sstream.clear();  // Clear buffer (will this happen anyway?)
    return result;
}

For example, xor_str("74657374696e6731", "1111111111111111") returns "65746265787f7620".

\$\endgroup\$
1

2 Answers 2

2
\$\begingroup\$

How about doing the xor on patched ASCII values instead, I'm sort of in doubt about performance of general purpose strtoul.

I didn't profile it, so I may be underestimating the optimizations of modern compilers. Anybody will profile it, just for curiosity? :)

edit: The OP code will work even for input strings with different lengths (i.e. ("1234", "4") will produce 0000000000001230. My code will work only with already leading-zero extended numbers of same length, although the length can be arbitrary, not just 16.

std::string xor_str(const std::string& astr, const std::string& bstr)
{
    const size_t bsize = bstr.size();
    assert(astr.size() == bsize);
    // this xor_str will work over arbitrary long strings, they just have to have same size
    string result(bsize, 0);
    for (size_t i = 0; i < bsize; ++i) {
        // astr[i] and bstr[i] is something from '0'..'9', 'a'..'f' or 'A'..'F'
        char ra = astr[i], rb = bstr[i];
        // make lower nibble of chars 0..F, from ASCII 'a'+9 = 0x6A, 'A'+9 = 0x4A
        if ('9' < ra) ra += 9;
        if ('9' < rb) rb += 9;
        ra = (ra^rb)&0x0F;  // xor lower nibbles of chars
        // transfer 'ra' back to ASCII and store it to result
        if (ra <= 9) result[i] = ra + '0';
        else         result[i] = ra + 'a' - 10; // or 'A' for uppercase output
    }
    return result;
}
\$\endgroup\$
4
  • \$\begingroup\$ I profiled both this and Quuxplusone's code, and this is almost twice as fast. \$\endgroup\$
    – 54 69 6D
    Jul 4, 2016 at 20:36
  • 1
    \$\begingroup\$ @54696D: in case you want to use as input non-leading-zero extended strings of different length, it's sort of easy to extend this code to handle it with fake '0' prologue. Also maybe using char buffer[] instead of string result, and let the return create instance of string from buffer may save you one clearing of memory (as there's no way to allocate result string with uninitialized memory, so the result(bsize, 0) is maybe wasting some small amount of time - but I have no idea how long the instance of string from buffer takes). How about not using string at all? (vector or array?) \$\endgroup\$
    – Ped7g
    Jul 6, 2016 at 11:22
  • \$\begingroup\$ @54696D: oh, now I have seen the profiling results, and indeed, the string itself is taking some measurable time. If you really want to have full performance for this, consider managing the memory on your own (vector/char[] with reserved sizes), string is a bit high level. And I have suspicion my routine can be written with SSE/AVX instructions in mind working on packed bytes, which would probably make it about 8-16 times faster. But I would have to study some materials for couple of hours before producing the source for that (not even sure how to do that in C++, some compiler intrinsics?). \$\endgroup\$
    – Ped7g
    Jul 6, 2016 at 11:33
  • \$\begingroup\$ I'm not planning on using intrinsic instructions, but I did swap all the strings with char arrays, and it's 25% faster. \$\endgroup\$
    – 54 69 6D
    Jul 7, 2016 at 17:08
6
\$\begingroup\$

Well, obviously you should get rid of all that stringstream stuff in favor of the straightforward

char buffer[100];
sprintf(buffer, "%016x", a ^ b);
return buffer;

That'll cut out all those virtual function calls and stateful stream operations in favor of just doing what you want: print a single integer in hex.


Also, you may not have noticed, but you're taking the parameters astr and bstr by value instead of by const reference, so depending on how you're calling this function, you might be spending most of your time making copies of std::string objects, not hexifying them per se. My guess is that this is actually a bigger time sink than the stringstream stuff, even though that's what caught my eye first.


Therefore I'd try benchmarking

std::string xor_str(const std::string& astr, const std::string& bstr)
{
    unsigned long a = strtoul(astr.c_str(), NULL, 16);
    unsigned long b = strtoul(bstr.c_str(), NULL, 16);
    char buffer[100];  // "big enough"
    snprintf(buffer, sizeof buffer, "%016lx", a ^ b);
    return buffer;
}

(Notice that you could use sprintf instead, since in this particular case you know there can't be any overflow — and you are concerned about raw speed. But my assumption is that you aren't very good at profiling to find hotspots, and are looking for style tips in general, so the general advice "Always use snprintf over sprintf" wins out over the very case-specific and chainsawish "Omit bounds checks when you're sure they're unnecessary.")

\$\endgroup\$
2
  • \$\begingroup\$ Since xor won't go out of bounds, couldn't the buffer just be 16 chars long? char buffer[16]; \$\endgroup\$
    – 54 69 6D
    Jul 3, 2016 at 22:35
  • 2
    \$\begingroup\$ Well, 17, because of the trailing null terminator... but yes, my 100 was just me being too lazy to figure out the exact maximum required size (which in this particular case is super easy to figure out, because we say "016lx" right in the code, but I was too lazy to even notice that). char buffer[17]; would be fine. \$\endgroup\$ Jul 4, 2016 at 4:36

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.