Ein gutes Beispiel für ein C-Array mit variabler Länge [geschlossen]

9

Diese Frage wurde bei SO ziemlich eiskalt aufgenommen, daher habe ich beschlossen, sie dort zu löschen und stattdessen hier zu versuchen. Wenn Sie der Meinung sind, dass es auch hier nicht passt, hinterlassen Sie bitte zumindest einen Kommentar zum Vorschlag, wie Sie ein Beispiel finden können, nach dem ich suche ...

Können Sie ein Beispiel geben , bei dem die Verwendung von C99-VLAs einen echten Vorteil gegenüber aktuellen C ++ RAII-Mechanismen mit Standardhaufen bietet?

Das Beispiel, nach dem ich suche, sollte:

  1. Erzielen Sie einen leicht messbaren (vielleicht 10%) Leistungsvorteil gegenüber der Verwendung von Heap.
  2. Keine gute Problemumgehung, die nicht das gesamte Array benötigen würde.
  3. Profitieren Sie tatsächlich von der Verwendung einer dynamischen Größe anstelle einer festen Maximalgröße.
  4. Es ist unwahrscheinlich, dass im normalen Verwendungsszenario ein Stapelüberlauf verursacht wird.
  5. Seien Sie stark genug, um einen Entwickler zu verführen, der die Leistung benötigt, um eine C99-Quelldatei in ein C ++ - Projekt aufzunehmen.

Hinzufügen einer Klarstellung zum Kontext: Ich meine VLA im Sinne von C99 und nicht in Standard-C ++ enthalten: int array[n]Dabei nhandelt es sich um eine Variable. Und ich bin nach einem Anwendungsfall, bei dem die Alternativen anderer Standards (C90, C ++ 11) übertroffen werden:

int array[MAXSIZE]; // C stack array with compile time constant size
int *array = calloc(n, sizeof int); // C heap array with manual free
int *array = new int[n]; // C++ heap array with manual delete
std::unique_ptr<int[]> array(new int[n]); // C++ heap array with RAII
std::vector<int> array(n); // STL container with preallocated size

Einige Ideen:

  • Funktionen, die varargs verwenden, wodurch die Anzahl der Elemente natürlich auf einen vernünftigen Wert begrenzt wird, jedoch keine nützliche Obergrenze auf API-Ebene vorliegt.
  • Rekursive Funktionen, bei denen verschwendeter Stapel unerwünscht ist
  • Viele kleine Zuweisungen und Releases, bei denen der Heap-Overhead schlecht wäre.
  • Umgang mit mehrdimensionalen Arrays (wie Matrizen beliebiger Größe), bei denen die Leistung von entscheidender Bedeutung ist und von kleinen Funktionen erwartet wird, dass sie stark eingebunden werden.
  • Aus dem Kommentar: Gleichzeitiger Algorithmus, bei dem die Heap-Zuweisung einen Synchronisierungsaufwand hat .

Wikipedia hat ein Beispiel, das meine Kriterien nicht erfüllt , da der praktische Unterschied zur Verwendung von Heap zumindest ohne Kontext irrelevant erscheint. Es ist auch nicht ideal, da ohne mehr Kontext die Anzahl der Elemente sehr wohl zu einem Stapelüberlauf führen kann.

Hinweis: Ich bin speziell auf der Suche nach einem Beispielcode oder einem Vorschlag für einen Algorithmus, der davon profitieren würde, damit ich das Beispiel selbst implementieren kann.

Hyde
quelle
1
Ein bisschen spekulativ (da dies ein Hammer ist, der nach einem Nagel sucht), aber vielleicht alloca()würde er malloc()in einer Multithread-Umgebung aufgrund des Lock-Konflikts in letzterer wirklich überstrahlen . Dies ist jedoch eine echte Strecke, da kleine Arrays nur eine feste Größe verwenden sollten und große Arrays den Heap wahrscheinlich sowieso benötigen.
Chrisaycock
1
@chrisaycock Ja, sehr viel Hammer auf der Suche nach einem Nagel, aber einem Hammer, der tatsächlich existiert (sei es C99 VLA oder der Nicht-in-irgendeinem-Standard alloca, von dem ich denke, dass er im Grunde dasselbe ist). Aber diese Multithread-Sache ist gut, die Frage zu bearbeiten, um sie aufzunehmen!
Hyde
Ein Nachteil von VLAs besteht darin, dass es keinen Mechanismus zum Erkennen eines Zuordnungsfehlers gibt. Wenn nicht genügend Speicher vorhanden ist, ist das Verhalten undefiniert. (Gleiches gilt für Arrays mit fester Größe - und für alloca ().)
Keith Thompson
@KeithThompson Nun, es gibt auch keine Garantie dafür, dass malloc / new einen Zuordnungsfehler erkennt, siehe beispielsweise die Manpage zu den Hinweisen für Linux malloc ( linux.die.net/man/3/malloc ).
Hyde
@hyde: Und es ist fraglich, ob das mallocVerhalten von Linux dem C-Standard entspricht.
Keith Thompson

Antworten:

9

Ich habe gerade ein kleines Programm gehackt, das eine Reihe von Zufallszahlen generiert, die jedes Mal mit demselben Startwert neu gestartet werden, um sicherzustellen, dass es "fair" und "vergleichbar" ist. Im Laufe der Zeit werden die Min- und Max-Werte dieser Werte ermittelt. Und wenn es den Satz von Zahlen generiert hat, zählt es, wie viele über dem Durchschnitt von minund liegen max.

Für SEHR kleine Arrays zeigt es einen deutlichen Vorteil, wenn VLAs vorbei sind std::vector<>.

Es ist kein wirkliches Problem, aber wir können uns leicht etwas vorstellen, bei dem wir die Werte aus einer kleinen Datei lesen würden, anstatt Zufallszahlen zu verwenden, und andere, aussagekräftigere Zähl- / Min / Max-Berechnungen mit derselben Art von Code durchführen würden .

Für SEHR kleine Werte der "Anzahl der Zufallszahlen" (x) in den relevanten Funktionen vlagewinnt die Lösung mit großem Abstand. Wenn die Größe größer wird, wird der "Gewinn" kleiner, und bei ausreichender Größe scheint die Vektorlösung effizienter zu sein - hat diese Variante nicht zu sehr untersucht, als wenn wir anfangen, Tausende von Elementen in einer VLA zu haben, ist dies nicht der Fall wirklich, was sie tun sollten ...

Und ich bin sicher, jemand wird mir sagen, dass es eine Möglichkeit gibt, diesen ganzen Code mit einer Reihe von Vorlagen zu schreiben und ihn dazu zu bringen, ohne mehr als das RDTSC und die coutBits zur Laufzeit auszuführen ... Aber ich denke nicht, dass das wirklich so ist Der Punkt.

Wenn ich diese spezielle Variante ausführe, erhalte ich ungefähr 10% Unterschied zwischen func1(VLA) und func2(std :: vector).

count = 9884
func1 time in clocks per iteration 7048685
count = 9884
func2 time in clocks per iteration 7661067
count = 9884
func3 time in clocks per iteration 8971878

Dies wird zusammengestellt mit: g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp

Hier ist der Code:

#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>

using namespace std;

const int SIZE = 1000000;

uint64_t g_val[SIZE];


static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}


int func1(int x)
{
    int v[x];

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}

int func2(int x)
{
    vector<int> v;
    v.resize(x); 

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

int func3(int x)
{
    vector<int> v;

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v.push_back(rand() % x);
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

void runbench(int (*f)(int), const char *name)
{
    srand(41711211);
    uint64_t long t = rdtsc();
    int count = 0;
    for(int i = 20; i < 200; i++)
    {
        count += f(i);
    }
    t = rdtsc() - t;
    cout << "count = " << count << endl;
    cout << name << " time in clocks per iteration " << dec << t << endl;
}

struct function
{
    int (*func)(int);
    const char *name;
};


#define FUNC(f) { f, #f }

function funcs[] = 
{
    FUNC(func1),
    FUNC(func2),
    FUNC(func3),
}; 


int main()
{
    for(size_t i = 0; i < sizeof(funcs)/sizeof(funcs[0]); i++)
    {
        runbench(funcs[i].func, funcs[i].name);
    }
}
Mats Petersson
quelle
Wow, mein System zeigt eine 30% ige Verbesserung der VLA-Version gegenüber std::vector.
Chrisaycock
1
Versuchen Sie es mit einem Größenbereich von etwa 5 bis 15 statt 20 bis 200, und Sie werden wahrscheinlich eine Verbesserung von 1000% oder mehr erzielen. [Hängt auch von den Compileroptionen ab - Ich werde den obigen Code bearbeiten, um meine Compileroptionen auf gcc anzuzeigen]
Mats Petersson
Ich habe gerade eine hinzugefügt, func3die v.push_back(rand())anstelle von verwendet v[i] = rand();und die Notwendigkeit für entfernt resize(). Es dauert etwa 10% länger als bei der Verwendung resize(). [Natürlich habe ich dabei festgestellt, dass die Verwendung von v[i]einen großen Beitrag zur Zeit leistet, die die Funktion benötigt - darüber bin ich ein wenig überrascht].
Mats Petersson
1
@MikeBrown Kennen Sie eine tatsächliche std::vectorImplementierung, die VLA / verwenden würde alloca, oder ist das nur Spekulation?
Hyde
3
Der Vektor verwendet zwar intern ein Array, aber soweit ich weiß, kann er keine VLA verwenden. Ich glaube, mein Beispiel zeigt, dass VLAs in einigen (vielleicht sogar vielen) Fällen nützlich sind, in denen die Datenmenge gering ist. Selbst wenn der Vektor VLAs ausgibt, würde dies nach zusätzlichem Aufwand innerhalb der vectorImplementierung erfolgen.
Mats Petersson
0

In Bezug auf VLAs im Vergleich zu einem Vektor

Haben Sie gedacht, dass ein Vektor die VLAs selbst nutzen kann? Ohne VLAs muss der Vektor bestimmte "Skalen" von Arrays angeben, z. B. 10, 100, 10000 für die Speicherung, damit Sie am Ende ein 10000-Element-Array für 101 Elemente zuweisen können. Wenn Sie bei VLAs die Größe auf 200 ändern, geht der Algorithmus möglicherweise davon aus, dass Sie nur 200 benötigen und ein Array mit 200 Elementen zuweisen können. Oder es kann ein Puffer von beispielsweise n * 1,5 zugewiesen werden.

Wie auch immer, ich würde argumentieren, dass eine VLA leistungsfähiger ist, wenn Sie wissen, wie viele Elemente Sie zur Laufzeit benötigen (wie der Mats-Benchmark gezeigt hat). Was er demonstrierte, war eine einfache Iteration mit zwei Durchgängen. Denken Sie an Monte-Carlo-Simulationen, bei denen wiederholt Zufallsstichproben entnommen werden, oder an Bildmanipulationen (wie Photoshop-Filter), bei denen Berechnungen für jedes Element mehrmals durchgeführt werden und möglicherweise bei jeder Berechnung für jedes Element Nachbarn betrachtet werden.

Dieser zusätzliche Zeigersprung vom Vektor zu seinem internen Array summiert sich.

Beantwortung der Hauptfrage

Wenn Sie jedoch über die Verwendung einer dynamisch zugewiesenen Struktur wie einer LinkedList sprechen, gibt es keinen Vergleich. Ein Array bietet direkten Zugriff mithilfe von Zeigerarithmetik auf seine Elemente. Mithilfe einer verknüpften Liste müssen Sie die Knoten durchlaufen, um zu einem bestimmten Element zu gelangen. Die VLA gewinnt also in diesem Szenario zweifellos.

Nach dieser Antwort ist es architektonisch abhängig, aber in einigen Fällen ist der Speicherzugriff auf den Stapel schneller, da der Stapel im Cache verfügbar ist. Bei einer großen Anzahl von Elementen kann dies negiert werden (möglicherweise die Ursache für die sinkenden Renditen, die Mats in seinen Benchmarks gesehen hat). Es ist jedoch erwähnenswert, dass die Cache-Größen erheblich zunehmen und Sie möglicherweise mehr davon sehen werden.

Michael Brown
quelle
Ich bin mir nicht sicher, ob ich Ihren Verweis auf verknüpfte Listen verstehe. Deshalb habe ich der Frage einen Abschnitt hinzugefügt, in dem der Kontext etwas näher erläutert und Beispiele für Alternativen hinzugefügt werden, an die ich denke.
Hyde
Warum sollte man std::vectorArrays skalieren? Warum sollte es Platz für 10K-Elemente benötigen, wenn es nur 101 benötigt? Außerdem werden in der Frage niemals verknüpfte Listen erwähnt, daher bin ich mir nicht sicher, woher Sie das haben. Schließlich werden VLAs in C99 stapelweise zugewiesen. Sie sind eine Standardform von alloca(). Alles, was Heap-Speicher benötigt (es lebt herum, nachdem die Funktion zurückgegeben wurde) oder a realloc()(das Array ändert die Größe selbst), würde VLAs sowieso verbieten.
Chrisaycock
@chrisaycock C ++ fehlt aus irgendeinem Grund eine realloc () - Funktion, vorausgesetzt, der Speicher wird mit new [] zugewiesen. Ist das nicht der Hauptgrund, warum std :: vector Skalen verwenden muss?
@Lundin Skaliert C ++ den Vektor um Zehnerpotenzen? Ich hatte gerade den Eindruck, dass Mike Brown angesichts der verknüpften Listenreferenz wirklich verwirrt von der Frage war. (Er machte auch eine frühere Behauptung, dass C99 VLAs auf dem Haufen leben.)
Chrisaycock
@hyde Ich wusste nicht, dass du darüber sprichst. Ich dachte, Sie meinen andere Heap-basierte Datenstrukturen. Interessant jetzt, da Sie diese Klarstellung hinzugefügt haben. Ich bin nicht genug von einem C ++ - Geek, um Ihnen den Unterschied zwischen diesen zu erklären.
Michael Brown
0

Der Grund für die Verwendung eines VLA ist in erster Linie die Leistung. Es ist ein Fehler, das Wiki-Beispiel als nur "irrelevant" zu betrachten. Ich kann leicht Fälle erkennen, in denen genau dieser Code einen großen Unterschied haben könnte, beispielsweise wenn diese Funktion in einer engen Schleife aufgerufen wurde, in der read_valsich eine E / A-Funktion befand, die auf einem System mit kritischer Geschwindigkeit sehr schnell zurückgegeben wurde.

In den meisten Orten, in denen VLAs auf diese Weise verwendet werden, ersetzen sie keine Heap-Aufrufe, sondern ersetzen Folgendes:

float vals[256]; /* I hope we never get more! */

Die Sache mit jeder lokalen Erklärung ist, dass sie extrem schnell ist. Die Zeile float vals[n]erfordert im Allgemeinen nur ein paar Prozessoranweisungen (möglicherweise nur eine). Sie addiert einfach den Wert nzum Stapelzeiger.

Andererseits erfordert eine Heap-Zuweisung das Durchlaufen einer Datenstruktur, um einen freien Bereich zu finden. Die Zeit ist wahrscheinlich sogar im glücklichsten Fall um eine Größenordnung länger. (Das heißt, nur das Platzieren nauf dem Stapel und das Aufrufen mallocsind wahrscheinlich 5-10 Anweisungen.) Wahrscheinlich viel schlimmer, wenn sich eine angemessene Datenmenge auf dem Heap befindet. Es würde mich überhaupt nicht überraschen, einen Fall zu sehen, mallocin dem ein reales Programm 100x bis 1000x langsamer war.

Natürlich haben Sie dann auch einige Leistungseinbußen beim Matching free, die wahrscheinlich in der Größe dem mallocAnruf ähneln .

Darüber hinaus gibt es das Problem der Speicherfragmentierung. Viele kleine Zuordnungen neigen dazu, den Haufen zu fragmentieren. Fragmentierte Haufen verschwenden sowohl Speicher als auch erhöhen die Zeit, die zum Zuweisen von Speicher erforderlich ist.

Gort den Roboter
quelle
Über Wikipedia Beispiel: Es könnte sein , Teil eines gutes Beispiel, aber ohne Zusammenhang, mehr Code um ihn herum, ist es nicht wirklich zeigen , eine der 5 Dinge in meiner Frage aufgezählt. Ansonsten stimme ich Ihrer Erklärung zu. Beachten Sie jedoch Folgendes: Die Verwendung von VLAs kann mit Kosten für den Zugriff auf lokale Variablen verbunden sein. Daher sind Offsets aller lokalen Variablen zum Zeitpunkt der Kompilierung nicht unbedingt bekannt. Daher muss darauf geachtet werden, dass einmalige Heap-Kosten nicht durch a ersetzt werden Strafe für die innere Schleife für jede Iteration.
Hyde
Ähm ... nicht sicher, was du meinst. Lokale Variablendeklarationen sind eine einzelne Operation, und jeder leicht optimierte Compiler zieht die Zuordnung aus einer inneren Schleife heraus. Es gibt keine besonderen "Kosten" für den Zugriff auf lokale Variablen, sicherlich keine, die durch eine VLA erhöht werden.
Gort the Robot
Konkretes Beispiel int vla[n]; if(test()) { struct LargeStruct s; int i; }:: Der Stapelversatz von sist zum Zeitpunkt der Kompilierung nicht bekannt, und es ist auch zweifelhaft, ob der Compiler den Speicher von iaus dem inneren Bereich auf einen festen Stapelversatz verschiebt. Daher wird zusätzlicher Maschinencode benötigt, da die Indirektion und dies auch Register verschlingen kann, die für PC-Hardware wichtig sind. Wenn Sie Beispielcode mit Compiler-Assembly-Ausgabe wünschen, stellen Sie bitte eine separate Frage;)
Hyde
Der Compiler muss nicht in der im Code angegebenen Reihenfolge zuordnen, und es spielt keine Rolle, ob Speicherplatz zugewiesen und nicht verwendet wird. Ein intelligenter Optimierer würde Speicherplatz für sund ibei Eingabe der Funktion zuweisen , bevor sie testaufgerufen oder vlazugewiesen wird, da die Zuweisungen für sund ikeine Nebenwirkungen haben. (Und tatsächlich ikönnte es sogar in ein Register gestellt werden, was bedeutet, dass es überhaupt keine "Zuordnung" gibt.) Es gibt keine Compiler-Garantien für die Reihenfolge der Zuordnungen auf dem Stapel oder sogar dafür, dass der Stapel verwendet wird.
Gort the Robot
(löschte einen Kommentar, der aufgrund eines dummen Fehlers falsch war)
Hyde