[C++ / OpenMP] Segmentatiefout

[maleadt]

Hallo,

Om een tool die ik geschreven heb (vector-based image viewer) te laten profiteren van multicore machines, ben ik gestart met het integreren van OpenMP in de code (leek me een makkelijke manier om wat perfomance bij te winnen). Daarbij heb ik momenteel de intensievere routines herschreven op een paralleliseerbare wijze, en dan de OpenMP pragma's geintroduceerd.

Een voorbeeld: de rotate() functie. Die moet adhv een gegeven hoek, alle punten/lijnen/beziers in de datastructuur roteren. Aangezien hierbij geen elementen uit de datastructuur gewist wordt, leek mij dit de een makkelijke methode om bij te beginnen Eerst heb ik volgens deze paper de std::list met iteratoren wat herschreven, en er voor gekozen om de hele loop te paralleliseren, en de berekening dan in een "single nowait" pragma te laten draaien (toegegeven, oplossing zoals deze zien er een pak interessanter uit, maar ik wil eerst beginnen met OpenMP zonder daarvoor ingrijpende code changes in te moeten voeren).

Uiteindelijk zag de functie er zo uit:

C++:

    // Rotate all elements
    list<Element>::iterator it;
    #pragma omp parallel private(it)
    {
        for (it = elements.begin(); it != elements.end(); it++)
        {
            #pragma omp single nowait
            {
                switch (it->identifier)
                {
                    // Point
                    case 1:
                        help_rotate(it->parameters[0], it->parameters[1], angle_rad);
                        break;

                    // Polyline
                    case 2:
                        for (unsigned int i = 0; i < it->parameters.size(); i+=2)
                            help_rotate(it->parameters[i], it->parameters[i+1], angle_rad);
                        break;

                    // Polybezier
                    case 3:
                        for (unsigned int i = 0; i < it->parameters.size(); i+=2)
                            help_rotate(it->parameters[i], it->parameters[i+1], angle_rad);
                        break;

                    default:
                        throw Exception("data", "rotate", "unsupported element with ID " + stringify(it->identifier));
                }
            }
        }

    // Invalidate caches
    cacheBoundsDirty = true;

    // Move the image back to it's original location (TODO: replace with some math)
    autocrop();

Waarbij de help_rotate functie een inline functie is om mij wat schrijfwerk te besparen:

C++:

inline void help_rotate(double& x, double& y, double angle_rad)
{
    double xc = x;
    x = x * cos(angle_rad) - y * sin(angle_rad);
    y = xc * sin(angle_rad) + y* cos(angle_rad);
}

Allemaal goed en wel, buiten het feit dat m'n programma crasht bij het roteren. Maar het vervelende is dat hij niet altijd crasht: some bij de eerste rotatie, soms moet ik verschillende keren roteren, vroeg of laat heb ik er van. Tweede vervelende feit is dat als ik het geheel onder valgrind draai, hij wijst naar een "unitialised read" in libgomp (onderdeel van OpenMP), maar de backtrace leidt naar het autocrop() commando dat niet eens in een threaded mode draait
Nog vreemder: als ik de autocrop() uitcommentarieer, crasht het geheel minder snel, maar het blijft crashen. Doe ik dit laatste onder valgrind, wordt de het commando voor de autocrop() (die cache boolean op true zette) als schuldige aangewezen... Een fragment van die backtrace:

code:

==28158== Use of uninitialised value of size 4
==28158==    at 0x45FC002: (within /usr/lib/libgomp.so.1.0.0)
==28158==    by 0x45FB6DA: GOMP_single_start (in /usr/lib/libgomp.so.1.0.0)
==28158==    by 0x8068CE2: _ZN4Data6rotateEd.omp_fn.0 (data.cpp:189)
==28158==    by 0x806930F: Data::rotate(double) (data.cpp:233)

(regel 233 is die cacheBoundsDirty assignment)

De tweede stap in de backtrace (regel 189) wijst naar die throw(), maar dat kan ik al helemaal niet in het plaatje passen (throw() gecalld door een bool op true te zetten, code die nota-bene niks met elkaar te maken heeft?)...

Kortom, ik snap er weer niks van Threads introduceren werkt, maar crasht soms, en altijd in de OpenMP library, maar de backtrace leidt naar code die niet onder controle van OpenMP draait...
Alvast bedankt als iemand hier te hulp kan schieten

[farlane]

Lijkt erop dat iets je stack vernaggelt wordt waardoor de foutoorzaak schijnbaar rond blijft springen.

[leuk_he]

klapt hij eruit als je "it" lijst een oneven aantal elementen heeft?

[maleadt]

@farlane:
Inderdaad, maar de manier waarop de foutoorzaak rondspringt is ook niet helemaak kosjer. Als mijn backtrace start in de autocrop() functieaanroep, leidt de volgende stap in de backtrace niet naar een foutieve instructie in die autocrop() aanroep, maar naar een throw() ergens helemaal anders...

@leuk_he: interessante suggestie, maar helaas. Bij zowel even als oneven datasets klapt hij er uit, en in beide gevallen ongeveer even snel. Merkwaardig is wel dat als ik de autocrop() call verwijder, hij er veel langer over doet om te segfaulten. Jammer genoeg kan ik niet zien wat juist in de autocrop() functie den boel om zeep helpt (om te zien welk geheugen gecorrumpteerd wordt), want zoals ik zei doet de backtrace daar raar.

EDIT: misschien nog een informatieve toevoeging, een volledig log van valgrind vind je hier. De laatste tig errors variëren telkens (hier wordt cairo blijkbaar geraakt), wat vermoedelijk afhankelijk is van het stuk geheugen dat gecorrumpteerd wordt, maar de eerste reeks is altijd constant. Uitleg van de relevante regelnummers: 189 = die throw, 236 = autocrop() call, en dat is het vermoed ik.

EDIT 2: ik heb ondertussen ook een alternatieve aanpak geprobeerd, waarbij ik de loop omzet naar een ordinaire for met als iteratievariabele een long (perfect paralleliseerbaar via OpenMP dus), en dan in een "omp critical" sectie de iterators verschuif. Code als volgt:

C++:

    // Rotate all elements
    list<Element>::iterator it = elements.begin();
    #pragma omp parallel private(it)
    {
        for (long l = 0; l < elements.size(); l++)
        {
            #pragma omp critical
            {
                it++;
            }
            switch (it->identifier)
            {
                // Point
                case 1:
                    help_rotate(it->parameters[0], it->parameters[1], angle_rad);
                    break;

                // Polyline
                case 2:
                    for (unsigned int i = 0; i < it->parameters.size(); i+=2)
                        help_rotate(it->parameters[i], it->parameters[i+1], angle_rad);
                    break;

                // Polybezier
                case 3:
                    for (unsigned int i = 0; i < it->parameters.size(); i+=2)
                        help_rotate(it->parameters[i], it->parameters[i+1], angle_rad);
                    break;

                default:
                    throw Exception("data", "rotate", "unsupported element with ID " + stringify(it->identifier));
            }
        }
    }

Deze manier komt ook uit bovenvermelde paper, maar heeft als nadeel dat alle synchronisatie (it++) single-threaded draait en dus een pak trager is. Los daarvan crasht de methode ook, en de backtrace leidt opnieuw naar de autocrop() functie, maar de bovenliggende stap in de backtrace leidt nu niet naar de throw() maar naar de iterator advancing (it++).

code:

==7193== Invalid read of size 4
==7193==    at 0x80693F9: std::_List_iterator<Element>::operator++(int) (stl_list.h:149)
==7193==    by 0x8068D11: _ZN4Data6rotateEd.omp_fn.0 (data.cpp:205)
==7193==    by 0x8069334: Data::rotate(double) (data.cpp:236)
=7193== Process terminating with default action of signal 11 (SIGSEGV)
==7193==  Access not within mapped region at address 0x0
==7193==    at 0x80693F9: std::_List_iterator<Element>::operator++(int) (stl_list.h:149)
==7193==    by 0x8068D11: _ZN4Data6rotateEd.omp_fn.0 (data.cpp:205)
==7193==    by 0x8069334: Data::rotate(double) (data.cpp:236)

Met regel 236 zijnde autocrop() call en 205 de it++ instructie.

[ Voor 73% gewijzigd door maleadt op 21-02-2009 11:25 ]

[farlane]

maleadt schreef op zaterdag 21 februari 2009 @ 10:50:
@farlane:
Inderdaad, maar de manier waarop de foutoorzaak rondspringt is ook niet helemaak kosjer. Als mijn backtrace start in de autocrop() functieaanroep, leidt de volgende stap in de backtrace niet naar een foutieve instructie in die autocrop() aanroep, maar naar een throw() ergens helemaal anders...

Het lullige is dat op het moment dat je stack kapot is ook de stacktrace niet meer kunt vertrouwen. In dit geval kan good old printf debugging helpen om te bepalen wat de volgorde is geweest.

[Cruise Control]

Wat gebeurt er als je 'elements' vervangt door een std::vector<> en binnen de for-lus 'elements' met operator [] indexeert i.p.v. met een iterator?

[maleadt]

@farlane:
Ach zo, verklaart veel. Ik had gedacht dat valgrind met die corruptie om kon gaan en dus correcte traces gaf, maar zo zit het precies niet

@Cruise Control:
Een vector gebruiken maakt het gemakkelijk natuurlijk, want daar kan OpenMP goed met overweg. Een vector gebruiken ipv een list lost ook de crashes op, het probleem ligt dus (denk ik) niet bij m'n Element datastructuur maar eerder bij de combinatie van OpenMP en sequentiele iterators.
Ik was enkel bang voor de overhead die optreedt bij het omzetten van de std::list naar een std::vector/std::valarray, aangezien daarbij niet alleen nog een extra omzetting optreedt, maar ook alle voordelen van het gebruik van de list (snelle sequentiele access) wegvalt. En die overhead is bijzonder groot. Zonder conversie doe ik 90.000 translaties per seconde, met conversie zijn dat er 20.000, en met conversie en multithreading stijgt dit getal tot 30.000. Ik blijf dus zoeken naar een oplossing met minder overhead.
FYI ziet de code er zo uit:

C++:

    // Convert list to a vector in order to support parallelisation
    valarray<Element*> tempArray(elements.size());
    int element_i = 0;
    for (list<Element>::iterator it = elements.begin(); it != elements.end(); it++)
        tempArray[element_i++] = &(*it);

    // Rotate all elements
    #pragma omp parallel for default(shared)
    for (long i = 0; i < elements.size(); i++)
    {
        switch (tempArray[i]->identifier)
        {
          // tempArray[i]->do_iets()
        }
    }

[ Voor 21% gewijzigd door maleadt op 21-02-2009 14:09 ]

[maleadt]

Teveel informatie voor een edit, vandaar de dubbelpost

Na nog even vruchteloos gezocht te hebben op de oorspronkelijke code, heb ik het maar over een andere boeg gegooid: met behulp van Boost's iterator_range de lijst in verschillende delen hakken, en die dan door verschillende threads laten verwerken die elk een begin en einditerator krijgen. Zo moet OpenMP zich zelf niks aantrekken van de iterators, wat anders voor problemen zorgt

De code die de container verwerkt ziet er dan als volgt uit:

C++:

// Save the size (expensive operation)
#ifdef WITH_OPENMP
int size = elements.size();
#endif

// Process all items in a parallelised manner
#pragma omp parallel
{
    // Calculate a range
    #ifdef WITH_OPENMP
    boost::iterator_range<list<Element>::iterator> range = split_range_openmp(boost::make_iterator_range(elements.begin(), elements.end()), size);
    #else
    boost::iterator_range<list<Element>::iterator> range = boost::make_iterator_range(elements.begin(), elements.end());
    #endif

    // Process the range
    for (list<Element>::iterator it = boost::begin(range); it != boost::end(range); ++it)
    {
        it->do_iets()
    }
}

waarbij make_iterator_range een lidfunctie is van boost/range.hpp, en de functie split_range_openmp gedefinieerd is in de header van op bovenvermelde site.

Er is wel wat overhead. Door louter de iterators te vervangen door hun Boost range alternatief (zonder WITH_OPENMP dus) degradeert performance met een goeie 10%. Door het inschakelen van OpenMP (WITH_OPENMP -> iterator range wordt berekend) maar slechts 1 thread te gebruiken, daalt de performance opnieuw met nu ongeveer 25%. De overhead alleen is dus 33% (eigenlijk nog wat meer, aangezien de range berekening wat anders is in geval van meerdere threads).

Nu hoop ik die overhead terug te winnen door te profiteren van extra processorkracht. Dit kan ik echter nu niet testen, want op deze Pentium 4 (HyperThreading = fake dualcore) daalt de performance nog eens met 15%, wat normaal is voor HyperThreading (wordt bevestigd door andere synthetische benchmarks). Wordt dus wachten tot volgende week voor uitsluitsel, maar ik denk wel dat een winst van ten minste 33% er in zit. Ik twijfel alleen nog of een verlies van 10% voor single-core gebruikers verantwoord is, misschien sloop ik heel Boost er nog uit om louter std::iterator's te gebruiken in single threaded mode (maar dat zorgt dan weer voor meer code).