WIe schnell sind STL-Listen

FelixManke

Hi,

ich brauche für ein 3D-Partikelsystem eine Liste zur Speicherung der einzelnen Partikel. Hier kommt es natürlich stark auf die Performance an. Nun meine Frage: Wie schnell und optimal programmiert sind STL-Listen? Und welcher Container ist der Schnellste?

Shade Of Mine

welche operationen willst du denn ausführen?

einfügen in der mitte?
schneller index zugriff?
schnell iterieren?
oft die größe ändern? (einfügen, löschen)

rüdiger

Wie schnell und optimal programmiert sind STL-Listen?

das kann man nicht sagen, dass hängt von der Implementierung ab. Mach doch einfach ein paar Tests. Wobei ich bei einem Partikel System eher ein vector nehmen würde

Und welcher Container ist der Schnellste?

wobei? Du musst dir immer bewusst sein, was du mit dem Container machst. Wenn du viel löschst und einfügst, kann die Liste schneller sein. Wenn du viel iterierst und wenig löschst und einfügst, ist vermutlich der Vector schneller.

Für am besten selbst mal ein paar Tests durch, damit du dafür ein Gefühl entwickelst.

FelixManke

Ja, da habt ihr natürlich recht. Mein Fehler. Gelöscht wird eigentlich nicht, denke ich.

Aber noch ein ganz anderes Problem, was mir mittlerweile aufgefallen ist. Dafür mal ein wenig mehr Information. Ich habe ein Basis-Partikelsystem. Dort möchte ich alle Funktionalität reinpacken, die allen verschiedenen Partikelsystemen gemeinsam ist.

Eine aktuelle Position jedes Partikels
DIe Werte an die Grafikkarte schicken. Dafür muss die Position in einen Puffer kopiert werden.

Desweiteren habe ich abgeleitete Partikelsysteme. Diese erweitern die Partikel (Geschwindigkeit, ...) und aktualisieren deren Werte, so, wie sich das Partikelsystem verhalten soll.

Ich wollte das ganze eigentlich wie folgt implementieren (Auszüge):

public class BaseParticleSystem
{
private:
    /// copies all relevant data within the particles to the vertexbuffer
    HRESULT    CopyToVertexBuffer();
protected:
    /// structure to hold the particle's data
    typedef struct BaseParticle
    {
        /// current position
        D3DXVECTOR3 pos;
    }BaseParticle;

    /// vertex buffer of all particles
    CComPtr<IDirect3DVertexBuffer9> m_vertexBuffer;    
    /// Pointer to an array of particles
    BaseParticle*  m_particles;
...
};

class TestObject :
    public BaseParticleSystem
{
protected:
    typedef struct TestParticle : public BaseParticle
    {
        // velocity
        D3DXVECTOR3 vel;
        // init. time
        double t0;
        // lifetime in millis
        float lifetime;
    }TestParticle;

    virtual HRESULT UpdateParticles();

...
};

Soweit erstmal. Die CopyToVertexBuffer-Funktion ist momentan wie folgt, aber falsch! Bitte nicht an dem hr = m_vertexBuffer->Lock... stören, dass muss leider so sein. DirectX...

HRESULT    BaseParticleSystem::CopyToVertexBuffer()
{
    HRESULT hr = S_OK;
    if(m_vertexBuffer == NULL)
        return E_FAIL;

    PSystemVertex* pVBuff;
    BaseParticle* b = m_particles;
    hr = m_vertexBuffer->Lock(0, m_numParticles * sizeof(EffectPSVertex),(void**)&pVBuff, 0);
    for(UINT i = 0; i < m_numParticles; i++)
    {
        pVBuff->pos = b->pos;
        pVBuff++;
        b++;
    }
    hr = m_vertexBuffer->Unlock();

    return hr;
}

Wie schaffe ich es am einfachsten, dass das Kopieren der Position gelingt? Momentan kopiert er halt bei i == 0 die Position, bei i == 1 die 'vel' usw. Wenn ich einen STL-Vector nehme, kann ich da von BaseParticle ableiten??

HILFE!!

RHBaum

prinzipiell:

Wenn es wirklich um geschwindigkeit gehen soll ....

DIe Werte an die Grafikkarte schicken. Dafür muss die Position in einen Puffer kopiert werden.

damit steht ein Teil deiner Datenstruktur!
Sprich ich wuerde meine Klasse so aufbauen, dass aus deren datenstruktur direkt auf den Puffer verweisen kannst ... sprich die Daten binaer so vorliegen, wie sie die Graka braucht.
AUch wenn sie trotzdem kopieren musst, ists besser du kannst es in einem rutsch, als scheibenweisse woher zusammenbauen und womoeglich noch iteratoren fuer benutzen wollen.
Meist sind dass c-arrays die man braucht. Vorsicht ! normal sollte ein std::vector die daten auch in C-Array-Form ablegen. Meistens tut er es auch, es soll aber implementationen geben ....
Ich denk mal, du willst eh nicht plattformunabhaengig programmieren, also schau wie sich deine STL Impl verhaelt, und nutze vectoren. die M$ Impl haelt sich zumn beispiel dran, der STLPort auch.
2.

Desweiteren habe ich abgeleitete Partikelsysteme.

Was genau verstehst du unter abgeleitet ? Das ist ja schon ne halbe Implementationsvorschrift ! :p
wiederverwendbarkeit kann man ned nur durch ableiten erreichen .... Ableiten bringt leider laufzeitoverhaed durch die vtables . Manchmal laesst es sich aber nicht vermeiden.
schau dir mal an, wie die std::string klasse implenetiert ist.
also besser gesagt std::basic_string< char,char_traits<char>,allocator<char> > ...
Und schau ob du so aehnlich wie da grundlegende verhaltensmuster (traits, allocator, policies) definieren kannst und um die dann zu der Endklasse zusammenzusetzen (ohne Polymorphie) ....
Dazu ist natuerlich etwas tiefgruendigeres wissen ueber templates noetig.
Aber du willst ja Geschwindigkeit (ich hoffe ned beim compilieren) ....

Ciao ...

P.S.
die STL ist schnell, wenn man ne vernuenftige Impl verwendet und wenn man sie richtig verwendet, ich glaub mal der unterschied zu reinem C code ist bei der Rechenleistung der heutigen maschinen doch eher vernachlaessigbar.

Ciao ...

Helium

Wie schnell und optimal programmiert sind STL-Listen?

In nur 4 Wochen. Und in der Optimalheitsbewertung gibt's 'ne glatte 42.