[Solved] Problem mit einer Liste beim freigeben/clearen

nali

Hallo liebe Forengemeinde,

habe mich hier gerade mal angemeldet da ich mir öfters schon die Zähne manchen c/c++ Dingen ausgebissen haben, aber nun brauche ich endgültig Hilfe

Zu meinem Problem, ich habe mir eine Stringliste ala TStrings von Delphi gebaut, Doppelt verkettete Liste alles ganz gewöhnlich eigentlich, nun ist diese aber beim Clearen etwas sehr langsam, und ich weiß keinen Rat mehr.

Hier noch etwas Code zum veranschaulichen des Ablauf:

struct SDataItem
{
    std::string strValue;
    __int64 intValue;
    void* dataValue;
};

struct SListItem
{
    int idx;
    SListItem* prev;
    SDataItem* data;
    SListItem* next;
};

/* ... */

void CStringList::Clear()
{
    SListItem* item = NULL;

    while (this->first != this->last)
    {
        item = this->first;

        if (item->next != NULL)
        {
            item->next->prev = item->prev;
        }
        if (item->prev != NULL)
        {
            item->prev->next = item->next;
        }

        if (this->first == item)
        {
            this->first = item->next;
        }
        if (this->last == item)
        {
            this->last = item->prev;
        }

        delete item->data; // <- sobald ich das freigeben des data containers raus nehme ist das Clear in ~100ms duch sonst braucht er knapp 10 Sekunden
        delete item;
    }
}

Die Zeiten beziehen sich auf 100000 Einträge.
Time (fill): 624ms
Time (clear): 9735ms

Hoffe ihr könnt mir da weiterhelfen.

Viele Grüße
Daniel

crashterpiece

versuchs mal prinzipiell einfacher:

next = this->start();
while (next != this->last) {
  item = next;
  next = item->next();
  delete item;
};

nali

Die Schleife ist denke ich mal nicht das Problem, denn die läuft ohne ein delete in wenigen ms (10-20 bei 100000 Einträgen) durch. Das delete des data containers frisst wohl die Zeit, nur ich habe keine Ahnung warum, wenn ich "delete item->data;" auskommentiere ist die Laufzeit von Clear max. noch 90ms, aber wieso?

camper

mehr als eine halbe Sekunde für 100.000 Einträge (also mehr als 10.000 Zyklen pro Eintrag bei 1GHz - ein bisschen viel)? Ich hoffe doch, dass du deinen Compiler angewiesen hast, den Code zu optimieren. Andernfalls ist die Diskussion recht sinnlos.

nali

camper schrieb:

mehr als eine halbe Sekunde für 100.000 Einträge (also mehr als 10.000 Zyklen pro Eintrag bei 1GHz - ein bisschen viel)? Ich hoffe doch, dass du deinen Compiler angewiesen hast, den Code zu optimieren. Andernfalls ist die Diskussion recht sinnlos.

In meinen Augen etwas ZU viel...

Im Debug und Release (auf volle Optimierung eingestellt VS2005 Standard) Build beides in etwa das selbe +-100ms vllt. Hatte anfangs auch gedacht es liegt am Debug Build, aber wie gesagt mit Release Config das selbe!

Ich habe auch schon VS gesagt es solle den ICL anstelle des MS-Compiler nehmen, selbe in Grün

camper

Würdest du mal compilerfähigen Code zeigen, der dieses Verhalten hat?

nali

Klar, ich habe mal das notwendigste zusammengepackt, es verhält sich genauso wie im eigentlichen Projekt.

#include <windows.h>
#include <stdio.h>
#include <conio.h>
#include <string>

struct SDataItem
{
    std::string strValue;
    __int64 intValue;
    void* dataValue;
};

struct SListItem
{
    int idx;
    SListItem* prev;
    SDataItem* data;
    SListItem* next;
};

class CStringList
{
    private:
        int count;
        SListItem* first;
        SListItem* last;
    public:
        CStringList(void)
        {
            this->count = 0;
            this->first = NULL;
            this->last  = NULL;
        };

        ~CStringList(void)
        {
            this->Clear();
        }

        int AddItem(const char* str, __int64 number, void* data)
        {
            this->count++;

            SListItem* item     = new SListItem;
            SDataItem* itemdata = new SDataItem;

            itemdata->dataValue = data;
            itemdata->intValue  = number;
            itemdata->strValue  = str;

            item->idx  = 0;
            item->data = itemdata;
            item->prev = NULL;
            item->next = NULL;

            if ((this->first != NULL) && (this->last != NULL))
            {
                this->last->next = item;
                item->idx        = this->last->idx + 1;
                item->prev       = this->last;
                item->next       = NULL;
            } else
            {
                this->first = item;
            }

            this->last = item;

            return item->idx;
        };

        void Clear()
        {
            SListItem* item = NULL;

            while (this->first != this->last)
            {
                item = this->first;

                if (item->next != NULL)
                {
                    item->next->prev = item->prev;
                }
                if (item->prev != NULL)
                {
                    item->prev->next = item->next;
                }

                if (this->first == item)
                {
                    this->first = item->next;
                }
	            if (this->last == item)
                {
                    this->last = item->prev;
                }

                delete item->data;
                delete item;
            }

            this->count = 0;
        };
};

int main(int argc, const char* argv[])
{
    char text[128];
    CStringList *strLst = new CStringList();

    DWORD tick = GetTickCount();
    for (int i = 0; i < 100000; i++)
    {
        sprintf(text,"Foooooooooooo%d\0",i);
        strLst->AddItem(text,i,NULL);
    }
    printf("Time (fill): %d\r\n",GetTickCount() - tick);

    tick = GetTickCount();
    strLst->Clear();
    printf("Time (delete): %d\r\n",GetTickCount() - tick);

    delete strLst;

    getch();

    return 0;
}

camper

kann ich nicht nachvollziehen. wie sehen denn die Optimierungseinstellungen aus und welchen Prozessor verwendest du?

nali

Urgs, sitze gerade am Notebook, dachte schau mal ins Forum ob sich schon jemand gemeldet hat, und als ich dein Beitrag las dachter ich mir so, hmm teste es mal hier (mit dem Debug Build getestet):

Time (fill): 1141
Time (delete): 531

Es ist die selbe Executable.

Meine Workstation ist ein Intel D950 (2 Cores) 3,4Ghz (OS:Vista x32) das Notebool ist ein Centrino (1 Core) 1,3Ghz (OS:XP).

Dann ist jetzt meine Frage warum ist es auf meiner Workstation so langsam?

nali

Ok das Problem hat sich gelößt, sowas beklopptes echt mal, der Debugger war schuld. Ich habe die Anwenudng auf dem Notebook ja nicht in der IDE mit laufendem Debugger gestartet, aber der wurstet da wohl so extrem im Speicher rum das das so lange dauert. Darauf muss man erst mal kommen

Naja man lernt nie aus Dennoch vielen Dank für die Mühen.