CODEWITHSUNDEEP
c++performancesearchc-strings
Conner
Conner

Reputation: 361

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?

Upvotes: 2

Views: 458

Answers (3)

Luis Colorado
Luis Colorado

Reputation: 12708

If you try to compare all the strings to each other you'll get in a O(N*(N-1)) problem. The best thing, as you have stated the lists can grow large, is to sort them (qsort algorithm has O(N*log(N))) and then compare each element with the next one in the list, which adds a new O(N) giving up to O(N*log(N)) total complexity. As you have the list already ordered, you can just traverse it (making the thing O(N)), comparing each element with the next. An example, valid in C and C++ follows:

for(i = 0; i < N-1; i++)  /* one comparison less than the number of elements */
    if (strcmp(array[i], array[i+1]) == 0) 
        break;
if (i < N-1) {  /* this is a premature exit from the loop, so we found a match */
    /* found a match, array[i] equals array[i+1] */
} else { /* we exhausted al comparisons and got out normally from the loop */
    /* no match found */
}

Upvotes: 0

Jarod42
Jarod42

Reputation: 218098

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

Upvotes: 3

Ashouri
Ashouri

Reputation: 906

I think using hash tables can improve the speed of comparison drastically. Also, if your program is multithreaded, you can find some useful hash tables in intel thread building blocks library. For example, tbb::concurrent_unordered_map has the same api as std::unordered_map

I hope it helps you.

Upvotes: 0

Related Questions