Conner Conner - 2 months ago 11
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
reportMatch(stringY);
}
}


You can assume that
stringX
and
stringY
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
strcmp
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

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";
        }
    }
}

Demo

Comments