Schneller zu Malloc mehrere kleine Zeiten oder wenige große Zeiten?

Question

Wenn Sie malloc verwenden, um Speicher zuzuordnen, ist es in der Regel schneller, mehrere mallocs aus kleineren Datenblöcken oder weniger mallocs aus größeren Datenblöcken zu erstellen? Angenommen, Sie arbeiten mit einer Bilddatei, die schwarze Pixel und weiße Pixel enthält. Sie durchlaufen die Pixel und möchten die x- und y-Position jedes schwarzen Pixels in einer neuen Struktur speichern, die auch einen Zeiger auf die x- und y-Werte der nächsten und vorherigen Pixel hat. Wäre es im Allgemeinen schneller, durch die Pixel zu iterieren, die mit den Zeigern eine neue Struktur für die x- und y-Werte jedes schwarzen Pixels zuweisen, oder wäre es schneller, eine Zählung der Anzahl der schwarzen Pixel durch einmaliges Durchlaufen zu erhalten und dann ein großes zuzuweisen Speicherbereich, der eine Struktur verwendet, die nur die x- und y-Werte enthält, aber keine Zeiger, und dann erneut durchläuft, wobei die x- und y-Werte in diesem Array gespeichert werden? Ich gehe davon aus, dass bestimmte Plattformen anders sind als andere, was schneller ist, aber was denken alle im Allgemeinen, dass es schneller wäre?

Answer 1

Es hängt davon ab:

• Mehrere kleine Zeiten mehrmals bedeutet, die langsamer ist
• Es kann eine spezielle/schnelle Implementierung für kleine Zuweisungen sein.

Wenn ich mich kümmerte, würde ich es messen! Wenn mir wirklich viel am Herzen liegt und ich nicht raten kann, dann kann ich beides implementieren und zur Laufzeit auf der Zielmaschine messen und entsprechend anpassen.

Im Allgemeinen würde ich annehmen, dass weniger besser ist: aber es gibt Größen- und Laufzeitbibliotheksimplementierungen, so dass eine (ausreichend) große Zuweisung an das (relativ langsame) O/S delegiert wird. während eine (ausreichend) kleine Zuteilung von einem (relativ schnell) bereits zugewiesenen Haufen bedient wird.

Answer 2

Im Allgemeinen wird das schnellere Zuteilen größerer Speicherbereiche schneller. Bei jedem Aufruf von malloc() ist ein Overhead erforderlich.

Answer 3

Das Zuweisen von großen Blöcken ist effizienter; Da Sie größere zusammenhän- gende Blöcke verwenden, haben Sie außerdem eine größere Referenz- fläche, und wenn Sie Ihre speicherinterne Struktur durchlaufen haben, sollte sie auch effizienter sein! Außerdem sollte die Zuweisung großer Blöcke dazu beitragen, die Speicherfragmentierung zu verringern.

Answer 4

Wie bereits erwähnt, ist malloc teuer, daher werden wahrscheinlich weniger schneller sein. Auch die Arbeit mit den Pixeln hat auf den meisten Plattformen weniger Cache-Fehler und wird schneller sein. Es gibt jedoch keine Garantie für alle Plattformen

Answer 5

Speicherzuordnung ist Arbeit. Der Arbeitsaufwand bei der Zuweisung eines Speicherblocks ist typischerweise unabhängig von der Größe des Blocks. Du machst es von hier aus.

Answer 6

Im Allgemeinen ist Malloc teuer. Es muss einen geeigneten Speicherblock finden, aus dem Speicher zugewiesen und nicht zusammenhängende Speicherblöcke verfolgt werden können. In mehreren Bibliotheken finden Sie kleine Speicherzuordner, die versuchen, die Auswirkungen zu minimieren, indem Sie einen großen Block zuweisen und den Speicher im Zuordner verwalten.

Alexandrescu behandelt das Problem in "Modern C++ Design" und in der Loki-Bibliothek, wenn Sie sich eine solche Bibliothek ansehen möchten.

Answer 7

Außer Geschwindigkeitsproblemen gibt es auch die memory fragmentation problem.

Answer 8

Diese Frage ist eine Frage des Pragmatismus, fürchte ich; das heißt, es kommt darauf an.

Wenn Sie eine Menge Pixel haben, von denen nur einige schwarz sind, dann könnte das Zählen der höchsten Kosten sein.

Wenn Sie C++ verwenden, was Ihre Tags vorschlagen, dann würde ich Ihnen STL empfehlen, etwas wie std :: vector.

Die Implementierung von Vektor, wenn ich mich richtig erinnere, verwendet einen pragmatischen Ansatz für die Zuordnung. Es gibt ein paar Heuristiken für die Zuteilung Strategien, ein informativer ist dies:

class SampleVector { 
    int N,used,*data; 
public: 
    SampleVector() {N=1;used=0;data=malloc(N);} 

    void push_back(int i) 
    { 
     if (used>=N) 
     { 
      // handle reallocation 
      N*=2; 
      data=realloc(data,N); 
     } 
     data[used++]=i; 
    } 
}; 

In diesem Fall DOUBLE Sie die Größe des Speichers jedes Mal, wenn Sie realloc zugeordnet. Dies bedeutet, dass sich die Neuzuweisungen schrittweise in der Häufigkeit halbieren.

Ihre STL-Implementierung wurde gut abgestimmt, also wenn Sie das verwenden können, tun Sie!

Answer 9

Neben dem Allocation-Overhead selbst kann das Zuweisen mehrerer kleiner Chunks zu einer Menge Cache-Misses führen, während die Chancen, wenn Sie durch einen zusammenhängenden Block iterieren können, besser sind.

Das von Ihnen beschriebene Szenario erfordert die Vorbelegung eines großen Blocks, imho.

Answer 10

Obwohl das Zuweisen großer Blöcke schneller ist, wird es wahrscheinlich nicht schneller sein, wenn Sie die Zuordnungsgröße nur künstlich erhöhen, um es selbst zu zerhacken. Sie duplizieren nur die Speicherverwaltung.

Answer 11

Es ist schneller, nicht im leistungsempfindlichen Code überhaupt zuzuweisen. Ordnen Sie den Speicher, den Sie benötigen, einmal im Voraus, und dann verwenden und wiederverwenden Sie so viel wie Sie möchten.

Speicherzuweisung ist im Allgemeinen ein relativ langsamer Vorgang, also tun Sie es nicht öfter als nötig.

Answer 12

"Ich kann zuteilen-it-all" (wirklich, ich kann!)

Wir können Philosophie über einige spezielle Implementierungen, die erheblich kleiner Zuweisungen beschleunigen ... ja! Aber im Allgemeinen gilt das:

malloc muss allgemein sein. Sie muss alle Arten von Zuordnungen implementieren. Das ist der Grund, warum es sehr langsam ist! Es kann sein, dass Sie eine spezielle Kinky-Super-Duper-Bibliothek verwenden, die die Dinge beschleunigt, aber auch diese können keine Wunder vollbringen, da sie malloc in ihrem vollen Spektrum implementieren müssen.

Die Regel ist, wenn Sie mehr spezialisierte Zuteilung Codierung haben, sind Sie immer schneller als die breite "Ich kann-es-all" Routine "malloc" zuweisen.

Wenn Sie in der Lage sind, den Speicher in größeren Blöcken in Ihrer Codierung zuzuordnen (und es kostet Sie nicht viel), können Sie die Dinge erheblich beschleunigen. Außerdem - wie von anderen erwähnt - werden Sie viel weniger Speicherfragmentierung bekommen, was auch die Geschwindigkeit erhöht und weniger Speicher kostet. Sie müssen auch sehen, dass Malloc für jeden Speicherbereich, den es Ihnen zurückgibt, zusätzlichen Speicher benötigt (ja, spezielle Routinen können dies reduzieren ... aber Sie wissen nicht, was es wirklich tut, es sei denn, Sie haben es selbst implementiert oder etwas Wunder gekauft -Bibliothek).

Answer 13

Ein weiterer zu berücksichtigender Punkt ist, wie dies mit Threading interagiert. Die häufige Verwendung von malloc in einer parallelen Threading-Anwendung beeinträchtigt die Leistung erheblich.In dieser Umgebung sind Sie mit einem skalierbaren Allokator wie dem in Intels Thread Building Blocks oder Hoard verwendeten besser dran. Die größte Einschränkung bei malloc besteht darin, dass es eine einzige globale Sperre gibt, nach der alle Threads streiten. Es kann so schlimm sein, dass das Hinzufügen eines anderen Threads Ihre Anwendung dramatisch verlangsamt.

Answer 14

Führen Sie eine Iteration über die Pixel durch, um die Anzahl der zu speichernden Pixel zu zählen. Dann ordnen Sie ein Array für die genaue Anzahl der Elemente zu. Dies ist die effizienteste Lösung.

Sie können std :: vector für eine einfachere Speicherverwaltung verwenden (siehe die Prozedur std :: vector :: reserve). Hinweis: Reserve reserviert wahrscheinlich ein wenig (wahrscheinlich bis zu 2 mal) mehr Speicher als nötig.