Drobne programowanie

Kaczuś zaprasza do opowieści o algorytmach, językach programowania i strukturach danych

Na stronie stosowane są pliki cookies. Więcej na podstronie.
odsłon: 1491

Przyspieszamy dzięki sprytnym wskaźnikom

Minęło trochę czasu od ostatniego mojego wpisu na stronie, a jeszcze więcej od ostatniego artykułu w tym cyklu. No ale cóż, jak to mówią czas nie jest z gumy i czasami brakuje go (znaczy się czasu), aby zrobić wszystko co sobie zaplanowaliśmy.

No ale wróćmy do tematu. Zajmowaliśmy się optymalizowaniem funkcji odczytującej dane w formacie CSV. Mamy już w miarę standardowy interface, oraz pierwszą optymalizację związaną z prostym zabiegiem (zastąpiliśmy std::string przez std::stringstream przy buforowaniu danych). Teraz warto pomyśleć o następnych. Ale nim zaczniemy optymalizować, warto zastanowic się, gdzie najwiecej tracimy czasu (i pamięci). Okazuje sie, iż przy zwracaniu danych kopiowana jest cała kolejka ze stringami. Czy takie kopiowanie nam jest potrzebne? Wydaje mi się, że nie. Więc nasuwa się pomysł, by przekazać po prostu wskaźnik. No tak, ale to oznaczałoby, iż będziemy musieli zwalniać pamięć sami, a chcielibyśmy tego jednak uniknąć. I tu z pomocą przychodzi dobrodziejstwo nowego standardu - sprytne wskażniki. Skorzystamy z std::shared_ptr.
Nasz typ tlistarr wygladał będzie następująco:
typedef std::shared_ptr<std::deque<trecofarr>> tlistarr;
Aby ułatwić sobie dalsze zmiany wprowadźmy jeszcze typ pośredni:
typedef std::deque<trecofarr> tlltype;
typedef std::shared_ptr<tlltype> tlistarr;
Kolejna zmiana, to jawne wywołanie konstruktora w funkcji GetCSV. czyli zamiast:
tlistarr res;
będziemy mieli:
tlistarr res(new tlltype);
pozostaje jeszcze zmiana operatorów wyłuskania (gdyż typ std::shared_ptr<> jest typem podobnym wskaźnikom i w wielu przypadkach zachowuje się jak wskaźnik). Więc zamiast:
res.push_back(row);
będziemy mieli:
res->push_back(row);
No i taka niewielka zmiana przynosi w moim testowanym przypadku ok 20% przyspieszenie względem poprzedniej wersji!

Uwaga:

Aby skorzystać z dobrodziejstw sprytnych wskaźników w niektórych kompilatorach musimy ustawić odpowiednią flagę. GCC pod MorphOS-em w wersji 4.4.5 wymaga flagi:
-std=c++0x


Jak zauważyliście, takie wyniki zostały uzyskane dzięki braku konieczności kopiowania pamięci. Można pokusić się o kolejne podobne sztuczki. Zaingerujemy w kolejne typy danych i tak:
Stworzymy typ pomocniczy tbufrow, który będzie nam służył do zbierania kolejnych pól wiersza. Nie potrzebujemy w nim swobodnego dostępu do kolejnej porcji danych, toteż umieścimy je w liście:
std::list<char *> m_arr;
stworzymy metodę:
	void push_back(const std::string &s, unsigned int x)
	{
            char *z = (char *)malloc(x + 1);

            memcpy(z, s.c_str(), x);
            z[x] = 0;
            m_arr.push_back(z);
       	}
W której będziemy dodawać kolejne dane do listy. Przy okazji będziemy podawali ilość znaków, aby nie musiec liczyć rozmiaru przy każdym kopiowaniu. Dodatkowo wyposażymy tę klasę w metody:
	size_t size()
        {
            return m_arr.size();
        }
        void clear()
        {
            m_arr.clear();
        }
Zauważmy, że o ile w metodzie push_back alokujemy pamięć na dane, to jej nigdzie nie zwalniamy - to taka trochę nieelegancka sztuczka, ale w tym wypadku wymagana.

Samą klasę trecofarr zdefiniujemy również osobno. Potrzebujemy szybkiego dostępu, do danego pola, oraz podczas tworzenia znamy wielkość potrzebnej tablicy danych, toteż samo się nasuwa, aby dane tu trzymać w kontenerze std::vector. Z racji, że w konstruktorze kopiującym przejmiemy wskaźniki z ciągami znaków, to napiszmy też destruktor zwalniający dane zaalokowane wcześniej.
        trecofarr(tbufrow &arg)
        {
            int j = 0;
            std::list<char *>::iterator it;
            m_arr.reserve(arg.size());
            for (it = arg.m_arr.begin(); it != arg.m_arr.end(); ++it, ++j)
            {
            	m_arr.push_back(*it);
            }

        }
        ~trecofarr()
        {
            int i, k = m_arr.size();
            char *z;
            for (i = 0; i < k; ++i)
            {
            	z = m_arr[i];
                if (z)
                {
                    free(z);
                }
                m_arr[i] = NULL;
            }

        }  


Dodatkowo musimy też stworzyć klasę tlltype, ponieważ kopiowanie obiektów klasy trecofarr byłoby kłopotliwe, toteż mamy tu kolejkę:
std::deque<trecofarr *> m_arr;

Nasza główna funkcja teraz ma postać:
template <class xstream>
tlistarr GetCSV(TStreamIterator<xstream> &iter, char arecsep)
{
    tlistarr res(new tlltype);
    int lstatus = 0; // 0 - standardowy tryb, 1 bit otwarcie cudzyslowia, 2 bit jest w cudzyslowie
    unsigned int lsize = 0;
    std::stringstream lsbuf;
    tbufrow row;

    for (; (*iter); ++iter)
    {
        if ((lstatus & 1) > 0)
        {
            if (*iter == '\"')
            {
               //wstawić "
               lsbuf << "\"";
               ++lsize;
               lstatus &= (~1);
               continue;

            }
            else if ((lstatus & 2) > 0)
            {
              // zakończyć
              lstatus = 0;
            }
            else
            {
                //rozpoczynamy "
                lsbuf << (*iter);
                ++lsize;
                lstatus = 2;
                continue;
            }


        }
        if ((*iter == arecsep) && (lstatus != 2))//koniec rekordu
        {
            //utwórz pole z danych w lsbuf
            row.push_back(lsbuf.str(), lsize);
            lsize = 0;
            lsbuf.str("");
    	}
    	else if (((*iter == '\n') || (*iter == '\r')) &&  (lstatus != 2))
        {
            if (lsbuf.rdbuf()->in_avail() > 0)//jeśli są jeszcze dane w buforze - to dodać
            {
                row.push_back(lsbuf.str(), lsize);
                lsize = 0;
                lsbuf.str("");
            }
            if (row.size() > 0)
            {
                //utwórz rekord
                res->push_back(new trecofarr(row));
                row.clear();
            }


        }
        else if ((*iter == '\"') )
        {
            lstatus |= 1;
        }
        else
        {
            lsbuf << (*iter);
            ++lsize;

        }

    }
    // na zakończenie sprawdzenie, czy nie powinno się czegoś dodać
    if (lsbuf.rdbuf()->in_avail() > 0)
    {
    	row.push_back(lsbuf.str(), lsize);
    }
    if (row.size() > 0)
    {
        res->push_back(new trecofarr(row));
    }
    return res;

}
Uzyskane przyśpieszenie to ok 2%, tak więc dużo nie zyskaliśmy. Można jeszcze przyśpieszyć - potencjał jest (np. alokacja danych poolami) - ale tu zysk już będzie niewielki (bo kod będzie się komplikował). Tak więc proponuję na tym skończyć, tym bardziej, że to raczej program szkoleniowy, a nie narzędziowy tworzyliśmy i był potrzebny tylko w celach szkoleniowych.
Na tym kończę ten cykl.
Kaczuś

PS: oczywiście pliki ze źródłami do zabawy są do pobrania.

2015-02-23 20:25:18


Optymalizacja shared_ptr C++ sprytne wskaźniki CSV