Dotaz: Dynamicky alokované pole struktur

[Beda0]

Zdravím,

mam dynamicky alokované pole struktur, které obsahují další struktury s 2D poli floatů a dašlích věcí a nějak jsem se do toho zamotal. Začínalo to poměrně jednoduše, ale pak se to postupně narostlo. Potřeboval bych poradit, jestli to uvolňuju správně a jestli je zvolené řešení vůbec vhodné.

Je to psané v C++, takže to je rozházené do tříd, zde pro jednoduchost jsou jen funkce. Data alokuju dynamicky až v readData(), protože na začátku čtení dat netušim, kolik jich bude a může jich být docela dost - v řádu tisíců struktur Data.

typedef struct {
    float** fDataA; //2D array of ...
    ...
}Data2;

typedef struct{
 float a[3];
 int b[4];
 int c;
 string string;
 Data2 data2;
 ...
} Data;

int allocateData(Data **data,...){
  *data = (Data*) malloc( pocetDat * sizeof(Data));
  for(int y = 0;y < pocetDat; y++){
    (*data)[y].data2.fDataA = (float**) malloc((*data)[y].data2.pocetDat2*sizeof(float*));
    
    for(int i = 0;i < pocetDat2;i++){
      (*data)[y].data2.fDataA[i] = (float*) malloc(pocetDat3*sizeof(float));
    }
  }
  ... //dalsi dynamicke alokace, overeni, jestli se to opravdu alokovalo...
}

int freeData(mainData **data){
  for(int y = 0;y < pocetDat; y++){
    for(int i = 0;i < pocetDat2; i++){
      free((*data)[y].data2.fDataA[i]);
    }
  }
  free(*data);
}
    
readData(Data **data,...){
   ...
   allocateData(data,...);
   ...
   //nactu hodnoty do data
   ...
}

main(){
   Data *data;
   ...
   readData(&data,...);
   ...
   printf("integer %i",data[2586].b[4]);
   freeData(&data);
}

Odpovědi

[Josef Kufner]

Příliš intenzivní používání malloc je značně neefektivní. Alokuj si velký kus paměti najednou, který ti bude většinou stačit a kdyby náhodou ne, tak přialokuj další. Nebo raději použij už hotový alokátor. Ten rozdíl ve výkonu je celkem značný.

Co se samotného alokování týče (ať už malloc nebo něco jiného), od toho jsou konstruktory a destruktory. A vůbec, co se ti nelíbí na new?

[Beda0]

Díky za reakci. Takže je vhodnější spočítat, kolik paměti budu potřebovat, což je v době volání allocateData známo a pak použít *data = (Data*) malloc(spocitanaVelikost);?

Malloc je použit protože to původně bylo v C a až do teď jsem nějak nepřemýšlel v čem se vlastně tak liší od New.

Jenže Data a Data2 jsou struktury, ne třídy, takže jejich konstruktory použít nemůžu i když by se tím asi dost věcí zjednodušilo.

Vlasně možná by nemuseli být - budu k tomu muset udělat binding do Pythonu, který znám jen z rychlíku, ale předpokládal jsem, že bude vhodnější nechat data ve strukturách, než ve třídách, což asi nemusí být pravda. Struktura Data se předává mezi knihovnou a programem a nějak jsem předpokládal, že bude vhodnější předávat data ve struktuře a ne ve třídě, co je taky asi jedno....

[chrono]

Ak tie údaje nie sú príliš veľké, tak sa môže priamo cez CPython vytvárať pythonovský objekt. Prípadne, ak spracovanie nie je príliš zložité, môže sa k tej knižnici pristupovať cez ctypes a údaje sa budú spracovávať až v Python.

[Jan Trávníček]

Proč by si nemohl v C++ použít konstruktor a destruktor u struktury?

[potato]

Protože strukturou myslí nejspíš plain-old-data[*], stejně jako normální lidi, kteří když má něco konstruktor a destruktor, tak tomu řeknou třída.

Na rozdíl od jazykových právníků, kteří samozřejmě vědí, že ten nejdůležitější rozdíl mezi stukturou a třídou v C++ je marginální, tedy výchozí přístupová práva ke členům, a pak se diví, že se s nikým nedomluví.

[*] Zde experti na C+11 zajásají, protože dostali příležitost vysvětlit, jak tam byl tento koncept rozveden a rozdělen, etc.

[Jan Trávníček]

Což ovšem neodpovídá na otázku zda by díky té možnosti něco nezlehčilo/nezjednodušilo.

[potato]

To už nedovedu posoudit z hlediska možnosti vytváření bindingů z C++ do jiných jazyků, protože to nesleduji zase tak podrobně -- občas napíši něco ručně, ale jinak je dělám hlavně z C pomocí g-ir. Každopádně bindingy C++ tříd vyžadují obecně dost jiné přístupy než POD + funkce.

[Beda0]

Struktury jsou bez konstruktorů proto, že jich je tam víc a některé z nich nemam pod kontrolou - používají se i jinde a nemůžu je měnit. Proto mi přišlo vhodné ukládat všechno do struktur a ne půlku do struktur a půlku do tříd.

Na druhou stranu nemám pod kontrolou jen struktury výrazně jednodušší, do kterých se ukládají dost odlišná data, proto by bylo možné v tomto případě použít třídy, ale narážím na problém s bindingem, který může a nemusí být reálný, zatím jsem neměl čas to dopodrobna studovat.

Vím, že jediný rozdíl mezi strukturou a třídou v C++ je to, že struktura má členy implicitně public, označil jsem to nepřesně přesně ve smyslu jak píše potato.

[Beda0]

Takže jsem upravil a používám new/delete místo malloc/free. Vím, že by šlo vše optimalizovat použitím fDataA[i*pocetDat2+y] místo fDataA[i][y],ale podle mě při takovém množství dat ta malá úspora paměti na úkor přehlednosti nemá cenu. Rychlost alokace je v porovnání s rychlostí načítání dat zanedbatelná. Jediný problém tuším v tom, že data nebudou v paměti za sebou, což nedokážu posoudit, jaký může mít vliv.

int allocateData(Data **data,...){
  *data = new Data[pocetDat];
  for(int y = 0;y < pocetDat; y++){
     (*data)[y].data2.fDataA = new float*[pocetDat2];
     for(int i = 0; i < pocetDat2; ++i){
        (*data)[y].data2.fDataA[i] = new float[pocetDat3];
     }
  }
  ...
}

int freeData(Data **data,...){
  for(int y = 0;y < pocetDat; y++){
    for(int i = 0;i < pocetDat2; i++){
      delete [] (*data)[y].data2.fDataA[i];
    }
    delete [] (*data)[y].data2.fDataA;
  }
  delete [] *data;
}

[TonyMi]

Když už to je C++, tak bych použil std::vector. Kód je pak mnohem čistější, dealokace je často "bez práce" a rychlost nebude nižší (pokud velikost znáte stačí použít reserve či resize). Navíc se kdykoliv můžete zeptat na počet prvků a nemusíte si jej spravovat sám.

[Jardík]

Mé atomy souhlasí. Děláš to v C++, použij std::vector a vyser se na pitomý malloc/free. Např. podívej, jak se ti zjednoduší uvolnění paměti, jeden pitomej clear() na std::vector<Data> a vše ostatní jde samo. A i když ten clear nezavoláš, vše se stejně uvolní v destruktoru vectoru pro tebe, úpně bez práce, bez jediného řádku kódu. Příklad (netestovaný, na rychlo spatlaný, bez přemýšlení, možná s chybama):

struct Data2
{
  std::vector<std::vector<float>> fDataA;
  // ...
};

struct Data
{
  float a[3];
  float b[4];
  int c;
  string string;
  Data2 data2;
  // ...
};

int allocateData(std::vector<Data>& data, ...)
{
  data.resize(pocetDat);
  
  for (size_t y = 0; y < pocetDat; ++y)
  {
    Data& dy = data[y];
    
    dy.data2.fDataA.resize(pocetDat2);
    for (size_t i = 0; i < pocetDat2; ++i)
    {
      dy.data2.fDataA[i].resize(pocetDat3);
    }
  }
  
  // blabla
}

int freeData(std::vector<Data>& data)
{
  // aneb vyser se na malloc a free
  data.clear();
}

[Beda0]

Nojo, proč mě to nenapadlo? Nějak mi nedošlo, že už nejsem v C a mam všechny ty úžasný věcičky z C++. Díky.

[Beda0]

S tou paměťovou náročností std::vector to nebude zas tak růžový, jak všude čtu - s vektorama si to vezme o 5 MB víc - 67 místo 62 - a to jsem vektory použil jen na floaty, ne na celý struktury. Mam 25920 struktur data, každá obsahuje 3 pole floatů 4*25. Měřeno "od oka" ve správci procesů. Připadá mi to docela vysoká cena za zjednodušení.

Testuju na x86_64, ale poběží to na ARMu s né zrovna moc pamětí, takže nějaký šetření je na místě.

[Jardík]

Tak s vectorem je to tak, že tam pravděpodobně bude držet nějaký dvě hodnoty (počet prvků a velikost naalokovaného bufferu) a nějaký ukazatel. Proto asi vector<vector<float>> nebude udeální, ale pro jednoduchost jsem to tam narval. Lepší by asi byl vector<float> s velikostí cols*rows a index počítat jako row*cols+col nebo tak něco.

[Šangala]

Jen pro doplnění, následný kód paměť neuvolní (jen k poznámce „aneb vyser se na malloc a free“).

int freeData(std::vector<Data>& data)
{
  // aneb vyser se na malloc a free
  data.clear();
}

optimističtější varianta by musela vypadat asi takto nějak:

int freeData(std::vector<Data>& data)
{
  data.clear();
  // aneb vyser se na malloc a free
  std::vector<Data> tmp;
  data.swap(data);
}

Jinak vector určitě jo, nicméně pokud to má mít i malé paměťové nároky, tak bohužel jen jeden a počítat si to růčo a přistupovat k prvkům přes at(), ale zamyslel bych se nad tím, jestli mi opravdu vadí použít vector vector-ů při drobném navýšení nároků. Kdyby se jednalo o miliony a více záznamů, tak to má význam, ale tísíce znamená 10tis, což je asi 280KB navíc).

[Šangala]

Jeda sorry, opravička:

int freeData(std::vector<Data>& data)
{
  // aneb vyser se na malloc a free
  data.clear();
  std::vector<Data>& tmp;
  data.swap(tmp);
}

[Beda0]

S těma tisícema jsem to trošku podcenil - těch floatů je na datech, na kterých to testuju 26000*3*4*25 = 7 800 000. (26000 struktur Data, každá obsahuje 3 pole floatů, každé o velikost 4*25) Paměťová náročnost 2D polí je bohužel výrazná, viz níže. Zítra si s tím ještě zkusím pohrát a uvidím, jaký bude rozdíl použití float vs std::vector. Díky.

[Beda0]

Ty data toho obsahují daleko víc, než 3 pole floatů, ale teď se zabývám jen těma třema polema....

[Šangala]

Jestli to není třeba vhodné na:

typedef struct{
  float ttt[3][4][25];
}myrec;

std::vector<myrec> data;

[Beda0]

To mě nikdy nenapadlo, že 2D pole mají tak velkou režiji - se std::vector<float> to má 56MB, s float* 55.5MB - rozdíl necelých 0.5MB, ale 11MB, resp. 6MB oproti použití 2D polí. Nicméně při použití pouze jednorozměrných polí se vytrácí výhoda std::vector, protože stejně musím udržovat informace o velikostech kvůli ručnímu počítání iterací float[i*size1+y]. .size() je mi k ničemu. Navíc všechny ostatní data mám ve standardních polích a není vhodné mít půlku tak a půlku tak.

Kdybych všechny data uložená v polích převedl na std::vector, tak bude rozdíl v paměťové náročnosti větší než nynějších 0.5MB a práci mi to neulehčí (kromě alokace a uvolnění paměti) vůbec v ničem.

[Šangala]

Příloha:

• kuk.cpp (1080 bytů)

Dej přesně všechny podmínky, ten rozdíl je, že vector jestli má s spou režii, ukazatel, kapacita, velikost. S resize můžeš přidat více paměti než chceš viz příloha (kompilovatelná g++ kuk.cpp -o kuk), ono vector je super, ale zrovna ve správě paměti se lehce naseká spousta chyb (platí pro celou stl).
Jde o to co má pevnou délku a co nemá, z toho je třeba u takové aplikace vyjít.

[Beda0]

Díky za osvětlení problematiky. STL jsem nikdy moc nepoužíval, takže tady mam dost mezery.

Mno, je z toho tady už docela zmatek, takže stav, v jakym to je teď:

typedef struct {
    u64 neco;
    u8 neco2;
    u8 neco3;
    float pole1[4];
    float pole2[4];
    ... /dalsi data - celkem 846B dat ulozenych vetsinou ve ve 4 prvkovych float polich s pevnou delkou

    //nasleduje pet poli o ktere mi ted jde predevsim - na testovacich datech jsou tri
    //z nich o velikosti 4*25 a dve prazdne. Maximalne muze v soucasne dobe mit kazde 
    //velikost 4*50. Velikost poli neznam v dobe kompilace, ale v dobe volani allocateData
    //uz jo a nikdy se potom nemeni.
    float *dulezitePole1; /**< 2D array of ... */
    float *dulezitePole2; /**< 2D array of ... */
    float *dulezitePole3; /**< 2D array of ... */
    float *dulezitePole4; /**< 2D array of ... */
    float *dulezitePole5; /**< 2D array of ... */

} Data;
allocateData(Data **data,...){
    //pocetDat = pocet struktur Data je na testovacich datech 26000,
    //v realu muze byt vyrazne min, ale i o dost vic.
    *data = new Data[pocetDat];
    
    for(int y = 0;y<pocetDat;y++){
        (*data)[y].dulezitePole1 = new float[pocetDat21 * pocetDat3];
        (*data)[y].dulezitePole2 = new float[pocetDat22 * pocetDat3];
        (*data)[y].dulezitePole3 = new float[pocetDat23 * pocetDat3];
        (*data)[y].dulezitePole4 = new float[pocetDat24 * pocetDat3];
        (*data)[y].dulezitePole5 = new float[pocetDat25 * pocetDat3];
    }
}

Když jsem místo float *dulezitePole1 zkoušel std::vector<float> dulezitePole1 a ve funkci allocateData použil dulezitePole1.resize(pocetDat21 * pocetDat3); byla spotrebovana pamet jen o 0.5 MB vetsi nez pri pouziti float* a new.

Jenže použití std::vector mi nepřineslo žádný viditelný užitek - stejně jsem si musel iterovat a pamatovat velikosti sám, protože dulezitePole1.size() je mi k ničemu. Navíc zde dochází k tomu, že většina polí je float[4] a 5 polí je std::vector, což je matoucí - tu knihovnu nebudu používat jen já.

Když jsem použil std::vector na všehny 4 prvkové pole floatů ve struktuře Data (je jich 50), tak paměťová náročnost vzrostla o 11,5MB.

[Beda0]

Odpovídající freeData:

int freeData(Data **data){
    for(int y = 0;y < pocetDat; y++){
      delete [] (*data)[y].dulezitePole1;
      delete [] (*data)[y].dulezitePole2;
      delete [] (*data)[y].dulezitePole3;
      delete [] (*data)[y].dulezitePole4;
      delete [] (*data)[y].dulezitePole5;
    }
    delete [] *data;
    return 0;
}

[TonyMi]

Když místo resize použijete reserve, tak se sice paměť naalokuje, ale size bude ukazovat reálný počet prvků a přidávat pak budete pomocí push_back.

Na ta pole float[4] skutečně nemá cenu std::vector používat. Nevím co s těmi poli děláte, možná by zpřehlednění pomohl typedef či lépe nějaká obalující třída (pokud to jsou třeba quatermiony, tak se do obalující třídy dají přidat metody pro různé operace nad nimi, přetížit operátory a podobně).

Padesát čtyrprvkových polí ve struktuře mi trochu zavání špatným návrhem, opravdu to potřebujete takto udělat? Nestačilo by jedno padesátiprvkové pole tříd se čtyřmi floaty uvnitř?

Z mého pohledu má std::vector hlavní výhody v tom, že si nemusím udržovat počet prvků, v dealokaci a v čistotě kódu. Při vývoji velkých aplikací se mi to osvědčilo. Pokud tyto tři aspekty hodnotíte jinak, asi pro Vás nemá std::vector význam.

[Beda0]

Díky za postřehy.

Data obsahují údaje o různých vlastnostech - těch vlastností je 50, proto 50 polí. Každá vlastnost je ukládaná pro 4 "jednotky", proto 4 prvky každého pole. Jednou ty data načtu a pak je zobrazuju - podle vlastností pro všechny jednotky naráz - tzn. např. v grafu zobrazím jednu vlastnost pro všechny 4 jednotky. Návrh určitě není ideální, proto se také tady ptám, ale nenapadá mě, jak to udělat jednodušeji při zachování přehlednosti. Jsou to jednoduchá data, takže nad nimi žádné operace provádět nepotřebuju - jen je nějak zobrazit a o to se stará jiná aplikace.

Jenže já o tu největší přednost std::vector - to, že si nemusim udržovat počet prvků - přijdu, když použiju jednorozměrné pole pro uložení dat z matice s "dynamickou" velikostí (kvůli úspoře paměti) - samotné .size() je mi tady k ničemu, protože stejně musím iterovat sám - (*data)[y].dulezitePole1[i*pocetDat3 + y]. Při použití std::vector by mi stačilo udržovat informaci o pocetDat3 a druhou velikost dopočítat ze .size(), takhle musím udržovat informace i o dalších 5 velikostech(pocetDat2x). To je pravda. Ale velikosti se dají dopočítat vcelku jednoduchou funkcí z konfiguračních dat, které načítám také, takže si je nemusím pořád pamatovat. Navíc je IMHO už jedno, jestli si pamatuju jednu velikost nebo 6 uložených v jedné struktuře.

Zjednodušení při alokaci a dealokaci, kterou provádím ve funkcích je minimální. Naprogramuju jednou funkce pro alokaci a dealokaci, které bych musel mít stejně a víc mi to nic nezesložiťuje ani nedělá kód čistší.

Výše popsané (v tomto konkrétním případě né příliš výrazné) výhody std::vector mi IMHO nevyváží to, že se mi nelíbí mít v jedné struktuře míchané standardní pole se STL kontejnery.

Abych nebyl špatně pochopen - nemám nic proti std::vector a v Qt s oblibou požívám QVector a podobné kontejnery, jen pro jejich požití v tomhle konkrétním případě nevidím moc důvod, ale je možné, že mi pořád něco uniká...

[Josef Kufner]

Takže ty chceš místo std::vector implementovat vlastní kontejner, který bude obsahovat předalokované dvojrozměrné pole a bude umět k němu hezky přistupovat. Nepatlej to dohromady a implementuj kontejner.

[Beda0]

Jenže std::vector je příliš paměťově náročný, když mam 26000 struktur Data, který sice obsahujou dynamicky alokovaný pole, ale ve všechn 26000 případech odpovídající pole mají stejný rozměr (což sem asi měl zmínit dřív) - takže tady 26000*5 ukládám ve std::vector kromě vlstních dat to samý - velikost + další režii, což mi ve výsledku zvýší paměťovou náročnost a skoro mi to nepomůže.

[Josef Kufner]

Čti pozorněji Povídám místo std::vector.

Prostě si naprogramuj úsporné, efektivní a snadno použitelné 2D pole přesně takové, jaké potřebuješ. Transformace souřadnic jsem tu už viděl, jen to pěkně zabalit, aby se s tím dalo pracovat. Jeho prvky pak budou nějaké rozumné třídy/struktury/cokoliv, to už jsi tu snad už vyřešil o pár komentářů výše.

[lacod]

Neviem ako je mysleny riadok string string; ale ak predpokladame objekt triedy std::string, tak alokovanie instancie struktury data pomocou funckie malloc nie je korektne, pretoze sa nezavola konstruktor triedy std::string. Tu su nejake tipy v C++ bez kontajnerov:

// vytvorenie pola objektov , !!pouziva def.konstruktor pre Data
Data *data = new Data[pocetDat]; 
// dealokovanie objektov Data
delete[] data;

// alokovanie pola smernikov (pointer) na typ float
(*data)[y].data2.fDataA = new float*[(*data)[y].data2.pocetDat2];
// alokovanie  pola float-ov
(*data)[y].data2.fDataA[i] = new float[pocetDat3];

// dealokovanie 
for(int y=;...;y++)
  for(int i;...;i++)
    delete  (*data)[y].data2.fDataA[i] ;
  delete (*data)[y].data2.fDataA;