Chiarimento tecnico -- Stack vs heap

Ciao,
ho ormai svolto qualche problema su questa piattaforma ma ultimamente mi è sorto un dubbio (probabilmente molto stupido agli occhi degli addetti ai lavori).

Nelle mie soluzioni ho infatti sempre allocato tutto sulla stack, senza avere mai alcun tipo di problema nonostante i dati in input fossero spesso di gran lunga superiori all’1/2 mb.
Come già detto, questo non mi ha mai dato nessun tipo di problema e non capisco come possa funzionare… evidentemente mi sto perdendo qualcosa…

Qualcuno saprebbe risolvere questo mio dubbio?
Grazie in anticipo!! :smile:

CMS disabilita il limite di memoria dello stack, su linux si può fare attraverso il comando ulimit -s unlimited. Tuttavia se partecipi ad altri contest in cui non c’è CMS, è probabile che ciò non accada.

In genere è comunque una brutta abitudine allocare grandi quantità di memorià nello stack, il mio consiglio è:

  • usa std::vector che alloca automaticamente le cose nell’heap ed ha molti metodi utili che gli array normali non hanno; oppure
  • usa array globali che vengono allocati staticamente in un segmento a parte e che vengono inoltre inizializzati a 0; oppure
  • dichiara gli array con la keyword static, in questo modo vengono allocati staticamente insieme alle variabili globali. Nota però che in questo modo l’array viene allocato un’unica volta anche se la funzione in cui si trova viene chiamata più volte.
1 Mi Piace

Capito, grazie mille, molto chiaro!
L’unico dubbio che mi rimane è: allocare grandi quantità di dati nello stack è pratica sconsigliata anche in ambito di programmazione competitiva? Non si potrebbe avere un discreto beneficio in quanto a performance (quantomeno utile per scalare la classifica) allocando nello stack invece che nell’heap?

Grazie ancora!

Le performance sono date da quanto velocemente la CPU riesce a leggere il dato dalla memoria. Se la variabile si trova in cache L1 allora la CPU è in grado di accedervi molto velocemente, in cache L2 e L3 è progressivamente più lento e in RAM c’è una latenza aggiuntiva.

Tuttavia anche nelle CPU moderne la cache L1 è nell’ordine di grandezza dei kilobyte, perciò un array di discrete dimensioni difficilmente può starvi interamente. Quindi che l’array sia nello stack o nello heap è abbastanza indifferente in quanto verrà caricato in cache spezzato in blocchi più piccoli.

In ogni caso, sconsiglio comunque di dichiarare gli array nello stack perché, come ho detto prima, in alcune gare è possibile che lo stack abbia un limite e superandolo, generi uno stack overflow

1 Mi Piace