Conner Conner - 1 year ago 59
C++ Question

C++ if statement order

A portion of a program needs to check if two c-strings are identical while searching though an ordered list (e.g.

{"AAA", "AAB", "ABA", "CLL", "CLZ"}
). It is feasible that the list could get quite large, so small improvements in speed are worth degradation of readability. Assume that you are restricted to C++ (please don't suggest switching to assembly). How can this be improved?

typedef char StringC[5];
void compare (const StringC stringX, const StringC stringY)
// use a variable so compareResult won't have to be computed twice
int compareResult = strcmp(stringX, stringY);
if (compareResult < 0) // roughly 50% chance of being true, so check this first
// no match. repeat with a 'lower' value string
compare(stringX, getLowerString() );
else if (compareResult > 0) // roughly 49% chance of being true, so check this next
// no match. repeat with a 'higher' value string
compare(stringX, getHigherString() );
else // roughly 1% chance of being true, so check this last
// match

You can assume that
are always the same length and you won't get any invalid data input.

From what I understand, a compiler will make the code so that the CPU will check the first if-statement and jump if it's false, so it would be best if that first statement is the most likely to be true, as jumps interfere with the pipeline. I have also heard that when doing a compare, a[n Intel] CPU will do a subtraction and look at the status of flags without saving the subtraction's result. Would there be a way to do the
once, without saving the result into a variable, but still being able to check that result during the both of the first two if-statements?

Answer Source

std::binary_search may help:

bool cstring_less(const char (&lhs)[4], const char (&rhs)[4])
    return std::lexicographical_compare(std::begin(lhs), std::end(lhs),
                                        std::begin(rhs), std::end(rhs));

int main(int, char**)
    const char cstrings[][4] = {"AAA", "AAB", "ABA", "CLL", "CLZ"};
    const char lookFor[][4] = {"BBB", "ABA", "CLS"};

    for (const auto& s : lookFor)
        if (std::binary_search(std::begin(cstrings), std::end(cstrings),
                               s, cstring_less))
            std::cout << s << " Found.\n";