Hoe werken arrays in memory?

[ONiel]

Hi

Dus, je kan uit een array elementen opvragen via de index, je microprocessor weet wat het moet opvragen omdat het adres van het eerste element opgeslagen is.

Dus e.g:

code:

int foo[5] = {
5,   => 0x0000
8,
455,
7,
786468
};

De lengte van een integer (er vanuit gaand dat de microprocessor de 64-bit architectuur hanteert) is 8 bytes.
Dus simplistisch gezegd (en als ik correct ben), zou het tweede element adres 0x0008 zijn, en het derde 0x0010,...

Toch heb ik hier enkele vragen bij,
als enkel het eerste adres opgeslagen wordt en de rest op dat adres gecalculeerd wordt, waar wordt dat adres opgeslagen dan? In hetzelfde memory block als het eerste element in de array? Elk element wordt toch in een aparte memory block opgeslagen, toch?

En wat, als de array geinitaliseerd is, daarna nog enkele variabelen zijn gedefinieerd, en de programmeur daarna een element aan de array toevoegt (via vector bijvoorbeeld), die adressen zullen mekaar toch nooit niet mooi opvolgen?

e.g:

code:

int foo[8] = {
5,   => 0x0000
8,
455,
7,
786468
};

int bar = 4568; // => 0x0020
foo.push_back(745); // => 0x001c  (Pseudo-code)

/*
Current values:
int foo[6] = {
5,   => 0x0000
8,
455,
7,
786468,
745
};
*/

cout << foo[5];
/*
zou 0x0020 opvragen, wat 4568 zou zijn. Want het eerste element heeft 0x0000:
<=> (gevraagdeIndex) * aantalBytes = 40 == 0x001c
*/

Dus, hoe werken arrays of collecties nu precies in relatie met de microprocessor en het geheugen? Ik heb
al opzoekwerk gedaan en gelezen (en geleerd natuurlijk), alleen de bovenste twee vragen vindt ik maar niet.

Bedankt!

[nIghtorius]

zover ik weet is foo een pointer die wijst waar de array begint.

ik doe het 32-bits (dus 4 bytes)

b.v.

int foo[4]= {1, 2, 3, 4}; <-- dit reserveert 4x 4 bytes geheugen en vult dit op met 1, 2, 3 en 4 als waarden. en foo krijgt het adres van dat structuur, foo is in wezen een pointer die wijst naar een stuk voor-geïnitialiseerd geheugen.

foo kan b.v. zijn: 0x00FCABCD <- de pointer die wijst naar het structuur van de array.
dus foo[0] geeft de waarde op die opgeslagen is op 0x00FCABCD
en foo[1] (32-bits, 4 byte) geeft de waarde op die opgeslagen is op 0x00FCABD1
en foo[2] 0x00FCABD5 en foo[3] 0x00FCABDA

in C is foo dus gewoon letterlijk een pointer, niet meer.
dus arrays in C zijn in wezen gewoon pointers.


bewijslast

C:

// testuh.
#include "stdafx.h"
#include <stdio.h>
#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "testen arrays" << endl;

    int a[4] = { 1, 2, 3, 4 };
    int *b = a;

    cout << hex << "Pointer adres voor a is " << a << endl;
    cout << hex << "Pointer b wijst naar a dus " << b << endl;
    cout << hex << "Index #0 = " << a[0] << ", pointer index #0" << &a[0] << endl;
    cout << hex << "Index #1 = " << a[1] << ", pointer index #1" << &a[1] << endl;
    cout << hex << "verschil is (32-bits, verwacht 4 byte): " << (int(&a[1]) - int(&a[0])) << endl << endl;

    cout << hex << "voor de grap b[3]: " << b[3] << endl;
    // yup b[3] = 4, zelfde is a[3], klopt b point naar a. Dit bewijst dat arrays gewoon ordinaire pointers zijn.

    int q;
    cin >> q;
    return 0;
}

[ Voor 7% gewijzigd door nIghtorius op 11-12-2015 23:18 ]

[Creepy]

En wat, als de array geinitaliseerd is, daarna nog enkele variabelen zijn gedefinieerd, en de programmeur daarna een element aan de array toevoegt (via vector bijvoorbeeld), die adressen zullen mekaar toch nooit niet mooi opvolgen?

Een array is geen Vector. Een gewone array kan je niet vergroten, dan wordt er een nieuwe array op een nieuwe plek in het geheugen gemaakt en de oude data gekopieerd. Had je bijv gezocht op hoe een Vector werkt dan had je bijv dit gevonden via Google:

http://www.cplusplus.com/reference/vector/vector/
Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity (see push_back).

Met alle respect natuurlijk, maar je zegt wel dat je hebt gezocht, maar op wat dan precies? Met welke zoekmachine? Wat waren dan je resultaten? En waarom krijg ik wel de gelinkte pagina als hit 1 op Google?

[ Voor 6% gewijzigd door Creepy op 11-12-2015 23:22 ]

[NMe]

ONiel schreef op vrijdag 11 december 2015 @ 22:55:
Dus, hoe werken arrays of collecties nu precies in relatie met de microprocessor en het geheugen?

Dat hangt maar net van de taal af. PHP kent bijvoorbeeld geen "echte" arrays en het zou me niks verbazen als dat effect heeft op het geheugen.

De meeste talen die ik ken slaan arrays in het geheugen op als één grote opeenvolgende rits. Als je een array van 8-bits integers (chars) maakt van 3 tekens lang met daarin opeenvolgend de waardes 255, 10 en 16, dan ziet dat in je geheugen bijvoorbeeld uit als 111111110000101000010000.

Wat me wel een beetje verbaast is dat je zegt dit niet te kunnen vinden. Er zijn echt boeken vol geschreven over memory management en korte papers zoals deze die het heel basaal uitleggen liggen voor het oprapen.

[nIghtorius]

als je een vector maakt van b.v. 4 elementen. Dan word er ruimte gemaakt voor b.v.: 8 elementen. (dit kan per implementatie verschillen).

als je een push_back doet komt het er gewoon bij. Maar als je de >8 elementen gaat dan moet het worden gereallocate. Dus krijg je een ruimte voor 16 elementen en de huidige 8 elementen worden ernaar toe gekopieerd en de 9de geplaatst. <-- dit is een kostbare operatie. vooral bij enorm grote verzamelingen(collections)

[ONiel]

Hartelijk bedankt allemaal! Ik snap het nu helemaal.

En ik had gezocht via Startpage, op DreamInCode en cplusplus.com.
Misschien had ik inderdaad ook op 'vector' moeten zoeken, i.p.v enkel 'array' en 'memory allocation'.

[ZpAz]

ONiel schreef op vrijdag 11 december 2015 @ 23:56:
Hartelijk bedankt allemaal! Ik snap het nu helemaal.

En ik had gezocht via Startpage, op DreamInCode en cplusplus.com.
Misschien had ik inderdaad ook op 'vector' moeten zoeken, i.p.v enkel 'array' en 'memory allocation'.

Je had letterlijk je vraag in Google kunnen stoppen.

[jeroen3]

Soms kan je array ook meer geheugen alloceren dan daadwerkelijk wordt gebruikt.
Zoek eens naar Memory Alignment en Unaligned Access.

[MSalters]

jeroen3 schreef op zaterdag 12 december 2015 @ 13:02:
Soms kan je array ook meer geheugen alloceren dan daadwerkelijk wordt gebruikt.
Zoek eens naar Memory Alignment en Unaligned Access.

Die zoektermen hebben geen verband met je eerste zin, of de vraag van de TS.

[MSalters]

ONiel schreef op vrijdag 11 december 2015 @ 22:55:
als enkel het eerste adres opgeslagen wordt en de rest op dat adres gecalculeerd wordt, waar wordt dat adres opgeslagen dan?

Het adres wordt normaal gesproken* opgeslagen in alle instructies die de array gebruiken. Soms is het een relatief adres (array op de stack), some een absoluut adres (globals).

* Sommige obscure CPU's kunnen geen pointers in de instructies opslaan. Gangbaar is dan om een verborgen array met pointers te hebben, en in de code alleen een index in deze tabel. Dit regelt de compiler voor je, tenzij je in die obscure assemblytaal programmeert.