Wie viel Overhead führen Realloc-Aufrufe ein?

8

Ich verwende realloc in jeder Iteration einer for -Schleife, die mehr als 10000-mal iteriert.

Ist das eine gute Übung? Wird realloc einen Fehler verursachen, wenn es oft aufgerufen wurde?

    
saber 29.03.2011, 11:06
quelle

7 Antworten

13

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.

    
Alexander Gessler 29.03.2011 11:07
quelle
7

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.

    
ffhaddad 29.05.2013 16:31
quelle
3

Sie riskieren, Ihr Gedächtnis zu fragmentieren, wenn Sie dies tun. Dies führt zu einer Leistungsverschlechterung und kann bei 32-Bit-Systemen zu Speichermangel führen, da große zusammenhängende Speicherblöcke nicht verfügbar sind.

Ich nehme an, dass Sie die Länge eines Arrays jedes Mal um 1 erhöhen. Wenn dies der Fall ist, können Sie Kapazität und Länge besser verfolgen und die Kapazität nur erhöhen, wenn Sie eine Länge benötigen, die die aktuelle Kapazität übersteigt. Wenn Sie die Kapazität erhöhen, tun Sie dies um einen größeren Betrag als nur 1.

Natürlich werden die Standardcontainer so etwas für Sie tun, wenn Sie sie also verwenden können, ist es das Beste.

    
David Heffernan 29.03.2011 11:12
quelle
3

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
  3. 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:

%Vor%

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

%Vor%

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).

    
FrankH. 29.03.2011 12:19
quelle
2

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.

    
Adrian McCarthy 29.05.2013 17:00
quelle
1

sollten Sie auf Größen mit der Potenz von 2 umverteilen. Dies ist die Richtlinie, die von stl verwendet wird und ist gut, da der Speicher verwaltet wird. Realloc funktioniert nicht, es sei denn, Sie haben keinen Speicher mehr (und geben NULL zurück), aber Ihre vorhandenen (alten) Daten werden an den neuen Speicherort kopiert, was ein Leistungsproblem darstellen kann.

    
cprogrammer 29.03.2011 11:15
quelle
0

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:)

    
user237419 29.03.2011 11:17
quelle