Warum haben gezeigt, dass Datenstrukturen in der Regel eine Größe von 2 ^ n?

StackOverflow https://stackoverflow.com/questions/1816727

Frage

Sie haben einen historischen Grund, oder was? Ich habe schon ein paar Mal so etwas wie char foo[256]; oder #define BUF_SIZE 1024 gesehen. Auch nicht nur verwende ich meistens 2 n Größe Puffer, vor allem, weil ich denke, es ist elegant aussieht und auf diese Weise muss ich denken nicht an eine bestimmte Nummer. Aber ich bin mir nicht ganz sicher, ob das der Grund, warum die meisten Menschen, die sie nutzen, mehr Informationen geschätzt.

War es hilfreich?

Lösung

Es kann eine Reihe von Gründen, obwohl viele Leute wie Sie es gerade Gewohnheit aus tun sagen.

Ein Ort, an dem es sehr nützlich ist, ist bei der effizienten Durchführung von Ringpuffern, insbesondere auf Architekturen, bei denen der Operator% teuer ist (die ohne Hardware-Kluft - in erster Linie 8-Bit-Mikrocontroller). Durch die Verwendung von a 2 ^ n in diesem Fall puffer, die Modulo ist einfach ein Fall von Bit-Maskieren des oberen Bits, oder, im Fall von beispielsweise einen 256-Byte-Puffer, einfach unter Verwendung eines 8-Bit-Index und läßt sie wraparound.

In anderen Fällen Ausrichtung mit Seitenbegrenzungen usw. Caches Optimierungsmöglichkeiten auf einigen Architekturen bieten kann - aber das wäre sehr Architektur spezifisch sein. Aber es kann nur sein, dass solche Puffer den Compiler mit Optimierungsmöglichkeiten bieten, so dass alle anderen Dinge gleich sind, warum nicht?

Andere Tipps

Cache Linien sind in der Regel ein Vielfaches von 2 (oft 32 oder 64). Daten, die ein ganzzahliges Vielfaches dieser Zahl ist, würde in der Lage sein, zu passen (und eine optimale Nutzung), um die entsprechende Anzahl von Cache-Zeilen. Je mehr Daten können Sie in Ihre Cache packen, desto besser die Leistung .. so dass ich glaube, die Leute, die ihre Strukturen auf diese Weise entwerfen für die Optimierung.

Ein weiterer Grund, zusätzlich zu dem, was alle anderen erwähnt ist, SSE-Befehle nehmen mehrere Elemente, und die Anzahl der Elemente Eingang ist immer eine Zweierpotenz. Machen die eine Leistung von zwei Garantien Puffer werden Sie nicht nicht zugewiesenen Speicher lesen. Dies gilt nur, wenn Sie tatsächlich SSE-Befehle verwenden though.

ich am Ende denke, die überwiegende Grund in den meisten Fällen ist jedoch, dass Programmierer wie Zweierpotenzen.

Hash Tables, Zuordnung von Seiten

Das hilft wirklich für Hash-Tabellen, weil Sie den Index Modulo der Größe zu berechnen, und wenn diese Größe eine Zweierpotenz ist, kann das Modul mit einer einfachen bitweise und oder & berechnet wird eher eine viel langsamere Teile-Klasse Anweisung zur Durchführung des % Betreibers als verwenden.

Mit Blick auf einem alten Intel i386 Buch, and 2 Zyklen und div 40 Zyklen. Eine Ungleichheit bleibt heute aufgrund der viel größeren grundlegenden Komplexität der Teilung, obwohl die 1000x schnellere Gesamtzykluszeiten neigen dazu, die Auswirkungen von selbst die langsamste Maschine ops zu verbergen.

Es gab auch eine Zeit, als malloc Kopf gelegentlich in großer Ausführlichkeit vermieden wurde. Allokation der verfügbaren direkt aus dem Betriebssystem wäre (immer noch) eine bestimmte Anzahl von Seiten, und so eine Zweierpotenz wäre wahrscheinlich die meisten Verwendung der Zuweisung Granularität machen.

Und, wie andere haben darauf hingewiesen, Programmierer wie Zweierpotenzen.

kann ich mich vorstellen ein paar Gründe aus der Spitze von meinem Kopf:

  1. 2 ^ n ist ein sehr verbreiteter Wert in allen Computer-Größen. Dies wird direkt auf die Art und Weise Bits beziehen, werden in Computern dargestellt (2 mögliche Werte), was bedeutet, Variablen sind in der Regel im Bereich von Werten, deren Grenzen haben, sind 2 ^ n.
  2. Da oben von dem Punkt, werden Sie oft den Wert 256 als die Größe des Puffers finden. Dies ist, weil es die größte Zahl, die in einem Byte gespeichert werden können. Also, wenn Sie eine Zeichenfolge zusammen mit einer Größe der Zeichenfolge speichern wollen, dann werden Sie am effizientesten, wenn Sie es als speichern: SIZE_BYTE+ARRAY, wobei die Größe Byte Sie die Größe des Arrays erzählt. Dies bedeutet, dass die Anordnung eine beliebige Größe von 1 bis 256 sein kann.
  3. Viele andere Zeiten sind Größen auf der Grundlage physikalischer Dinge (zum Beispiel die Größe des Speichers ein Betriebssystem aus können wählen, um die Größe der Register der CPU usw. verwandt ist) gewählt, und diese sind auch eine sein würde bestimmte Menge an Bits. Das heißt, die Menge an Speicher, den Sie in der Regel verwenden können, werden einige Wert von 2 ^ n sein (für ein 32-Bit-System, 2 ^ 32).
  4. Es könnte Leistungsvorteile / Ausrichtungsprobleme für solche Werte sein. Die meisten Prozessoren können zu einem Zeitpunkt eine bestimmte Menge an Bytes zugreifen, so dass selbst wenn Sie eine Variable, deren Größe haben, ist sagen wir mal) 20 Bit, ein 32-Bit-Prozessor lesen noch 32 Bits, egal was passiert. So ist es oft effizienter, nur die Variable 32 Bit zu machen. Auch einige Prozessoren erforderlich Variablen auf eine bestimmte Menge an Bytes ausgerichtet werden (weil sie nicht Speicher von zum Beispiel Adressen im Speicher, die sonderbar sind lesen können). Natürlich ist es manchmal nicht über ungerade Speicherplätze, aber Orte, die ein Vielfaches von 4 oder 6 von 8 sind, etc. So in diesen Fällen ist es effizienter ist machen Puffer nur die immer ausgerichtet werden .

Ok, kamen diese Punkte etwas wirre aus. Lassen Sie uns wissen, wenn Sie weitere Erklärung benötigen, insbesondere Punkt 4, die IMO ist das wichtigste.

Aufgrund der Einfachheit (lesen Sie auch Kosten ) der Basis 2-Arithmetik in der Elektronik: Verschiebung nach links (mit 2 multiplizieren), nach rechts verschieben (durch 2)

.

In der CPU-Domäne, viele Konstrukte drehen sich um Basis-2-Arithmetik. Busse (Kontrolle & data) Speicherstruktur für den Zugriff auf häufig Kraft ausgerichtet sind, 2. Kosten der Logik-Implementierung in der Elektronik (z.B. CPU) für Arithmetik in der Basis 2 macht zwingend.

Natürlich, wenn wir analoge Computer hätten, wäre die Geschichte anders sein.

FYI: die Attribute eines Systems auf Schicht X sitzt eine direkte Folge ist der Server Schichtattribute des Systems sitzt unterhalb d.h. Schicht

z. die Eigenschaften, die bei der „Kompilierer“ -Niveau manipuliert werden können, sind geerbt & abgeleitet von den Eigenschaften des Systems darunter das heißt die Elektronik in der CPU.

Ich wollte die Shift-Argument verwenden, könnte aber denken Sie an einen guten Grund, es zu rechtfertigen.

Eine Sache, die über einen Puffer schön ist, die eine Zweierpotenz ist, dass Ringpuffer Handhabung einfach ands anstatt dividieren verwenden kann: 

#define BUFSIZE 1024

++index;                // increment the index.
index &= BUFSIZE;       // Make sure it stays in the buffer.

Wenn es nicht eine Potenz von zwei ist, eine Division erforderlich wäre. In den alten Tagen (und zur Zeit auf kleine Chips), das zählte.

Es ist auch üblich, pagesizes Potenzen von 2 zu sein.

Unter Linux Ich mag getpagesize () verwenden, wenn etwas zu tun, wie ein Puffer Chunking und es an eine Steckdose oder Dateideskriptor zu schreiben.

Es macht eine schöne, runde Zahl in der Basis 2. Wie 10, 100 oder 1000000 sind schöne, runde Zahlen in der Basis 10

Wenn es nicht eine Potenz von 2 (oder so nah wie 96 = 64 + 32 oder 192 = 128 + 64), dann könnte man sich fragen, warum es die zugegebene Präzision. Basis nicht 2 gerundet Größe kann von äußeren Zwängen oder Programmierer Unwissenheit kommen. Sie werden wissen wollen, welches es ist.

Andere Antworten haben auch eine Reihe von technischen Gründen darauf hingewiesen, dass in besonderen Fällen gültig sind. Ich werde nicht wiederholen, jeder von ihnen hier.

In Hash-Tabellen, 2 ^ n macht es einfache Schlüssel collissions in einer bestimmten Art und Weise zu handhaben. In der Regel, wenn es ein Schlüssel collission, Sie entweder einen Unterbau machen, z.B. eine Liste aller Einträge mit dem gleichen Hash-Wert; oder Sie finden einen anderen freien Steckplatz. Sie könnten nur 1 an den Slot-Index hinzufügen, bis Sie einen freien Steckplatz finden; aber diese Strategie ist nicht optimal, weil es Cluster von blockierten Stellen schafft. Eine bessere Strategie ist es, eine zweite Hash-Zahl h2 zu berechnen, so dass gcd (N, h2) = 1; dann h2 in dem Slot-Index hinzufügen, bis Sie einen freien Steckplatz (mit Wrap-around) finden. Wenn n eine Potenz von 2 ist, ein h2 zu finden, die GCD erfüllt (n, h2) = 1 ist einfach, wird jede ungerade Zahl tun.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top