Speichersparend verindexen statt verpointern

Hallo,

Ich will eine Triangulierung, also sowas:

http://img705.imageshack.us/img705/6662/debug2.gif

speichereffizient und schnell für mehrere Mio. Punkte implementieren.

Ansatz 1: Die Dreiecke und Punkte werden am Heap erzeugt und jedes Dreieck
speichert Pointer auf die 3 Eckpunkte und die 3 Nachbardreiecke, also 6 Pointer
a' 8 Bytes pro Dreieck auf einer 64bit-Maschine.

Ansatz 2: Die Dreiecke und Punkte liegen in Arrays, und jedes Dreieck speichert
nur Indizes auf seine Eckpunkte und Nachbardreiecke, also 6 Integer a' 4 Bytes,
auch auf 64bit-Maschinen.

Ansatz 1 ist teuer bezüglich Speicherkonsum. Ansatz 2 ist deutlich billiger,
aber auch langsamer. Fällt Euch was besseres als Ansatz 2 ein? Wichtig ist,
daß der Zugriff verdammt schnell geht, da diese Informationen häufig abgefragt
oder geändert werden.

lg

drakon

Ich denke, dass es auf die Art des Zugriffes ankommt, den du machst. Wie sieht denn das übeliche Zugriffszenario aus? Ändern an benachbarten Dreiecken, oder wild herum?

Ich persönlich würde mal zu Ansastz 1 tendieren, bis ich merke, dass der Speicher wirklich ausschlaggebend wird.

drakon schrieb:

Ich denke, dass es auf die Art des Zugriffes ankommt, den du machst. Wie sieht denn das übeliche Zugriffszenario aus? Ändern an benachbarten Dreiecken, oder wild herum?

Ich persönlich würde mal zu Ansastz 1 tendieren, bis ich merke, dass der Speicher wirklich ausschlaggebend wird.

Alle Operationen arbeiten ausschließlich mit den genannten Nachbarschafts-
beziehungen, also lokal in zusammenhängenden Gebieten. Daher müssen diese
Nachbarschaftsbeziehungen schnell sein. Speicher ist wegen großer Daten-
mangen ausschlaggebend, daher habe ich Ansatz 2 eingeführt. Mir fällt nix
mehr ein, aber vielleicht gibts noch einen Ansatz 3, der besser ist?

lg :xmas2:

knivil

Wichtig ist, daß der Zugriff verdammt schnell geht, da diese Informationen häufig abgefragt oder geändert werden.

Das sagt absolut ueberhaupt nichts aus. Zu welchem Zweck werden Nachbarschaftsinformationen wie abgefragt? Um wieviel MByte an Daten geht es? (mehrere Millionen Dreiecke ergeben 8 MByte?)Welche Operationen? etc. etc. ... Ansaetze sind vielleicht double connected edge list oder trapezoidal map. Aber normalerweise tauscht man Speicher gegen Geschwindigkeit, beides geht meist nicht.

knivil schrieb:

Wichtig ist, daß der Zugriff verdammt schnell geht, da diese Informationen häufig abgefragt oder geändert werden.

Das sagt absolut ueberhaupt nichts aus. Zu welchem Zweck werden Nachbarschaftsinformationen wie abgefragt? Um wieviel MByte an Daten geht es? (mehrere Millionen Dreiecke ergeben 8 MByte?)Welche Operationen? etc. etc. ... Ansaetze sind vielleicht double connected edge list oder trapezoidal map. Aber normalerweise tauscht man Speicher gegen Geschwindigkeit, beides geht meist nicht.

1 Mio. Punkte ergeben 2 Mio Dreiecke, und alleine die Nachbarschaftsbeziehungen
dafür kosten nach dem ersten Ansatz 6 * 8 * 2000000 = 96 MB. Die Nachbarschaften
werden abgefragt, um zusammenhängende Zonen mit bestimmten Eigenschaften zu
finden. DCEL ist eine Überlegung wert, muß mal überlegen, ob das in mein Konzept
geht, danke.

lg

hustbaer

Ich denke auch dass Ansatz 2 besser sein wird.
Nicht nur was Speicherverbrauch angeht, sondern u.U. auch was die Geschwindigkeit angeht.
Zig Millionen kleine Speicheranforderungen sind nicht gerade billig...

Ansatz 2 wird nur dann lästig, wenn man mal Dreiecke und/oder Punkte löschen will. Dann muss man entweder alle Indizes anpassen (laaaaaaaangsam), oder die Dreiecke/Punkte nicht wirklich löschen, sondern einfach den Platz im Array unbenutzt lassen. Ggf. kann man auch eine eigene Free-List programmieren, in der man Indizes von unbenutzten Dreiecken/Punkten zur Wiederverwendung abspeichert.

Was spricht gegen Ansatz 2, wobei die Arrays in Blöcken auf dem Heap erzeugt werden.

Siassei

hustbaer schrieb:

Zig Millionen kleine Speicheranforderungen sind nicht gerade billig...

Für sowas verwendet doch man einen Pool! Selbst implementiert oder einen fertigen.

z.B.

unsigned int size = /* Vorausberechnete Größe oder geschätzt anhand ein paar Parameter */;

void *raw = operator::new(size);
// Oder void *raw = malloc(size);

Dreieck *rawD = (Dreieck*) raw;

Dreieck *p = new (rawD) Dreieck(10,1,25);
rawD++; // Vorsicht vor überlauf!

[cpp]

hustbaer

Siassei schrieb:

hustbaer schrieb:

Zig Millionen kleine Speicheranforderungen sind nicht gerade billig...

Für sowas verwendet doch man einen Pool! Selbst implementiert oder einen fertigen.

Ja kann man. Ich finde die Variante mit einem Array (std::vector) trotzdem besser.
Ist denke ich inetwa gleich viel Aufwand. Vom Speicherverbrauch mal abgesehen würde ich sagen ist es einfach Geschmackssache.

BTW: den grössten Geschwindigkeitsgewinn würde es hier wohl bringen, wenn man die Dreiecke/Punkte Cache-freundlich arrangieren könnte. Wenn man das Zugriffsmuster kennt, und daraus eine günstige Anordnung ableiten kann, kann man das mit einem Array ganz einfach umsetzen. Mit einem Allokator (egal ob Pool oder sonstwas) ginge das nur, wenn man auch den Allokator kontrolliert. Und man schafft dadurch eine zusätzliche Abhängigkeit: wenn der Allokator geändert wird, kann es sein, dass die Anordnung auf einmal garnichtmehr Cache-freundlich ist.