[C++] Optimalisatie images/arrays

[Iska]

Hey,

Ik ben momenteel bezig met een programma dat gebruik maakt van grote hoeveelheden afbeeldingen en functies adhv de invidiuele pixel waarden (volume rendering).
Nu merk ik echter dat het volgende erg traag gaat:
- De alpha waarden vaan meerdere PNG's opslaan in één lange array

code:

    char* chBuffer = new char[iImageWidth*iImageHeight*iImageCount];
    int i = 0, index = 0;
    while(pos2)
    {
        std::vector<unsigned char> image;
        error = lodepng::decode(image, width, height, CString2String(Files.GetNextPathName(pos2))); 
// PNG inlezen in vector image
        
        for(int x = 0; x < iImageWidth; ++x)
        {
            for(int y = 0; y < iImageHeight; ++y)
            {
                index = x*iImageWidth + y;

                chBuffer[i*iImageWidth*iImageHeight + index] = image[index*4 + 3]; 
// Alpha waarde opslaan in lange array
            }
        }
        
        ++i;
    }

- Een for loop met hierin een if-then operatie op iedere waarde in de lange array

code:

    int index = 0;
    for(int i = 0; i < iImageCount; ++i)
    {
        for(int x = 0; x < iImageWidth; ++x)
        {
            for(int y = 0; y < iImageHeight; ++y)
            {
                index = i*iImageWidth*iImageHeight + x*iImageWidth + y;
                
                chBuffer[index] = func(chBuffer[index]);
            }
        }
    }

Mijn C++ kennis is redelijk beperkt, en ik ben na vandaag nog niet veel verder gekomen met dit optimalizeren.
Mijn vraag is of dit te optimalizeren valt en hoe ik dit het beste aan kan pakken.

Bvd!

[Soultaker]

Met deze code lijkt me niet zoveel mis. Op zich is het onnodig om index steeds opnieuw te berekenen (je kunt 'm binnen de lus steeds met 1 ophogen) maar dit is ook iets wat de compiler kan optimaliseren, dus dat zou voor de snelheid niet veel uit moeten maken.

Je compileert wel met optimalisaties, toch?

edit:
Je zou die lusjes ook nog kunnen combineren tot:

C:

for(int index = 0; index < iImageCount*iImageWidth*iImageHeight; ++index)
      chBuffer[index] = func(chBuffer[index]);

[ Voor 24% gewijzigd door Soultaker op 07-02-2014 22:52 ]

[Iska]

Dan denk ik dat ik de meeste tijd verlies bij het inlezen van de files. Als ik namelijk 100 512x512 png's inlees en verwerk, duurt het hele proces zo'n 7-8 seconden (standaard SATA schijf, 8gb DDR2, Intel Q9450).

[Soultaker]

Als dat zo is kun je eens proberen of libng sneller is dan lodepng. Sowieso lijkt het me wel nuttig om te meten waar de tijd precies heengaat voordat je begint te optimaliseren.

[Iska]

@Lusjes combineren en index: heb je helemaal gelijk. Thx!

Ik ga dan nogmaals proberen AMD CodeAnalyst aan de praat te krijgen. Hij werkte nog niet erg mee vanmiddag

Edit: Kom er zojuist achter dat optimalisatie van de compiler alleen wordt toegepast op de Release in Visual Studio . Laadtijd is van ~8s naar een kleine 2 gegaan!

Update:
Het probleem zit hem in LodePNG. Een loop door alle pixels gaat heel snel (milliseconden), maar het inlezen van de 300 512x512 png's kost al snel een aantal seconde. Is dit altijd het geval of valt hier nog een hoop te halen (bijvoorbeeld door .tif te gebruiken ipv .png?)

[ Voor 62% gewijzigd door Iska op 08-02-2014 00:49 ]

[Mijzelf]

Hangt van je systeem af. Uitgaande van 24bits kleur +8bit alpha, bevat 1 image van 512*512 1MiB aan data. Dus als je (ongecomprimeerde) tif's wil inlezen, is dat 300MiB. Dat kost tijd. Png's nemen minder ruimte in, dus inlezen van schijf gaat sneller, maar je moet ze nog decomprimeren, wat processortijd kost.
Oftewel, een langzame HD met een snelle processor is sneller voor png, terwijl een SSD vrijwel zeker sneller is voor (ongecomprimeerde) tif.
Als je een multicore systeem hebt zou je het inladen van de png's kunnen multithreaden.

Overigens, jouw eerste stukje code heeft twee geneste lussen, waarbij de buitenste door de kolommen loopt, en de binnenste door de rijen. Daarmee loop je met sprongen door het geheugen. Als het je om milliseconden gaat kun je dat beter omdraaien, dan loop je linear door het geheugen, en kan je meer profijt hebben van je cache.

[Zoijar]

Wat is die 'if'? Als dat een moeilijk te voorspellen branch is kost dat waarschijnlijk veel tijd. Het is misschien beter je 'if' buiten de loop te plaatsen en er twee keer doorheen te gaan. Ook zou het schelen niet steeds je vector te destructen, geheugen vrij te geven, en weer te alloceren, hoewel ik niet denk dat dat veel uitmaakt voor slechts 300 keer. Wat tijd kost op moderne systemen zijn dingen als branches, geheugen allocaties en cache misses.

Bottleneck is waarschijnlijk gewoon de disk en png decoding.

[PrisonerOfPain]

Mocht je overhead bij de processing liggen; probeer te denken aan je CPU cache. Zorg dat je je afbeelding in tiles (64x64 bijvoorbeeld - net wat er in je cache past) processed. Waar je nog over zou kunnen denken is om je image planes apart te processen. Dus ipv een argb* naar je data heb je een a*, r*, g* en b*.

[Soultaker]

Mijzelf schreef op zaterdag 08 februari 2014 @ 10:19:
Overigens, jouw eerste stukje code heeft twee geneste lussen, waarbij de buitenste door de kolommen loopt, en de binnenste door de rijen. Daarmee loop je met sprongen door het geheugen.

Volgens mij is dat niet zo; hij gebruikt alleen x/y op een ongebruikelijke manier.

[PrisonerOfPain]

Soultaker schreef op zaterdag 08 februari 2014 @ 17:26:
[...]

Volgens mij is dat niet zo; hij gebruikt alleen x/y op een ongebruikelijke manier.

Wat ook het eerste wat mij opviel idd, x/y zijn omgewisseld maar het access pattern is wel gewoon goed.

[Zoijar]

hehe, ja, inderdaad Het werkt toevallig omdat hij het heeft over 512x512 png's

[Iska]

De genestelde loop heb ik ondertussen veranderd in een enkele loop met een counter adhv Soultakers eerdere advies. Daarnaast heb ik de texture in OpenGL veranderd van RGBA naar Intensity, waardoor nog maar 8 bit per voxel gebruikt wordt.

Bottleneck blijft hem inderdaad zitten in de PNG's inlezen en decoden. Na nog wat optimalisatie zit ik nu op 7-8 seconde voor 250 512x512 PNG's, wat nog wel te doen is gezien dit dus maar éénmaal nodig is.
Op andere plekken in het programma heb ik loops staan die door het hele volume gaan, en deze duren in de range van milliseconden. Voor grote hoeveelheden PNG's is mijn huidige tactiek dus maar resizen naar 256x256

Ik ga nog even kijken of het omwisselen van de rows/cols nog ergens toepasbaar is

Nog wel een ander vraagje:
Met LodePNG lees ik de PNG's in:

code:

    error = lodepng::decode(image, width, height, CString2String(Files.GetNextPathName(pos2)));
        
    for(int x = 0; x < iImageWidth*iImageHeight; ++x)
    {
        chBuffer[i*iImageWidth*iImageHeight + index] = image[index*4];

        ++index;
    }

Waarbij chBuffer en image unsigned chars zijn.

Wanneer ik echter in een later stadium de donkere pixels (weefsel in CT scan) probeer te filteren adhv de volgende loop:

code:

    char CRawDataProcessor::TransferFunction(char Input, int TF)
    {
        if (TF == 1) {
            if (Input <= 50) { return 0; }
            return Input;
        }

        return Input;
    }

Merk ik in de render dat juist de lichte pixels verwijderd zijn. Lopen de pixelwaarden bij een PNG niet van 0-255, kan ik een unsigned char niet zo lezen of doe ik iets anders fout?

Ik vergeleek met char Input <= int ipv unsigned char Input. Nu gefixt

BvD


Edit
Voorbeeld met Input >= 50

Zonder filter

[ Voor 41% gewijzigd door Iska op 08-02-2014 20:30 ]

[PrisonerOfPain]

Heeft het zin om de png's te pre-processen? Je zou bijvoorbeeld kunnen kijken om er een 8-bit png van te maken (als je dat nog niet doet) en ze te concatten naar een grote .png zodat je wat meer lineare file-io hebt. Nu gaat het namelijk redelijk in bursts. Dus IO, transform, IO, transform, IO transform. Dus een deel van de tijd (tijdens de transforms) starve je de IO driver van werk.

Verder zou je de X threads kunnen maken die niets anders doen dan files uitlezen, transformen en uploaden. Ik weet dat je in DX je resource creation op meerdere threads kunt laten verlopen zonder dat het blocked. Of dat met OpenGL ook kan weet ik niet (kan prima zijn dat je tegen driver locks aanloopt).

In dat geval kun je altijd nog X threads gebruiken om de IO & transforms te doen en dan op de main thread alle uploads.

[ Voor 11% gewijzigd door PrisonerOfPain op 08-02-2014 19:51 ]

[Iska]

Samenvoegen iseen goed idee , maar het geval is dat het user-friendly moet zijn en men dus gemakkelijk een reeks PNG's moet kunnen selecteren. Denk dus niet dat dat uiteindelijk sneller zou zijn

Meerdere threads ga ik nu naar kijken, nog geen eerdere ervaring

Edit: for the moment lijkt het alsof de CFileDialog.GetNextPathName(pos) geen fan is van multithread

[ Voor 34% gewijzigd door Iska op 08-02-2014 20:11 ]

[HuHu]

Noem sowieso bij je tijden even of dit in release of debug gecompileerde code is. Dat maakt een wereld van verschil. Meet daarna even specifiek welke regel(s) code veel tijd in beslag nemen.

Kleine suggestie: haal de regel std::vector<unsigned char> image; buiten de while. Volgens mij kun je die prima hergebruiken en het scheelt steeds het aanmaken/verwijderen van stukjes geheugen. En ook de volgorde van je x/y loops kan uitmaken.

[Mijzelf]

for the moment lijkt het alsof de CFileDialog.GetNextPathName(pos) geen fan is van multithread

Nee, dat klopt. Je kunt beter een verzameling 'jobs' aanmaken in een enkele thread, en dan een aantal threads deze jobs laten afhandelen.

Iets als:

C++:

struct{
    char *chBuffer;
    char *chFilename;
} Jobs[ 300 ];
int schrijfpointer = 0, leespointer = 0;

Hoofdlus()
{
    StartHulpThreads();
    while( CFileDialog.GetNextPathName(pos) )
    {
        Jobs[ schrijfpointer ].chFilename = stdup( pos ); // of hoe CFileDialog::GetNextPathName() ook moge werken
        Jobs[ schrijfpointer ].chBuffer = &chBuffer[ index * width * heigth ];
        schrijfpointer++;
    }
    WachtOpThreads();
    DoeDeRest();
}

ThreadFunctie()
{
    while( true )
    {
        int index = ::InterlockedIncrement( &leespointer );
        if( index >= 300 )
            return;
        while( index >= schrijfpointer )
            ::Sleep( 10 );
        leespng( Jobs[ index ].chFilename );
        verwerkdata( Jobs[ index ].chBuffer );
    }
}

Natuurlijk kan dit mooier, met events ipv sleeps. Hoewel ik niet denk dat je verschil in performance zult merken.