Wie am Besten Objekt-Funktionen, die Buffer nutzen parallel ausführen (OMP thread)

[OhMyPie]

Hi, ich möchte meinen Code ein wenig schneller machen und parallel ausführen (mit open mp).

Nun benötig ein Objekt zur Berechnung einer Funktion (die von extern ausgeführt wird) einen Buffer. Wenn nun mehrere Threads diese ausführen, brauchen die alle ihren eigenen Buffer.
Wie implementiert man das in der Regel?

1. Bei Objekterstellung die Anzahl der Threads mit übergeben und so viele Buffer erstellen
2. Bei Objekterstellung automatisch für die maximale Anzahl möglicher Threads Buffer erstellen (omp_get_max_threads())
3. Den Buffer beim Funktionsaufruf für jeden Thread individuell übergeben. Buffer also außerhalb erstellen und zeiger darauf übermitteln.
4. Buffer jedes mal erst bei dem Funktionsaufruf erstellen und am ende wieder löschen.
5. oder besser ganz anders machen

## und wie legt man fest welcher buffer bzw welche ID verwendet werden soll.
6) Thread-ID beim Funktionsaufruf übergeben und buffer mit dieser ID verwenden
7) Thread-ID in der Funktion automatisch ermitteln und dann diese ID verwenden (omp_get_thread_num())
oder besser ganz anders machen

[zerg]

Wenn die Größe des Buffers fest ist und nicht etwa 1 GB groß sein muss, dann in der Funktion auf dem Stack anlegen. Das kostet keine Laufzeit.

Wenn nicht, dann mit dynamischer Allokation z.B. mit std::vector - es sei denn, die Funktion wird zig Millionen mal pro Sekunde ausgeführt. Erst dann muss man über kompliziertere Methoden wie thread-local storage nachdenken.

[OhMyPie]

Je nach Daten und Parameter, zwischen 20 Tausend und 20 Millionen mal die Sekunde.
Bei einem Objekt (welches für die gesammte Laufzeit weniger relevant ist) kann unter Umständen die Laufzeit für mehrere Threads länger dauern als bei einem Thread, Funktionslaufzeit verkürzt sich zwar aber Zeit für Konstruktor und Destruktor nimmt da mehr zu. Das Objekt selbst wird sehr oft erstellt, und dann wieder jeweils die Funktion oft ausgeführt.
Größe des Buffers ist zur Kompilezeit unbekannt. Während der Ausführung dann aber immer konstant.

[OhMyPie]

Habe mal getestet. Wenn ich es bei jedem Aufruf erstelle, ist es über 10% langsammer.

[OhMyPie]

Hier mal ein Beispiel.

#include <omp.h>
#include <iostream>

class Obuff{

    int buffSize;

    int **buffer;
    const int threads;
    int ovar;
public:
    Obuff(int ovar)
            :ovar(ovar),threads(omp_get_max_threads()),buffSize(ovar*ovar+1){
        buffer = new int*[threads];        
        for(int t=0; t<threads; t++){
            buffer[t] = new int[buffSize];
        }
    }
    //oder so
    Obuff(int ovar, int threads)
            :ovar(ovar),threads(threads),buffSize(ovar*ovar+1){
        buffer = new int*[threads];        
        for(int t=0; t<threads; t++){
            buffer[t] = new int[buffSize];
        }
    }
    ~Obuff(){
        for(int t=0; t<threads; t++){
            delete[] buffer[t];
        }
        delete[] buffer;
    }

    int dummy(int i, int j){
        int id = omp_get_thread_num();

        int* const mybuff = buffer[id];

        //sinnlose for schleifen
        for(int m = 0; m< buffSize; m++)
            mybuff[m] = i + j + m - ovar;
        for(int m = 0; m< buffSize; m++)
            mybuff[m] /= (ovar +m-buffSize/2+1.0+1e-1*std::abs(i-j));
        int sum = 0;
        for(int m = 0; m< buffSize; m++)
            sum += -((m-i) * mybuff[m] 
                    - (m-buffSize/2-j) * mybuff[buffSize-m-1])/buffSize;
        return sum;
    }
};

int main(){

    const int max = 1000;   
    int ovar = 10;
    Obuff obj(ovar); // oder obj(ovar, omp_get_max_threads())
    int sum = 0;

    #pragma omp parallel for reduction(+:sum)
    for(int i=0; i < max; i++)
        for(int j=0; j < max; j++)
            sum += (obj.dummy(i, j))>0;

    std::cout<< sum << std::endl;

}

[zerg]

Kann ich nicht bestätigen. Bei mir ist deine gepostete Variante langsamer als andere Methoden.
Das liegt im wesentlichen daran, dass gcc die Schleifen in diesem Fall nicht mithilfe von SSE/AVX vektorisiert, in den anderen Fällen aber schon.

Ich habe folgendes gemessen (mit max=2000):

auto mybuff=buffer[omp_get_thread_num()];         //0.56s
std::unique_ptr<int[]> mybuff(new int[buffSize]); //0.50s
std::unique_ptr<int[]> mybuff(new int[buffSize]); //0.43s (mit jemalloc)
int mybuff[buffSize];                             //0.40s (VLAs sind eine gcc extension)
auto mybuff=(int*)alloca(buffSize*sizeof(int));   //0.38s

Generell würde ich dir empfehlen, alle deine Projekte gegen jemalloc zu linken. Gerade wenn dein Programm mehrere Threads benutzt, bekommst du so einen erheblichen Geschwindigkeitsschub ohne dafür etwas tun zu müssen.

[OhMyPie]

Hi hatte wohl nicht ganz eindeutig geschrieben, sorry.
Das sollte nur ein allgemeines Beispiel sein. Die 10% waren bei meinem richtigen Programm. Mir ging es hauptsächlich darum wo und wie ich den Speicher anlege und wo und wie ein Thread weiß welchen Speicher er nehmen soll. In dem Beispiel ist der Buffer auch nur 100 groß (ovar^2).

Derzeit habe ich ein alligend malloc für SSE. Bin mir aber nicht ganz sicher, ob das wirklich richtig funktionert "#pragma omp simd" nützen fast nix. Vielleicht besser mit anderen malloc.
Jemalloc und alloca kannte ich bisher nicht. std::unique_ptr auch noch nicht verwendet. Werde ich mir mal anschauen. Alloca scheint ja noch schneller als jemalloc zu sein.

[OhMyPie]

alloca ist in meinen Programm (nicht dem Beispiel) etwa so schnell wie meine derzeitige Version (sogar 1% schneller im Test).
So weit ich gelesen habe, scheint das nicht umbedingt Standard zu sein und mit inline kann da auch etwas schief gehen, sollte bei mir aber nicht. Nicht sicher, ob ich es verwenden sollte.
VLA und jemalloc scheinen auch gut zu sein aber dann ist die Verwendung des Programmes nur mit Einschänkungen für andere Nutzer möglich.

[zerg]

OhMyPie schrieb:

VLA und jemalloc scheinen auch gut zu sein aber dann ist die Verwendung des Programmes nur mit Einschänkungen für andere Nutzer möglich.

Welche Einschränkungen soll denn jemalloc verursachen? Du linkst die Bibliothek und fertig.

OhMyPie schrieb:

So weit ich gelesen habe, scheint das nicht umbedingt Standard zu sein und mit inline kann da auch etwas schief gehen, sollte bei mir aber nicht.

GCC inlined standardmäßig keine Funktionen, die alloca verwenden. alloca gehört nicht zur C++-Standardbibliothek, steht aber auf allen Betriebssystemen zur Verfügung.

[OhMyPie]

jemalloc musste ich erst herunterladen. Kann nicht sicher sein, dass die Nutzer Adminrechte haben. Es mit zum Programm hinzufügen will ich aber auch nicht. Für andere Programme könnt ich es aber verwenden.
Soweit ich gelesen habe muss man bei alloca mindestens "-ansi" oder "-std=c++xx" angeben, damit nicht inlined wird. Es steht zwar bei allen Betriebssystemen zur Verfügung, die Implementation kann aber unterschiedlich sein.
Ich werde noch ein wenig testen.

[zerg]

OhMyPie schrieb:

Kann nicht sicher sein, dass die Nutzer Adminrechte haben.

Weder der Entwickler noch der Nutzer benötigt Adminrechte. Kompilieren kannst du die Bibliothek natürlich auch ohne Adminrechte und du wenn du jemalloc statisch linkst, ändert sich für den Nutzer nichts.

OhMyPie schrieb:

Soweit ich gelesen habe muss man bei alloca mindestens "-ansi" oder "-std=c++xx" angeben, damit nicht inlined wird.

?? Wo hast du das gelesen? Ist allerdings für deinen Fall ohnehin irrelevant. Hier werden keine derart horrende Datenmengen alloziiert, als dass Probleme mit inline auftreten könnten.

[OhMyPie]

Ja kompilieren kann man sie auch ohne Rechte. Der Nutzer soll es ja auch selber kompilieren können. Das soll nach Möglichkeit einfach bleiben.

http://man7.org/linux/man-pages/man3/alloca.3.html
"Normally, gcc(1) translates calls to alloca() with inlined code.
This is not done when either the -ansi, -std=c89, -std=c99,..."

In dem richtigen Programm kann der benötigte Stack Speicher schon paar MB groß werden. Jeder Omp thread hat da seinen eigenen, oder? setrlimit() ist nur für Linux und Mac?

[zerg]

Ja, wenn die Buffer auch deutlich größer werden können als die ~400 Bytes hier, würde ich alloca nicht verwenden.
Bzw. verwende ich persönlich sowieso nie.

Das mit jemalloc musst du selbst wissen. Du kannst den Source der Bibliothek mitliefern oder aber einfach jemalloc als Option im configure script/Makefile haben.

Wenn es um Performance geht, halte ich es aber für Pflicht, einen guten Allokator einzusetzen und jemalloc ist eben der beste. Die Standardallokatoren von Windows/Linux/Mac OS X sind zwar brauchbar aber trotzdem eher bescheiden, gerade in Programmen die mit vielen Threads arbeiten.

Unter Linux kommt erschwerend dazu, dass der Standardallokator kleine Allokationen nie wieder an das OS zurückgibt, jemalloc aber schon. Ohne jemalloc würde ich auf meinen Servern zig GB an RAM verschenken.

[OhMyPie]

Habe mal getestet. Mit 8MB Stack (Standard bei mir), würde man ganz gut hinkommen.
In 99% der Fälle wird man nicht mehr brauchen. Zumindest mit den heutigen home PC's nicht. Mein PC würde damit 3 Wochen rechnen...
Normal wird man nicht über ein 1MB kommen. Normal sind vielleicht 100KByte. Ist dann alloca noch empfehlenswert?

Unabhängig davon wie ich es nun mache, angenommen jemalloc, alloca, VLA sind keine Lösung, wie implementiert man das dann?

[zerg]

Wenn du alloca verwenden willst, muss garantiert sein, dass die Größe im Rahmen bleibt. Für einen stack overflow kannst du keine vernünftige Fehlerbehandlung schreiben, das darf nie passieren.

Im Zweifelsfall einfach die Variante 2 mit normaler dynamischer Allokation nehmen, da kann nichts schief gehen. Wenn ich alle Register ziehen möchte (bei 3 Wochen Laufzeit sind jede 10% Einsparung immerhin zwei Tage), würde ich es so machen, mit maxAllocaSize <= 500K:

#ifndef HAVE_ALLOCA
std::unique_ptr<int[]> mybuff(new int[buffSize]);
#else
std::unique_ptr<int[]> heapbuff;
int* mybuff=0;

if (buffSize*sizeof(int)<maxAllocaSize)
{
  mybuff=(int*)alloca(buffSize*sizeof(int));
}
else
{
  heapbuff.reset(new int[buffSize]);
  mybuff=&heapbuff[0];
}
#endif

Aber wahrscheinlich lässt sich durch das Optimieren der Berechnung selbst weitaus mehr rausholen. Womöglich ist sogar der Buffer überflüssig, aber das kann ich nicht beurteilen.

[OhMyPie]

Ich werde mal testen wie schnell std::unique_ptr<int[]> läuft (muss dazu bisschen mehr ändern, Unterfunktionen etc).
Wenn ich beides verwende, bleibt noch die Frage wie ich maxAllocaSize bekomme. Gibt es da etwas, dass alle gängigen Betriebssystem und Kompiler unterstützen?
getrlimit() ?