[C# multithreading] Functie aanroepen in nieuwe thread

[PiepPiep]

Ik ben een beetje aan het spelen met meerdere threads in C#
Quicksort is makkelijk aan te passen naar multithreading omdat het telkens het op te lossen probleem in 2 stukken hakt en elk afzonderlijk oplost.
Echter kom ik er niet uit hoe ik dit moet doen in C#
De functie ziet er ongeveer zo uit

C#:

public void Sort(int[] buffer, int startPosition, int endPosition, int threadDepth)
{
    // <knip> code die ervoor zorgt dat van startPosition tot buffer[i] lagere waarden
    // heeft dan buffer[i] en na i tot endPosition grotere waarden heeft

    Sort(buffer, startPosition, i - 1, 0);
    Sort(buffer, i + 1, endPosition, 0);
}

Wat ik nu zou willen is

C#:

public void Sort(int[] buffer, int startPosition, int endPosition, int threadDepth)
{
    // <knip> code die ervoor zorgt dat van startPosition tot buffer[i] lagere waarden
    // heeft dan buffer[i] en na i tot endPosition grotere waarden heeft

    start_in_een_nieuwe_thread ( Sort(buffer, startPosition, i - 1, 0) );
    Sort(buffer, i + 1, endPosition, 0);
    wacht_op_andere_thread
}

Ik kom 2 opties tegen om te kunnen multithreaden, dat zijn ThreadPool en Thread.

Als ik ThreadPool gebruik kan ik via QueueWorkerItem een functie op een lijst zetten die uitgevoerd wordt zodra er een thread vrij is.
De functie die aangeroepen is kan ik 1 argument meegeven wat een structure kan zijn met daarin de gegevens die de functie nodig heeft.
Tot zover is het goed, maar het wachten tot de thread klaar is lijkt onmogelijk.

Via de class Thread kan ik met Join() wachten op de andere thread zodat ik weet wanneer deze klaar is, maar deze heeft weer als nadeel dat ik geen structure kan meegeven met de informatie wat hij moet doen.
Wat ik kan vinden om deze data mee te geven is dat ik een aparte class moet maken en de data erin stoppen en vervolgens de ThreadProc van de nieuwe thread een function uit deze class meegeven.

Ik vind het eigenlijk al een beetje omslachtig om voor die ThreadPool een structure te maken en vullen, laat staan dus een hele class met functies om het via Thread te doen.
Is hier niet een makkelijkere oplossing voor?

Tot nu toe kan ik dus alleen deze 2 oplossingen vinden (waarvan de 1e dus eigenlijk niet eens gaat werken).
Ik heb gezocht in het boek Microsoft .Net framework application development foundation (70-536) en via google.

[pedorus]

Hier en hier heeft iemand hetzelfde 'probleem' opgelost. Parallel.Do is later Parallel.Invoke geworden.

[ Voor 16% gewijzigd door pedorus op 28-08-2010 19:05 ]

[Verwijderd]

Parallel.Invoke heeft alleen zin als je beide sorts als delegates tegelijk meegeeft. Als je voor elke sort een Parallel.Invoke doet kun je het net zo goed serieel doen.

[Soultaker]

Ik denk dat de ThreadPool oplossing wel kan werken, als je expliciet joint, bijvoorbeeld met een expliciete semaphore (een mutex volstaat niet omdat die binnen dezelfde thread moet worden geclaimt en vrijgegeven).

Je creëert in de main thread dus een gelockte semaphore, die je releaset in de child thread (nadat die klaar is met sorteren); in de main thread kun je daar op wachten en daarna de semaphore weer opruimen (als dat nodig is in C#).

Overigens is de overhead van zo'n constructie relatief hoog (met een ThreadPool wel minder dan met een nieuwe Thread, maar dan nog) dus is het alleen zinnig om nieuwe threads te spawnen als je een relatief grote deelarray gaat sorteren.

Verder is deze constructie niet echt optimaal omdat zo steeds de ene thread op de andere moet wachten. Een betere aanpak (met de ThreadPool) zou zijn:

code:

void Sort(Semaphore sem, int[] data, int start, int end)
{
    if (end - start > 1000) {
        sem.WaitOne();
        ThreadPool.AddTask(new SortTask(sem, data, start, end));
    } else {
        // sorteer hier
    }
}

void SortTask(Semaphore sem, int[] data, int start, int end)
{
    int middle = Partition(sem, data, start, end);
    Sort(sem, data, start, middle);
    Sort(sem, data, middle + 1, end);
    sem.Release();
}

void Sort(int[] data)
{
    Semaphore sem = new Semaphore();
    Sort(sem, data, 0, data.length);
    sem.wait();
}

(Bovenstaande is natuurlijk pseudocode want ik kan geen C#.) Het voordeel van zo'n constructie is dat er maar één thread is die wacht (de main thread) en alle andere threads kunnen nuttig werk verrichten. De semaphore wordt gebruik om bij te houden hoeveel work items er nog in de queue zitten en daar kun dus op gewacht worden.

[ Voor 72% gewijzigd door Soultaker op 28-08-2010 20:11 ]

[PiepPiep]

Het werkt!
Ik zocht dus Parallel.
Ik werk nog met visual studio 2008 en .net versie 3.5 dus ik moest even iets installeren. In .net 4.0 zit het wel standaard erin begreep ik.
Mijn code ziet er nu als volgt uit :

C#:

            // start 2 other quicksorts now
            if (threadDepth > 0)
            {
                Parallel.Invoke(
                    () => Sort(buffer, startPosition, i - 1, threadDepth - 1),
                    () => Sort(buffer, i + 1, endPosition, threadDepth - 1));
            }
            else
            {
                Sort(buffer, startPosition, i - 1, 0);
                Sort(buffer, i + 1, endPosition, 0);
            }

Met die laatste parameter threadDepth geef ik aan of er nog wel extra threads gemaakt mogen worden.

Mijn test resultaten :

Voor de test maak ik een reeks van 10 miljoen int's aan die ik sorteer.
Dit doe ik met threadDepth 0 t/m 9 om te kijken hoe snel het geheel is met telkens 2 keer meer threads.
De tijden die ik kreeg waren

00:00:08.097 1 thread
00:00:07.784 2 threads
00:00:06.281 4 threads
00:00:05.847 8 threads
00:00:04.712 16 threads
00:00:04.326 32 threads
00:00:04.115 64 threads
00:00:04.125 128 threads
00:00:03.243 256 threads
00:00:03.287 512 threads

Als ik niet met threadDepth werk maar met

C#:

            if (endPosition - startPosition > 100000)

Dan kan ik die 100.000 varieren tussen 10.000 en 1.000.000 en kom altijd rond de 3.2 seconden uit.

Als ik de if er helemaal uit sloop dan haalt hij het nog net binnen een minuut.
Veel te veel overhead dus.


/edit
De oplossing van Soultaker vind ik trouwens ook wel mooi, die ga ik misschien nog een andere keer proberen.
Dat zal iets meer code geven om de lock en/of semaforen te maken, maar je hebt er niet perse de nieuwste .net versie of externe libraries voor nodig.
(veel klanten op m'n werk hebben namelijk zelfs .net 3.5 nog niet eens)

[ Voor 9% gewijzigd door PiepPiep op 28-08-2010 21:03 ]

[pedorus]

Eigenlijk wacht .Invoke op teveel plekken, alleen het wachten op de volledige methode is relevant. Wat gebeurd er als je in plaats daarvan een counter bijhoudt, zeg:

C#:

int openTasks = 1;

en deze verhoogt met Interlocked.Increment(openTasks) als je iets nieuws scheduled met ThreadPool.QueueWorkerItem(), en met if(Interlocked.Decrement(openTasks)==0) een ManualResetEvent voor het geheel zet op het einde van een taak? (Zowel ref openTasks als de ManualResetEvent doorgeven aan Sort natuurlijk.)