Heap vs Stack [C]

Jaz sem začel programirati v Pythonu in Javi in v bistvu sedaj ne razumem dinamične alokacije pomnilnika v C-ju. Prebral sem mnogo tutorialov na spletu in pogledal nekaj youtube razlag, vendar še vedno ne razumem. Ali lahko kdo to razloži na enostaven in pregleden način (kot idiotu, nepoznavalcu programskih jezikov ipd.)?

Vem, da ko naredimo tole:

int tabela[100];

Se rezervira pomnilnik na Stacku.

Ko naredimo tole je isto, samo se rezervira na Heapu:

ptr = (int*) malloc(100 * sizeof(int));

Prebral sem, da je sklad precej majhen v primerjavi s kopico. Vendar ne razumem, za koliko celih števil, decimalnih števil ali nizov uporabimo eno ali drugo?

Skratka, če tabelo deklariram s 1000 ali več elementi bo sklada zmanjkalo in verjetno bo prišlo do stack overflowa. V bistvu, bi se moral sklad uporabljati samo znotraj funkcij, vendar sem na spletu našel kodo, ki naredi natanko to, da rezervira (deklaracija) "int tabela[100];" zunaj int main() funkcije. V bistvu znotraj ničesar.

Ne razumem.

Razlika se najboljše vidi, ko pogledaš program z debuggerjem, recimo z GDBjem...

Načeloma imaš 3 možnosti pri spremenljivah, te lahko živijo na stacku, heapu in pa statične spremenljivke, ki živijo kar v posebnem segmentu binaryja in zato mora biti njihova velikost znana ob compailanju, odpri scompailan program recimo z Ghidra orodjem pa boš videl različne segmente (.data itd..).

Heap je omejen z RAMom tvojega PCa, ko bo heapa začelo zmanjkovati, ti bo operacijski sistem dodal nov del RAMA, da bo heapa vedno dovolj. Načeloma na heap postaviš velike spremenljivke oziroma take, katerih velikost določa nekdo drug (recimo uporabnik). Prostor na heapu rezerviraš z mallocom ali kakšno podobno komando. Potem pa pointer na ta prostor potiskaš naokoli. Samo na koncu ne pozabu sprostiti pomnilnika z free funkcijo in nastaviti pointerja na NULL, tako se izogneš neprijetnim situacijam kot sta recimo memory leak in use after free vulnarability.

Stack je fina zadeva za lokalne variable funkcije, preko njega se pošiljajo tudi argumenti pri klicih funkcij (to se lepo vidi v GDBju). Pazi edino to, da ko returnaš iz funkcije ven, se variable na stacku izgubijo, tudi če vrneš pointer nanj ven. V nadaljevanju se bo to polje v stacku prepisalo. Torej v tem primeru uporabi heap.

Če pa že ob pisanju programa veš kako velika bo spremenljivka, jo pa lahko pospraviš med statične spremenljivke. Taka spremenljivka se bo ohranila med klici funkcij, nerabiš jo mallocat, freejat, ker je že tam. Edino pazi na to, da njene velikosti ne moraš spremeniti drugače kot da popraviš v kodi in nanovo scompailaš.

najprej je vse v heapu, ko pa se program izvaja in pride do ene funkcije naloži spremenljivke od te funckije v stack. če imaš pointer se naloži samo referenca, podatki na katerega kaže pointer pa še vedno ostanejo v heapu.

stack overflow se ponavadi dobi, ko delaš neskončno rekuzrijo in se spremenljivke kopičijo v stack in ne sprostijo, dokler ne požrejo celega mb stacka.

zadaj je vse RAM, samo razlika je kako so podatki strukturirani: v stacku je vse lepo zloženo za hiter acces, heap pa je fragmentiran.

ko se funkcija konča se iz stacka avtomatično pobrišejo vse njene spremenljivke in naredijo prostor za nove, zato ne rabiš delat npr free (nek integer).

vsak program ima funkcijo main, ta kliče funkcijo x, ta kliče funkcijo y itd. tako se gnezdijo funkcije in kopičijo na stack svoje spremenljivke v LIFO metodi (last in, first out).

ko debuggiraš program imaš call stack in lahko vidiš to vgnezdenost funkcij. vse spremenljivke teh funkcij so shranjene v stacku in njihove vrednosti lahko vidimo z debuggerjem, pointerji pa imajo dodatno še podatke v heapu.

zdej nisem ziher a vsi OSi uporabljajo stack arhitekturo? tu bi bilo treba še naštudirat kako točno deluje CPU, to je povezano. baje če ni rekurzije se da preživet tudi brez stacka, to mi še ni čist jasno.

marjan_h je 28. jul 2022 ob 21:26 izjavil:

Jaz sem začel programirati v Pythonu in Javi in v bistvu sedaj ne razumem dinamične alokacije pomnilnika v C-ju. Prebral sem mnogo tutorialov na spletu in pogledal nekaj youtube razlag, vendar še vedno ne razumem. Ali lahko kdo to razloži na enostaven in pregleden način (kot idiotu, nepoznavalcu programskih jezikov ipd.)?

Ne razumem.

Postavil si zelo tezko vprasanje. Da ne razumes, je popolnoma razumljivo za zacetnika.

Vredno je zelo pocasi prebrati:
Stack-based memory allocation @ Wikipedia

kuall je 29. jul 2022 ob 10:49 izjavil:

kow, on hoče domačo razlago ne fakin wikipedia članka, to si lahko sam najde.
za to bi celo znal biti slo tech koristen, za domačo slovensko razlago. žal je le redkokdo sposoben razložiti, najbrž iz strahu, da bi napisal kake neumnosti in se osramotil. :D

No, gospod STROKOVNJAK! A bi Vi razložili razliko med dinamično in statično alokacijo, ali je tema preneumna za vas?

OP, na Linuxu je stack size ~ 8MB (ulimit -s), za Visual Sudio interneti pravijo 1MB.

Pri linuxu je tudi tako, da ima vsak thread, ki ga na novo kreiras 8 MB stack size, ki se potem dalje uporablja pri funkcijskih klicih.

Naceloma se stack uporablja za res manjse alokacije (recimo 8kb), seveda pa ce ves koliko stacka pokuri tvoj program, pa tut lahko kamot tistih 8 MB uporabis, ni pa priporocljivo, ker potem lahko hitro prides do stack overflow, kakor si omenil.

to imaš prav, sem se hotel že sam popraviti.

do stackoverflow pride v praksi samo, če ima program buge in skor vedno je to infinite rekuzrzija. tak da stackoverflow bugi so izi! če vidiš stackoverflow napako si lahko ziher, da jo boš hitro rešil za razliko od kakih mnogo bolj zajebanih bugov.

Zato python nima težav z globokimi rekurzijami, saj vse funkcijske okvirje (spremenljivke z življenjsko dobo enega klica funkcije) zmeče na heap.

Aja, spraševal si glede statične/dinamične alokacije. Funkcijski okvir kamot izračuna prevajalnik. npr. Imaš 2 inta kot parametra, v funkciji pa še 3 inte in 2 shorta, in to nanese 40+4 bytov. To je ta statična alokacija. Če pa upprabnik vnese neko število x, ti moraš pa alocirati polje z x elementi, pa tega prevajalnik ne more statično alocirati. Ti kločeš malloc za teh x elementov na heapu, na stack bo pa verjetno prevajalnik dal samo kazalec na prvi element, to je 8 bajtov.

Stacka lahko zmanjka tudi brez neskoncne rekurzije, ga mi je ze veckrat. Vsaki funkciji compiler izracuna velikost stack framea, ko jo klices se premakne stack pointer za to vrednost in notri skopira parametre od funkcije (je pa tam tudi prostor za vse lokalne spremenljivke. Pri trenutno izvajajoci niti je stack pointer v enem registru in je zelo hitro samo povecat to vrednost. Ko se nit zamenja se iz tega registra vrednost shrani. V tipicne OSu ima vsaka nit dva stacka, enega v kernelu in enega v user spaceu.

Vesoljc in WhiteAngel sta verjetno najbolj preprosto povedala, npr. Vesoljc je napisal tole:

ko recimo vnaprej ne ves koliko res potrebujes, recimo ob pisanju programa ne ves ali bos rabil tabelo veliko 100 ali pa 100000 elementov.

To sem dejansko testiral:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int number;
    printf("Enter an integer: ");  
    scanf("%d", &number);
    
    int array[number];
    
    array[0] = 42;
    array[1] = 2;
    array[2] = 3;
    
    printf("\n %d", array[0]);
        
    return 0;
}

In to deluje. Kljub temu, da ne vemo za koliko elementov potrebujemo tabelo, se stvar prevede in lahko vnesem poljuben integer. Ter tako rezerviramo na stacku 100, 1000 ali koliko pač prenese (1MB windows, Linux 8MB), celih števil. Kot ste nekateri napisali.

Nekateri ste pisali tudi, da naj si pogledam Assembler. Nekaj osnov imam iz zbirnega jezika. Vendar tam sem samo postavljal registre na neko vrednost, ali pa delal logične operacije z biti. Vem, kaj je register, vem kaj je sklad, vem kaj je kopica (to ni podatkovna struktura) v mojem primeru, gre samo za košček RAMa.

Vidim, da je tudi veliko zanimanja za ta topic, glede na število klikov na temo , kar pomeni, da tudi tisti ki programirajo v C/C++ jih zanima kaj točno počne PC, ko kliče malloc.


Bo kdo komentiral mojo kodo, ali sem jaz narobe razumel Vesoljca glede tistega citata? Uporabljam gcc prevajalnik.

Hm, bom še počakal Vesoljca.

Vendar kaj jaz želim slišati je izkušnja: Sem programer, ki programira v C 10+ let in, ko imam problem X rezerviram dinamični pomnilnik zaradi A in ko imam problem Y uporabim kar stack zaradi B. Ja in kow ima prav, stack se ne rezervira, v bistvu se samo pointer premakne, ko se pusha gor ali popa.

marjan_h je 30. jul 2022 ob 13:46 izjavil:

Ja in kow ima prav, stack se ne rezervira, v bistvu se samo pointer premakne, ko se pusha gor ali popa.

No, nisem povedal pravilno. Obstajati mora tudi naslov zacetka arraya. Drugace "array[0] = 42;" ne bi vedel kam zapisati.
Torej, premakni pointer za X bajtov on naslova Y. Dokler smo znotraj funkcije, se naslov Y ne sme prepisati z drugo vrednostjo.

Vsak netrivialen program, ima recimo kaksen cache itd. Tako, da se malloc vedno uporablja.

Da. Marjan tvoj tesni program, bi moral tudi kaj ZAPISATI za sledeco vrstico: int array[number];
Pa ne na zacetek arraya, kot si pisal ti.
Dodaj samo int z = 15; ter prevedi in pozeni (vnesi visoki number, recimo milijarda). Za vsak slucaj tudi izpisi to stevilko na zaslon, da ne bo kompiler pameten in bo odvrgel neuporabljeno vrstico.

Če imaš npr array s črkami abecede ali imeni mesecev to daš na stack ampak skor bolj smiselno naredit global const array iz tega (tako se dela v praksi), kar pa ne gre na stack ampak v data segment.

Sem se malo igral:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int number;
    printf("Enter an integer: ");  
    scanf("%d", &number);
    
    int array[number];
    int z = 15;
    
    array[0] = 42;
    array[1] = 2;
    array[2] = 3;
    
    printf("\n %d", array[0]);
    printf("\n %d", z);
    printf("\n %d", number);
     
    return 0;
}

Ko vnesem 100 000 ali 1 000 000. Stvar deluje. Vendar pa neha delovati pri okoli 2 000 000, vrne sledečo napako: "Napaka segmentacije (izpis jedra)".
In ker uporabljam Linux ter rezerviram cela števila (4 B), je to ravno okoli 8 MB pri 2 000 000, kar pomeni, da se vse ujema.

Tole si preberite, pa vam bo zelo veliko jasno. Ne pravim, da kodirajte v assemblerju, vzamite kot arhitekturne osnove, ko jih enkrat poznas, ni C noben bavbav vec.
https://www.ic.unicamp.br/~pannain/mc40...

kuall je 31. jul 2022 ob 22:01 izjavil:

po moje c++ prevede tele oglate oklepaje v kak malloc. nisem c++ stručnjak samo vem, da se da tudi določene operaterje overloadat pa take fore.

Wtf... ne nic jih ne prevede v malloc (heap), alocira na stacku (alloca).

marjan_h je 31. jul 2022 ob 20:31 izjavil:

Ko vnesem 100 000 ali 1 000 000. Stvar deluje. Vendar pa neha delovati pri okoli 2 000 000, vrne sledečo napako: "Napaka segmentacije (izpis jedra)".

Da, ker je velikost stacka definirana ob casu compajliranja in ti si z 2000000 presegel defaultno vrednost. Ali bos uporabil na gccju -Wl,--stack,*size*, bos klical getrlimit ali pa bos nehal uporabljati stack za take neumnosti in bos uporabil heap, kar bi naredila vecina ljudi. Ko se ze ravno na C spravljas, ti dam eno veliko pomoc, memorija v Cju ni nek tip, ampak je tip samo kako predstaviti memorijo. In se ena zlata: pointer je memorija, kjer je napisan naslov memorije, kjer so podatki. Brez * se sprasujes po naslovu, z zvezdico po podatkih.

Stacka in heapa ti pa ne mislim razlagat, imas na netu toliko sranja spisanega okrog tega, da ne bom tratil casa, pac BERI, namesto iskanja bliznjic.

:)

zivimo v svetu luksuza, desktop aplikacije imajo "ogromno" pomnilnika na voljo. naj si bo 1MB ali 8MB stacka, za solske primere in ucenje "osnov" je to v 99% cisto dovolj. kako bos iteracijo cez polje z for zanko nekoga naucil, ce mu bos notri vrinil se pointerje? pac nardis polje na stacku, veliko ali 100 ali pa 100.000 in to je to. vse spila.

ne gre za to da tega ne smes tako delat, pac lahko, compiler/linker to dovolita, samo zavedat se moras omejitev. pa tudi heap ni nek bav bav, ze nek semi primitiven tool za obdelavo slik ne more laufat na stacku, ce rabi za obdelavo imet celotno sliko v pomnilniku (ce obdelujes ikone ajdi :) ), takrat moras uporabit heap, druge nimas.