Optimale Verwendung von malloc und realloc für dynamische Speicherung

Question

Ich versuche herauszufinden, wie man malloc und realloc am besten nutzt, um unbekannte Mengen von Zeichen vom Benutzer zu empfangen, sie zu speichern und sie erst am Ende zu drucken .

Ich habe festgestellt, dass die Berufung Realloc zu oft nicht so schlau sein wird. so zuteile ich jedes Mal eine bestimmte Menge an Speicherplatz, sagen wir sizeof char * 100 und am Ende der Datei, verwende ich Realloc, um die Größe des Ganzen genau zu passen.

Was denken Sie, ist das ein guter Weg? würden Sie auf einem anderen Weg gehen?

Bitte beachten Sie, ich habe nicht die Absicht, verkettete Listen, getchar(), putchar() zu verwenden. mit malloc und Realloc ist nur ein Muss.

Answer 1

Wenn Sie die Zuweisung auf die genaue Datenmenge zurücksetzen, optimieren Sie den Speicherverbrauch. Dies wird wahrscheinlich langsameren Code ergeben, weil 1) Sie zusätzliche Realloc-Aufrufe erhalten und 2) Sie möglicherweise keine Beträge zuweisen, die gut zu CPU-Ausrichtung und Daten-Cache passen. Möglicherweise führt dies auch zu Problemen bei der Heap-Segmentierung aufgrund der wiederholten Realloks, in welchem ​​Fall tatsächlich Speicher verloren gehen könnte.

Es ist schwer zu beantworten, was „beste“ generisch, aber die folgenden Verfahren sind ziemlich verbreitet, da es zwischen Verringerung der Ausführungsgeschwindigkeit für realloc Anrufe und Senken Speichernutzung ist ein guter Kompromiss:

Sie ordnen ein Segment, dann Verfolgen Sie, wie viel von diesem Segment Benutzerdaten sind. Es ist eine gute Idee, size_t mempool_size = n * _Alignof(int); Bytes zuzuordnen, und es ist wahrscheinlich auch ratsam, eine n zu verwenden, die von 8.

Jedes Mal, wenn Sie in diesem Segment laufen aus freien Speicher teilbar ist, können Sie realloc zu mempool_size*2 Bytes. Auf diese Weise verdoppelt sich der verfügbare Speicher jedes Mal.

Answer 2

Ich habe festgestellt, dass das Anrufen zu viele Male nicht so intelligent sein wird.

Wie haben Sie es herausgefunden? Denn der einzige Weg, um wirklich zu wissen, ist die Leistung zu messen.

Ihre Strategie muss möglicherweise davon abweichen, wie Sie die Daten vom Benutzer lesen. Wenn Sie getchar() verwenden, möchten Sie wahrscheinlich realloc() nicht verwenden, um die Puffergröße bei jedem Lesen eines Zeichens um ein Zeichen zu erhöhen. Eine gute realloc() wird jedoch viel weniger ineffizient sein als Sie selbst unter diesen Umständen denken. Die minimale Blockgröße, die glibc Ihnen als Antwort auf eine malloc() tatsächlich geben wird, ist, glaube ich, 16 Bytes. Wenn Sie also von 0 bis 16 Zeichen wechseln und jedes Mal neu zuweisen, müssen Sie nicht kopieren. In ähnlicher Weise muss für größere Umverteilungen möglicherweise kein neuer Block zugewiesen werden, es kann möglich sein, den vorhandenen Block größer zu machen. Vergessen Sie nicht, dass realloc() sogar bei seiner langsamsten Geschwindigkeit schneller ist, als eine Person eingeben kann.

Die meisten Leute gehen nicht für diese Strategie. Was eingegeben werden kann, kann piped werden, so dass das Argument, dass Leute nicht sehr schnell tippen, nicht unbedingt funktioniert. Normalerweise führen Sie das Konzept der Kapazität ein. Sie ordnen einen Puffer mit einer bestimmten Kapazität zu und wenn er voll ist, erhöhen Sie seine Kapazität (mit), indem Sie einen neuen Block einer bestimmten Größe hinzufügen. Die Anfangsgröße und die Neuzuordnungsgröße können auf verschiedene Arten abgestimmt werden. Wenn Sie Benutzereingaben lesen, können Sie sich für kleine Werte entscheiden, z. 256 Byte, wenn Sie Dateien von der Festplatte oder über das Netzwerk lesen, könnten Sie nach größeren Werten suchen, z. 4 KB oder größer.

Die Inkrementgröße muss nicht einmal konstant sein. Sie können die Größe für jede erforderliche Neuzuweisung verdoppeln. Dies ist die Strategie einiger Programmierbibliotheken. Zum Beispiel verwendet die Java-Implementierung einer Hash-Tabelle, glaube ich, und so möglicherweise die Cocoa-Implementierung eines Arrays.

Es ist unmöglich vorher zu wissen, was die beste Strategie in einer bestimmten Situation ist. Ich würde etwas auswählen, das sich richtig anfühlt, und dann, wenn die Anwendung Leistungsprobleme hat, würde ich testen, um es abzustimmen. Ihr Code muss nicht so schnell wie möglich sein, aber nur schnell genug.

Jedoch eine Sache, die ich absolut nicht tun würde, überlagert einen Home Rolled Memory-Algorithmus über den integrierten Zuordner. Wenn Sie feststellen, dass Sie eine Liste der Blöcke verwalten, die Sie nicht verwenden, anstatt sie zu befreien, tun Sie es falsch. Das hat OpenSSL in Schwierigkeiten gebracht.