Serialisierung

Blackthorne

Ich möchte zwischen zwei Prozessen, die auf verschiedenen Rechnern laufen, Objekte/Strukturen austauschen. Als Kommunikationsbibliothek nutze ich MPI. Da ich die von MPI bereitgestellten Operationen MPI_Pack und MPI_Unpack meiden will/muss, muss ich die Attribute der Objekte/Strukturen per Hand in einen zusammenhängenden Speicherbereich (Sendepuffer) umkopieren, den Inhalt des Buffers zum Empfänger schicken und dort wieder entpacken.

Kann mir jemand verraten, wie ich das Umkopieren eines Objekts/einer Struktur in einen zusammenhängenden Speicherbereich am geschicktesten/schnellsten löse?

Nehmen wir als Beispiel diese Struktur und die unten stehende Methode reduce:

struct Problem {
	int size;
	vector<int> v;
	Problem(): v(0) {}; // zu verschickende Probleme sind unterschiedlich gross!
};

// IN: Problem p
// OUT: Zeiger auf Sendepuffer (char*) und Grösse des Puffers (pSize)
char* reduce(Problem* p, int* pSize) {
    // benötigte Bytes zur Speicherung des Objekts berechnen
    *pSize = sizeof(int) + sizeof(int) * p->v.size();

  // Speicher anfordern (was ist schneller: malloc oder array???)
  // char* buffer = new char[*pSize];    // ???
  char* buffer = (char*) malloc(*pSize); // ???

  // Struktur in den Puffer schreiben

  // ... WIE MACHT MAN DAS AM BESTEN/SCHNELLSTEN ???

  return buffer;
}

Wer hat eine gute Idee und kann mir helfen!?

thordk

afaik liegen die elemente eines std::vectors im speicher hintereinander, wie bei einem array. also solltest du die einfach mit memcpy in den buffer schaufeln können.

DDR-RAM

in der Regel unterscheidet sich operator new von malloc nur durch einen jmp zu malloc. Es bleibt dir überlassen. Du solltest bloß nicht durcheinander kommen mit der Freigabe.
Wenn die Probleme alle in diese Struktur passen, dann wird memcpy wohl das einfachste und schnellste sein. Aber das kann auch gefährlich sein, je nachdem was du kopierst. Ich würde eher folgende Variante wählen:

char* reduce(Problem* p, int* pSize)
{
    // benötigte Bytes zur Speicherung des Objekts berechnen
    *pSize = sizeof(int) + sizeof(int) * p->v.size();

    // Speicher anfordern 
    char* buffer = new char[*pSize];
    char* tmp = buffer;
    // Struktur in den Puffer schreiben
    new (tmp) int(p->size);
    tmp += sizeof(int);
    for (It i = p->v.begin(); i != p->v.end(); ++i)
    {
        new (tmp) int(*i);
        tmp += sizeof(int);  // edit von i auf int
    }

    return buffer;
}

Blackthorne

@thordk:
Es ist zwar richtig, dass Vektoren intern auf C-Arrays basieren, allerdings kann ich nicht einfach ab der Adresse des Vektors mit memcpy loskopieren. Da stehen ja noch andere Attribute in der Vektorklasse, z.B. size, die mich an der Stelle ja gar nicht interessieren. Ausserdem können in einem Vektor auch mehrere Objekte liegen, in denen Zeiger stecken. Ich will ja nicht die Zeiger kopieren, sondern deren Inhalte. Man denke sich daher ein beliebig verschachteltes Objekt, z.B.

class A {
    int* x;
    vector<int> v;
    B* b; // Dieses Objekt muss ebenfalls serialisiert werden
}

class B {
    int* a;
    long l; 
}

Zyklische Strukturen müssen dann natürlich auch berücksichtigt werden. Das soll hier aber nicht das Thema sein.

DDR-RAM

Bau dir ne Art stream.

class myByteStream
{
    int   m_nSize;
    char* m_pBufferStart;
    char* m_pBufferCur;
public:
    myByteStream(int nSize) :
        m_nSize(nSize),
        m_pBufferStart(new char[nSize]),
        m_pBufferCur(m_pBufferStart)
    {
    }

public:
    myByteStream& operator <<(int i)
    {
        *reinterpret_cast<int*>(pBufferCur) = i;
        pBufferCur += sizeof(int);
        return  *this;
    }
//  usw..
    myByteStream& operator <<(char i);
    myByteStream& operator <<(long i);
    myByteStream& operator <<(short i);
//  usw..
};

class A {
    int* x;
    vector<int> v;
    B* b; // Dieses Objekt muss ebenfalls serialisiert werden
    friend myByteStream& operator << (myByteStream& rStream, const A& r);
}

myByteStream& operator << (myByteStream& rStream, const A& r)
{
    rStream << *r.x << r.v << *r.b;
    return rStream;
}
template <class T, class U>
myByteStream& operator << (myByteStream& rStream, const std::vector<T, U>& r)
{
    for (It i = r.begin(); i != r.end(); ++i)
        rStream << *i;

    return rStream;
}

Verstehe es als Idee

MfG
DDR-RAM

thordk

Blackthorne schrieb:

@thordk:
Es ist zwar richtig, dass Vektoren intern auf C-Arrays basieren, allerdings kann ich nicht einfach ab der Adresse des Vektors mit memcpy loskopieren. Da stehen ja noch andere Attribute in der Vektorklasse, z.B. size, die mich an der Stelle ja gar nicht interessieren.

nicht von der adresse des vektors, von der adresse des ersten elements. wobei ich mich frag, wieviel langsamer ein zugriff über iteratoren is. soviel langsamer kanns eigentlich gar nicht sein.

ist das ganze so zeitkritisch, dass jeder rausgekitzelter zyklus ne rolle spielt? gerade bei abhängigen verteilten systemen sind die netzwerk latenzen u.u. so dramatisch hoch, dass sich optimierung bei der serialisierung kaum lohnt.

camper

@DDR-RAM:Das ist soweit eine gute Idee, nur zwei Hinweise:
Da die Erweiterung durch zusätzliche Operatoren << bzw. >> von vornherein vorgesehen ist, sollten am besten alle diese Operatoren als freie Funktionen implementiert werden. Bei std::basic_ostream ist das z.B. nicht der Fall mit der Konsequenz, so daß Konstrukte wie

(std::ostringstream()<<"foo").str()

zwar funktionieren, aber nicht das tun, was man naiverweise erwartet.

*reinterpret_cast<int*>(pBufferCur)

das ist schlicht böse, da pBufferCur im Allgemeinen nicht hinreichend ausgerichtet ist (das trifft auch den vorherigen Code mit placement new, wenn verschiedene Typen gemischt werden). Das ist ein legitimer Einsatzort für memcpy. Besser noch eine definierte Konvertierungsroutine, die möglichst unabhängig ist von Parametern der eingesetzten Plattform wie der Größe und des Layouts von skalaren Typen. Letzters wird allerdings ggf. mit Performanceeinbußen verbunden sein; solange hier keine Unterschiede zwischen Sender und Empfänger existieren, ist ein schlichtes memcpy genauso gut.

DDR-RAM

camper schrieb:

@DDR-RAM:Das ist soweit eine gute Idee, nur zwei Hinweise:
Da die Erweiterung durch zusätzliche Operatoren << bzw. >> von vornherein vorgesehen ist, sollten am besten alle diese Operatoren als freie Funktionen implementiert werden. Bei std::basic_ostream ist das z.B. nicht der Fall mit der Konsequenz, so daß Konstrukte wie
(std::ostringstream()<<"foo").str()
zwar funktionieren, aber nicht das tun, was man naiverweise erwartet.

Da steh ich jetzt aufm Schlauch.

*reinterpret_cast<int*>(pBufferCur)
das ist schlicht böse, da pBufferCur im Allgemeinen nicht hinreichend ausgerichtet ist (das trifft auch den vorherigen Code mit placement new, wenn verschiedene Typen gemischt werden).

muss operator new nicht einen mindestens auf sizeof(int) aligned pointer liefern? Ich bin mir da jetzt nicht sicher.

Das ist ein legitimer Einsatzort für memcpy. Besser noch eine definierte Konvertierungsroutine, die möglichst unabhängig ist von Parametern der eingesetzten Plattform wie der Größe und des Layouts von skalaren Typen. Letzters wird allerdings ggf. mit Performanceeinbußen verbunden sein; solange hier keine Unterschiede zwischen Sender und Empfänger existieren, ist ein schlichtes memcpy genauso gut.

Naja, schlichtes memcpy. Wenn man POD's ohne Zeiger und Referenzen hat, dann mag das stimmen, aber das scheint nicht der Fall zu sein.

MfG
DDR-RAM

camper

DDR-RAM schrieb:

camper schrieb:
@DDR-RAM:Das ist soweit eine gute Idee, nur zwei Hinweise:
Da die Erweiterung durch zusätzliche Operatoren << bzw. >> von vornherein vorgesehen ist, sollten am besten alle diese Operatoren als freie Funktionen implementiert werden. Bei std::basic_ostream ist das z.B. nicht der Fall mit der Konsequenz, so daß Konstrukte wie
(std::ostringstream()<<"foo").str()
zwar funktionieren, aber nicht das tun, was man naiverweise erwartet.
Da steh ich jetzt aufm Schlauch.

probier einfach ein

#include <iostream>
#include <ostream>
#include <sstream>
#include <string>
using namespace std;
int main()
{
    cout << static_cast<ostringstream&>(ostringstream()<<"foo").str();
}

DDR-RAM schrieb:

*reinterpret_cast<int*>(pBufferCur)
das ist schlicht böse, da pBufferCur im Allgemeinen nicht hinreichend ausgerichtet ist (das trifft auch den vorherigen Code mit placement new, wenn verschiedene Typen gemischt werden).
muss operator new nicht einen mindestens auf sizeof(int) aligned pointer liefern? Ich bin mir da jetzt nicht sicher.

Das ist richtig, daher der Nebensatz. Wenn du es mit ein und demselben Typen zu tun hast, besteht kein Problem.

DDR-RAM schrieb:

Das ist ein legitimer Einsatzort für memcpy. Besser noch eine definierte Konvertierungsroutine, die möglichst unabhängig ist von Parametern der eingesetzten Plattform wie der Größe und des Layouts von skalaren Typen. Letzters wird allerdings ggf. mit Performanceeinbußen verbunden sein; solange hier keine Unterschiede zwischen Sender und Empfänger existieren, ist ein schlichtes memcpy genauso gut.

Naja, schlichtes memcpy. Wenn man POD's ohne Zeiger und Referenzen hat, dann mag das stimmen, aber das scheint nicht der Fall zu sein.

MfG
DDR-RAM

Ich meine damit ausschließlich die Implementation für skalare Typen (ganz so, wie du es wohl mit deinem reinterpret_cast beabsichtigst). Es geht ja gerade darum, dass der Benutzer von irgendwelchen Klassen selbst einen geeigneten Operator überlädt (das muss er sowieso tun), der selbst nicht auf memcpy baut, sondern die einzelnen Member über die vorgegebenen Operatoren in geeigneter Weise serialisiert. Schließlich gibt es keinen Grund, das Ganze auf PODs zu beschränken. Im Übrigen sind Klassen mit Referenzen niemals PODs, damit ist die Anwendung von memcpy auf die gesamte Klasse ohnehin ausgeschlossen.

Blackthorne

thordk schrieb:

ist das ganze so zeitkritisch, dass jeder rausgekitzelter zyklus ne rolle spielt? gerade bei abhängigen verteilten systemen sind die netzwerk latenzen u.u. so dramatisch hoch, dass sich optimierung bei der serialisierung kaum lohnt.

Bei verteilten Systemen ist das richtig. Allerdings beschäftige ich mich nicht mit verteilten Systemen, sondern mit Parallelrechnern (mit verteiltem Speicher) bzw. Rechenclustern. Dort hat man i.d.R. ein extrem schnelles Netzwerk (in meinem Fall ein Myrinet). Um ein Problem parallel lösen zu können, müssen Teilprobleme generiert und auf die einzelnen Prozessoren verteilt werden. Diese Teilprobleme werden durch die Objekte/Strukturen beschrieben, die ich verschicken will. Damit die parallelen Algorithmen gut skalieren, ist eine effiziente Implementierung der Kommunikation extrem wichtig. Daher bin ich für jede Anregung dankbar, wie man das Serialisierungsproblem auch noch lösen kann...