Zmienne lokalne globalne a szybkość algorytmu

Wszędzie gdzie czytałem uczą że zmienne lokalne są lepsze od globalnych. Ale zastanawiam się co będzie lepsze. Wiem czemu tak piszą i wygoda też ma dla mnie znaczenie ale.

   int main()
{
int pomocnicza;
for(int i=0;i<20000000;i++)
{
    ///////jakiś kod//////////////
    //////////////////////////
    pomocnicza= zmienna_z_tego_kodu;
    //operacje na zmiennej pomocniczej
}
}

//czy

    int main()
{
for(int i=0;i<20000000;i++)
{
    ///////jakiś kod//////////////
    //////////////////////////
   int pomocnicza= zmienna_z_tego_kodu;
    //operacje na zmiennej pomocniczej
}
}

Ponoć zmienne lokalne kiedy kod w nawiasie dobiegnie końca są niszczone i zwalnia miejsce. Wydaje się jakby ze zmeinną lokalną było więcej roboty do wykonania bo trzeba zarezerwować i zwolnić ale mogę się mylić. Widać że musi tu działać jakiś mechanizm który odpowiedzialny jest za sprawdzanie czy dana pamięć jest wolna bo może korzysta z niej inna zmienna. A może kompilator sam rozwiązuje takie problemy i widząc coś takiego postanowi, że zrobi ze zmiennej lokalnej globalną. W innych postach pisali że to coś daje.

Zmienne globalne są niemal zawsze alokowane w pamięci, podczas gdy zmienne lokalne na ogół w rejestrach (o ile jest tyle miejsca) - więc taką rule of thumb byłoby "zmienne lokalne są szybsze w runtime od zmiennych globalnych".

Tym niemniej w 99% przypadków nie ma to znaczenia - kod powinien być przede wszystkim czytelny dla ludzi; jeśli natrafisz na jakiś przykład wolno działającego algorytmu (na tyle, że czas działania rzeczywiście będzie problematyczny), wykonaj benchmark i wtedy optymalizuj mając go za punkt odniesienia :-)

1. Najszybsze są te które są trzymane aktualnie w rejestrach procesora.
2. Potem te w cache.
3. CPU w większości popularnych architektur i tak nie potrafi wykonywać operacji arytmetycznych na danych w innej lokalizacji niż w jego rejestrach. Samo załadowanie danych z lokalizacji odległych bardziej niż inne rejestry czy cache owszem jest bardziej kosztowne, ale warto mieć na uwadze jak często jest wykonywane w skali całego algorytmu.
4. Co gdzie trafi potrafi zależeć od kompilatora i stosowanych optymalizacji oraz samego kodu. Jak kod bedzie skakał pomiedzy procedurami i odkładał/pobierał kontekst ze stosu to będzie to wolniejsze niż wykonywaie operacji w ramach tego samego kontekstu. Lokalność tych zmiennych niewiele im pomoże bo i tak będą sobie siedzieć na stosie (w optymistycznym wariancie będzie się on znajdował w cache, w mniej optymistycznym w RAM) czekając na załadowanie.
5. Przy pętlach generalnie na większości popularnych platform szybsze zrobienie loop unroll niż wykonywanie pętli sprawdzając czy osiągnięto warunek stopu.

MOV AL, 10    ; ustaw wartość rejestru AL na 10
L1:           ; etykieta
DEC AL        ; odejmij od AL jeden
JNZ L1        ; jeśli wynikiem poprzedniej operacji arytmetycznej nie jest zero to  skocz do miejsca w kodzie o adresie etykiety L1

będzie wolniejsze niż wykonanie 10 pod rząd odejmowań wstawinych żywcem

MOV AL, 10    ; ustaw wartość rejestru AL na 10
DEC AL        ; odejmij od AL jeden
DEC AL        ; odejmij od AL jeden
DEC AL        ; odejmij od AL jeden
DEC AL        ; odejmij od AL jeden
DEC AL        ; odejmij od AL jeden
DEC AL        ; odejmij od AL jeden
DEC AL        ; odejmij od AL jeden
DEC AL        ; odejmij od AL jeden
DEC AL        ; odejmij od AL jeden
DEC AL        ; odejmij od AL jeden

gdyż pierwsze po ustawieniu AL na 10 oznacza wykonanie 20 operacji [ (wykonanie dekrementacji zmiennej + sprawdzenie czy wynik operacji wynosi zero)*10 ], zaś drugie już tylko dziesięciu. Efekt działania obu wersji jest identyczny, więc jeśli kompiler rozpozna tego typu pętlę i będzie skonfigurowany na maksymalne przyśpieszzenie działania kodu prawopodobnie zrobi loop unroll w tym miejscu. Kosztem jest tutaj to, że wynikowy program będzie dłuższy bo będzie zawierał ciąg powtórzonych pod rząd instrukcji VS dwie.

kamil kowalski napisał(a):

Wszędzie gdzie czytałem uczą że zmienne lokalne są lepsze od globalnych. Ale zastanawiam się co będzie lepsze. Wiem czemu tak piszą i wygoda też ma dla mnie znaczenie ale.

   int main()
{
int pomocnicza;
for(int i=0;i<20000000;i++)
{
    ///////jakiś kod//////////////
    //////////////////////////
    pomocnicza= zmienna_z_tego_kodu;
    //operacje na zmiennej pomocniczej
}
}

//czy

    int main()
{
for(int i=0;i<20000000;i++)
{
    ///////jakiś kod//////////////
    //////////////////////////
   int pomocnicza= zmienna_z_tego_kodu;
    //operacje na zmiennej pomocniczej
}
}

...

eee, ale przecież w obu przypadkach powyżej mamy zmienną lokalną. zmienna lokalna żyje tyle ile otaczający ją blok. zmienna globalna żyje przez całą długość programu (tzn. od zainicjowania do zakończenia całego procesu).

różnica powyżej jest taka, że w pierwszym przypadku zmienna jest lokalna dla całej funkcji, a w drugiej dla samego fora. zaawansowany kompilator powinien zoptymalizować obie postacie do tego samego kodu dzięki optymalizacjom opartym o https://en.wikipedia.org/wiki/Static_single-assignment_form - tzn. nie ma znaczenia kiedy zmienna typu int zostanie (semantycznie rzecz biorąc) zdealokowana. różnica byłaby, gdyby ta zmienna pociągała za sobą dealokację pamięci ze sterty (obojętne czy przez garbage collector, automatyczny destruktor, ręczną dealokację, etc) - wtedy krócej żyjąca zmienna to krócej żyjący obiekt do którego prowadzi ta zmienna, a więc szybsze zwalnianie zasobów.

Ale w jakim języku? :o

1a2b3c4d5e napisał(a):

Ale w jakim języku? :o

Pytanie niby dobre bo w każdym języku może być inaczej. Chociaż tu chyba wszyscy założyli że chodzi o C. Ale IHMO już pierwsze pytanie @kamil kowalski jest niepraktyczne bo jakikolwiek większy program robiący więcej niż jeden algorytm nie powinien używać zmiennych globalnych

Ale żeby nie było że odpowiadam nie na temat to w tym kodzie (przy założeniu że to C) zmienna lokalna jest tworzona na stosie, a więc utworzenie jej to inkrementacja (dekrementacja - zależy od kierunku stosu) wskaźnika stosu. A możliwe nawet że tej inkrementacja nie będzie. Albo i tak zostanie wykonanyna, ale inną wartością jeśli będą wywoływane jeszcze jakieś inne funkcje. W zasadzie to jedyną sensowną odpowiedzą jest skompilować ten kod z włączonymi wszystkimi optymalizacjami i porównać kod assemblera

użyj sobie godbolta zamiast bawić w spekulacje :D

https://godbolt.org/

z -O2

int main()
{
    for(int i=0;i<20000000;i++)
    {
        int pomocnicza= i * 5;
    }
}

=

main:                                   # @main
        xor     eax, eax
        ret

oraz

int main()
{
    int pomocniczna;
    for(int i=0;i<20000000;i++)
    {
        pomocniczna = i * 5;
    }
}

=

main:                                   # @main
        xor     eax, eax
        ret

z -O0

int main()
{
    int pomocniczna;
    for(int i=0;i<20000000;i++)
    {
        pomocniczna = i * 5;
    }
}

=

main:                                   # @main
        push    rbp
        mov     rbp, rsp
        mov     dword ptr [rbp - 4], 0
        mov     dword ptr [rbp - 12], 0
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        cmp     dword ptr [rbp - 12], 20000000
        jge     .LBB0_4
        imul    eax, dword ptr [rbp - 12], 5
        mov     dword ptr [rbp - 8], eax
        mov     eax, dword ptr [rbp - 12]
        add     eax, 1
        mov     dword ptr [rbp - 12], eax
        jmp     .LBB0_1
.LBB0_4:
        mov     eax, dword ptr [rbp - 4]
        pop     rbp
        ret

oraz

int main()
{
    for(int i=0;i<20000000;i++)
    {
        int pomocniczna = i * 5;
    }
}

=

main:                                   # @main
        push    rbp
        mov     rbp, rsp
        mov     dword ptr [rbp - 4], 0
        mov     dword ptr [rbp - 8], 0
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        cmp     dword ptr [rbp - 8], 20000000
        jge     .LBB0_4
        imul    eax, dword ptr [rbp - 8], 5
        mov     dword ptr [rbp - 12], eax
        mov     eax, dword ptr [rbp - 8]
        add     eax, 1
        mov     dword ptr [rbp - 8], eax
        jmp     .LBB0_1
.LBB0_4:
        mov     eax, dword ptr [rbp - 4]
        pop     rbp
        ret

Diff:

Sensowniejszy przykład z -O1

Brak różnicy.

z -O0

Diff:

kamil kowalski napisał(a):

Ponoć zmienne lokalne kiedy kod w nawiasie dobiegnie końca są niszczone i zwalnia miejsce. Wydaje się jakby ze zmeinną lokalną było więcej roboty do wykonania bo trzeba zarezerwować i zwolnić ale mogę się mylić. Widać że musi tu działać jakiś mechanizm który odpowiedzialny jest za sprawdzanie czy dana pamięć jest wolna bo może korzysta z niej inna zmienna. A może kompilator sam rozwiązuje takie problemy i widząc coś takiego postanowi, że zrobi ze zmiennej lokalnej globalną. W innych postach pisali że to coś daje.

Dobra złota zasada: im więcej powiesz kompilatorowi tym więcej będzie w stanie zrobić, bo wie czego chcesz. Jeśli powiesz kompilatorowi, że zmienna x ma być użyta tylko w pętli to może zrobić z nią cokolwiek, bo jedyna umowa jaka jest między tobą a kompilatorem to standard i semantyka języka. Jeśli zrobisz zmienną globalną to kompilator ma małe pole do manewru: przy pomocy extern int pomocnicza; możesz użyć danej zmiennej w innym pliku .c/.cpp. Kompilator nie ma pojęcia co się dzieje w innych plikach, więc musi przyjąć najgorsze: każdy zapis i odczyt musi być wykonany tak jak to napisał programista, nie można użyć rejestru do trzymania poprzednio przeczytanej wartości, bo w między czasie wszystko może się zmienic

Ja celowo nie podałem języka bo liczyłem na ogólną odpowiedź, ale takiej nie ma.
Napisałem że lokalne i globalne. Bo lepiej to brzmi i łatwiej się było połapać niż zmienna lokalna i zmienna lokalna bardziej zagnieżdrzona.

kamil kowalski napisał(a):

Napisałem że lokalne i globalne. Bo lepiej to brzmi i łatwiej się było połapać niż zmienna lokalna i zmienna lokalna bardziej zagnieżdrzona.

nie. jak mylisz pojęcia to wcale nie jest łatwiej się połapać.

Ja celowo nie podałem języka bo liczyłem na ogólną odpowiedź, ale takiej nie ma.

większe znaczenie ma rodzaj zmiennej. w przypadku lokalnej zmiennej typu int nie ma żadnego znaczenia jak mocno jest zagnieżdżona.

kamil kowalski napisał(a):

Ja celowo nie podałem języka bo liczyłem na ogólną odpowiedź, ale takiej nie ma.
Napisałem że lokalne i globalne. Bo lepiej to brzmi i łatwiej się było połapać niż zmienna lokalna i zmienna lokalna bardziej zagnieżdrzona.

Bo takiej nie ma. W zależności od trybu kompilacji albo heurystyk może się dużo zmienić. Domyślnie kompilator języków C/C++ nie wie co się dzieje w innych plikach niż bieżący dlatego musi być ostrożny. Ale da się włączyć tryb LTO/whole-program, które to zmieniają

Tak czy owak: znając podstawy tego jak działają kompilatory mogę z dużym przekonaniem powiedzieć, że im bardziej lokalna zmienna tym lepiej. Kompilator i tak wszystko pomiesza po swojemu, jedyne co go ogranicza to kod

Współcześnie nie ma to znaczenia, z punktu widzenia wydajności. Zmiennych globalnych unikamy z zupełnie innego powodu. Mianowicie, każda zmienna globalna utrudnia zrozumienie działania kodu, bo trudniej dojść gdzie jeszcze może być ona zmieniona. Natomiast jeśli masz zmienną używaną wewnętrznie przez funkcję, chcesz, żeby była lokalna, bo przecież ta sama funkcja może być używana jednocześnie przez kilka wątków. To, że zmienna lokalna musi być alokowana nie ma wielkiego znaczenia, bo alokacja polega na przesunięciu wierzchołka stosu (jedno dodawanie/odejmowanie na rejestrze). Co innego zmienne alokowane na stercie (malloc()), one istotnie mogą być wolniejsze i sprawiać różne inne problemy.
To wszystko, oczywiście zakładając że programujesz w C/C++, w innych językach może być inaczej.

kamil kowalski napisał(a):

Ja celowo nie podałem języka bo liczyłem na ogólną odpowiedź, ale takiej nie ma.
Napisałem że lokalne i globalne. Bo lepiej to brzmi i łatwiej się było połapać niż zmienna lokalna i zmienna lokalna bardziej zagnieżdrzona.

Nie ma czegoś takiego jak szybkość dostępu do zmiennych lokalnych i globalnych w ogólności.
Nie ma to nawet sensu w zawężeniu do C++/c.
Dopiero jak ustalisz:

• Konkretną architekturę
• os,
• wersje kompilatora,
• parametry kompilacji
• i konkretny kod (fragment) na jakim to testujesz (!!!)
• to można ewentualnie odpowiedzieć na to pytanie.

Jest też druga prawda. Nie ma czegoś takiego jak zmienne globalne - to są po prostu, błędy, braki w umiejętności programowania (pomijając języki, gdzie zmienne globalne są nieodzowne ( np. BASIC na C64))

dorzucę swój kamyczek do tego co już przedmówcy świetnie wyłożyli. Warto sobie spojrzeć czasami w pewne dokumentacje tam są czasami madre rzeczy dajmy weźmy na warsztat architekturę atmela AVR str 5. masz krótkie wytłumaczenie + nawet test porównawczy global vs local
https://ww1.microchip.com/downloads/en/Appnotes/doc8453.pdf
myślę że to clue które koledzy przedstawili wyżej ale z kronikarskiego obowiązku przytoczę(PAMIĘTAJ ARCHITEKTURA AVR, JĘZYK C)

If a global variable is declared, a unique address in the SRAM will be assigned to this
variable at program link time. Also accessing to a global variable will typically need
extra bytes (usually two bytes for a 16 bits long address) to get its address.
Local variables are preferably assigned to a register or allocated to stack if supported
when they are declared. As the function becomes active, the function’s local variables
become active as well. Once the function exits, the function’s local variables can be
removed.

Podsumowanie: Kiedyś ci napisałem żebyś zapoznał się z książką do systemów operacyjnych, teraz napiszę że może warto też podejśc do podstaw i budowy procków, assemblera tu temat bo to pewne światło ci rzuci na temat. Bo to jet skomplikowane.
link

@recovery:

Nie wiem czy jest sens iść w procki tak szybko, cytując klasyka So you run this program 100 times. It never runs the same way twice ever.