C++中变量与常量作为模数时的性能差异及超时问题排查

Great question! The performance gap you're seeing comes down to how the C++ compiler optimizes access to the modulus value m, depending on whether it's declared as a constant or a regular variable. Let's break this down:

The Context: Your High-Frequency Loop #

First, let's zoom in on where the critical performance hit happens:

for (int j = 1; j <= x; j++) {
    for (auto coin : c) {
        if (j - coin >= 0) {
            counts[j] += counts[j - coin];
            counts[j] %= m; // This line runs millions of times
        }
    }
}

In your failing test case, x=1000000 and n=100—that means this inner loop runs up to 100 million times. Every tiny overhead in this line gets amplified into a noticeable delay that pushes your code over the 1-second time limit.

Case 1: int m = 1'000'000'000 +7; (non-const) #

When m is a regular int, the compiler can't be 100% sure its value won't change during runtime (even if you never modify it in code). Because of this uncertainty, every time you use m in the modulus operation, the CPU has to:

1. Fetch the value of m from memory
2. Perform the modulus calculation

Memory access is significantly slower than operations using immediate values or CPU registers. Over 100 million iterations, this repeated memory read adds up to enough time to trigger a timeout.

Case 2: const int m = 1'000'000'000 +7; #

Declaring m as const tells the compiler: this value is fixed at compile time and will never change. This unlocks a key optimization called constant folding:

• The compiler replaces every instance of m in your code with the literal value 1000000007
• When the modulus runs, the CPU uses this immediate value directly (no memory fetch needed)

This cuts out the expensive memory access step entirely for each iteration. For 100 million operations, this saves enough time to get your code under the time limit.

Why One Test Case Worked and the Other Didn't #

The second test case that didn't timeout likely had coin values that resulted in fewer j - coin >=0 checks passing. This meant the inner loop ran fewer total times, so the memory access overhead didn't accumulate enough to hit the timeout threshold. But with const, both test cases benefit from the optimized modulus operation and run within the time limit.

内容的提问来源于stack exchange，提问作者Sergei Shumilin