Czy operacje na int są szybsze od operacji na long long?

Robiłem pewne zadanie, w którym często korzystam z operacji bitowych i modulo, dla wygody zrobiłem 3 tablice long long

long long sum[MAXDP], cash[MAXN], ways[MAXDP]; 

jednak tak naprawdę takiego zakresu potrzebowała tylko tablica sum. Zamieniłem kod na taki

int cash[MAXN], ways[MAXDP]; 
long long sum[MAXDP];

Mój program zdecydowanie przyśpieszył np w jedym teście z 0.39s do 0.24s. Czy operacje na long long są wolniejsze od tych na int?

Cały program:

#include <bits/stdc++.h>
    
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define ll long long
#define ull unsigned long long
    
const int MOD = 1e9 + 7, MAXN = 20, MAXDP = 1 << MAXN;
int cash[MAXN], ways[MAXDP]; 
ll sum[MAXDP];
bool seen[MAXDP];

void solve(){
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> cash[i];

    queue<int> que;
    que.push(0);
    ways[0] = 1;
    seen[0] = true;
    while (!que.empty()){
        for (int i = 0; i < n; i++){
            if ((que.front() & (1 << i)) == 0 && sum[que.front()] + cash[i] >= 0){
                ways[que.front() | (1 << i)] = (ways[que.front()] + ways[que.front() | (1 << i)]) % MOD;
                if (seen[que.front() | (1 << i)] == false){
                    seen[que.front() | (1 << i)] = true;
                    que.push(que.front() | (1 << i));
                    sum[que.front() | (1 << i)] = sum[que.front()] + cash[i];
                }
            }
        }
        que.pop();
    }

    cout << ways[(1 << n) - 1] % MOD << "\n";
}

    
void testcases(){
    int t;
    cin >> t;
    while(t){
        solve();
        t--;
    }
}
    
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    //testcases();
    solve();
    return 0;
}

Gdyby ktoś chciał to tutaj link do zadania, niestety nie wiem czy jest możliwe obejrzenie go bez zalogowania się :/
https://szkopul.edu.pl/c/oki-dla-zaawansowanych/p/got/

To raczej zlożone pytanie, bo dużo moze zależeć od samego procesora. Mimo wszystko są 2 powody czemu coś może być szybsze:

1. Używając mniejszego rozmiaru zmiennych pozwalasz kompilatorowi używać połówek rejestrów co może wpłynąć na inny kod wynikowy
2. Mniejsze rozmiary zmiennych to potencjalnie lepsze wykorzystanie CPU cache, bo więcej się tam zmieści (przy czym niekoniecznie, może się trafić jakiś false sharing!)

Masz tam u siebie dwa razy po milion elementów, czyli 4 albo 8 MB per tablica. W jednym przypadku może się okazać ze wszystko się zmieści w cache, w drugim przypadku nie.

Zależy jak długi jest long long, jak długi jest int itd. Kwestia architektury, kompilatora itd.
Z jakiegoś powodu istnieją typy (u)int32_fast_t, czyli "zmieści się w nim (u)int32 ale będzie zoptymalizowany pod wydajność" (czyli może mieć np. 64 bity długości).
@Shalom dobrze to opisał, do tego dochodzi tego jeszcze masa innych czynników, np. różny czas (o ile dobrze pamiętam) word/halfword access na ARM.

Shalom napisał(a):

1. Używając mniejszego rozmiaru zmiennych pozwalasz kompilatorowi używać połówek rejestrów co może wpłynąć na inny kod wynikowy

W przypadku prostych instrukcji o małych opóźnieniach (jak np dodawanie, odejmowanie, operacje logiczne, często też mnożenie, ale już nie dzielenie) używanie połówek (ćwiartek, etc) rejestrów ogólnego przeznaczenia raczej spowalnia niż przyspiesza, bo nowoczesne procesory śledzą zależności między rejestrami i mapują między rejestrami z ISA (np. x86), a tymi wbudowanymi w procesor (np. nowoczesne procesory x86 mają setki rejestrów ogólnego przeznaczenia). Szczegóły: https://en.wikipedia.org/wiki/Register_renaming Z x86-64 sprawa jest jednak taka, że zapis do 32-bitowych rejestrów zeruje górną połówkę odpowiadających im rejestrów 64-bitowych, a więc zarówno przy operacjach 32-bitowych jak i 64-bitowych śledzenie zależności działa tak samo.

Widzę, że w kodzie jest dzielenie modulo. Szybkość dzielenia mocno zależy od rozmiaru rejestru. Z drugiej strony dzielenie przez stałą jest zamieniane przez kompilator na mnożenie + trochę sztuczek opartych na tanich instrukcjach i, koniec końców, dzielenie modulo przez stałą jest szybkie.

2. Mniejsze rozmiary zmiennych to potencjalnie lepsze wykorzystanie CPU cache, bo więcej się tam zmieści (przy czym niekoniecznie, może się trafić jakiś false sharing!)

Masz tam u siebie dwa razy po milion elementów, czyli 4 albo 8 MB per tablica. W jednym przypadku może się okazać ze wszystko się zmieści w cache, w drugim przypadku nie.

To już ma raczej większą szansę na zmianę wydajności (w tym przypadku). Weźcie też pod uwagę, że cache ma kilka poziomów, a więc dylemat nie jest tylko czy dane zmieszczą się w cache ogólnie, ale jakie jest cache miss rate dla każdego poziomu pamięci podręcznej. Do zmierzenia tego można użyć np cachegrind https://valgrind.org/docs/manual/cg-manual.html . Kolejne poziomy cache mają coraz dłuższe czasy dostępu i mniejszą przepustowość.

Prosta tabelka ze strony http://instlatx64.atw.hu/

Lx latency (clk) to opóźnienia (w cyklach procesora) w dostępie do konkretnego poziomu pamięci podręcznej.

Jest jeszcze taka rzecz, że mniejszych zmiennych więcej mieści się do rejestrów AVX/SSE. Jeśli kompilator zwektoryzuje kod, to możliwe że dzięki zmniejszeniu rozmiaru zmiennej przetworzy 2x więcej elementów tablicy w jednej instrukcji.

Dochodzą jeszcze różne szczegóły przez które możesz się zdziwić, np. rozmiar rejestru (może long long nie mieści się w rejestrze, więc kompilator musi załatać braki w sprzęcie) co wchodzi w skład zestawu instrukcji procesora i czy np. faktycznie ISA ma instrukcje wspierające operacje na połówkach, ćwiartkach itd. rejestru, ładowanie do pamięci wielokrotności / połówek słowa, lub pojedynczych bajtów, jaka jest długość słowa itd. itd.

x86 i x86-64 to ulepek ciągnący się jeszcze od czasów 8086, więc ma bagaż 40+ lat dorzucania nowych instrukcji do worka. W innych architekturach mógłbyś znaleźć różne bomby np. procesor nie umie załadować sobie 4B, więc ładuje 8B i potem zeruje / obcina zbędne śmieci. Albo odwrotnie - ładuje 8B na raty, bo umie jedynie 4B naraz.

Shalom napisał(a):

2. Mniejsze rozmiary zmiennych to potencjalnie lepsze wykorzystanie CPU cache, bo więcej się tam zmieści (przy czym niekoniecznie, może się trafić jakiś false sharing!)

Z tablicami raczej tak powinno być, ale zwykłe zmienne i pola struktury mogą być hojniej obdarzane miejscem w pamięci, żeby miały ładnie wyrównane adresy - i tyle z lepszego wykorzystania cache ;)

Z tablicami raczej tak powinno być, ale zwykłe zmienne i pola struktury mogą być hojniej obdarzane miejscem w pamięci, żeby miały ładnie wyrównane adresy - i tyle z lepszego wykorzystania cache

@superdurszlak: Paradoksalnie to może właśnie czasem pomóc :) Wynika to z faktu ze linia cache ma spory rozmiar 16-128 bajtów (nie bitów!), więc w jednej linii może zmieścić się kilka elementów takiej tablicy. I teraz jeśli jeden z tych elementów się zmieni to cała linia jest dirty. Pesymistyczna sytuacja jest taka, że w każdej linii masz tylko jeden mały element który się zmienia, cała reszta jest stała, a mimo to non stop cache musi się flushować. W takiej sytuacji jakieś wyrównania mogą sprawić ze mniej znaczy więcej :)