---

Er der en der kort kan definere STACK og HEAP?
Jeg har en ide om at stack'en bliver skabt ved kompileringen og ikke ændres,
hvorimod heap'en ændres mens programmet kører. Er det helt galt?

---------------------------------------------
Thomas Sejr Jensen
Thomassj@worldonline.dk
www.worldonline.dk/~thomassj
---------------------------------------------

---

[ "Thomas Sejr Jensen" <thomassj@worldonline.dk> ]

> Er der en der kort kan definere STACK og HEAP?

En stak er en data-struktur der tilgås i dens ene ende, og som typisk
har to operationer (tilføj og læs) tilknyttet. Dvs. at hvis man har
en stak af heltal, hvorpå man skubber 117 og 42, kan man læse dem i
omvendt rækkefølge (42 efterfulgt af 117).

Hob har jeg ikke lige nogen definition af ved hånden.

> Jeg har en ide om at stack'en bliver skabt ved kompileringen og ikke
> ændres, hvorimod heap'en ændres mens programmet kører. Er det helt
> galt?

Hoben er almindeligvis der hvor man afsætter plads til dynamisk
allokerede data (f.eks. når du kalder malloc i C). Kald-stakken
indeholder argumenter og returadresser (== aktiveringsposter, næsten),
så hver gang du kalder en ny funktion ændres stakken -- men typisk på
en måde der er bestemt på oversætningstidspunktet.

--
Sune Kirkeby Test-tube babies shouldn't throw stones.
http://mel.interspace.dk/~sune/

---

Hej,

> Hob har jeg ikke lige nogen definition af ved hånden.

En hob defineres normalt som en datastruktur som indeholder ordnede
elementer og hvor man har tre operationer til rådighed: Man kan indsætte et
element, få at vide hvad det mindste element er samt fjerne dette mindste
element.

Derudover bruges hob også ofte om en datastruktur hvor der administrerer et
lagerområde og hvor man kan bede om at få allokeret et stykke lager med en
ønsket størrelse og implicit eller eksplicit deallokere et tidligere
allokeret stykke lager.

Hvad de to ting så har med hinanden at gøre har jeg undret mig over i mange
år. Jeg spurgte engang en klog mand om sammenhængen. Hans forklaring var så
vidt jeg husker at hob kunne oversættes med "bunke" og man kunne betragte
begge datastrukturer som en slags bunker. Formodentlig i den forstand at der
oftest vil være flere muligt måder disse strukturer kan organisere sig
gyldigt på - der er altså en vis form for rod i dem.. Ak ja...


Venlig Hilsen

Christian Worm

---

> Jeg har en ide om at stack'en bliver skabt ved kompileringen og ikke
ændres,

Det er godt at forstå hvad en stack er og hvordan den virker, men jeg
mener ikke man nogensinde manipulerer med den direkte i C eller C++ (well,
man kan vel i en asm{} blok) Det hører mere til assembler-programmering.

Når du kalder en funktion i dit program, gemmes først addressen på den
efterfølgende instruktion på stacken, derefter hopper programudførslen hen
til funktionen. Når funktionen så er færdig og udfører sin "return", læses
de øverste værdier på stacken, som fortolkes som en addresse, og programmet
fortsætter derfra. Dermed er programudførslen hoppet tilbage til linien
under funktionskaldet, og dit program fortsætter som
forventet.
(overvej hvilken katastrofe der kunne ske, hvis man inde i sin underrutine
flytter stackpointeren ved et uheld. )

Så hvis brugeren kan påvirke programudførslen (Fx i et menu-system) så kan
du godt se, at stacken ikke kan være lavet på forhånd.

> hvorimod heap'en ændres mens programmet kører. Er det helt galt?
Korrekt, fx hvergang du skriver "new"


tpt

---

"Thomas Sejr Jensen" <thomassj@worldonline.dk> wrote in message
news:sOFb6.8319$fa3.454156@news010.worldonline.dk...
> Er der en der kort kan definere STACK og HEAP?
> Jeg har en ide om at stack'en bliver skabt ved kompileringen og ikke
ændres,
> hvorimod heap'en ændres mens programmet kører. Er det helt galt?

Det var dog nogen knudrede forklaringer du har fået. Her er et efter min
mening simplere bud:

Stakken er et hukommelsesområde der bliver brugt til midlertidige data, det
være sig både returadresser og lokale variabler og parameteroverførsler.
Den/de (man kan godt have flere) har en fast defineret størrelse bestemt ved
kompileringen.

Heap'en er den hukommelse der iøvrigt er tilgængelig. Den bruges for
eksempel når man dynamisk allokerer et hukommelsesområde med new eller
malloc()

mvh
Lars

--
Remove ***nospam*** from email address

---

* Lars Blaabjerg

[snip]

> Det var dog nogen knudrede forklaringer du har fået. Her er et efter min
> mening simplere bud:


.... åh?


> Stakken er et hukommelsesområde der bliver brugt til midlertidige
> data, det være sig både returadresser og lokale variabler og
> parameteroverførsler.


Jeg kjenner til et språk der runtimesystemet _ikke_ kan bruke den
tradisjonelle "stack'en" i det hele tatt: *alle* midlertidige data,
*alle* returadresser blir allokert på heap'en.


> Den/de (man kan godt have flere) har en fast defineret størrelse
> bestemt ved kompileringen.


Huh? Størrelsen på lokalvariablene er blitt bestemt ved compile-time?
Er du _sikker_ på det? (tilsvarende gjelder
funksjonsargumenter/parametre).


> Heap'en er den hukommelse der iøvrigt er tilgængelig. Den bruges for
> eksempel når man dynamisk allokerer et hukommelsesområde med new
> eller malloc()


Jeg foretrekker den definisjonen at stack'en er den delen av
hukommelsen som oppfører seg som en stack (ADT) for
innsetting/sletting av elementer. Ofte (men langt ifra alltid) vil den
delen av hukommelsen bli brukt til plassering av aktiveringsblokker
(eng: activation records) til prosedyrer som inneholder bl.a.
returadresse og lokale variable. heap'en er den delen av hukommelsen
som ikke trenger å følge FIFO prinsippet for allokering/deallokering.





ivr
--
Besides, meat tends to run away when possible, or fights. Either
response presents behavioral challenges too complex for any existing
robot.
      -- Stuart Wilkinson, inventor of the "gastrobot"

---

Igor V. Rafienko <igorr@ifi.uio.no> skrev i en
nyhedsmeddelelse:xjv3ddildd7.fsf@jormunrekk.ifi.uio.no...

> Huh? Størrelsen på lokalvariablene er blitt bestemt ved compile-time?
> Er du _sikker_ på det? (tilsvarende gjelder
> funksjonsargumenter/parametre).

Vi taler vel om cpu-stakken eller hvad? Altså processorens private
"notesblok" i hukommelsen (Push HL - Pop BX osv).

Hvis det er tilfældet, bør compileren være i stand til at tælle stakkens
maxlængde op. Den er vel nødt til at initiere processorens SP register med
en adresse, som sikrer at stakken ikke vokser ind i et sårbart
hukommelsesområde. Okay, jeg har ikke programmeret med assembler i hundrede
år, så det kan jo have ændret sig. (Jeg vidste fx ikke, at man kunne arbejde
med flere stakke. Hvorfor mon det?)

> som ikke trenger å følge FIFO prinsippet for allokering/deallokering.

(Psst! LIFO - FIFO er netop ikke en stak, men en kø).

mvh Ulrik J.

---

U. Jantzen skrev:

>Vi taler vel om cpu-stakken eller hvad?

Nej. Man kan lave lige så mange stakke som man bare gider. Det
eneste krav er faktisk at der er en stakpeger og at det er en
LIFO-struktur.

--
Bertel   http://lundhansen.dk/bertel/
   FIDUSO: http://fiduso.dk/

---

* U. Jantzen

> > Huh? Størrelsen på lokalvariablene er blitt bestemt ved
> > compile-time? Er du _sikker_ på det? (tilsvarende gjelder
> > funksjonsargumenter/parametre).
>
> Vi taler vel om cpu-stakken eller hvad? Altså processorens private
> "notesblok" i hukommelsen (Push HL - Pop BX osv).
>
> Hvis det er tilfældet, bør compileren være i stand til at tælle
> stakkens maxlængde op.


Nei, overhodet ikke:

int
printf( const char* format, ... )
{
/* whatever */
}

hvor mange variable push'es på stack'en før printf blir kalt? Og som
en variasjon:

void
foo( int n )
{
int x;

// whatever
if ( n > 10 ) {
int y;
// whatever
}
}

Hvorvidt man trenger plass til 3 int'er eller 2 på stack'en når man
kaller foo er heller ikke kjent compile-time (tilsvarende gjelder
anonyme mellomresultater). Dog, i _dette_ tilfellet kan en kompilator
anta konservativt maksstørrelsen på aktiveringsblokken. Og _så_ har vi
VLA'er (og jeg skulle gjerne ha visst hvordan maksstørrelsen på
aktiveringsblokken skulle beregnes i det tilfellet).


> Den er vel nødt til at initiere processorens SP register med en
> adresse, som sikrer at stakken ikke vokser ind i et sårbart
> hukommelsesområde. Okay, jeg har ikke programmeret med assembler i
> hundrede år, så det kan jo have ændret sig. (Jeg vidste fx ikke, at
> man kunne arbejde med flere stakke. Hvorfor mon det?)


Kristen Nygaard kalte disse for "multistack programming languages".
Simula er et eksempel på slike (språket støtter korutiner, hvilket
gjør at stackbegrepet ikke er egnet til implementasjon av
runtime-systemet).


> > som ikke trenger å følge FIFO prinsippet for allokering/deallokering.
>
> (Psst! LIFO - FIFO er netop ikke en stak, men en kø).


D'uh! [smash the forehead against the keyboard] Takk.





ivr
--
Besides, meat tends to run away when possible, or fights. Either
response presents behavioral challenges too complex for any existing
robot.
      -- Stuart Wilkinson, inventor of the "gastrobot"

---

"Igor V. Rafienko" <igorr@ifi.uio.no> wrote in message
news:xjv3ddildd7.fsf@jormunrekk.ifi.uio.no...
> * Lars Blaabjerg
>
> [snip]
>
> > Det var dog nogen knudrede forklaringer du har fået. Her er et efter min
> > mening simplere bud:
>
>
> ... åh?
>
>
> > Stakken er et hukommelsesområde der bliver brugt til midlertidige
> > data, det være sig både returadresser og lokale variabler og
> > parameteroverførsler.
>
>
> Jeg kjenner til et språk der runtimesystemet _ikke_ kan bruke den
> tradisjonelle "stack'en" i det hele tatt: *alle* midlertidige data,
> *alle* returadresser blir allokert på heap'en.
>

Nu er det her jo en c gruppe

>
> > Den/de (man kan godt have flere) har en fast defineret størrelse
> > bestemt ved kompileringen.
>
>
> Huh? Størrelsen på lokalvariablene er blitt bestemt ved compile-time?
> Er du _sikker_ på det? (tilsvarende gjelder
> funksjonsargumenter/parametre).
>

Kompileren kan ikke selv finde ud af denne størrelse. Hvis din stack er for
lille vil du løbe ind i stack overflow runtime fejl. Kompileren kan ikke
selv finde ud af størrelsen der er nødvendig, da kald jo i princippet kan
nestes uendeligt i en rekursiv funktion. F.eks. er default størrelsen i
MSVC++6, 1 MB (for hver tråd)

>
> > Heap'en er den hukommelse der iøvrigt er tilgængelig. Den bruges for
> > eksempel når man dynamisk allokerer et hukommelsesområde med new
> > eller malloc()
>
>
> Jeg foretrekker den definisjonen at stack'en er den delen av
> hukommelsen som oppfører seg som en stack (ADT) for
> innsetting/sletting av elementer. Ofte (men langt ifra alltid) vil den
> delen av hukommelsen bli brukt til plassering av aktiveringsblokker
> (eng: activation records) til prosedyrer som inneholder bl.a.
> returadresse og lokale variable. heap'en er den delen av hukommelsen
> som ikke trenger å følge FIFO prinsippet for allokering/deallokering.
>
>
>
>
>
> ivr
> --
> Besides, meat tends to run away when possible, or fights. Either
> response presents behavioral challenges too complex for any existing
> robot.
> -- Stuart Wilkinson, inventor of the "gastrobot"