[C] Probleem met gebruik van grote arrays

[Knakker]

Ik zit met een probleem, en het betreft geheugentoewijzing. Ik heb best veel gezocht, maar alle gevonden resultaten hebben betrekking op problemen die véél ingewikkelder zijn. Mijn probleem is héél simpel, zie ter illustratie de volgende code:

code:

main () {
   int Matrix[1000][1000];
   Matrix[759][862] = 1;
   }

Dit genereert een Segmentation Fault. Verander ik het datatype naar short int of verklein ik de dimensie van de matrix (zodanig dat de array dus minder geheugenruimte inneemt) dan werkt het wel (ongeveer tot +- 720x720).

Ik weet heel weinig van C en geheugentoewijzing. Ik weet wel dat ik op dit moment een slordige 400 MB aan geheugen vrij heb, en het lijkt me dat een matrix van 1000x1000 (een integer neemt 4 bytes toch?) er mákkelijk in moet passen. De grootte van de matrix is gedurende het hele programma constant; ik moet met instances van ~ 3000x3000 gaan werken welke de hele tijd tot mijn beschikking moet zijn (kan dus niet gedeeltes opslaan op hardeschijf enzo).

Wie-o-wie heeft de oplossing voor mijn simpele probleem? Bedankt!

[H!GHGuY]

jouw Matrix wordt op de stack aangemaakt. deze stack is voor zover ik weet niet oneindig groot. (ik denk dat de grens met ints rond de 4000/5000 ligt)

gebruik dus

C++:

int** Matrix = new int*[4000];
for (int i = 0; i < 4000;i++)
   Matrix[i] = new int[5000];

ik twijfel nu wel zelf of

C++:

int** Matrix = new int[4000][5000]

kan.

ik zie net dat je met C werkt en niet met C++., dan moet je malloc() en free() gebruiken ipv new en delete

[ Voor 14% gewijzigd door H!GHGuY op 28-09-2005 17:32 ]

[.oisyn]

HIGHGuY: een int** is een pointer naar pointers naar int (waarbij je 'pointer naar' uiteraard ook kunt substitueren met 'array van'). In een int[2][3] zitten geen pointers; het is een stukje geheugen van 2*3 = 6 ints groot, de compiler genereert de code om bij een opvraag van [1][2] de berekening 1 * 3 + 2 te doen.

Maar laten we het eens omdraaien: stel je hebt een int bla[4];. Je kunt nu een pointer naar die bla maken door &bla te doen (en dus niet bla, want dat resulteert dan weer in een pointer naar het eerste element van bla, oftewel &bla[0]). Het type van die pointer naar bla is int (*ptr_bla)[4];. ptr_bla wijst naar bla, oftewel *ptr_bla is een int[4]; Maar dat is hetzelfde als ptr_bla[0], en dat suggereert dat je ook ptr_bla[1] kunt doen (wat natuurlijk fout gaat, omdat het geen array van int[4] was, maar slechts een enkele int[4]), en dat is de volgende int[4] die na de eerste int[4] komen.

Ergo, new int[4000][5000] levert een int(*)[5000] op

[H!GHGuY]

ik snap pointers wel, ik was enkel ff aan het missen of het nou kon of niet
ik gebruik niet vaak multi-dimensionele arrays...

edit maar eigenlijk is het naast de kwestie aangezien hij C gebruikt en geen C++
dus hij zal malloc moeten gebruiken en zelf de juiste int selecteren
malloc(sizeof(int) * 4000 * 5000)
en dan Matrix[5000*i + j] aangezien de C compiler niet kan weten wat de grote van zijn array is ?

[ Voor 54% gewijzigd door H!GHGuY op 28-09-2005 17:53 ]

[Robbbert]

Probeer je arrays, net als de rest van je variabelen buiten main() te definïeren:

Zo dus WEL:

code:

#include<iets.h>

int array[1000][1000];

int main()
{
   array[457][568]=98;
   bla bla bla;
}

En zo dus NIET:

code:

#include<iets.h>

int main()
{
   int array[1000][1000];
   array[457][568]=98;
   bla bla bla;
}

[.oisyn]

HIGHGuY schreef op woensdag 28 september 2005 @ 17:51:
ik snap pointers wel, ik was enkel ff aan het missen of het nou kon of niet

Daar twijfelde ik niet aan, maar ik legde het even aan de hand van pointers uit

en dan Matrix[5000*i + j] aangezien de C compiler niet kan weten wat de grote van zijn array is ?

Lees mijn uitleg nog eens . Je geeft de dimensies mee aan het type, alleen de 'buitenste' kan variabel zijn:

C:

int (*Matrix)[1000] = (int(*)[1000])malloc(2000 * 1000 * sizeof(int));

De cast is in C dacht ik niet nodig maar heb ik erbij gezet ter verduidelijking

[H!GHGuY]

idd, dat frist het wat op...

met je neus in C# zitten is niet bevorderlijk voor het beetje C/C++ kennis dat ergens achterin de roestige schuur onder de spinnewebben zit

[Soultaker]

Merk ook op dat .oisyn daar een int[2000][1000] declareert (en dus geen int[1000][2000] ofzo.)

Een int[1][2][3] zou zoiets worden:

C:

int (*Matrix)[2][3] = (int(*)[2][3])malloc(1 * 2 * 3 * sizeof(int));

[ Voor 3% gewijzigd door Soultaker op 28-09-2005 21:16 ]

[.oisyn]

Robbbert schreef op woensdag 28 september 2005 @ 20:55:
Probeer je arrays, net als de rest van je variabelen buiten main() te definïeren:

Nee, alloceer ze, maak ze static (als het gaat om een locale var in een singlethreaded functie), maar maak ze niet global. Wat als je er nou meer dan 1 nodig hebt?

[PrinsEdje80]

Heb zelf dit probleem gehad, alleen dan bij C++. Zie hier voor hoe ik het opgelost heb uiteindelijk. Goed, ik geef toe, je zult zelf het moeten omschrijven naar malloc() etc, maar de for-loop blijft in principe hetzelfde...

[farlane]

AFhankelijk van wat je ermee wil is het wellicht duidelijker om een array van structs te maken

[ShadowLord]

Als je met datavelden van dit soort formaten gaat werken (5000*5000*4bytes is een kleine 100 Megabyte), kun je beter zelf een lap geheugen alloceren, maar NIET van de heap (wat de met malloc doet). De heap is bedoeld voor een hele hoop kleinere geheugen allocaties. BIj dit soort formaten heb je een erg grote kans dat malloc een error zal tergugeven omdat hij geen virj blok van dat formaat kan vinden. Het alloceren op de stack (door als 'vaste' var in je functie of global in je programma te zetten) is ook niet verstandig. Alhoewel het in principe zou moeten werken (zeker als je je initial stack size ophoogd) is het niet geweldig.

Bij dit soort formaten zul je je eigen geheugen moeten gaan reserveren en alloceren. Als het om een Windows app gaat raad ik je aan een boek over de Win32 API te kopen, of de MSDN een grondig door te spitten. Je kan dan namelijk tot 2GB (en on Win64 waarschijnijk veel meer) geheugen vrij gebruiken.

[H!GHGuY]

ShadowLord schreef op donderdag 29 september 2005 @ 20:37:
Als je met datavelden van dit soort formaten gaat werken (5000*5000*4bytes is een kleine 100 Megabyte), kun je beter zelf een lap geheugen alloceren, maar NIET van de heap (wat de met malloc doet). De heap is bedoeld voor een hele hoop kleinere geheugen allocaties. BIj dit soort formaten heb je een erg grote kans dat malloc een error zal tergugeven omdat hij geen virj blok van dat formaat kan vinden. Het alloceren op de stack (door als 'vaste' var in je functie of global in je programma te zetten) is ook niet verstandig. Alhoewel het in principe zou moeten werken (zeker als je je initial stack size ophoogd) is het niet geweldig.

Bij dit soort formaten zul je je eigen geheugen moeten gaan reserveren en alloceren. Als het om een Windows app gaat raad ik je aan een boek over de Win32 API te kopen, of de MSDN een grondig door te spitten. Je kan dan namelijk tot 2GB (en on Win64 waarschijnijk veel meer) geheugen vrij gebruiken.

als de windows memory manager geen aansluitend blok kan vinden van die grootte dan zal die ander geheugen doen aansluiten om zo 1 blok van 100MB vrij te maken (evt zelf virtueel geheugen)

bovendien is een malloc/free of new/delete een redelijk dure operatie, dus om veelvuldig kleine hoeveelheden geheugen te alloceren/dealloceren is het juist niet geschikt.

[.oisyn]

malloc/free wrappen onder NT direct naar de win32 heap functies, die zijn voor 100mb prima geschikt en die doen hun werk behoorlijk rap.

Voor datastructuren groter dan 1GB zou ik kijken naar memory mapped files

[Knakker]

Sorry dat ik niet meer heb gereageerd; ik ben te druk bezig geweest met mijn onderzoek.

Het doel van het programma is om de (praktische, niet theoretische) snelheid van wiskundige algoritmes te testen. Zodra de matrix eenmaal in het geheugen zit laat ik de algoritmes erop los; heb ik dat eenmaal gedaan, dan ben ik klaar en draai ik het programma nooit weer.

Een snellere en efficientere manier om de matrix in het geheugen te plaatsen is, anders dan vanuit didactisch oogpunt, voor mijn onderzoek gewoonweg niet nodig.

De optie met de for-loops en malloc werkt feilloos; heb al zonder problemen een matrix van 10000x10000 ingeladen (slordige 400 mb denk ik?). Erg bedankt voor jullie uitgebreide reacties; het was in dienst van de wetenschap

[H!GHGuY]

de optie met for-loops en malloc is wel trager. niet alleen tijdens de allocatie maar ook tijdens het gebruik.

wanneer je malloc gebruikt met for-loops dan krijg je bij 1 geheugentoegang dit scenario veronderstellend dat het geheugenadres van je array in een register zit:
1) fetch array+i => rij
2) fetch rij + j => value
dit zijn 2 geheugen-reads. rekenend met het feit dat jij 10000x10000 arrays gebruikt, kan dit wel eens lijden tot hogere latencies voor geheugentoegang.
(prefetch algo's niet meegerekend)

wanneer je de andere oplossing gebruikt gebeurt dit
1) fetch array + i*aantal_rijen + j => value
dit is slechts 1 geheugen-read. wanneer je veel in je array werkt, en niet zoveel bewerkingen doet, denk ik dat je een behoorlijke verbetering kan hebben wanneer je deze laatste methode toepast!!

en dit allemaal in de naam van de wetenschap

[MSalters]

HIGHGuY schreef op zondag 02 oktober 2005 @ 15:48:
de optie met for-loops en malloc is wel trager. niet alleen tijdens de allocatie maar ook tijdens het gebruik

Nee, onzin. bytes zijn bytes en hoe C ze noemt maakt voor de processor niet uit.

wanneer je malloc gebruikt met for-loops dan krijg je bij 1 geheugentoegang dit scenario veronderstellend dat het geheugenadres van je array in een register zit:
1) fetch array+i => rij
2) fetch rij + j => value
dit zijn 2 geheugen-reads.

Heb je wel eens de assembly bekeken? Ten eerste doe je geen rij fetch maar een address calculation (in registers), waarna precies 1 element geladen wordt. Ten tweede is dat zo'n gangbare operatie dat vell processoren waaronder de x86 daar directe support. Ten derde wordt de berekening van de buitenste loop (indien niet gratis) gehoist.

[H!GHGuY]

MSalters schreef op zondag 02 oktober 2005 @ 17:54:
[...]
Nee, onzin. bytes zijn bytes en hoe C ze noemt maakt voor de processor niet uit.
[...]
Heb je wel eens de assembly bekeken? Ten eerste doe je geen rij fetch maar een address calculation (in registers), waarna precies 1 element geladen wordt. Ten tweede is dat zo'n gangbare operatie dat vell processoren waaronder de x86 daar directe support. Ten derde wordt de berekening van de buitenste loop (indien niet gratis) gehoist.

ik heb het over deze code

C:

int** array = (int**)malloc(1000*sizeof(int*))
for (int i = 0; i < 1000; i++)
   array[i] = (int*)malloc(1000*sizeof(int))

tegenover

C:

int (*array)[1000] = (int(*)[1000])malloc(1000 * 1000 * sizeof(int));

in het eerste geval weet de compiler niets over het array, behalve dat het een verwijzing naar een tabel van pointers is. het kon evengoed een driehoekvormige tabel zijn.
bovendien zijn alle waarden apart ge'malloc'd waardoor het stukken in het geheugen kunnen zijn die ver uiteen liggen of niet eens in volgorde liggen van allocatie.

in het tweede geval weet de compiler dat het een verwijzing is naar een tabel pointers die elk verwijzen naar een tabel ints van 1000 lang.
bovendien is het geheugen in 1 keer gealloceerd en liggen alle waarden bijeen.

in het eerste geval zal je bij een geheugen allocatie dus eerst de pointer ophalen in de pointertabel en daarop dan opnieuw gaan indexeren. in het tweede geval weet de compiler waarmee hij werkt en dal hij in 1 keer de indexering kunnen doen. bovendien werk je slechts met 1 basisadres.

dat is wat ik bedoelde