Decrease in performance when dividing by variable vs. dividing by const in C++

Question

I was solving a programming task and encountered the problem. The task:

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum x using the available coins.

Print one integer: the number of ways modulo 10^9+7.

The code I wrote:

#include <iostream>
#include <vector>

using namespace std;

int m = (1'000'000'000 + 7); // the line of concern

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, x, i = 0, t;
    cin >> n >> x;
    vector<int> c(n);
    while (i < n) { cin >> t;  c[i] = t; i++; }
    vector<int> counts(x + 1);

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

    cout << counts[x];

    return 0;
}

Time limit is 1s. Then I wrote the code that passed all except 2 test cases. One of them:

100 1000000
27 69 68 13 1 63 28 44 45 67 57 11 8 85 42 20 32 77 39 52 70 24 4 79 7 15 54 88 51 73 89 66 48 56 47 18 2 30 21 49 74 9 99 83 55 95 62 90 22 31 71 98 43 75 25 16 12 64 61 38 40 26 3 96 41 86 5 14 91 33 78 50 23 84 94 36 46 97 53 81 65 34 93 59 6 35 72 10 82 60 19 92 29 87 76 100 80 17 58 37

In this test the time limit exceeded.

But in this test it was ok:

100 1000000
649304 85832 159093 841262 930486 225095 306941 914339 469211 156923 460959 236712 440066 842678 379057 615269 321673 694036 378785 792217 78290 15844 644234 752342 102458 30237 191522 388758 697655 113684 20857 639493 641307 527161 977787 505822 196847 735190 169901 417528 342499 102964 907594 780802 577476 162325 790726 579970 148134 144070 624899 392951 594195 813112 534969 856431 25058 630213 641105 636550 762730 873997 275210 717753 243026 915205 52253 613173 751823 647785 928932 305278 858885 496267 717378 426281 245531 139541 942976 912031 550043 194533 504278 552822 805186 950257 673230 484067 790808 762595 590958 799224 711398 599947 858840 212470 820350 710862 546121 159727

Then I started to catch a bug and finally understood that when I change int m --> const int m all tests pass. I use m in modular operation (highlighted in the code).

Why is this?

This reads like it came from a contest/challenge/competitive coding/hacking site. Is it? If your goal is to learn C++, you won't learn anything there. In nearly all cases, like this one, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program runs slow and fails for that reason. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Jan 19 '21 at 15:39
If m is const, or better yet constexpr the compiler can make optimizations it cannot otherwise safely make. — Michael Galassi, Jan 19 '21 at 15:41
A side note: if the number of coins is not too large (less than about 200), you can take the modulo only after the sum over `c`. — Damien, Jan 19 '21 at 15:48
Moreover, you could replace `x=x%m;` with `if (x >= m) x -= m;` — Damien, Jan 19 '21 at 15:53

score 2 · Accepted Answer · answered Jan 19 '21 at 15:47

The fact that the difference is that noticeable is.. surprising. Or lucky, that the difference was just enough to lower your run time enough to pass your arbitrary threshold of one second.

However what shouldn't be a surprise is the fact that a constant is faster to work with than constantly reading your random memory, especially since you're invalidating your CPU caches with very large arrays.

Consider this code for the const version:

    mov     rcx, rax
    mov     edx, DWORD PTR [rcx]
    movsx   rax, edx
    imul    rax, rax, 1152921497
    shr     rax, 32
    sar     eax, 28
    mov     esi, edx
    sar     esi, 31
    sub     eax, esi
    imul    esi, eax, 1000000007
    mov     eax, edx
    sub     eax, esi
    mov     DWORD PTR [rcx], eax

Versus this code for the non-const version:

    mov     rcx, rax
    mov     eax, DWORD PTR [rcx]
    mov     esi, DWORD PTR m[rip]
    cdq
    idiv    esi
    mov     eax, edx
    mov     DWORD PTR [rcx], eax

The const version can do some squirrely math to avoid the expensive division and modulo operation, while the non-const version just runs your code as written with no optimizations.

Decrease in performance when dividing by variable vs. dividing by const in C++

1 Answers1