Speicherverbrauch: Nested Struct oder interne Pointer?

[Nirvash]

Hallo Zusammen!

mich würde mal interessieren was vom Speicherbedarf her sinnvoller ist:
Verschachtelte Strukturen oder diese Datenstruktur mithilfe von Pointern in den einzelnen Structs zu definieren?

Um das ganze etwas klarer zu machen:
Ich habe folgende Datenstruktur:

struct token_stream{

  struct element{
    char type; 
    unsigned int line; 

    struct _token {
      char t; 
    }token; 

    struct _number {
      int n;
      unsigned int ID; 
    }number; 

    struct _word {
      unsigned int ID; 
      char w[MAX_LENGTH]; 
    }word; 

  }element; 

  token_stream *next; 
  token_stream *previous; 
};

Dieses Objekt verbraucht 72 Byte an Speicher und innerhalb des element structs wird immer nur eines der drei structs mit Daten erfüllt. Sogesehen wird Speicherplatz verschwendet.
Nun war ich am überlegen, ob es an dieser Stelle nicht sinnvoller wäre ungefähr folgendes zu machen, um somit den Speicherverbrauch zu verringern:

struct token {
  char t; 
}; 

struct number {
  int n;
  unsigned int ID; 
}; 

struct word {
  unsigned int ID; 
  char w[MAX_LENGTH]; 
}; 

struct element{
  char type; 
  unsigned int line;

  token *token_ptr;
  number *number_ptr;
  word *word_ptr;    
}; 

struct token_stream{    
  element *element_ptr;

  token_stream *next; 
  token_stream *previous; 
};

Die zweite Variante ist natürlich in der Erzeugung und Speicherreservierung sowie -Freigabe wesentlich komplizierter.

Gruß,
Nirvash

[volkard]

würde da nicht das Schlüsselwort union genau passend sein?

[Nirvash]

volkard schrieb:

würde da nicht das Schlüsselwort union genau passend sein?

Mit union habe ich es schon probiert, jedoch ganz seltsame Ergebnisse erhalten. Aus irgendeinem Grund haben sich einige Speicherbereiche überlagert. Ich erzeuge eine Liste in der ich einzelne Token speichere. Das union führte dann dazu, dass einige Variablen-Inhalte des letzten Elements in das nachfolgende hineinreichten. Dies hat mich dazu veranlasst die drei Elemente voneinander zu trennen.

[volkard]

union saubere machen, das ist der Weg, denke ich. Das muss klappen. Ausweichen ist keine Lösung. Damit machste den Fehler nur *deutlich* seltener.
Aber auch *deutlich* unfindbarer. Hast ja am Ende nix davon, wenn die Anwendung nur alle vier Wochen mal abkackt. Das ist der Super-Gau für Dich, weil Du den Fehler nicht selber jagen kannst, sonder Dich nur die Kunden anrufen "zu Hülfää, meine Daten sind kaputt." und Du den Fehler natürlich nicht nachvollziehen kannst.
Sei hart gegen Dich. Mach es so, daß jeder kleinste Fehler bei Dir auf dem Schreibtisch passiert. Das macht glückliche Kunden.

Ich musste mal eine Software debuggen, deren erster Fehler (einfach so im Code gesehen nach 5 Minuten anschauen) so war, daß ich rechnerisch abschätzen konnte, daß er bei Rund-Um-Die-Uhr-Betrieb ca alle 40 Tage einmal kommt. Happy Debugging! Da helfen die Meldungen von den Benutzer nichts. Zu selten. Aber doch zu oft. Sowas mag ich nicht abgeben.

[Nirvash]

Ok, dann werde ich das mit dem union nochmal versuchen sauberer zu gestalten. Danke dir!

[volkard]

Nirvash schrieb:

Ok, dann werde ich das mit dem union nochmal versuchen sauberer zu gestalten. Danke dir!

Bist Du an C gebunden?
Kannst Du C++ lernen und in C++ forschen und die Ergebnisse wieder runter nach C tun? Das könnte bei komplexeren Aufgaben gut sein. (Hab untertrieben, es ist der Götterhammer; langfristig ein MUSS, um sehr gut in C zu werden.)

Abgesehen davon, zeig mal Dein Typlayout mit union.
Ich höre der Nachtigall tapsen, daß Du den type geuniont hast. Haste bestimmt nicht, aber nur mal zur Sicherheit.

[Nirvash]

volkard schrieb:

Abgesehen davon, zeig mal Dein Typlayout mit union.
Ich höre der Nachtigall tapsen, daß Du den type geuniont hast. Haste bestimmt nicht, aber nur mal zur Sicherheit.

Gebunden bin ich nicht an C, jedoch reizt mich diese Sprache sehr.

Hier mal mein Typ mit union:

struct _token_stream{

  union _element{
    char type; 
    unsigned int line;

    struct _token {
      char t; 
    }token; 

    struct _number {
      int n; 
      unsigned int ID;
    }number; 

    struct _word {
      unsigned int ID; 
      char w[MAX_LENGTH]; 
    }word; 

  }element; 

  token_stream *next; 
  token_stream *previous; 
};

Über char type will ich den union eindeutig identifizierbar machen.

[volkard]

Über char type will ich den union eindeutig identifizierbar machen.

Dann raus aus der union. line auch, nehme ich an.

struct _token_stream{
  char type; 
  unsigned int line;
  union _element{
    struct _token {
      char t; 
    }token; 

    struct _number {
      int n; 
      unsigned int ID;
    }number; 

    struct _word {
      unsigned int ID; 
      char w[MAX_LENGTH]; 
    }word; 

  }element; 

  token_stream *next; 
  token_stream *previous; 
};

[Nirvash]

volkard schrieb:

Dann raus aus der union. line auch, nehme ich an.

Gnargh, Denkfehler. Vielen Dank, jetzt läufts

[volkard]

Nirvash schrieb:

Gebunden bin ich nicht an C, jedoch reizt mich diese Sprache sehr.

Mich auch!!!

C++ ist wie C auf Extasy. Als Programmierer darf man offiziell sogar süchtigmachende Programmiersprachen konsumieren, ohne mit dem Gesetz in Konflikt zu geraten. Viele Programmierer erliegen der Droge und schnüffeln sich dermaßen viel davon rein, daß sie wie ein auf dem Buckel liegender Marienkäfer wild mit den Ärmchen wackeln, aber nichts mehr zustande bringen (Haha, Haskell!). Das ist mir vielleicht auch ein paar Jährchen passiert. Aber damals wußte noch keiner, wie gefährlich das ist. Die Schlimmen Sachen habe ich hinter mir und bin im Nachhinein wirklich sicher, daß ich davon soo viel gelernt habe, daß ich den Weg jedem empfehle. Naja, ich nahm, nur Lisp, Prolog, Basic, ASM, Pascal, C#, VB, Java, Forth und ein Dutzent andere weiche Drogen. (Ok, Forth und Lisp und C(==ASM-Makrocompiler) lassen einen niemals wieder ganz los, nimmermehr.)
Was kann schon schlimmstenfalls passieren? Eine C++-Tröte werden? Ok, bessere Einstellungschancen als jemand, der "nur" C kann.

Optimal Du wirst nicht süchtig, dann biste auf beiden welten Überdurchschnittlich. C braucht mehr OO, C++ braucht mehr Bescheidenheit.

[Nirvash]

volkard schrieb:

Mich auch!!!

C++ ist wie C auf Extasy. Als Programmierer darf man offiziell sogar süchtigmachende Programmiersprachen konsumieren. Viele Programmierer erliegen der Droge und schnüffeln sich dermaßen viel davon rein, daß sie wie ein auf dem Buckel liegender Marienkäfer wild mit den ärmchen wackeln, aber nichts mehr zusatnde bringen. Ist mir vielleicht auch ein paar Jährchen passiert. Aber damals wußte noch keiner, wie gefährlich das ist. Die Schlimmen Sachen habe ich hinter mir und bin im Nachhinein wirklich sicher, daß ich davon soo viel gelernt habe, daß ich den Weg jedem empfehle.
Was kann schon schlimmstenfalls passieren? Eine C++-Tröte werden? Ok, bessere Einstellungschancen als jemand, der "nur" C kann.

Optimal DU wirst nicht süchtig, dann biste auf beiden welten Überdurchschnittlich. C braucht mehr OO, C++ braucht mehr Bescheidenheit.

Ok, dem entnehme ich, dass ich meine C++ Kenntnisse aus der Berufsschule wieder auffrischen sollte Sobald ich mit dem C Projekt fertig bin, werde ich mich dann mal ransetzen und es in C++ nachbauen, evnetuell kann ich danach ja dann das C Programm verbessern.

[volkard]

Genau.
Beispiel: http://www.c-plusplus.net/forum/314445
Nehme er doch einfach eine std::unordered_map und der Käse wäre gegessen.
Fertig. O(1) und offensichtlich asymptotisch optimal.
Ok, er hat kein C++. Dann baue er sowas ähnliches nach.
Sogar mit mehr Performance für seine Anwendung, weil die C++-Klassen so Allerweltsklassen sind, die irgendwie nie was halbes und nix Ganzes sind, sondern so allgemein für alle denkbaren Anwendungen ziemlich gut sind und für keine konkrete Anwendung optimal.
Als C++-Opfer wäre ihm die std::unordered_map ein geläufiger Begriff und er müßte nur noch rausgoogeln, wie das geht.

[Nirvash]

volkard schrieb:

Ok, er hat kein C++. Dann baue er sowas ähnliches nach.
Sogar mit mehr Performance für seine Anwendung, weil die C++-Klassen so Allerweltsklassen sind, die irgendwie nie was halbes und nix Ganzes sind, sondern so allgemein für alle denkbaren Anwendungen ziemlich gut sind und für keine konkrete Anwendung optimal.

Genau aus dem Grund mag ich so sehr C. Ich muss zugeben, ich arbeite erst seid kurzem mit der Sprache und mein Code hat garantiert an vielen Stellen noch Optimierungsbedarf, da mir die Feinheiten der Sprache noch nicht so geläufig sind. Dennoch mag ich es sehr, mich um vieles selber kümmern zu müssen und nicht auf irgendwelche Funktionen oder Klassen zurückzugreifen, mit denen ich alles mögliche zwar machen kann, doch dafür dann die Laufzeit oder der Speicherverbrauch darunter leiden muss.

[Nathan]

Die Laufzeit oder der Speicherverbrauch leidet darunter nicht!
Als Anfänger sind die C++ STL-Container wesentlich besser, als eigene, selbst zusammengebastelte Container (meistesn lineare Listen, obwohl andere Container u.U. besser sind).
Klar, wenn man C komplett beherrscht, kann es sein, dass eigene Container besser sind, weil die dann wirklich nur die Funktionalität bieten, die man wirklich braucht und nicht so überladen sind wie die STL-Container (wenn man die Größe nie abfragen will, muss man auch nicht dafür den Speicherplatz verschwenden sie zu speichern).
Dafür sind die STL-Container wesentlich generischer als C-Container. Dort nutzt man oft immer den gleichen Code.
Und ehe ich hier jetzt angeschnauzt werde: Auch ich habe zuerst C gelernt. Als ich dann zu C++ wechselte, kam ich mir vor, als hätte ich in meinem Lieblingsspiel gecheatet... Aber mit der Zeit lernt man so etwas zu schätzen.

[TyRoXx]

volkard schrieb:

Ok, er hat kein C++. Dann baue er sowas ähnliches nach.
Sogar mit mehr Performance für seine Anwendung, weil die C++-Klassen so Allerweltsklassen sind, die irgendwie nie was halbes und nix Ganzes sind, sondern so allgemein für alle denkbaren Anwendungen ziemlich gut sind und für keine konkrete Anwendung optimal.

Warum soll eine unordered_map denn nicht optimal sein?

[volkard]

TyRoXx schrieb:

volkard schrieb:

Ok, er hat kein C++. Dann baue er sowas ähnliches nach.
Sogar mit mehr Performance für seine Anwendung, weil die C++-Klassen so Allerweltsklassen sind, die irgendwie nie was halbes und nix Ganzes sind, sondern so allgemein für alle denkbaren Anwendungen ziemlich gut sind und für keine konkrete Anwendung optimal.

Warum soll eine unordered_map denn nicht optimal sein?

Weil sie üblicherweise eine Hashtable ist, die Ankerpunkte auf einfach verkettet Listen gibt. Also Verkettung in relativ teurem Überlaufbereich. Je nach dem kann es deutlich billiger sein, im Hauptbereich zu verketten, double hashing zu verwenden, eine cuchoo-hashtable, eine dynamische wachsende oder (gerade bei strings!) doch einen Baum.

[It0101]

volkard schrieb:

Sogar mit mehr Performance für seine Anwendung, weil die C++-Klassen so Allerweltsklassen sind, die irgendwie nie was halbes und nix Ganzes sind, sondern so allgemein für alle denkbaren Anwendungen ziemlich gut sind und für keine konkrete Anwendung optimal.

Wow! Volkard! Kannst du diese Aussage bitte in der C++-Sparte verbreiten.
Ich hab durchaus den Eindruck, dass dieses Wissen dort noch nicht komplett durch die "geheiligt seie dein Name, oh STL"-Mentalität durchgedrungen ist...

[It0101]

Nathan schrieb:

Dafür sind die STL-Container wesentlich generischer als C-Container. Dort nutzt man oft immer den gleichen Code.
Und ehe ich hier jetzt angeschnauzt werde: Auch ich habe zuerst C gelernt. Als ich dann zu C++ wechselte, kam ich mir vor, als hätte ich in meinem Lieblingsspiel gecheatet... Aber mit der Zeit lernt man so etwas zu schätzen.

Wenn man aber um das letzte Prozentchen Performance kämpft, dann kann ein selbstgebauter Container, immer vorausgsetzt man weiß was man tut, durchaus helfen. Denn die STL ist eben, wie du schon sagst, für flexible möglichst breite Nutzung ausgelegt.
Das erinnert mich an den Thread zu STL-Strings, wo doch tatsächlich jemand überrascht war, dass die in der Verkettung spürbar langsamer sind als reine char*-Buffer.

Erkenntnis: Selber denken lohnt sich manchmal