Inserting and fetching values slower on an unordered_map in C++ than on a dictionary in Python

Question

I was solving a CodeForces problem, and kept getting Time Limit Exceeded, so as usual in these cases, I decided to try to migrate my code from Python to C++ in order to go faster. I noticed that my C++ implementation goes slower than my Python code.

The code dynamically updates a dictionary (in Python) or a map<long,long> in C++. The only thing I see to explain that my C++ code is twice as slow as my Python 2 code is that a C++ map<long,long> would be slower to access/insert than a Python dictionary, so I tried to change them into unordered_map, to no avail.

The code runs with this example input instantaneously in Python, but takes more than 10 seconds in the C++ implementation. I see no reason for this code (that contains at most a few thousands simple operations) to last this long:

25
14 17 5 42 2 53 61 61 65 56 42 64 10 8 56 38 50 36 7 46 42 46 13 43 11

So my main question is: Which data structure should I use instead of unordered_map to make this code as efficient as possible?

The only reason that I see for my code to be so inefficient would be that the implementation of find() in an unordered_map is incredibly slower, so I guess I'm not using the right structure to mimic the performance of Python's dictionary.

Of course, if you have any other remark on how I use C++, I will welcome your insights.

The problem if it interests you

C++ code (extremely slow):

#include <unordered_map>
#include <iostream>
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define RI(X) scanf("%d", &(X))
#define Fi first
#define Sn second
typedef long long LL;
using namespace std;


bool isin(long s, unordered_map<long,long> m){
    return (m.find(s)!=m.end());
}


long deuxpownmodprime(long n,long mod){
    n=(n%(mod-1));
    long res;
    res = 1;
    if (n&1){res=2;}
    if (n<=1) {return res;}
    long ps2=deuxpownmodprime(n/2,mod);
    long long resll;
    resll=res;
    resll*=ps2;
    resll*=ps2;
    return (resll%mod);
}

int main(){
    long totf=0;
    int n;
    RI(n);
    int decomps[71]={0, 0, 1, 2, 0, 4, 3, 8, 1, 0, 5, 16, 2, 32, 9, 6, 0, 64, 1, 128, 4, 10, 17, 256, 3, 0, 33, 2, 8, 512, 7, 1024, 1, 18, 65, 12, 0, 2048, 129, 34, 5, 4096, 11, 8192, 16, 4, 257, 16384, 2, 0, 1, 66, 32, 32768, 3, 20, 9, 130, 513, 65536, 6, 131072, 1025, 8, 0, 36, 19, 262144, 64, 258, 13};

    long mod= 1000000000+7;
    unordered_map<long,long> ot;
    long nbm=(1<<19);
   // long tot[nbm]={0};
    ot.insert(pair<long,long> (0,1));
    int dn[71]={0};    
    REP(i,n){
        int a;
        RI(a);
        dn[a]++;
    }
    REP(i,71)
    {
        if (dn[i]>0){
            totf+=dn[i]-1;
            int a=decomps[i];
            unordered_map<long,long> ta;
            for (auto it : ot){
                long m=(it.Fi)^a;
                bool j=isin(m,ta);
                if (!j){
                    ta.insert(pair<long,long> (m,it.Sn));
                }
                else{
                    ta[m]+=it.Sn;
                    //ot[it.Fi]=ot[m];
                }
            }
            for (auto it: ta)
            {
                if (!isin(it.Fi,ot)){
                    ot[it.Fi]=it.Sn;
                }
                else{
                    ot[it.Fi]+=it.Sn;
                }
            }
        }
    }
    long long c=ot[0];
    c*=deuxpownmodprime(totf,mod);
    cout<<(c-1)%mod<<endl;
}

Python code that does the exact same thing but working faster:

n=[int(k) for k in raw_input().split(" ")][0]
a=[int(kk) for kk in raw_input().split(" ")]

mod= 1000000000+7;
global pows2
pows2={}

def p2(n):
    if n<=1:
        return 2**n
    if n in pows2:
        return pows2[n]
    res=2**(n%2)
    p2m=p2(n/2)
    res=((res*p2m*p2m)%mod)
    pows2[n]=res
    return res

decomps=[0, 0, 1, 2, 0, 4, 3, 8, 1, 0, 5, 16, 2, 32, 9, 6, 0, 64, 1, 128, 4, 10, 17, 256, 3, 0, 33, 2, 8, 512, 7, 1024, 1, 18, 65, 12, 0, 2048, 129, 34, 5, 4096, 11, 8192, 16, 4, 257, 16384, 2, 0, 1, 66, 32, 32768, 3, 20, 9, 130, 513, 65536, 6, 131072, 1025, 8, 0, 36, 19, 262144, 64, 258, 13]
p219=524288;
ot={0:1}

dn=[0]*71

for k in range(n):
    dn[a[k]]+=1

totp=0
for i in range(1,71): 
    if dn[i]>0:
        aa=decomps[i]
        totp+=dn[i]-1
        ta={}
        for k in ot.keys():
            m=k^aa
            ta[m]=ot[k]
        for k in ta.keys():
            if k not in ot:
                ot[k]=0
            ot[k]+=ta[k]
print (ot[0]*p2(totp)-1)%mod

Answer 1

Alright, I finally decided to actually review how you use C++ this because I want to practice structuring feedback for code structured like this.

Be advised that I'm reviewing this from a specific lens, which is the one used in professional environments: Code should be written in a way to be read by other people.

1: Macros

You should not be using macros like this... ever. There's a few reasons for this, but the most important is: it makes your code hard to read.

Looking at your main function, I see this:

REP(i,n){
    int a;
    RI(a);
    dn[a]++;
}

I don't know what REP() or RI is, so I have to look it up. That means stopping my reading of the main function, finding REP(), understanding what it does, keep it in mind, and restart reading the main function. That's cognitive load, and the act of reading and understanding code is already cognitively intensive, any extra load is just hinderance.

This is tough because you intimately know what REP() and RI() does, so this looks really obvious to you. It's really important that you put yourself in the shoes of someone coming in to your code fresh.

If you had written:

for(int i = 0 ; i < n; ++i) {
  int a;
  scanf("%d", &a);
  dn[a]++;
}

Then I would have been able to understand it all without having to interrupt my reading, and really, it's not really any harder to write.

The same thing goes for your Fi and Sn macros, you are not judged by how short your code is.

2: Whitespace

Your code is too tightly packed. Blocks of code can often be broken down in logical units using whitespace carefully. Let it breathe a bit. For example, check out my slightly improved version of deuxpownmodprime():

long deuxpownmodprime(long n,long mod){
    n=(n%(mod-1));

    long res;
    res = 1;
    if (n&1) {res=2;}
    if (n<=1) {return res;}

    long ps2=deuxpownmodprime(n/2,mod);

    long long resll;
    resll=res;
    resll*=ps2;
    resll*=ps2;

    return (resll%mod);
}

3: Don't use using namespace std

It pollutes your global namespace, and causes nothing but grief in the long run.

4: Don't use scanf()

It's a completely deprecated pure C interface. Use std::cin instead:

int v;
std::cin >> v;

5: Avoid redundant lookups

find() and operator[] both do essentially the same thing.

This:

bool j=isin(m,ta);
if (!j){
    ta.insert(pair<long,long> (m,it.Sn));
}
else {
    ta[m]+=it.Sn;
    //ot[it.Fi]=ot[m];
}

becomes (with a few miscellaneous other improvements):

auto found = ta.find(m);
if(found == ta.end()) {
  ta.emplace(m, it.second);
}
else {
  found->second += it.second;
}

6: Initialize your variables

This:

long res;
res = 1;

should simply be:

long res = 1;

Conclusion

At the end of the day, most of these things are details, the thing you really should focus improving on is related to the explanation I gave at the start of point #1.

As much as possible, you want to write code in a way that makes reading it possible without having to jump up and down the page. That takes the form of better variable names, better function names, good use of whitespace, clarification with comments where needed, using standard stuff as much as humanly possible, etc...

Taking your deuxpownmodprime() function for example, it took me too long to understand what it says. Is it de_ux_pow_n_mod_prime, or (as I suspect) deux_pow_n_mod_prim (with the French deux)? And it's lucky for you the other words were easily separable. You should use either a camelCase or underscore_separated scheme so that it's clear where each word ends and the next begins.

Answer 2

Here are some things to improve your code. First, we'll address the performance issue, followed by a number of other things that could be improved.

Use const references where practical

The code currently declares its main search function like so:

bool isin(long s, unordered_map<long,long> m)

This has two problems. First it passes by value, so a new std::unordered_map is created on every call. This is extremely wasteful of both time and memory. Second, it should actually be a const reference.

bool isin(long s, const unordered_map<long,long> &m)

Results of that single change on the sample data provided in the question:

$$ \begin{array}{|l|r|} \hline \text{program} & \text{time (ms)} \\ \hline \text{Python 2.7} & 15 \\ \text{original C++} & 2475 \\ \text{C++ with const ref} & 3 \\ \hline \end{array} $$

As you can see, despite the title of this question, in fact the C++ version is about 5 times faster than the Python version, with no other changes applied.

Don't abuse using namespace std

Putting using namespace std within your program is generally a bad habit that you'd do well to avoid.

Avoid C-style macros

I'd advise not using C-style macros like REP, Fi, etc. They only make your program harder to read and understand and obfuscate the underlying meaning. Further, function-like macros are notorious sources of bugs in C. They have very little use in modern C++.

Eliminate unused typedef

The LL typedef is never used in the program and could simply be omitted.

Use whitespace to improve readability

Lines like this:

long ps2=deuxpownmodprime(n/2,mod);

become easier to read with a little bit of whitespace:

long ps2 = deuxpownmodprime(n/2, mod);

Eliminate magic numbers

The constants 71 is used in multiple places. It would be better to have such numbers as named const or constexpr values so that it would be clear what those numbers represent.

Eliminate unused variables

Unused variables are a sign of poor code quality, so eliminating them should be a priority. In this code, nbm is defined but unused. Your compiler is probably also smart enough to tell you that, if you ask it to do so.

Use consistent formatting

The code as posted has inconsistent use of {} which makes it a little harder to read and understand. Pick a style and apply it consistently.

Iterate over const references where possible

In the main() routine, the range for loops should iterate over const references instead of forcing temporary copies. In other words, change the code from this:

for (auto it : ot) {

to this:

for (const auto &it : ot) {

Simplify the code using uniform initialization syntax

The code currently has a number of lines like this:

ta.insert(pair<long, long>(m, it.second));

This can easily be simplified using uniform initialization syntax.

ta.insert({m, it.second});

Also these two lines:

std::unordered_map<long, long> ot;
ot.insert(pair<long, long>(0, 1));

Can be simplified to this:

std::unordered_map<long, long> ot{{0,1}};

Use constexpr where practical

In main, the variables decomps and mod are actually used as constants, so it would make sense to at least declare them as const and preferably constexpr.

Understand the risk of unsanitized user input

The code currently contains equivalent to these lines (after undoing macros and use operator>> instead of horrible scanf):

int dn[71] = { 0 };
for (int i = 0; i < n; ++i) {
    int a;
    std::cin >> a;
    dn[a]++;
}

What happens if one of the input numbers is greater than 71? Undefined behavior and probably a program crash. The problem constrains no doubt tell you that all of the data is guaranteed good, but adding in a bounds check here would make the program more robust and cost very, very little time. One way to do it would be to use std::array:

std::array<int, 71> dn{};  // value-initialized to all zero
for (int i = 0; i < n; ++i) {
    int a;
    std::cin >> a;
    dn.at(a)++;
}

Use C++ idioms

With the modification suggested above, some of the code looks like this:

for (const auto &it : ta) {
    if (!isin(it.first, ot)) {
        ot[it.first] = it.second;
    } else {
        ot[it.first] += it.second;
    }
}

The isin function is not bad, but to experienced C++ programmers, this might be clearer:

for (const auto &it : ta) {
    if (ot.find(it.first) == ot.end()) {
        ot[it.first] = it.second;
    } else {
        ot[it.first] += it.second;
    }
}

However, a real C++ programmer would instead write this:

for (const auto &it : ta) {
    ot[it.first] += it.second;
}

This works because operator[] will create the entry if it does not exist (value initializing the data value to 0) and then adds the desired value. The previous loop can similarly be written like this:

for (const auto &it : ot) {
    ta[(it.first) ^ decomps[i]] += it.second;
}

Add some comments

This looks like a clever algorithm, but it's not obvious how it works or why. Comments describing, for instance, what the values of decomps mean and how they're derived, would add a lot to the program.

Answer 3

Since you're concerned with performance, I'll add a point to @Frank's review regarding the use of C++-standard-library maps:

When map access performance is important, don't use std::map nor std::unordered_map

Note that map access does not seem to be the cause of your problem here; but if it were the case, you would do well not to use the standard ordered map (std::map) and unordered map (`std::unordered_map) as they are known to be quite slow. They are perfectly usable and recommended for most settings though.

Performance-improving alternatives include You should use one of several alternatives to them, such as Google's sparse or dense hash, Intel TBB's maps, khash, uthash and others mentioned at the link.