kostenloser Webspace werbefrei: lima-city

C++: Verständnis: Merken sich Zeiger ihre Größe?

lima-city → Forum → Programmiersprachen → C/C++ und D

1. «
2. 1
3. 2

1. bladehunter

   

   bladehunter hat kostenlosen Webspace.

   12:40, 6.3.2009

   merovius schrieb:
   Die Speicherung der "Freiheit" von Speicher lässt sich auch mit einer einfachen binären Abbildung implementieren, sprich, es existiert ein Speicherbereich in dem jedem Speicherblock eine 0 oder eine 1 zugewiesen ist, ob er vergeben ist oder nicht. Aus so einer Abbildung lässt sich allerdings nicht rekonstruieren, welche dieser Blöcke gemeinsam allokiert wurden udn welche nicht, ergo, welche Blöcke gemeinsam freigegeben werden müssen und welche nicht.
   

   
   Richtig, das ist eine Möglichkeit, wie man das machen kann. Und wie du bereits erwähnt hast, ist es eine sehr ineffiziente und problematische Möglichkeit.
   Ich weiß selber nicht, wie das ganze konkret realisiert wird, aber ich vermute einfach, dass man einen binären Baum benutzt, um die vergebenen Speicherblöcke wiederzufinden. In den Blättern des Baumes kann dann problemlos ein Wert gespeichert sein, der angibt, wie lang der Speicherblock ist und die inneren Knoten des Baumes sind dann die Adressbereiche der Kinderknoten des Teilbaums.
   Somit könnte man innerhalb von logarithmischer Zeit den entsprechenden Speicher wieder freigeben. Pro vergebener Speicherblock würde man dann nur z.B. 4 Byte (auf einer 32 Bit Maschine) vergeben werden, die dann speichern, wie lang der allokierte Block ist(*).
   Also ist das alles kein Problem mit der Realisierung. Aber wie gesagt. Das ist jetzt nur eine erste Idee, wie ich das lösen würde. Es durchaus denkbar, dass man einen anderen Algorithmus und andere Datenstrukturen dafür verwendet.
   
   (*) Der Baum verbraucht natürlich auch noch Speicher.
   
   Beitrag zuletzt geändert: 6.3.2009 12:52:18 von bladehunter

2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

3. c*****s

   14:56, 6.3.2009

   Solang es also wirklich so eine Tabelle gibt, wie ich sagte, dann bin ich auch zufrieden. Die Idee ist mir ehrlich gesagt auch erst gekommen, als ich sie aufgeschrieben hab. Dennoch erscheint mir das ineffizient... Ich mein, für die reine Tabelle "belegt oder nicht" geht ja schon plusminus ein Achtel des Speichers drauf (wenn man davon ausgeht, dass pro Byte ein Bit verwendet wird). Dazu dann noch die Tabelle für zusammenhängende Speicherblöcke, die auch recht teuer werden dürfte (bis zu 8 Byte pro zusammenhängenden Block)...

   Ich spekuliere jetzt mal, dass sich die Tabelle nicht merkt:
   Speicheradresse 3A45821 = frei 3A45822 = belegt 3A45823 = belegt ... 3A45850 = belegt 3A45851 = frei
   
   sondern es in der Form
   ---frei---3A45822---belegt---3A45851---frei---3A45890---belegt---
   speichert.
   Ob das nun in einem Baum oder linear gespeichert wird, ist nur für die Geschwindigkeit relevant.
   
   In den meisten Fällen wirst du doch nicht tausend kleine Objekte auf dem Heap erzeugen und die Referenzen irgendwo speichern, sondern gleich einen ganzen Array von Objekten anlegen...
   
   Ich denke durch dieses Beispiel wird es klar:
   

   #include <iostream.h>
   
   int main(int argc, char *argv[])
   {
   int i;
   int n = 10000000;
   int * * a = new int * [n];
   
   for(i=0;i<n;i++){
   a[i] = new int(i);        
   }
   
   /*for(i=0;i<n;i++){
   cout << (* (a[i])) << "\n";
   }*/
   
   system("PAUSE");
   }

   dieses Programm belegt 190 MB Speicher. Eigentlich haben wir nur ein Array von int-Pointern der Größe 10.000.000 erzeugt (das macht 40 MB) und 10.000.000 mal ein int-Objekt auf dem Heap erzeugt (das macht noch mal 40 MB), also insgesamt 80 MB... aber wir haben eben den Speicherbedarf für Speicherverwaltung künstlich in die Höhe geschraubt.
   
   Dieser Code macht genau das gleiche (10 Millionen ints und ein Array mit Pointern auf diese ints) :

   #include <iostream.h>
   
   int main(int argc, char *argv[])
   {
   int i;
   int n = 10000000;
   int * * a = new int * [n];
   int * b = new int[n]; 
   
   for(i=0;i<n;i++){
   b[i] = i;
   }
   
   for(i=0;i<n;i++){
   a[i] = b + i;
   }
   
   /*for(i=0;i<n;i++){
   cout << (* (a[i])) << "\n";
   }*/
   
   system("PAUSE");
   }

   nur werden die int-Objekte als Array allokiert und nicht einzeln und, siehe da, das Programm belegt die erwarteten 80 MB (und läuft auch schneller).
   
   Beitrag zuletzt geändert: 6.3.2009 14:58:10 von caiexus

4. m******s

   19:26, 6.3.2009

   @caiexus:
   
   Das ist sehr überzeugend, danke ;)
   
   Aber immernoch, wenn jemand ne Quelle hat, bin ich noch zufriedener ;) Aber ist jetzt nicht mehr so wichtig ;)

5. c*****s

   10:28, 7.3.2009

   Aber immernoch, wenn jemand ne Quelle hat, bin ich noch zufriedener ;) Aber ist jetzt nicht mehr so wichtig ;)

   Irgendwie ist es schwer was dazu zu finden. Die Manpage von FreeBSD erzählt einem ein klein wenig, wie das implementiert ist.

6. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

1. «
2. 1
3. 2

Dir gefällt dieses Thema?