C/C++ Programmierung: Einen eigenen Memory-Manager entwickeln

Verkettete Listen sind eine schöne Sache. Sie zeugen von Eleganz, man kann mit ihnen angeben und sie sind langsam. Spaß beiseite, warum sind verkettete Listen langsam? Wenn man irgendeinen Knoten suchen muss, sei es, um ihn zu löschen oder um sonst etwas mit ihm zu machen, muss erst einmal die ganze Liste bis zum gesuchten Knoten durchlaufen werden. Erschwerend kommt hinzu, dass die Reihenfolge, in der die Game-Objekte in der Liste abgespeichert sind, normalerweise nicht der Reihenfolge entspricht, in der man auf diese Objekte Zugriff nehmen muss. Und wenn einmal nicht genügend Speicher vorhanden ist und die Erzeugung eines neuen Objekts fehlschlägt, bringt das bestenfalls den Spielablauf durcheinander.

Die soeben besprochenen Probleme können durch die Verwendung von Arrays umgangen werden. Kritiker werden sicherlich einwenden, dass man Unmengen an Speicherplatz verschenkt und Arrays viel zu unflexibel in der Anwendung sind.

Diese Annahme ist schlichtweg falsch – jedenfalls was die Spieleprogrammierung betrifft. Man stelle sich ein 3D-Szenario vor, in dem einige Asteroiden platziert werden sollen. Was spricht dagegen, eine Obergrenze für deren Anzahl festzulegen? Aus Performancegründen können sowieso nicht beliebig viele Objekte animiert und gerendert werden. Speicherverschwendung ist das auch nicht, wenn man davon ausgeht, dass zu irgendeinem Zeitpunkt die Obergrenze erreicht wird. Weiterhin ist der Zugriff auf ein Arrayelement deutlich schneller möglich als der Zugriff auf ein Element der verketteten Liste.

Im Folgenden soll ein einfaches System für die Speicherverwaltung vorgestellt werden, das mit vorinitialisierten Arrays arbeitet. Je nach konkreter Anforderung kann der Memory-Manager beliebig erweitert werden. Hier nun die Objekt-Klasse, deren Instanzen es zu verwalten gilt:

// Macros:
#define SAFE_DELETE(p) {if(p) {delete (p); (p)=NULL;}}
#define SAFE_DELETE_ARRAY(p) {if(p) {delete[] (p); (p)=NULL;}}

class CObject
{
public:

    long id;
    bool active;

    CObject()
    {
        active = false;
        id = -1;
    }

    ~CObject()
    {}

    // Neues Objekt initialisieren:
    void Initialize(long ID)
    {
        active = true;
        id = ID;
    }

    // Objekt freigeben, Aufräumarbeiten durchführen:
    void TurnBack(void)
    {
        active = false;
        id = -1;
    }

    // Irgend eine Aktion mit dem Objekt durchführen:
    void Do_Something(void)
    {
        if(active == false)
            return;

        // Aktion durchführen:
        printf("Objekt ID: %d\n", id);
    }
};

Die CObject_Memory_Manager-Manager-Klasse stellt mit Init_Memory_Manager() eine Methode zum Vorinitialisieren des Spieleobjekt-Arrays, mit New_Object() eine Methode zum Initialisieren eines neuen Spieleobjekts, mit Do_Something() eine Methode zum Handling aller aktiven Spieleobjekte sowie mit Delete_All_Objects_In_List(), Delete_Object_With_IndexNr() und Delete_Object_With_ReadingOrderPositionNr() drei Methoden zum Löschen aktiver Spieleobjekte bereit.

class CObject_Memory_Manager
{
public:

    // Zeiger auf das Spieleobjekt-Array:
    CObject* pObject;

    long Element_UnUsed;
    long NoMore_Element;

    // Zeiger auf das pReadingOrder-Array:
    long* pReadingOrder;

    // Zeiger auf das pUsedElements-Array:
    long* pUsedElements;

    // Anzahl der aktiven Elemente:
    long NumActiveElements;

    // Array Größe:
    long Size;

    CObject_Memory_Manager()
    {
        pUsedElements = NULL;
        pReadingOrder = NULL;
        pObject = NULL;

        NumActiveElements = 0;
        Size = 0;
    }

    ~CObject_Memory_Manager()
    {
        SAFE_DELETE_ARRAY(pUsedElements)
        SAFE_DELETE_ARRAY(pReadingOrder)
        SAFE_DELETE_ARRAY(pObject)
    }

    void Init_Memory_Manager(long size = 20);
    void New_Object(void);
    void Do_Something(void)
    void Delete_All_Objects_In_List(void);

    void Delete_Object_With_IndexNr(long id);

    void Delete_Object_With_ReadingOrderPositionNr(long nr);

};

Hier nun die Methode zum Vorinitialisieren des Spieleobjekt-Arrays:

void CObject_Memory_Manager::Init_Memory_Manager(long size = 20)
{
    SAFE_DELETE_ARRAY(pUsedElements)
    SAFE_DELETE_ARRAY(pReadingOrder)
    SAFE_DELETE_ARRAY(pObject)

    Element_UnUsed = -10000;
    NoMore_Element = -10000;

    Size = size;

    // In dieser Liste stehen die Indices aller
    // aktiven CObject-Array-Elemente
    // Die Liste wird immer mit NoMore_Element
    // abgeschlossen, darum das +1!
    pReadingOrder = new long[Size+1];

    // In dieser Liste wird eingetragen, ob ein
    // CObject-Array-Element aktiv oder inaktiv ist.
    // Bei einer Neuinitialisierung wird hier nach dem
    // ersten nicht benutzten Element gesucht:
    pUsedElements = new long[Size];

    // Hier wird das Array für die Game-Objekte erzeugt.
    // Zu Beginn sind alle Elemente unbenutzt, das wird in die
    // pUsedElement-Liste eingetragen:
    pObject = new CObject[Size];

    for(long i = 0; i < Size; i++)
    {
        pUsedElements[i] = Element_UnUsed;
    }

    // Zur Zeit kein aktives Spieleobjekt:
    pReadingOrder[0] = NoMore_Element;
    NumActiveElements = 0;
}

Beim Initialisieren eines neuen Spieleobjekts wird innerhalb einer Schleife erst einmal nach einem unbenutzten CObject-Array-Element gesucht. Ist dieses gefunden, dann wird es initialisert. In die pUsedElements-Liste wird eingetragen, dass das betreffende Element jetzt verwendet wird. In die pReadingOrder-Liste wird der Index des neuen Elements eingetragen. Die Anzahl der aktiven Elemente wird um 1 erhöht und die pReadingOrder-Liste mit dem Eintrag NoMore_Element abgeschlossen.

void CObject_Memory_Manager::New_Object(void)
{
    for(long i = 0; i < Size; i++)
    {
        if(pUsedElements[i] == Element_UnUsed)
        {
            pObject[i].Initialize(i);
            pUsedElements[i] = i;
            pReadingOrder[NumActiveElements] = i;
            NumActiveElements++;
            pReadingOrder[NumActiveElements] = NoMore_Element;
            break;
        }
    }
}

Die Methode Do_Something() soll das Handling der aktiven Spieleobjekte demonstrieren:

void CObject_Memory_Manager::Do_Something(void)
{
    // In dieser Schleife werden die gewünschten Aktionen mit
    // den CObject-Array-Elementen ausgeführt, deren Indices
    // in der pReadingOrder-Liste stehen:

    long i, j;

    for(j = 0, i = 0; i < Size; i++)
    {
        j = pReadingOrder[i];

        if(j != NoMore_Element)
        {
            pObject[j].Do_Something();
        }
        else if(j == NoMore_Element)
            break;
    }

    // Nach Game-Objekten suchen, die im aktuellen Frame inaktiv
    // geworden sind und diese wieder freigeben:

    for(j = 0,  i = 0; i < Size; i++)
    {
        j = pReadingOrder[i];

        if(j != NoMore_Element)
        {
            if(pObject[j].active == false)
            {
                // Variante 1:
                //Delete_Object_With_IndexNr(j);

                // Variante 2:
                Delete_Object_With_ReadingOrderPositionNr(i);
                i--;
            }
        }
        else if( j == NoMore_Element)
            break;
    }
}

Zum Löschen aller aktiven Spieleobjekte steht die Methode Delete_All_Objects_In_List() zur Verfügung:

void CObject_Memory_Manager::Delete_All_Objects_In_List(void)
{
    NumActiveElements = 0;

    for(long i = 0; i < Size; i++)
    {
        pReadingOrder[i] = NoMore_Element;
        pUsedElements[i] = Element_UnUsed;
        pObject[i].TurnBack();
    }

    pReadingOrder[Size] = NoMore_Element;
}

Mithilfe der Methode Delete_Object_With_IndexNr() wird ein einzelnes Spieleobjekt gelöscht. Identifiziert wird das Objekt über seinen Index (seine ID-Nummer). In der äußeren Schleife wird nach dem zu löschenden Indexeintrag in der pReadingOrder-Liste gesucht. Dieser Eintrag wird dann aus der Liste entfernt, indem die nachfolgenden Einträge um eine Position nach links (vorne) geschoben werden, bis der Eintrag NoMore_Element gefunden wird. Die Anzahl der aktiven Spieleobjekte wird um 1 erniedrigt. In die pUsedElements-Liste wird dann an der zugehörigen Indexposition der Wert Element_UnUsed eingetragen. Anschließend wird das Objekt zurückgesetzt.

void CObject_Memory_Manager::Delete_Object_With_IndexNr(long id)
{
    long i, j;

    for(i = 0; i < Size; i++)
    {
        if(pReadingOrder[i] == id)
        {
            for(j = i; j < Size; j++)
            {
                pReadingOrder[j] = pReadingOrder[j+1];

                if(pReadingOrder[j] == NoMore_Element)
                    break;
            }

            NumActiveElements--;
            pUsedElements[id] = Element_UnUsed;
            pObject[id].TurnBack();

            break;
        }
    }
}

Mithilfe der Methode Delete_Object_With_ReadingOrderPositionNr() wird ein einzelnes Spieleobjekt gelöscht. Identifiziert wird das Objekt über seine Position in der pReadingOrder-Liste. Vorsicht, wenn die Listen-Position nicht besetzt ist, kommt es zum Programmabsturz. Aus dieser Liste muß zunächst der Array-Index des zu löschenden CObject-Array-Elements ermittelt werden. Diese Funktion ist etwas schneller als die vorherige Lösch-Funktion, da der Objekt-Index nicht erst in der pReadingOrder-Liste gesucht werden muß.

void CObject_Memory_Manager::Delete_Object_With_ReadingOrderPositionNr(long nr)
{
    NumActiveElements--;
    pUsedElements[pReadingOrder[nr]] = Element_UnUsed;
    pObject[pReadingOrder[nr]].TurnBack();

    for(long j = nr; j < Size; j++)
    {
        pReadingOrder[j] = pReadingOrder[j+1];

        if(pReadingOrder[j] == NoMore_Element)
            break;
    }
}

class CObject_Memory_Manager
{
public:

    CObject* pObject;

    long Element_UnUsed;
    long NoMore_Element;

    // Zeiger auf pReadingOrder-Array:
    long* pReadingOrder;

    // Zeiger auf pUsedElements-Array:
    long* pUsedElements;

    // Anzahl der aktiven Elemente:
    long NumActiveElements;

    // Array Größe:
    long Size;

    CObject_Memory_Manager(long size = 20)
    {
        Element_UnUsed = -10000;
        NoMore_Element = -10000;

        Size = size;

        // In dieser Liste stehen die Indices aller
        // aktiven CObject-Array-Elemente
        // Die Liste wird immer mit NoMore_Element
        // abgeschlossen, darum das +1!
        pReadingOrder = new long[Size+1];

        // In dieser Liste wird eingetragen, ob ein
        // CObject-Array-Element aktiv oder inaktiv ist.
        // Bei einer Neuinitialisierung wird hier nach dem
        // ersten nicht benutzten Element gesucht:
        pUsedElements = new long[Size];

        // Hier wird das Array für die Game-Objekte erzeugt.
        // Zu Beginn sind alle Elemente unbenutzt, das wird in die
        // pUsedElement-Liste eingetragen:
        pObject = new CObject[Size];

        for(long i = 0; i < Size; i++)
        {
            pUsedElements[i] = Element_UnUsed;
        }

        // Zur Zeit kein aktives Game-Objekt:
        pReadingOrder[0] = NoMore_Element;
        NumActiveElements = 0;
    }

    ~CObject_Memory_Manager()
    {
        SAFE_DELETE_ARRAY(pUsedElements)
        SAFE_DELETE_ARRAY(pReadingOrder)
        SAFE_DELETE_ARRAY(pObject)
    }

    // Hier werden neue Game-Objekte initialisiert:
    void New_Object(void)
    {
        // In dieser Schleife wird erst einmal nach einem unbenutzten
        // CObject-Array-Element gesucht.
        // Ist dieses gefunden, dann wird es initialisert.
        // In die pUsedElements-Liste wird eingetragen, dass das
        // betreffende Element jetzt verwendet wird.
        // Die pReadingOrder-Liste wird um das neue Element
        // erweitert.
        // Die Anzahl der aktiven Elemente wird um 1 erhöht.
        // Die pReadingOrder-Liste wird mit NoMore_Element
        // abgeschlossen.

        for(long i = 0; i < Size; i++)
        {
            if(pUsedElements[i] == Element_UnUsed)
            {
                pObject[i].Initialize(i);
                pUsedElements[i] = i;
                pReadingOrder[NumActiveElements] = i;
                NumActiveElements++;
                pReadingOrder[NumActiveElements] = NoMore_Element;
                break;
            }
        }
    }

    void Do_Something(void)
    {
        // In dieser Schleife werden die gewünschten Aktionen mit
        // den CObject-Array-Elementen ausgeführt, deren Indices
        // in der pReadingOrder-Liste stehen:

        long i, j;

        for(j = 0, i = 0; i < Size; i++)
        {
            j = pReadingOrder[i];

            if(j != NoMore_Element)
            {
                pObject[j].Do_Something();
            }
            else if(j == NoMore_Element)
                break;
        }

        // Nach Game-Objekten suchen, die im aktuellen Frame inaktiv
        // geworden sind und diese wieder freigeben:

        for(j = 0,  i = 0; i < Size; i++)
        {
            j = pReadingOrder[i];

            if(j != NoMore_Element)
            {
                if(pObject[j].active == false)
                {
                    // Variante 1:
                    //Delete_Object_With_IndexNr(j);

                    // Variante 2:
                    Delete_Object_With_ReadingOrderPositionNr(i);
                    i--;
                }
            }
            else if( j == NoMore_Element)
                break;
        }
    }

    void Delete_All_Objects_In_List(void)
    {
        NumActiveElements = 0;

        for(long i = 0; i < Size; i++)
        {
            pReadingOrder[i] = NoMore_Element;
            pUsedElements[i] = Element_UnUsed;
            pObject[i].TurnBack();
        }

        pReadingOrder[Size] = NoMore_Element;
    }

    void Delete_Object_With_IndexNr(long element)
    {
        // In der äußeren Schleife wird in der pReadingOrder-
        // Liste nach dem zu löschenden Element gesucht.
        // Dieses Element wird dann aus der Liste entfernt, indem
        // die nachfolgenden Elemente um eine Position nach links
        // (vorne) geschoben werden, bis der Eintrag NoMore_Element
        // gefunden wird.
        // Die Anzahl der aktiven Elemente wird um 1 erniedrigt.
        // In die pUsedElements-Liste wird dann an der zugehörigen
        // Indexposition der Wert Element_Unbenutzt eingetragen.
        // Anschließend wird das Objekt zurückgesetzt.

        long i, j;

        for(i = 0; i < Size; i++)
        {
            if(pReadingOrder[i] == element)
            {
                for(j = i; j < Size; j++)
                {
                    pReadingOrder[j] = pReadingOrder[j+1];

                    if(pReadingOrder[j] == NoMore_Element)
                        break;
                }

                NumActiveElements--;
                pUsedElements[element] = Element_UnUsed;
                pObject[element].TurnBack();

                break;
            }
        }
    }

    void Delete_Object_With_ReadingOrderPositionNr(long ii)
    {
        // Vorsicht, wenn die Listen-Position nicht besetzt ist,

        // kommt es zum Programmabsturz.

        // In dieser Funktion geschieht dasselbe wie in der Funktion

        // zuvor, mit dem Unterschied, daß man nicht den
        // CObject-Array-Index übergibt, sondern die Indexposition
        // in der pReadingOrder-Liste.
        // Aus dieser Liste muß der Array-Index ermittelt
        // werden, bevor das CObject-Array-Element zurückgesetzt
        // werden kann.
        // Diese Funktion ist etwas schneller als die vorherige
        // Funktion, da das Object in der pReadingOrder-
        // Liste nicht erst gesucht werden muß.

        NumActiveElements--;
        pUsedElements[pReadingOrder[ii]] = Element_UnUsed;
        pObject[pReadingOrder[ii]].TurnBack();

        for(long j = ii; j < Size; j++)
        {
            pReadingOrder[j] = pReadingOrder[j+1];

            if(pReadingOrder[j] == NoMore_Element)
                break;
        }
    }
};