Wie viel Overhead führen Realloc-Aufrufe ein?

Es wird nicht fehlschlagen, es sei denn, Sie haben keinen Speicher mehr (was auch mit anderen Zuordnern passieren würde) - aber Ihr Code wird normalerweise viel schneller laufen, wenn Sie es schaffen, den benötigten Speicher im Voraus zu schätzen.

Oft ist es besser, eine extra Schleife auszuführen, um die Speicheranforderungen zu ermitteln.

Ich würde nicht sagen, dass realloc ein No-Go ist, aber es ist auch keine gute Übung.

Ich bin kürzlich auf diese Frage gestoßen, und obwohl es ziemlich alt ist, habe ich das Gefühl, dass die Information nicht ganz korrekt ist.

In Bezug auf eine zusätzliche Schleife, um vorzubestimmen, wie viele Bytes Speicher benötigt werden,

Die Verwendung einer zusätzlichen Schleife ist nicht immer oder sogar oft besser. Was ist erforderlich, um festzulegen, wie viel Speicher benötigt wird? Dies kann zu zusätzlichen E / A führen, die teuer und unerwünscht sind.

Was die Verwendung von realloc im Allgemeinen betrifft,

Die alloc-Familie von Funktionen (malloc, calloc, realloc und free) ist sehr effizient. Das zugrundeliegende Alloc-System weist dem Betriebssystem einen großen Chunk zu und übergibt Teile an den Benutzer wie angefordert. Konsekutivanrufe auf Realloc werden mit ziemlicher Sicherheit nur zusätzlichen Speicherplatz für den aktuellen Speicherort bereitstellen.

Sie möchten keinen Heappool selbst pflegen, wenn das System dies von Anfang an effizienter und korrekter für Sie erledigt.

Zusätzlich zu dem, was vorher gesagt wurde, gibt es noch ein paar Dinge zu beachten:

Die Leistung von realloc(<X-sized-buf>, X + inc) hängt von zwei Dingen ab:

1. die Geschwindigkeit von malloc(N + inc) , die sich normalerweise in Richtung O(N) mit der Größe des zugewiesenen Blocks verschlechtert
2. die Geschwindigkeit von memcpy(newbuf, oldbuf, N) , die auch O(N) mit der Größe des Blocks
ist

Das bedeutet für kleine Inkremente, aber große existierende Blöcke, realloc() Leistung ist O(N^2) in Bezug auf die Größe des existierenden Datenblocks. Denken Sie bubblesort vs. quicksort ...

Es ist vergleichsweise günstig, wenn Sie mit einem kleinen Block beginnen, aber Sie werden erheblich bestraft, wenn der zuzuteilende Block groß ist. Um dies zu vermeiden, sollten Sie sicherstellen, dass inc relativ zur vorhandenen Größe nicht klein ist. Die Umverteilung um einen konstanten Betrag ist ein Rezept für Leistungsprobleme.

Auch wenn Sie in großen Schritten wachsen (z. B. die neue Größe auf 150% der alten Größe skalieren), gibt es die Speicherbelegungsspitze , wenn Sie einen großen Puffer neu zuweisen; Während der Kopie des vorhandenen Inhalts verwenden Sie doppelt so viel Speicher. Eine Folge von:

fällt daher (viel) früher als:

Es gibt Datenstrukturen, die nicht realloc() benötigen, um zu wachsen; verknüpfte Listen, Überspringlisten, Intervallbäume können alle Daten anhängen, ohne bestehende Daten kopieren zu müssen. C ++ vector<> wächst auf diese Weise, es beginnt mit einem Array für die anfängliche Größe und behält anhängig bei, wenn Sie es darüber hinaus vergrößern, aber nicht realloc() (d. H. Kopieren). Überlegen Sie, ob Sie etwas Ähnliches implementieren (oder eine bereits vorhandene Implementierung verwenden).

In C:

Bei korrekter Verwendung ist mit realloc nichts falsch. Das heißt, es ist einfach, es falsch zu benutzen. In Solide Code schreiben finden Sie eine ausführliche Beschreibung aller Arten und Weisen, wie Sie Fehler machen können Aufruf realloc und für die zusätzlichen Komplikationen, die es beim Debuggen verursachen kann.

Wenn Sie feststellen, dass Sie denselben Puffer immer wieder mit nur einem kleinen inkrementellen Größen-Bump neu zuweisen, beachten Sie, dass es normalerweise viel effizienter ist, mehr Speicherplatz zuzuweisen, als Sie benötigen, und dann den tatsächlich belegten Speicherplatz zu verfolgen. Wenn Sie den zugewiesenen Speicherplatz überschreiten, ordnen Sie einen neuen Puffer in größerer Größe zu, kopieren Sie den Inhalt und geben Sie den alten Puffer frei.

In C ++:

Sie sollten wahrscheinlich realloc vermeiden (sowie malloc und frei). Verwenden Sie wann immer möglich eine Containerklasse aus der Standardbibliothek (z. B. std :: vector). Sie sind gut getestet und gut optimiert und entlasten Sie von den vielen Details zur ordnungsgemäßen Verwaltung des Speichers (wie zum Beispiel mit Ausnahmen).

C ++ hat nicht das Konzept, einen vorhandenen Puffer neu zuzuweisen. Stattdessen wird ein neuer Puffer in der neuen Größe zugewiesen, der Inhalt wird kopiert und der alte Puffer wird gelöscht. Dies ist, was Realloc tut, wenn es die neue Größe an dem vorhandenen Speicherort nicht erfüllen kann, was es scheint, dass C ++ - Ansatz weniger effizient ist. Es ist jedoch selten, dass Realloc tatsächlich eine In-Place-Neuzuweisung nutzen kann. Und die C ++ - Standardcontainer sind recht clever, wenn es darum geht, die Fragmentierung zu minimieren und die Kosten über viele Updates hinweg zu amortisieren. Daher lohnt es sich in der Regel nicht, realloc zu betreiben, wenn Sie die Leistung steigern wollen.

Wenn Sie den gleichen Puffer in der Schleife neu zuweisen (siehe Abbildung), sehe ich keine Probleme, solange Sie genug Speicher haben, um die zusätzlichen Speicheranforderungen zu erfüllen:)

normalerweise realloc () erweitert / schrumpft den vorhandenen zugewiesenen Speicherplatz, an dem Sie arbeiten, und gibt Ihnen denselben Zeiger zurück; wenn dies nicht inplace geschieht, dann sind eine Kopie und eine freie Datei beteiligt. In diesem Fall wird realloc () teuer. und Sie erhalten auch einen neuen Zeiger:)