Dynamická alokace

Motivace

Až doteď jsme byli schopni pracovat s daty, o kterých jsme dopředu věděli, jak jsou rozsáhlá. Pokud jsme chtěli zpracovávat text po řádkách, museli jsme mít a priori znalost maximální délky řádku. Důvodem bylo, že jsem museli řádku uchovat v paměti a vytvořené pole mělo velikost danou přímo v programu (byla pevně daná už před překladem). Tento problém částečně řeší lokální nekonstantní pole zavedené ve standardu C99. Nicméně takto vytvořené pole nelze měnit v době běhu programu, jeho délka je neměnná.

Proměnná či pole vytvořená v době překladu se nazývá staticky alokovaná proměnná. Její velikost zná překladač předem. Výhoda takového přístupu je prvně jeho rychlost a též bezobslužnost – při definování proměnné se vyhradí data a při opuštění příslušného bloku kódu se paměť automaticky uvolní. Tím, že se místo vyhrazuje pouze posunem ukazatele na zásobníku programu, máme zaručenu konstantní složitost takové alokace.

Dále v textu se budeme zabývat tzv. dynamicky alokovanými daty, tedy daty, jejichž místo v paměti je vyhrazeno až při běhu programu. Výhodou tohoto přístupu je velká flexibilita – máme kompletní kontrolu nad délkou alokace a můžeme ji dodatečně ovlivnit. Nevýhodou je relativní náročnost tohoto typu alokace, kde se musí projít halda a vyhledat v ní příslušně dlouhý úsek spojité paměti. Správa paměti je přenechaná plně na programátorovi, který musí zajistit správné zacházení se zdroji v paměti, jinak může dojít k pádům programu nebo k vyčerpání volné paměti.

Vyhrazení a uvolnění paměti

Pro alokaci úseku paměti máme k dispozici několik funkcí z hlavičkového souboru stdlib.h:

void* malloc(size_t velikost);

Vyhradí velikost bajtů paměti a vrátí ukazatel na první prvek. Ukazatel je bez doménového typu, je tedy třeba ho přetypovat na typ, který požadujeme.

void* calloc(size_t nclenu, size_t velikost);

Vyhradí pole o nclenu členech, kde každý má velikost velikost bajtů. Alokované pole je vyplněno binárními nulami. Tato funkce je pomalejší než malloc(). Funkce vrátí ukazatel na první prvek a stejně jako u malloc() je vhodné přetypování.

void* realloc(void *pole, size_t velikost);

Realokuje pole pole. Funkce vytvoří nové pole o velikosti velikost bajtů a překopíruje do něj obsah původního pole, které muselo být dříve vytvořeno pomocí jedné z funkcí malloc(), calloc() nebo realloc(). Funkce vrátí ukazatel na první prvek nového pole. Nové pole může ležet na jiném místě v paměti než původní pole, původní ukazatel by se tedy již po zavolání neměl používat (zdrojové pole bude automaticky uvolněno). Je-li velikost menší, než je délka původního pole, bude v novém poli pouze fragment původního obsahu. Bude-li větší, nově vyhrazené místo nebude inicializováno. Nastavíme-li velikost na nulu, bude zdrojové pole uvolněno.

Velikost je udávaná v bajtech. Pokud chceme vytvořit pole typu int o deseti položkách, můžeme použít operátor sizeof() vysvětlený v sekci o ukazatelích. Výsledná velikost bude 10*sizeof(int).

Každá z výše uvedených funkcí vrátí ukazatel na první prvek alokovaného pole. Pokud ukazatel zahodíme, zůstane místo vyhrazené, ale do paměti se již nedostaneme. Mluvíme pak o úniku paměti, neboli memory leaku, kdy se alokované místo neuvolní a zabírá zdroje donekonečna. Takové chování může u programů, které běží dlouho, způsobit vyčerpání volných zdrojů nebo nadměrné využívání odkládacího prostoru a tedy zpomalení reakcí počítače. Řádné uvolnění paměti se provede voláním následující funkce:

void free(void *pole);

Bezpečně uvolní zabrané zdroje. Pole pole muselo být dříve vytvořeno voláním jedné z výše uvedených funkcí. Předáme-li NULL, funkce nic neprovede. Pokusíme-li se uvolnit paměť dvakrát, obdržíme chybu segmentace a program bude typicky ukončen.

Ke každé alokaci by správně mělo příslušet i volání free(). Toto bývá ve složitějších programech často velmi náročné, a proto existují nástroje, které odhalí neuvolněnou paměť.

Pro vyplnění vyhrazené paměti určitou hodnotou slouží následující funkce, jejíž deklarace je v hlavičkovém souboru string.h:

void *memset(void *zdroj, int vzor, size_t pocet);

Vyplní pocet bajtů pole zdroj vzorem uloženým v parametru vzor. Vrátí ukazatel na vyplněné pole zdroj.

Následuje malý příklad, ve kterém vyhradíme místo pro pole deseti celých čísel, vynulujeme jej voláním memset(), naplníme jej náhodnými daty, pak zvětšíme jeho velikost na dvacet čísel a poté jej uvolníme.

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

int main (int argc, char **argv)
{
  int i;
  int *pole, *docasne;
  srand(time(NULL));
  /* přetypování na int* není nutné v jazyce C,
  je ale nutné v C++ */
  pole = (int*)malloc(10*sizeof(int));
  /* kontrola úspěšné alokace zdrojů */
  if (!pole)
  {
    printf("dosla pamet\n");
    return -1;
  }
  /* vynulování všech bajtů pole */
  memset(pole, 0, 10*sizeof(int));
  
  /* naplnění pole klasickým cyklem */
  for (i = 0; i < 10; i++)
  {
    pole[i] = rand();
  }
  
  /* pokus o realokaci pole, zvětšení o deset prvků */
  docasne = realloc(pole, 20*sizeof(int));
  /* kdybychom použili rovnou ukazatel pole namísto dočasné,
  pak v případě selhání funkce realloc() by původní pole
  stále existovalo, ale náš ukazatel na něj by byl NULL,
  čili by došlo k úniku paměti. Proto si musíme pomoci jiným
  ukazatelem. */
  if (!docasne)
  {
    printf("dosla pamet\n");
    /* došlo k chybě, původní pole je ale stále alokované,
    musíme ho uvolnit */
    free(pole);
    return -1;
  }
  /* vše je OK, nastavíme náš ukazatel na nové větší pole */
  pole = docasne;
  /* zde můžeme využívat pole o dvaceti prvcích */
  /* ... */
  /* pole už není potřeba, uvolníme jej */
  free(pole);
  return 0;
}

Alokace vícerozměrného pole

Dynamicky alokované vícerozměrné pole lze vytvořit dvěma různými způsoby. Prvním a jednodušším postupem je vytvoření serializované verze vícerozměrného pole. Alokaci si vysvětlíme na příkladu vytvoření matice 3x3:

int i, j;
// jednorozměrné pole velikosti 9
int *matice3x3 = (int*)malloc(3*3*sizeof(int));
for (i = 0; i < 3; i++)
{
  for (j = 0; j < 3; j++)
  {
    // vyplnění matice daty
    // indexuje se jedním indexem
    matice3x3[i*3+j] = i + j;
  }
}

// ...
free(matice3x3);

Tento kód je jednoduchý, jeho jedinou nevýhodou je nutnost uchovávat velikost řádky pole, abychom mohli prvním indexem skákat přes celé řádky. Navíc tento přístup umožní operačnímu systému přednačítat data, která jsou uchována v řadě za sebou, tudíž je přístup do pole rychlejší.

Druhý přístup se velmi často vyskytuje v učebnicích o programování. Přesto se jedná o horší z obou přístupů. Nejen, že je konstrukce a uvolnění pole komplikovanější, ale vlivem nesouvislosti dat je přístup do pole pomalejší.

int i, j;
// vytvoření přístupového vektoru
int **matice3x3 = (int**)malloc(3*sizeof(int*));
for (i = 0; i < 3; i++)
{
  // vytváření jednotlivých řádek
  matice3x3[i] = (int*)malloc(3*sizeof(int));
  for (j = 0; j < 3; j++)
  {
    // vyplnění matice daty
    // indexuje se klasicky dvěma indexy
    matice3x3[i][j] = i + j;
  }
}

// ...

for (i = 0; i < 3: i++)
{
  //uvolnění řádek matice
  free(matice3x3[i]);
}
// uvolnění přístupového vektoru
free(matice3x3);

Základem tohoto postupu je vytvoření tzv. přístupového vektoru, tedy pole ukazatelů na jednotlivé řádky. V cyklu pak naalokujeme jednotlivé řádky, které jsou již klasická jednorozměrná celočíselná pole. Indexace pak probíhá tak, jak jsme zvyklí u staticky alokovaných polí přes dva indexy (nemusíme si pamatovat velikost řádky). Uvolňování pole probíhá v opačném pořadí – nejprve uvolníme řádky a poté přístupový vektor.

Nástroj Valgrind

Volně dostupný nástroj Valgrind je dynamický profilovací nástroj, který umožňuje mimo jiné odhalit chyby v použití paměti. Nástroj je dostupný pro operační systém GNU/Linux a Mac OS X. Jeho základní použití je velmi snadné. Předpokládejme, že máme následující program:

#include <stdlib.h>

int main (int argc, char **argv)
{
  int *pole = (int*) malloc(10*sizeof(int)); // alokace
  pole[0] = 1; // použití vyhrazené paměti
  return 0; // ukončení programu bez uvolnění paměti
}

Tento kód je chybně, protože v něm nevoláme free(pole). Když takový program přeložíme a spustíme, neuvidíme žádný problém. Program je velmi krátký a operační systém v dnešní době uvolní veškeré zdroje zabrané ukončeným programem. Program ale poslouží pro ukázku výstupu z nástroje Valgrind.

gcc program.c -o program
valgrind ./program

Obdržíme následující výstup.

==29047== Memcheck, a memory error detector
==29047== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==29047== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==29047== Command: ./program
==29047==
==29047==
==29047== HEAP SUMMARY:
==29047==     in use at exit: 40 bytes in 1 blocks
==29047==   total heap usage: 1 allocs, 0 frees, 40 bytes allocated
==29047==
==29047== LEAK SUMMARY:
==29047==    definitely lost: 40 bytes in 1 blocks
==29047==    indirectly lost: 0 bytes in 0 blocks
==29047==      possibly lost: 0 bytes in 0 blocks
==29047==    still reachable: 0 bytes in 0 blocks
==29047==         suppressed: 0 bytes in 0 blocks
==29047== Rerun with --leak-check=full to see details of leaked memory
==29047==
==29047== For counts of detected and suppressed errors, rerun with: -v
==29047== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

Blok LEAK SUMMARY poskytuje shrnutí paměťových operací. V našem případě jsem po ukončení programu přišli o čtyřicet bajtů, což odpovídá deseti čtyřbajtovým číslům v alokovaném poli. Během chviličky tedy vidíme, že jsme něco neprovedli správně, a že je nutné opravit uvolnění paměti. Pro podrobnější analýzu je možné Valgrind spustit s parametrem --leak-check=full, který je nutné zapsat před název spustitelného programu.

valgrind --leak-check=full ./program