[C# threading] Waarom zijn m'n threads zo sloom

[liquid_ice]

In navolging van mijn topic: [VS2008 prof / C#] profiler tools

Heb ik met een profiler de code doorzocht en vond dat op meerdere plekken er door een array van 320.000 werd gelopen om er bewerkingen op uit te voreren en dat zo'n 20 keer per seconde.

Nu is dit heb gecentraliseerd naar 1 plek is m'n code alvast veel sneller.

Gezien ik een intel core2 duo 1.8 Ghz heb en ik in de taskmanager zag dat maar 1 CPU 100% word belast tijdens deze acties had ik verwacht dat als ik 2 threads zou maken dat ik iets van 30% snelheids winst zou moeten kunnen halen. In plaats van sneller zijn m'n threads bijna 2 keer zo langzaam en zie ik dat beide CPU's voor 50% worden belast.

Ik heb een byte array waar per 3 bytes eigenlijk een int moet worden gemaakt en in de int-array moet worden gestopt. Ook moet er van de 2de en 3de byte 128 af worden gehaald om het 0-punt te verleggen.

[ Voor 16% gewijzigd door liquid_ice op 05-11-2009 10:09 ]

[Bob]

Ik weet niet hoe je het juist doet, maar zoals je het omschrijft gaat het vooral om het verplaatsen/copieren van data in het geheugen, en een zeer lichte rekentaak voor de CPU (dat van die 128). Het zou goed kunnen dat je hier zo hard vast hangt aan geheugen bandbreedte dat je beter af bent met de taak op een core te houden.

[roy-t]

Kan het niet zijn dat omdat thread1 en thread2 dezelfde int array willen vullen ze door locking slechts om en om hun taakje kunnen doen? Misschien eens proberen om de int array in twee te delen en elk thread 1 van de arrays te laten vullen. Misschien kun je ook het zelfde doen met de byte array en dan eens kijken hoe snel het gaat.

*disclaimer: ik weet niet precies hoe thread synchronisatie gaat van arrays

[FireDrunk]

Dat ligt een beetje aan het type array... C# heeft wel enige vorm van autolocking, maar niet op standaard typen dacht ik

dus:

C#:

//Niet threadsafe
int array[] = new int[100];

//Wel threadsafe
List<int> list = new List<int>();

Correct me if i'm wrong...

[liquid_ice]

sorry, beetje code erbij is wel handig natuurlijk.

dit is de bewerking:

code:

            for (int i = 0; i < len; i++)
            {
                imageData[i + 1] = (yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1]) << 8 | (byte)(yuvBuffer[j + 2])) ^ 0x00008080;
                j += 3;
            }

wat ik heb geprobeerd is inderdaad omde ene thread de eerste helft te laten doen en de 2de thread de 2de helft.

[FireDrunk]

Dan moet je wel handmatig locking / synchronising toepassen ja...
Wat je beter kan doen is de array's van te voren opdelen en dan elke thread op een eigen array laten werken...

* FireDrunk duikt even in Visual Studio

[liquid_ice]

Het code example is voor de gehele array.

Als ik beide threads een poiner geef naar de array en eentje zeg ik dat ie van 0 tot len(=lengte)/2 moet doen en de ander van len/2 tot len.

Dan hoef ik toch geen extra synchronisatie toe te passen?

synchronisatie is overhead en dat wil ik juist niet.

[MSalters]

Nee, inderdaad. Synchronisatie is nodig als 1 object door 2 threads gebruikt wordt. De twee threads gebruiken zo te zien verschillende elementen van de array, en dus verschillende objecten.

Verder kan ik ook zo niet zien waarom beide cores maar 50% halen. Dat komt ook gedeeltelijk omdat je niet laat zien wat imageData en yuvBuffer zijn.

[matthijsln]

Als je dit multithreaded gaat maken is het opdelen in twee op zich voldoende en heb je geen locking nodig, ze schrijven niet naar dezelfde locaties e.d.. Wel zitten de schrijflocaties in dezelfde memory page en tijdens parallele verwerking zullen de caches tussen de cores gesynchroniseerd moeten worden, wat het mogelijk trager maakt.

Ik zou eerst proberen je loopje zelf te optimaliseren, bijvoorbeeld door 4 bytes per pixel te gebruiken (dan kan hopelijk de compiler ook de shift en or wergoptimaliseren) en je array te alignen, je loop te unrollen, en mmx te gebruiken.

Dat je huidige code memory bandwidth limited is zoals Bob zegt lijkt me niet zo waarschijnlijk, zo zonder deze optimalisaties (anders zouden deze optimalisaties uberhaupt nooit toegepast worden). Dit kan je natuurlijk meten door je huidige code te profilen en de bandbreedte uit te rekenen en vergelijken met de max bandbreedte die je op je pc kan halen. Door unaligned en non-wordsize memory access, sisd en cache syncs tussen cores verlies je denk de meeste tijd.

[FireDrunk]

Tjah, als je het makkelijk wil maken, en je weet hoeveel data je hebt, en je hebt geen zin om je echt in thread synchronisatie te verdiepen. Zou ik de data opdelen in meerdere array's...

Dat werkt misschien niet optimaal, maar het werkt wel...

C#:

for (int i = 0; i < aantalThreads; i++)
{
    Thread t = new Thread(Worker.DoWork);
    int[] dataArray = new int[chunkSize];
    for (int index = i*chunksize; index < i*chunkSize+chunkSize; i++)
    {
        dataArray[index] = startData[index*i];
    }
    t.doWork(dataArray);
}

[matthijsln]

thijs_cramer schreef op donderdag 05 november 2009 @ 11:34:
Tjah, als je het makkelijk wil maken, en je weet hoeveel data je hebt, en je hebt geen zin om je echt in thread synchronisatie te verdiepen. Zou ik de data opdelen in meerdere array's...

Dat werkt misschien niet optimaal, maar het werkt wel...

C#:

for (int i = 0; i < aantalThreads; i++)
{
    Thread t = new Thread(Worker.DoWork);
    int[] dataArray = new int[chunkSize];
    for (int index = i*chunksize; index < i*chunkSize+chunkSize; i++)
    {
        dataArray[index] = startData[index*i];
    }
    t.doWork(dataArray);
}

Voor het simpele loopje van de TS levert deze extra memcopy en mem alloc wel heeeel veel overhead op

[liquid_ice]

@matthijsIn, de inkomende array komt van een camera af (soort van rgb bytes). Ik weet niet zeker of het lukt om dat aan te passen zodat het gealligned kan worden op 4 bytes per int.

Wat bedoel je met: "array te alignen, je loop te unrollen, en mmx te gebruiken"

[matthijsln]

liquid_ice schreef op donderdag 05 november 2009 @ 11:57:
@matthijsIn, de inkomende array komt van een camera af (soort van rgb bytes). Ik weet niet zeker of het lukt om dat aan te passen zodat het gealligned kan worden op 4 bytes per int.

Misschien dat je met de API waarmee die array gevuld wordt een pixelformat kan instellen?

Wat bedoel je met: "array te alignen, je loop te unrollen, en mmx te gebruiken"

Dat zijn optimalisatietechnieken die je normaal inderdaad niet tegenkomt, maar bij beeldverwerking en 3d engines en dergelijke is het nog niet geheel archaïsch om te gebruiken In veel gevallen uit de dagelijkse praktijk en hier in PRG zou je kunnen stellen dat het niet de moeite waard is (maar ik vind 't wel erg leuk ).

Ik zal dus alleen even een hele summiere beschrijving geven, want de exacte implementatie vereist toch wel wat kennis:
- Alignen zorgt ervoor dat gegevens efficient uit het geheugen kunnen worden opgehaald met zo min mogelijk operaties van de memory controller. Ook is het mogelijk eventueel een prefetch hint te geven
- Unrollen zorgt ervoor dat je de meerdere ALU's (verwerkingseenheden) tegelijk aan het werk kan zetten met out-of-order execution. Dit betekent bijvoorbeeld dat je in je loop body 4 pixels tegelijkertijd verwerkt en je loop counter niet met 1 pixel ophoogt maar met 4. Dit zorgt ervoor dat de CPU de pipeline beter kan benutten.
- MMX is een SIMD instructieset, wat betekent dat je met een enkele instructie meerdere data elementen kan processen (bijvoorbeeld 8 bytes van 2 pixels tegelijk XOR'en). De processor heeft speciale logica voor deze instructies zodat deze sneller zijn dan elk element afzonderlijk te doen met de normale instructies.

Hoeveel invloed de verschillende optimalisaties hebben en welke je dus het best als eerst kunt kiezen hangt van je algoritme af (en verschilt bij bepaalde situaties per architectuur). De juiste kiezen vereist de kennis van de methodes, en vaak ook gewoon wat prutsen en benchmarken

[FireDrunk]

Ik denk dat je dat soort implementatie niet gauw in C# kunt maken, maar dat je dan eerder C++ moet gebruiken (vanwege de unmanaged API calls).
C# kan veel, maar is in dat opzicht niet echt sterk...

En waarom levert mijn oplossing zoveel meer geheugen allocatie op?
Zodra een thread klaar is, word het geheugen toch weer vrij gegeven? Daar is een Garbage Collector voor

[.oisyn]

De GC geeft pas geheugen vrij als de GC runt, en dat is niet per se direct nadat een thread is gestopt. Bovendien klopt je manier van je array vullen niet, en daarnaast maakt het feit dat je eerst data moet kopiëren de boel alleen maar inefficienter.

[ Voor 41% gewijzigd door .oisyn op 05-11-2009 12:53 ]

[pedorus]

thijs_cramer schreef op donderdag 05 november 2009 @ 10:29:

C#:

//Wel threadsafe
List<int> list = new List<int>();

Absolute onzin!

quote: http://msdn.microsoft.com...dd997305%28VS.100%29.aspx

However, the .NET Framework 2.0 collection classes do not provide any thread synchronization; user code must provide all synchronization when items are added or removed on multiple threads concurrently.

Maar er is hier sowieso geen synchronisatie nodig totdat de operatie klaar is, aangezien het om aparte delen van een array gaat.

liquid_ice schreef op donderdag 05 november 2009 @ 10:29:
sorry, beetje code erbij is wel handig natuurlijk.

dit is de bewerking:

code:

            for (int i = 0; i < len; i++)
            {
                imageData[i + 1] = (yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1]) << 8 | (byte)(yuvBuffer[j + 2])) ^ 0x00008080;
                j += 3;
            }

wat ik heb geprobeerd is inderdaad omde ene thread de eerste helft te laten doen en de 2de thread de 2de helft.

Dit lijkt me niet alle relevante code. Hoe doe je multithreading? Is imageData of yuvBuffer 320.000 lang en wat zijn de types? Het lijkt me dat de gehele operatie toch maar een paar milliseconden duurt, en dat is ongeveer evenveel als de overhead die door synchronisatie gaat ontstaan. Kortom, sneller gaat het er nooit van worden, je moet op een ander niveau multithreaden.

[.oisyn]

pedorus schreef op donderdag 05 november 2009 @ 13:34:
Het lijkt me dat de gehele operatie toch maar een paar milliseconden duurt, en dat is ongeveer evenveel als de overhead die door synchronisatie gaat ontstaan.

Sorry, maar milliseconden voor synchronisatie? Dat is je reinste kolder. Voor PC games pushen we workloads in de orde van grootte van tientallen tot enkele honderden microseconden.

.edit: Ik heb het even geverifieerd, de occlusion culling van een scene in Tomb Raider: Underworld duurt hier op een Core 2 Quad 3GHz 1500us, en in die tijd worden er 240 workloads afgehandeld. Gezien het feit dat die allemaal binnen 1500us klaar zijn en ze maar over 3 cores verdeeld worden betekent dat een maximale gemiddelde tijd van 19us per workload (!!!)

[ Voor 32% gewijzigd door .oisyn op 05-11-2009 14:28 ]

[FireDrunk]

pedorus schreef op donderdag 05 november 2009 @ 13:34:
[...]

Absolute onzin!
[...]
Maar er is hier sowieso geen synchronisatie nodig totdat de operatie klaar is, aangezien het om aparte delen van een array gaat.

/offtopic

Dan zal ik wel in de war zijn met Java

[liquid_ice]

@.oisyn, als de overhead volgens jou maar enkele tiende van milliseconde is, waar licht het dan volgens jou aan dat ik het niet sneller krijg dmv threads?

@matthijsIn, je bedoelt met unrollen dus echt dat ik geen stappen per 1 pixel in m'n loopje zet, maar per 2 of 4.
dus dan zou het iets dit worden:

code:

  int j = 0;
  for (int i = 0; i < len; i+=4)
  {
     imageData[i] = yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1] - 128) << 8 | (byte)(yuvBuffer[j + 2] - 128);
     imageData[i+1] = yuvBuffer[j+3] << 16 | (byte)(yuvBuffer[j + 4] - 128) << 8 | (byte)(yuvBuffer[j + 5] - 128);
     imageData[i+2] = yuvBuffer[j+6] << 16 | (byte)(yuvBuffer[j + 7] - 128) << 8 | (byte)(yuvBuffer[j + 8] - 128);
     imageData[i+3] = yuvBuffer[j+9] << 16 | (byte)(yuvBuffer[j + 10] - 128) << 8 | (byte)(yuvBuffer[j + 11] - 128);
     j += 12;
 }

Ik heb een testje gedaan en daaruit leek te komen dat deze stap van 4 pixels per for wel wat sneller was.
Na 4000 keer de gehele loop te hebben gedaan was het van 16 naar 14 seconden gegaan.

[ Voor 20% gewijzigd door liquid_ice op 05-11-2009 13:58 ]

[D-Raven]

Ik zet overigens vraagtekens bij de keuze om dit te gaan multi-threaden. Als je dit op meerdere threads wilt gaan uitvoeren zal je toch je werk moeten verdelen. Het is nog maar zeer de vraag of het uitvoeren van je werk over meerdere threads, de extra load die de werkverdeling met zich meebrengt teniet doet.

[matthijsln]

liquid_ice schreef op donderdag 05 november 2009 @ 13:53:
@matthijsIn, je bedoelt met unrollen dus echt dat ik geen stappen per 1 pixel in m'n loopje zet, maar per 2 of 4.
dus dan zou het iets dit worden:

code:

  int j = 0;
  for (int i = 0; i < len; i+=4)
  {
     imageData[i] = yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1] - 128) << 8 | (byte)(yuvBuffer[j + 2] - 128);
     imageData[i+1] = yuvBuffer[j+3] << 16 | (byte)(yuvBuffer[j + 4] - 128) << 8 | (byte)(yuvBuffer[j + 5] - 128);
     imageData[i+2] = yuvBuffer[j+6] << 16 | (byte)(yuvBuffer[j + 7] - 128) << 8 | (byte)(yuvBuffer[j + 8] - 128);
     imageData[i+3] = yuvBuffer[j+9] << 16 | (byte)(yuvBuffer[j + 10] - 128) << 8 | (byte)(yuvBuffer[j + 11] - 128);
     j += 12;
 }

Ik heb een testje gedaan en daaruit leek te komen dat deze stap van 4 pixels per for wel wat sneller was.
Na 4000 keer de gehele loop te hebben gedaan was het van 16 naar 14 seconden gegaan.

Inderdaad op deze manier, en 12.5% is toch een redelijke verbetering, zelfs met C# dus. Wel moet je goed oppassen dat indien je array niet deelbaar is door vier je het restje nog wel goed doet

[.oisyn]

liquid_ice schreef op donderdag 05 november 2009 @ 13:53:
@.oisyn, als de overhead volgens jou maar enkele tiende van milliseconde is, waar licht het dan volgens jou aan dat ik het niet sneller krijg dmv threads?

Het creëren van threads is duur. Liefst gebruik je dus een thread pool constructie waarbij de threads al zijn gestart en simpelweg zitten te wachten op commando's om dingen te gaan doen. Het .Net framework heeft daar vast wel een constructie voor, maar daar weet ik vrij weinig van. Daarnaast, als je memory bound bent gaat meerdere threads niet helpen, omdat je daarmee nou eenmaal niet zorgt dat er meer data over de bus kan. Gezien de code die je tot nu toe gepost hebt lijkt me dat wel het geval.

[ Voor 17% gewijzigd door .oisyn op 05-11-2009 14:29 ]

[matthijsln]

In deze presentatie op slide 20 en 21 worden nog wat problemen genoemd met parallellisatie, zoals ik noemde het schrijven naar dezelfde memory pages wat mogelijk een cache line sync tussen cores oplevert, maar als je die presentatie doorleest zie je dat er nog veel meer bij komt kijken

[creator1988]

wat .oisyn ongeveer zegt, je moet niet elke keer nieuwe threads gaan spawnen.

Waar je naar kan kijken is het Parallels Framework van Microsoft, dat abstraheert dit soort dingen weg, en handlet ook thread pooling etc.

[pedorus]

.oisyn schreef op donderdag 05 november 2009 @ 13:39:
[...]

Sorry, maar milliseconden voor synchronisatie? Dat is je reinste kolder. Voor PC games pushen we workloads in de orde van grootte van tientallen tot enkele honderden microseconden.

Ehh, wacht, ik haal wat ordes door elkaar. Synchronisatie van wachten op 1 event is inderdaad meer in de orde van nanoseconden als het meezit.

@TS: Kijk eens naar ThreadPool, of naar het hierboven genoemde Parallel Framework dat er aan zit te komen (maar wat je al wel kan testen - oa Parallel.For). Daarnaast gebeuren dingen als 'unrolling the loop' volgens mij al deels automatisch als je alle optimalisaties aanzet (wat weer niet handig is met debuggen). Daarnaast is het ook mogelijk dat de bus gewoon niet snel genoeg is. En ik zou dus kijken of je de parallelisatie niet beter ergens anders kan doen.

[MSalters]

Ik zou een handmatig unrolled loop willen voorstellen:

code:

INT32* yuvBuf32 = (INT32*) yuvBuffer; 
for (int i = 0; i < len; i+4)
{
   imageData[i + 1] = (yuvBuf32[j] >> 8) ^x00008080;
   imageData[i + 2] = ((yuvBuf32[j] & 0xFF) | (yuvBuf32[j+1] >>16)) ^x00008080;
   imageData[i + 3] = ((yuvBuf32[j+1] & 0xFFFF) | ((yuvBuf32[j+2] >>24)) ^x00008080;
   imageData[i + 3] = ((yuvBuf32[j+2] & 0xFFFFFF))  ^x00008080;
   j += 3;
}

Door structureel gebruik te maken van 32 bits variabelen zou je een heel stuk sneller moeten zijn. De optimizer kan alle variabelen tracken, en weet dus dat er geen register spill nodig is. Er worden dus maar 0,75 reads gedaan per output (!), in plaats van 3.

[Soultaker]

@MSalters: dit kan toch helemaal niet in C#? (Sowieso is het niet zo netjes om code te schrijven die afhankelijk is van de juiste endianness en bovendien misaligned data leest, maar ik kan me voorstellen dat je 't zou doen als portability minder van belang is dan performance.)

(Los daarvan zitten er een paar kleine foutjes in je code, maar dat was vast bedoeld als oefening voor de TS. )

[ Voor 17% gewijzigd door Soultaker op 05-11-2009 16:13 ]

[.oisyn]

Soultaker schreef op donderdag 05 november 2009 @ 16:13:
@MSalters: dit kan toch helemaal niet in C#?

Sinds wanneer niet?

C#:

void Foo(int[] bla)
{
    unsafe
    {
        fixed(int* ptr = &bla[0])   // gewoon 'bla' ipv '&bla[0]' mag overigens ook
        {
            for (int i = 0; i < bla.Length; i++)
                System.Console.WriteLine(*ptr++);
        }
    }
}

[ Voor 23% gewijzigd door .oisyn op 05-11-2009 16:34 ]

[Soultaker]

Ik had in m'n hoofd dat yuvBuffer een byte-array was; MSalters lijkt die te casten naar een Int32 array en ik vermoedde dat dat niet zou mogen in C#. (Ik code er nooit in dus neem mijn commentaar sowieso met een korreltje zout.)

edit:
Hmz, de TS heeft het wel over een byte-array en deze code suggereert dat ook...

edit2:
Ok, dat kan wel. Zoals ik zei, ik ben geen C# expert. Ik kan me voorstellen dat het gebruiken van unsafe code niet in elk project wenselijk is.

[ Voor 84% gewijzigd door Soultaker op 05-11-2009 17:05 ]

[.oisyn]

C#:

static void Main(string[] args)
{
    byte[] b = { 1, 2, 3, 4 };

    unsafe
    {
        fixed (byte* bPtr = b)
        {
            int * iPtr = (int*)bPtr;
            System.Console.WriteLine(*iPtr);
        }
    }
}

Werkt prima hier

[pedorus]

Soultaker schreef op donderdag 05 november 2009 @ 16:27:
edit2:
Ok, dat kan wel. Zoals ik zei, ik ben geen C# expert. Ik kan me voorstellen dat het gebruiken van unsafe code niet in elk project wenselijk is.

Nu is de grap dat er ook nog een enorme hack is met StructLayout, die er voor zorgt dat het zelfs zonder /unsafe kan. Verder niet aan te raden lijkt mij (bijvoorbeeld als je de Length 'goed gaat zetten' pas je ook iedere keer de originele array verkeerd aan, daarnaast kun je opeens AccessViolationExceptions krijgen in managed(!) code).

[.oisyn]

Ik zat zelf nog even naar de Marshalling opties te kijken. Het array object is ook maar gewoon een wrapper om de array data zelf. Het zou dus prima mogelijk moeten zijn om op die manier een andere view te krijgen van dezelfde data, op dezelfde manier dat het mogelijk is om vanuit (unmanaged) C++ code een managed functie aan te roepen die een .Net array verwacht, terwijl je een native array meegeeft (zonder dat er data gekopiëerd wordt). Dit werkt alleen voor zogenaamde blittable types, maar dat zijn alle primitieven feitelijk ook.

Of en hoe dit mogelijk is vanuit C# code weet ik niet precies.

[FireDrunk]

Op school leer ik altijd dat je code Onderhoudbaar en Overzichtelijk moet zijn...
Dan denk ik toch dat je meer naar de 'officiele' functies van .NET moet gaan kijken...
Maar dat is meer mening dan feit

[H!GHGuY]

thijs_cramer schreef op donderdag 05 november 2009 @ 17:59:
Op school leer ik altijd dat je code Onderhoudbaar en Overzichtelijk moet zijn...
Dan denk ik toch dat je meer naar de 'officiele' functies van .NET moet gaan kijken...
Maar dat is meer mening dan feit

School is overrated

Misschien niet de juiste vraag maar draait de TS dit wel in release mode en zonder debugger attached?

[liquid_ice]

Ik had de applicatie gedraaid vanuit Visual studio, maar wel in Release mode.

ik ga er eigenlijk van uit dat als ik release in visual studio kies dat het optimaal geoptimaliseerd is, of zijn er nog settings die invloed kunnen hebben.

[pedorus]

Ctrl-F5 lijkt me goed genoeg.

liquid_ice schreef op donderdag 05 november 2009 @ 10:29:

code:

            for (int i = 0; i < len; i++)
            {
                imageData[i + 1] = (yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1]) << 8 | (byte)(yuvBuffer[j + 2])) ^ 0x00008080;
                j += 3;
            }

Een eenvoudige optimalisatie om bounds-checking tegen te gaan (2 veranderingen):

C#:

            for (int i = 0; i < imageData.Length; i++)
            {
                int j = i * 3;
                imageData[i] = (yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1]) << 8 |
                    (byte)(yuvBuffer[j + 2])) ^ 0x00008080;
            }

liquid_ice schreef op donderdag 05 november 2009 @ 13:53:
dus dan zou het iets dit worden:

code:

  int j = 0;
  for (int i = 0; i < len; i+=4)
  {
     imageData[i] = yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1] - 128) << 8 | (byte)(yuvBuffer[j + 2] - 128);
     imageData[i+1] = yuvBuffer[j+3] << 16 | (byte)(yuvBuffer[j + 4] - 128) << 8 | (byte)(yuvBuffer[j + 5] - 128);
     imageData[i+2] = yuvBuffer[j+6] << 16 | (byte)(yuvBuffer[j + 7] - 128) << 8 | (byte)(yuvBuffer[j + 8] - 128);
     imageData[i+3] = yuvBuffer[j+9] << 16 | (byte)(yuvBuffer[j + 10] - 128) << 8 | (byte)(yuvBuffer[j + 11] - 128);
     j += 12;
 }

Ik heb een testje gedaan en daaruit leek te komen dat deze stap van 4 pixels per for wel wat sneller was.
Na 4000 keer de gehele loop te hebben gedaan was het van 16 naar 14 seconden gegaan.

Dat lijkt me niet zonder debugger, of je hebt een erg trage processor. In de praktijk zorgt dit ervoor dat het 'opwarmen' langer duurt (de tijd waarin de runtime engine de boel optimaliseert). Voor de rest is het resultaat bij mij gelijk of zelfs trager. MSalters' suggestie is wel 2-5% sneller met unmanaged code (na 'opwarmen' van de managed code), maar dat is dus ook niet heel erg interessant.

[.oisyn]

pedorus schreef op donderdag 05 november 2009 @ 20:56:
Een eenvoudige optimalisatie om bounds-checking tegen te gaan (2 veranderingen):

C#:

            for (int i = 0; i < imageData.Length; i++)
            {
                int j = i * 3;
                imageData[i] = (yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1]) << 8 |
                    (byte)(yuvBuffer[j + 2])) ^ 0x00008080;
            }

[...]

Kun je uitleggen waarom jouw veranderingen de juiste optimalisaties in de VM triggert?

[pedorus]

Zeker weet ik het niet, maar ik heb het gewoon even getest, en de originele variant was zo'n 28% trager (!), ook na opwarmen(, wat nauwelijks effect heeft). Ik denk dat len ipv Length ervoor zorgt dat er bounds-checking wordt gedaan op imageData (+8-9%). j+=3 zorgt ervoor dat de koppeling tussen i en j niet duidelijk is, waardoor je bounds-checking op yuvBuffer krijgt (+20%!). Dit werkt onafhankelijk:

origineel	+28%
met j+=3, wel .Length	+20%
met i*3 en len	+8%
met i*3 en .Length	-
unsafe naar MSalters	-4%

Het is vreemd dat len zoveel anders is dan .Length (8%) en dat dat dus niet wordt gedetecteerd. Ik had nog een testideetje om met len dan [j/3] te gaan gebruiken, maar dat zorgt ervoor dat werkelijk alle optimalisaties overboord gaan (factor 3 ofzo...). i*1 helpt niets, en haalt de compiler gewoon weg. Kortom, het is belangrijk om daadwerkelijk .Length te gebruiken, en ook geen descending loop. Of deze resultaten echt alleen aan bounds-checking liggen is ook een beetje een gok.

[ Voor 5% gewijzigd door pedorus op 05-11-2009 22:00 . Reden: link eindelijk gevonden ]

[Soultaker]

Kun je de door de VM JIT-compiler gegenereerde code niet dumpen?

[ Voor 15% gewijzigd door Soultaker op 05-11-2009 22:58 ]

[.oisyn]

pedorus schreef op donderdag 05 november 2009 @ 21:50:
Zeker weet ik het niet, maar ik heb het gewoon even getest, en de originele variant was zo'n 28% trager (!), ook na opwarmen(, wat nauwelijks effect heeft). Ik denk dat len ipv Length ervoor zorgt dat er bounds-checking wordt gedaan op imageData (+8-9%). j+=3 zorgt ervoor dat de koppeling tussen i en j niet duidelijk is, waardoor je bounds-checking op yuvBuffer krijgt (+20%!). Dit werkt onafhankelijk:

origineel	+28%
met j+=3, wel .Length	+20%
met i*3 en len	+8%
met i*3 en .Length	-
unsafe naar MSalters	-4%

Interessant. Vooral omdat er geen relatie bestaat tussen imageData.Length en yuvBuffer.Length, maar hij blijkbaar wel een dynamische boundscheck op yuvBuffer buiten de loop doet door te verifieren dat yuvBuffer.Length minstens 3*imageData.Length is (tenminste, daar ga ik dan vanuit), maar dat niet meer kan als je [imageData.Length] keer [j met 3 ophoogt]. Wellicht omdat j signed is en de ophoging dus mogelijk een negatief resultaat kan hebben? Kun je eens proberen j als unsigned te definieren?

geen descending loop

Interessant artikel, thanks . Overigens vind ik die opmerking en ook dat stukje in het artikel een beetje het punt missen. De reden waarom je geen descending loop wil is omdat dat cache-technisch een ramp is. De array bounds checking is dan wel de minste van je zorgen

[Soultaker]

.oisyn schreef op donderdag 05 november 2009 @ 23:26:
Interessant artikel

Helaas vooral implementatiedetails en weinig fundamenteels.

De reden waarom je geen descending loop wil is omdat dat cache-technisch een ramp is.

Waarom Je moet precies dezelfde cache lines fetchen, alleen in omgekeerde volgorde?

[.oisyn]

Omdat de CPU anticipeert op lineaire reads.

[Soultaker]

Wat doet 'ie er dan concreet mee? Lijkt me niet dat 'ie automatisch prefetcht of wel? (En van achter naar voren is ook lineair natuurlijk. )

[.oisyn]

Oh crap ik ben in de war met writes naar write combined geheugen. Een test laat idd zien dat het geen drol uitmaakt.

[liquid_ice]

@Pedorus:

Ik kom niet aan dezelfde getallen als jij.
Mijn test geeft een HEEL andere uitkomst zelfs.
Dit is mijn complete testcode:

code:

        static int len = 300000;
        static int[] imageData = new int[len];
        static byte[] yuvBuffer = new byte[len*3];

        static void slowFunction()
        {
            int j = 0;
            for (int i = 0; i < len; i++)
            {
                imageData[i] = (yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1]) << 8 | (byte)(yuvBuffer[j + 2])) ^ 0x00008080;
                j += 3;
            }
        }
        static void fastFunction()
        {
            int j = 0;
            for (int i = 0; i < imageData.Length; i++)
            {
                j = i * 3;
                imageData[i] = (yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1]) << 8 | (byte)(yuvBuffer[j + 2])) ^ 0x00008080;
            }
        }
        static void Main(string[] args)
        {
            System.Diagnostics.Stopwatch st = new System.Diagnostics.Stopwatch();
            st.Start();
            for (int i = 0; i < 100; i++)
            {
                slowFunction();
            }
            st.Stop();
            Console.WriteLine("Slow function takes: " + st.ElapsedMilliseconds + " ms");
            st.Reset();

            st.Start();
            for (int i = 0; i < 100; i++)
            {
                fastFunction();
            }
            st.Stop();
            Console.WriteLine("Fast function takes: " + st.ElapsedMilliseconds + " ms");
            st.Reset();
            st.Start();
            for (int i = 0; i < 100; i++)
            {
                slowFunction();
            }
            st.Stop();
            Console.WriteLine("Slow function takes: " + st.ElapsedMilliseconds + " ms");
            st.Reset();

            st.Start();
            for (int i = 0; i < 100; i++)
            {
                fastFunction();
            }
            st.Stop();
            Console.WriteLine("Fast function takes: " + st.ElapsedMilliseconds + " ms");
            st.Reset();
            Console.ReadLine();
        }
    }

Ik heb um gedraaid op een core2duo laptop die aan de spanning hing en heb gecompileerd op release, maar buiten visual studio gedaaid.

slowFunction 1	fastFunction 1	slowFunction 2	fastFunction 2
141 ms	154 ms	139 ms	160 ms
163 ms	153 ms	139 ms	153 ms
144 ms	153 ms	139 ms	152 ms

Hieruit lijkt juist dat mijn originele code 10% sneller is dan die door Pedorus gegeven als laatste.
vreemd dat jij 30% winst meet en ik 10% verlies

[.oisyn]

Die test is ook oneerlijk, al je variabelen zijn static. Maak ze eens parameters van de functies, en definieer ze lokaal in Main()?

.edit: Zelf even geprobeerd, en dan zijn de aanroepen even snel. Zowel op x64 als op x86 (de x64 versie heeft wel 16% minder tijd nodig dan de x86 versie)

[ Voor 79% gewijzigd door .oisyn op 06-11-2009 02:11 ]

[H!GHGuY]

Al eens geprobeerd om je binary 2 maal te draaien (buiten VS om) om zo JIT optimization time niet mee te hoeven tellen?

[liquid_ice]

Ik heb um 3 maal gedraaid buiten visual studio om, zoals je in mijn tabel kan zien.

elke run van de binary doet de originele manier, dan die van Pedorus, dan de originele en dan weer die van Pedorus.

Dit om opstart stuff buiten beschouwing te laten.

[Alarmnummer]

thijs_cramer schreef op donderdag 05 november 2009 @ 13:52:
[...]


/offtopic

Dan zal ik wel in de war zijn met Java

In Java zal het echt liggen aan de List implementatie die je gebruikt.

Een Vector is threadsafe en een ArrayList/LinkedList niet. Eventueel kan je de laatste structuren wrappen in een synchronization wrapper.

[pedorus]

.oisyn schreef op donderdag 05 november 2009 @ 23:26:
[...]
Kun je eens proberen j als unsigned te definieren?

Unsigned maakt nauwelijks uit. De enige keer dat het echt effect heeft, dan werkt het negatief, en dat is als ik van i een UInt32 maak in combinatie met .Length (weer zo'n +8%). Het gekke is dat "UInt32 j = (UInt32) i * 3;" dan dus blijkbaar evengoed prima werkt, net als in het geval i een int is.

Soultaker schreef op donderdag 05 november 2009 @ 22:57:
Kun je de door de VM JIT-compiler gegenereerde code niet dumpen?

Suggesties voor tools? cordbg kon dit voor optimized code, maar tegenwoordig is er alleen nog mdbg, en die heeft de "dis"-functie niet. Ik vermoed dat (bijna) niemand dit soort dingen meer doet.

liquid_ice schreef op vrijdag 06 november 2009 @ 01:50:
@Pedorus:

Ik kom niet aan dezelfde getallen als jij.
Mijn test geeft een HEEL andere uitkomst zelfs.
Dit is mijn complete testcode:

Als ik jouw code gebruikt kom ik ook op dat soort resultaten, en dat lijkt vooral te liggen in het verschil tussen j=i*3/j+=3. Maar de reden is wat .oisyn aangeeft: je gebruikt static variabelen, die eventueel door andere Threads gewijzigd kunnen worden, waardoor je altijd bounds-checking krijgt. Daarnaast zie ik niet waarom je int j buiten de loop zou declareren, maar dat maakt niet zo veel uit. Probeer het eens met:

C#:

        static void fastFunction(int[] imageData, byte[] yuvBuffer)
        {
            for (int i = 0; i < imageData.Length; i++)
            {
                int j = i * 3;
                imageData[i] = (yuvBuffer[j] << 16 | (byte)(yuvBuffer[j + 1]) << 8 | 
                    (byte)(yuvBuffer[j + 2])) ^ 0x00008080;
            }
        }

En 100 is wat weinig, je had eerst 4000, dat lijkt me een mooier getal. Ik gebruik zelf trouwens Stopwatch.StartNew().

[liquid_ice]

@Pedorus, YOU ARE RIGHT.

+/- 25% snelheidswinst.

als dat zo is, waarom is de foreach dan eigenlijk niet NOG sneller, dan weet het systeem toch al lang van te voren dat ik ELK element wil hebben.

[.oisyn]

.oisyn schreef op vrijdag 06 november 2009 @ 00:53:
Oh crap ik ben in de war met writes naar write combined geheugen. Een test laat idd zien dat het geen drol uitmaakt.

Overigens, ik was dus niet in de war. Heb even gesproken met een guru op dit gebied, en hij zei dat de x86 sinds de P3 al lineaire access patterns herkent. Maar zowel voorwaarts als achterwaarts, en hij herkent ook meerdere onafhankelijke datastromen (de Core 2 doet er ongeveer 8). Ik heb nu een betere test [url=hhttp://pastebin.com/d60e98e3a]geschreven[/] waar dat ook uit blijkt.

total forward: 3202888266
total reverse: 3261369384
total random : 4969189827

Dat is nogal een verschil...

[ Voor 17% gewijzigd door .oisyn op 06-11-2009 15:37 ]

[liquid_ice]

ik volg je niet meer helemaal.

zou je een conclusie van je verhaaltje kunnen schrijven?

[.oisyn]

Dat als je je data op een lineaire manier accessed, dat de CPU dat herkent en dus van tevoren al dingen uit het geheugen gaat lezen in de cache gaat zetten (nog voordat jij om die data gevraagd hebt). Terwijl als je je data in een willekeurige volgorde afhandelt hij dat niet kan en je dus vaker cache misses zult zien. Maar dit verhaal gaat voor jou niet op omdat je sowieso bandwidth bound bent.

[ Voor 17% gewijzigd door .oisyn op 06-11-2009 15:42 ]