Why my implementation of Anagram function is redundant and might have cache issues?

Question

Task

I was asked to write a function, which can determine (return a bool) whether 2 given strings are anagrams of each other? That function should have the following constraints:

• Upper and lowercase letters are considered the same
• Non-letters (so numbers, punctuation, whitespace) should be ignored

My implementations:

I know there might be more improvments to my implementations, but I have questions regarding those implementations

• The Version1 iterates over two strings till the end. The processChar increases/decreses the counter of a letter.
• The Version2 avoids unnecessary processing of the rest of the second string if one of the strings ends first and there is at least one NEW char, in second string, that is not already in the hash table. E.g., s1="anag", s2="1234pgana". Once s1 ends (the iterator of s2 is on 'p' now), there is no point processing the rest of s2 since it has new char 'p' which is not in hash table.

Feedback from interviewer:

• He does not understand if there is any benefit from Version2.
• He's not sure if there is any benefit processing both strings in parallel VS iterating over each of them separately (one at a time). He wonders about very large strings and how this might impact caching. "Assume that the 2 strings are so large that they won't fit into the L1 cache (either of them). So by traversing both of them in parallel I am a bit concerned that we might not get the most efficient caching behavior, as in my opinion, it would be preferable to access the memory sequentially. So one string at a time. I do however admit that I cannot say conclusively whether this hypothetical scenario is actually an issue."

My questions

• Is there really no benefit from Version2. I had another Version3 that traverses the strings from start and end simultaneously to make it O(n/2) instead of O(n).

• I've never encountered with such cache problem like he explained. I think we need a profiler to check if it's really a problem. Especially when he admitted that he does not know if that's could be an issue.

Version1

bool isAnagram1(const std::string& s1, const std::string& s2)
{
    std::unordered_map<char, int> charCounter;

    auto processChar = [&](char c, int inc)
    {
        // increase/decrease counter if a letter
        if (isalpha(c))
        {
            c = tolower(c);
            charCounter[c] += inc;
            if (charCounter[c] == 0)
                charCounter.erase(c);
        }
    };

    for (int i = 0; i < s1.length() || i < s2.length(); i++)
    {
        if (i < s1.length())
            processChar(s1[i], 1);
        if (i < s2.length())
            processChar(s2[i], -1);
    }

    return charCounter.empty();
}

Version2

bool isAnagram2(const std::string& s1, const std::string& s2)
{
    if (s1.length() == 0 && s2.length() == 0)
        return true;

    std::unordered_map<char, int> charCounter;
    auto processChar = [&](char c, int inc)
    {
        // increase/decrease counter if a letter
        if (isalpha(c))
        {
            c = tolower(c);
            charCounter[c] += inc;
            if (charCounter[c] == 0)
                charCounter.erase(c);
        }
    };

    auto processIfCharNew = [&](char c, int inc)
    {  
        // if not a letter, then ignore it.
        if (!isalpha(c))
            return true;

        // if a new letter, then it's not anagram
        c = tolower(c);
        if (charCounter.find(c) == charCounter.end())
            return false;

        // if an old letter, then increase/decrease counter of a letter
        charCounter[c] += inc;
        if (charCounter[c] == 0)
            charCounter.erase(c);

        return true;
    };

    auto s1Inc = 1;
    auto s2Inc = -1;
    auto i = 0;
    while (i < s1.length() && i < s2.length())
    {
        processChar(s1[i], s1Inc);
        processChar(s2[i], s2Inc);
        ++i;
    }

    // if both strings ended then it's anagram if char counter is empty
    if (i == s1.length() && i == s2.length())
        return charCounter.empty();

    // if one of the strings finished first, then we need to continue processing the second string ONLY until the end OR until a new char is found. In the later case it means it's not anagram
    auto isFinishedS1 = i == s1.length();
    auto s3Inc = isFinishedS1 ? s2Inc : s1Inc;
    decltype(auto) s3 = isFinishedS1 ? s2 : s1;

    auto res = true;
    while (i < s3.length())
    {
        if (!(res = processIfCharNew(s3[i], s3Inc)))
            break;
        ++i;
    }

    return charCounter.empty() && res;
}

Answer 1

I see some things that may help you improve your program.

Provide a complete program

Part of the interface of a function is the associated list of required #includes which these functions are missing. Also, although it wasn't strictly necessary here, it often helps reviewers to include a sample main() that shows how to call the function(s).

Be careful with signed and unsigned

Several places in the code compares an int i to a std::string length(), but std::string::size_type can be unsigned and int is signed. Instead, declare both variables as std::string::size_type types. Better still, see the next suggestion.

Use "range for" and simplify your code

Instead of indexing through a string, iterators are often faster. Using a "range for" can both simplify and speed up your code.

Try to reserve space where known

If a std::unordered_map runs out of space, it must reallocate and rebuild which slows things down. That is probably not happening here, but I'd be inclined to write charCounter.reserve(26); to make sure we have at least enough for 26 letters. Different locales might have greater number of letters but few locales have fewer and reserving a little extra won't hurt. Either way, it demonstrates to the reviewer that you've considered this factor.

Prefer direct increment and decrement

The assembly languages of most processors include increment and decrement instructions which are often faster than the associated add instructions. For that reason, as well as for clarity, I'd omit the use of the lambda and simply rewrite the functions as inline code.

Consider additional early bailout

The code for isAnagram2 already has an early bailout, but it's unlikely to be useful:

if (s1.length() == 0 && s2.length() == 0)
        return true;

The reason is that the loops below will simply collapse and the function will not save much, if any, time. Within isAnagram2 the comment indicates that you've thought of the instance that the second string might contain a new character, but it uses a rather ungainly way of testing for it, invoking find for every letter.

Minimize processing per letter

Since your routine is going to process every letter, but only check for empty() once at the end, I'd omit the charCounter.erase(c) for each letter. It's better to minimize processing in tight loops, often for both clarity and speed.

If it's simpler, it's probably also faster

Here's the rewrite that incorporates most of the above:

bool isAnagram3(const std::string& s1, const std::string& s2)
{
    std::unordered_map<char, int> charCounter;
    charCounter.reserve(26);
    for (auto c : s1) {
        if (isalpha(c)) {
            ++charCounter[std::tolower(c)];
        }
    }
    for (auto c : s2) {
        if (isalpha(c)) {
            if (--charCounter[std::tolower(c)] < 0)
                return false;
        }
    }
    return std::all_of(charCounter.begin(), charCounter.end(), [](auto &p){
        return p.second == 0; 
    });
}

Test your code

If the goal here was speed, it's good to test for that by timing the various proposed algorithms. On my machine (a Linux box with i7 processor using gcc 12.1.1 with -O2 optimizations) and a sample file that I created with most lines around 950 characters, your two versions both took around the same time, with the second version averaging slightly longer (by < 1%). By contrast, the routine above ran about 4 times as fast (averaged 26% of the time of your isAnagram1()). This is going to be machine, memory, compiler and data dependent, so testing in a wide variety of those factors would likely be helpful for production code.

Your questions

As mentioned above, my testing indicates that your second version is actually slightly slower on the strings I used. YMMV.

As for cache, it's important but not perhaps in the way you mention. The most frequently used data structure is the unordered_map which is probably small enough to fit in the cache. The size of the strings is not likely to make much difference, so I see no advantage to processing both simultaneously.

Further speed might be obtained by parallelizing the algorithm, which is not too difficult, or by using a simple std::array instead of a std::map if your input is solely ASCII text (that is, not a large Unicode alphabet). Indeed, a quick check using std::array<int, 256> for charCounter showed a 2x speed improvement over the routine shown above.

Updated alternative version

As mentioned above, using std::array<int, 256> is one way to improve the speed of the code considerably. This also incorporates AJNeufeld's suggestion in a comment about using an overall counter to further simplify. It also processes the shortest string first, which should help. With the strings I have been using to test, this code is around 10x faster than the original two versions.

bool isAnagram4(const std::string& a, const std::string& b)
{
    auto s1{a.size() < b.size() ? a : b};
    auto s2{a.size() < b.size() ? b : a};
    int count{0};
    std::array<int, 256> charCounter{};
    for (auto c : s1) {
        if (isalpha(c)) {
            ++charCounter[std::tolower(c)];
            ++count;
        }
    }
    for (auto c : s2) {
        if (isalpha(c)) {
            if (--charCounter[std::tolower(c)] < 0)
                return false;
            --count;
        }
    }
    return count == 0;
}

Answer 2

You are focused far too much on the one special case: s1="anag", s2="1234pgana". Consider what happens with a slightly different one: s1="anag", s2="p1234gana".

At the very first character, you find a 'p', but neither string is at the end, you continue. Eventually you get to the end of s1. Now you continue processing all of the characters of s2 right to the bitter end, even though you should already know it is impossible to match the extra 'p' with a character in s1, since there are no more characters in s1.

Another case: s1="b", s2="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa". After processing the first character, charCounter has both 'a' and 'b'. Then s1 ends, and you continue processing characters from s2. They are all 'a' character, which are not new so don't terminate the loop early, even though they will always move the charCounter further away from zero.

Is there really no benefit from Version2?

There is not enough benefit for the added overhead in code, processing time, and complexity.