Beste Heuristik für malloc

Question

Betrachten Sie die Verwendung von malloc(), um x Bytes Speicher in einem fragmentierten Heap zuzuweisen. Angenommen, der Heap hat mehrere zusammenhängende Speicherplätze mit einer Größe von mehr als x Bytes.

Welche der folgenden Heuristiken ist die beste (die zu der geringsten Heap-Verschwendung führt), um einen Standort zu wählen?

1. Wählen Sie die kleinste Stelle, die größer als x Bytes ist.
2. Wählen Sie den größten Speicherplatz, der größer als x Bytes ist.

Meine Intuition ist der kleinste Ort, der größer als x Bytes ist. Ich bin mir nicht sicher, was in der Praxis das Beste ist.

Nein, dies ist keine Auftragsfrage. Ich habe dies gelesen Wie funktionieren malloc() und free()? und dies scheint eine gute Folgefrage zu sein, die man stellen sollte.

Answer 1

In einem allgemeinen Heap, in dem Zuweisungen verschiedener Größen gemischt werden, würde ich mich dafür entscheiden, die Zuweisung in den kleinsten Block zu legen, der sie aufnehmen kann (um zu vermeiden, dass die Größe des größten Blocks, den wir zuweisen können, reduziert wird, bevor wir ihn brauchen).

Es gibt jedoch auch andere Möglichkeiten, einen Heap zu implementieren, die diese Frage weniger relevant machen (z. B. das beliebte dlmalloc von Doug Lea - wo es Blöcke ähnlicher Größe zusammenfasst, um die Geschwindigkeit zu erhöhen und die Fragmentierung insgesamt zu verringern).

Welche Lösung die beste ist, hängt immer von der Art und Weise ab, wie die Anwendung ihre Speicherzuweisungen vornimmt. Wenn Sie das Muster einer Anwendung im Voraus kennen, sollten Sie in der Lage sein, die generischen Heaps sowohl hinsichtlich der Größe als auch der Geschwindigkeit zu schlagen.

Answer 2

Es ist besser, den kleinsten Standort zu wählen. Denken Sie an zukünftige malloc-Anforderungen. Sie wissen nicht, wie viele das sein werden, und Sie wollen so viele Anforderungen wie möglich erfüllen. Es ist also besser, einen Speicherplatz zu finden, der genau Ihren Bedürfnissen entspricht, so dass größere Anforderungen in der Zukunft erfüllt werden können. Mit anderen Worten: Die Auswahl des kleinsten Standorts verringert die Fragmentierung.

Answer 3

Die von Ihnen aufgeführten Heuristiken werden in den Algorithmen Best Fit bzw. Worst Fit verwendet. Es gibt auch den First Fit-Algorithmus, der einfach den ersten Platz nimmt, der groß genug ist. Er ist ungefähr so gut wie Best Fit, aber viel schneller.