So vermeiden Sie Speicherverschwendung bei 64-Bit-Zeigern ⇐ C++

[Anonymous]

Ich hoffe auf ein paar fundierte Ratschläge, wie ich an einen Entwurf herangehen soll, den ich gerade in Angriff nehme.

Die unkomplizierte Herangehensweise an mein Problem wird zu Abermillionen von Hinweisen führen. Auf einem 64-Bit-System handelt es sich vermutlich um 64-Bit-Zeiger. Aber was meine Anwendung betrifft, glaube ich nicht, dass ich mehr als einen 32-Bit-Adressraum benötige. Ich möchte jedoch immer noch, dass das System die Vorteile der 64-Bit-Prozessorarithmetik nutzt (vorausgesetzt, dass ich das bekomme, wenn ich auf einem 64-Bit-System laufe).

Weiterer Hintergrund

Ich implementieren eine baumartige Datenstruktur, in der jeder „Knoten“ eine 8-Byte-Nutzlast enthält, aber auch Zeiger auf vier benachbarte Knoten benötigt (übergeordneter, linkes Kind, mittleres Kind, rechtes Kind). Auf einem 64-Bit-System mit 64-Bit-Zeigern sind dies 32 Byte allein für die Verknüpfung einer 8-Byte-Nutzlast mit dem Baum – ein „Verknüpfungsaufwand“ von 400 %.

Die Datenstruktur wird Millionen dieser Knoten enthalten, aber meine Anwendung wird darüber hinaus nicht viel Speicher benötigen, sodass all diese 64-Bit-Zeiger verschwenderisch erscheinen. Was zu tun? Gibt es eine Möglichkeit, 32-Bit-Zeiger auf einem 64-Bit-System zu verwenden?

Ich habe darüber nachgedacht

• Die Nutzlasten in einem Array so zu speichern, dass ein Index eine „Baumadresse“ impliziert (und durch diese impliziert wird) und Nachbarn eines bestimmten Index mit einfacher Arithmetik für diesen Index berechnet werden können. Leider muss ich die Größe des Arrays entsprechend der maximalen Tiefe des Baums anpassen, die ich vorher nicht kenne, und es würde wahrscheinlich noch mehr Speicheraufwand aufgrund leerer Knotenelemente in den unteren Ebenen verursachen, da nicht alle Zweige des Baums in die gleiche Tiefe reichen.
• Speichern von Knoten in einem Array, das groß genug ist, um sie alle aufzunehmen, und dann Verwenden von Indizes anstelle von Zeigern, um Nachbarn zu verknüpfen. AFAIK, der Hauptnachteil wäre hier, dass jeder Knoten die Basisadresse des Arrays benötigen würde, um seine Nachbarn zu finden. Sie müssen es also entweder speichern (eine Million Mal) oder es muss bei jedem Funktionsaufruf weitergegeben werden. Das gefällt mir nicht.
• Angenommen, dass die höchstwertigen 32 Bits aller dieser Zeiger Null sind, wird eine Ausnahme ausgelöst, wenn dies nicht der Fall ist, und nur die niedrigstwertigen 32 Bits gespeichert. So kann der benötigte Zeiger bei Bedarf rekonstruiert werden. Das System wird wahrscheinlich mehr als 4 GB verbrauchen, der Prozess wird dies jedoch nie tun. Ich gehe nur davon aus, dass Zeiger von einer Prozessbasisadresse versetzt sind, und habe keine Ahnung, wie sicher (wenn überhaupt) dies auf den gängigen Plattformen (Windows, Linux, OSX) wäre.
• Speichern des Unterschieds zwischen 64-Bit-diesem und dem 64-Bit-Zeiger auf den Nachbarn, vorausgesetzt, dass dieser Unterschied im Bereich von liegt int32_t (und werfen, wenn dies nicht der Fall ist). Dann kann jeder Knoten seine Nachbarn finden, indem er diesen Offset dazu hinzufügt.

Irgendwelche Ratschläge? Kann ich in Bezug auf die letzte Idee (die meiner Meinung nach derzeit mein bester Kandidat ist) davon ausgehen, dass in einem Prozess, der weniger als 2 GB verbraucht, dynamisch zugewiesene Objekte innerhalb von 2 GB voneinander liegen? Oder gar nicht unbedingt?