Arhiiv

Archive for the ‘Alustus’ Category

Koondfunktsioonid ja pudelikael

LINQ koos oma koondfunktsioonidega on suurepärane asi. Rööpes on sama asi saadaval nime all PLINQ (Parallel LINQ). See kattub suuremas osas jada-LINQiga, seega on see asjaga tuttavale väga lihtne kasutada.

Ainuke küsimus, mis tekib, on see, kuhu kirjutada AsParallel(). Tooksin ühe keerulisema praktilise näite, millega saate katsetada.

Oletame, et meil on sotsiaalvõrgustik, kus igal inimesel võib olla sõpru, ja sul on vaja soovitada kasutajale uusi sõpru, pakkudes neid inimesi, kellega tal juba on ühiseid sõpru. Mida rohkem ühiseid sõpru, seda eespool pakutav nimekirjas on.

Nii, lihtne… aga et asja keerulisemaks teha, ei ole meie objekti struktuur kõige paremate killast. Teeme iga inimese kohta järgmise objekti:

class Person
{
public int Id;
public Person[] Friends;
}

Kasutame tavalist jadaprogrammi, et koostada 10 000 liikmega sotsiaalvõrgustik, kus igal liikmel on kuni 300 sõpra:

//tekitame 10000 isikut
Person[] persons = new Person[10000];
Random r = new Random(); 

//paneme neist igaühele 0 kuni 300 sõpra
for (int i = 0; i < persons.Length; i++)
persons[i] = new Person { Id = i + 1, Friends = new Person[r.Next(300)] };

//valime sõpradeks juhuslikud inimesed
foreach (Person person in persons)
for (int i = 0; i < person.Friends.Length; i++)
while (person.Friends[i] == null)
{
Person friend = persons[r.Next(persons.Length)];
//kontrollime, et sõber ei oleks mina ise ja et sõpru ei satuks topelt
if (friend != person && !person.Friends.Contains(friend))
person.Friends[i] = friend;
}

Jadaprogrammi kasutasin seepärast, et Random objekt ei ole lõimeturvaline. Muidu võiks seda ka rööbelda.

Võtame juhusliku inimese, kellele hakkame uusi sõpru soovitama:

//valime seltskonnast juhusliku isiku
Person me = persons[r.Next(persons.Length)];
Console.WriteLine(“Me: “ + me.Id + ” having “ + me.Friends.Count() + ” friends”);
int maxcount = 10;

Sain sellise, kellel oli 254 sõpra.

Tegin nüüd lähteviiteks jadaprogrammi, millega soovitused leida:

//siia salvestame potentsiaalsed sõbrad
Dictionary<Person, int> potential = new Dictionary<Person, int>(); 

//käime läbi kõik minu sõbrad
foreach (Person friend in me.Friends)
//käime läbi kõik inimesed
foreach (Person person in persons)
//kontrollime, et see ei oleks mina ise ega minu sõbrad
if (person != me && !me.Friends.Contains(person))
//kas minu sõber on tema sõber?
if (me.Friends.Contains(friend))
//lisame potentsiaalsete sõprade hulka
if (potential.ContainsKey(person))
potential[person]++;
else
potential[person] = 1;

//sorteerime ühiste sõprade kogused
List<int> quantities = new List<int>();
foreach (int quantity in potential.Values)
if (!quantities.Contains(quantity))
quantities.Add(quantity);
quantities.Sort();

//käime ühiste sõpradega inimesed läbi, alustades suurima ühisarvuga
int count = 0;
for (int i = quantities.Count – 1; i >= 0 && count < maxcount; i–)
foreach (Person person in potential.Keys)
if (potential[person] == quantities[i])
{
Console.WriteLine(person.Id + ” (“ + quantities[i] + ” mutual friends)”);
if (++count > maxcount)
break;
}

Uhh, päris pikk sai. Selle programmi läbimise ajaks võtame 100%.

Teeme sama asja LINQiga:

foreach
(
var person in
//käime läbi kõik minu sõbrad
me.Friends
//valime kõigi isikute hulgast need, kel on minuga ühiseid sõpru
.SelectMany(s => persons.Where(p => p != me && p.Friends.Contains(s)))
//välistame need, kes on juba minu sõbrad
.Where(w => !me.Friends.Contains(w))
//grupeerime isiku järgi
.GroupBy(g => g)
//tekitame uue grupeeritud objekti
.Select(p => new
{
Person = p.Key,
Count = p.Count()
})
//järjestame kahanevalt
.OrderByDescending(o => o.Count)
//võtame lubatud arvu
.Take(maxcount)
) Console.WriteLine(person.Person.Id + ” (“ + person.Count + ” mutual friends)”);

See jada-LINQ-programm võttis samade tulemustega 53% ajast (mis näitab, et minu jadaprogrammi saaks veel oluliselt optimeerida).

Ja kogu see krempel rööpes nägi välja sama, ainult et AsParallel() oli pandud sellisesse kohta: s => persons.AsParallel().Where.

Rööplemine võttis aega ainult 10% algsest jadaprogrammist.

Pane tähele, et AsParallel() on ainult ühes kohas, esimese filtri ees. Siin seisnebki rööplemise kunst: leida see õige koht, kuhu see maagiline sõna sisse kirjutada. Kirjuta see valesse kohta ja kogu protsess võib minna nii pikaks, et isegi pärast lõunat ei ole veel valmis.

Kui sa nüüd mõtlesid, et ma olen vana kala ja mul oli õige koha leidmine käkitegu, siis sa eksid. Ma katsetasin ikka kümneid variante, enne kui leidsin selle, mis on parim. See koht on loogiline, sest põhiline on leida inimesed, kellega on ühised sõbrad. Kuna neid inimesi on suhteliselt vähe, ei tasu rööplemine hiljem end enam ära.

Kas AsParallel() võiks olla mitmes kohas? Proovige ja katsetage, mina ei saanud ajavõitu, tegelikult hoopis kaotasin ajas. Põhjus on ilmselt selles, et lõimesid tuleb siis jagada mitme rööpe vahel ja see piirab pudelikaelale kättesaadavate ressursside arvu. Aga pudelikael peaks saama maksimaalse võimaliku.

Aga proovige, kas suudate seda värki veelgi optimeerida. Ja andke oma avastustest häbenemata teada.

Õpetus

Õpetus on ilmne: leia koodist üks pudelikael ja kasuta rööbet selles kohas ning efekt võib olla tohutu.

Rööpsusastme piiramine

Eelmises blogis vaatlesime, kuidas rööpe sektsioonimisega võib ehitada jadakoodi sektsioone ja piirata rööbete arvu. Tegelikult on .NETis olemas ka spetsiaalsed parameetrid.

double[] values = new double[10000];

List<int> threadids = new List<int>();

values.AsParallel().WithDegreeOfParallelism(5).ForAll(value =>
{
int id = System.Threading.Thread.CurrentThread.ManagedThreadId;
Console.WriteLine(id);
threadids.Add(id);
});

Console.WriteLine(threadids.Distinct().Count() + ” lõime”);

Ülaltoodud koodis näed sätet WithDegreeOfParallelism, mis minu katsete põhjal piirab kasutatavate lõimede arvu. Me lihtsalt salvestame kõigi lõimede id-d ja vaatame pärast, mitu erinevat oli. Antud juhtumil oligi see täpselt 5. Sisendväärtuse suurenedes üle 10 ei kasvanud kasutatavate lõimede arv üle 10.

double[] values = new double[10000];

List<int> threadids = new List<int>();

Parallel.For(0, values.Length, new ParallelOptions{ MaxDegreeOfParallelism = 2 }, (i) =>
{
int id = System.Threading.Thread.CurrentThread.ManagedThreadId;
Console.WriteLine(id);
threadids.Add(id);
});

threadids.GroupBy(g => g).AsParallel().ForAll(s => Console.WriteLine(s.Key + ” “ + s.Count()));

Teises näites on tulemus huvitavam. Siin anname kaasa ParallelOptions objekti ja selle MaxDegreeOfParallelism peaks tähendama igal ajahetkel maksimaalset töös olevate ülesannete (task) arvu. Tulemus on, et erinevate kasutatud lõimede arv on sisendväärtusest umbes 2 korda suurem. Sisendi 1 korral on see 1 (see on siis jadaprogramm), aga 2 korral 4 ja 5 korral 10. Kui palju neid korraga jooksis, seda ei tea, aga erinevate lõimede rakendatus oli üsna erinev (viimasel real olnud grupeerimist kasutades oli näha, et lõimede hõivatuse vahe oli kuni 5-kordne).

Kokkuvõtteks, WithDegreeOfParallelism tundub rangem, samas kui MaxDegreeOfParallelism on lõdvem ja näitab mingit venivat rööpsusastet.

Rööpe sektsioonimine

Väikese ressursinõudlusega rööpsilmuste puhul võib tekkida probleem, kus rööbete käivitamisele kulub rohkem auru kui on kasu nende tööst. Selle probleemi vältimiseks võimaldab rööp-C# rööbete sektsioonimist (inglise keeles partitioning).

Sektsioonimiseks tuleb teha using System.Collections.Concurrent.

Vaata alltoodud näidet, kus on kõrvutatud 3 varianti ruutjuure võtmiseks:

static void Main(string[] args)
{
double[] values = new double[0xFFFFFF];
Parallel.For(0, values.Length, i => values[i] = i); 

DateTime start;

//variant 1: jada
start = DateTime.Now;
foreach (double value in values)
{
Math.Sqrt(value);
};
Console.WriteLine((DateTime.Now – start).TotalMilliseconds.ToString(“0”));

//variant 2: automaatne rööplemine
start = DateTime.Now;
Parallel.ForEach(values, value =>
{
Math.Sqrt(value);
});
Console.WriteLine((DateTime.Now – start).TotalMilliseconds.ToString(“0”));

//variant 3: sektsioonitud rööplemine
start = DateTime.Now;
Parallel.ForEach(Partitioner.Create(0, values.Length, values.Length / 4), p =>
{
for (int i = p.Item1; i < p.Item2; i++)
Math.Sqrt(values[i]);
});
Console.WriteLine((DateTime.Now – start).TotalMilliseconds.ToString(“0”));
}

Esimene, nagu ise näed, on jadakood. See andis mul ajaks 256 millisekki.

Teine on tavaline rööplemine (ma pole küll ForEach()-meetodit varem käsitlenud, aga see on iseennast selgitav jadaprogrammi foreach analoog). Teises variandis käivatatakse nii palju rööpeid kui torust tuleb, ja kuna silmuse sisu on suhteliselt lihtne, võib rööplemise organiseerimisele kuluda liigselt aega. Teise variandi puhul sain ma ajaks 64 millisekki.

Kolmandas variandis loome me esiteks sektsioonija (Partitioner), mille sektsioone saab ForEach()-abil kasutada. Iga sektsiooni sees käivitame jadaprogrammi, aga sektsioone endid käsitleme rööpes.

Partititioner.Create() võtab 3 argumenti: algväärtus, lõppväärtus ja ühe sektsiooni maksimupikkus. Antud juhtumil on kolmandaks argumendiks antud values.Length / 4 ehk siis tulemuseks on, et meil tekitatakse 4 sektsiooni ja mitte rohkem.

Muidugi teid huvitab nüüd, kas sellest oli ka mingit kasu: jah, väga vähe. Ma sain ajaks 53 millisekki, mis on 17% ajavõitu. Arvata on, et minu 8-tuumane prose pani variandis 2 käiku kõik tuumad, aga variandis 3 ainult 4 tuuma.

Pange tähele, et muutuja p (tüübiga Tuple<int, int>) meetodid Item1 ja Item2 ütlevad, mis on iga sektsiooni piirid, ja siin ei ole enam võimalik jadaprogrammis foreach-lähenemist kasutada.

Konkreetsete operatsioonide optimeerimisel on sektsioonimine ilmselt üks etapp, mis tuleb sul läbi katsetada, et kindlaks teha, milline lähenemine on parim. Muidugi sõltub tegelik mõju omakorda kliendi arvuti prosest ja võimekusest, aga lohutav on teada, et rööplemine on üsnagi täpselt konfitav.

Järgmises blogis vaatame veel paari muudetavat parameetrit.

Eranditöötlus rööpsilmuses

Mis saab, kui ühes rööpsilmuse lõimes tekkib erand? Teised silmused lõpetavad töö samamoodi nagu Stop()-meetodi puhul. Erandi poolt tekitatud katkestus on suurema prioriteediga kui Stop() ja Break(), aga siiski lubatakse kõigil lõimedel oma käsilolev tsükkel lõpule viia.

Klassil ParallelLoopState on selline asi nagu IsExceptional, mida pikalt töötavad tsüklid saavad aeg-ajalt kontrollida, et siis kiiremini pillid kotti panna. Alltoodud näites ei ole state.IsExceptional kunagi tõene, sest seda küsitakse tsükli alguses ja uut tsüklit ei alustata kunagi, kui mingi tsükkel on erandi tekitanud. Aga pikema tsükli keskel on küsimusel jumet.

static void Main(string[] args)
{
try
{
Parallel.For(0, 20, (i, state) =>
{
if (state.IsExceptional)
Console.WriteLine("Ups!");
else
{
Console.WriteLine(i);
if (i == 3)
throw new Exception("Ämber");
}
});
}
catch (Exception x)
{
Console.WriteLine(x.Message);
}
}

Kui sa selle koodi käivitad, võid näha, et pärast vea genereerimist lõpetavad tsüklid töö, kus keegi parasjagu on. Silmus ise tekitab erandi “One or more errors occurred” ja rohkem infot sisaldab InnerException.

Parallel.For Break ja Stop

Teises artiklis vaatasime, kuidas kasutada Parallel.For() meetodit. Kuidas silmusest välja pääseda? Jadaprogrammis teeksime nii:

for (int i = 0, i < 20, i++)
{
Console.WriteLine(i);
if (i == 10)
break;
};

Rööplemises võib selle jaoks võib võtta objekti tüübiga ParallelLoopState, mis pakub meetodeid Break() ja Stop().

Break() lõpetab kõik lõimed, kuid garanteerib, et lõpetamise ajaks on iga lõim jõudnud sama väärtuseni, mis oli lõimel, mis kutsus välja katkestuse.

Parallel.For(0, 20, (i, state) =>
{
Console.WriteLine(i);
if (i == 10)
state.Break();
}

Minu katsetuse puhul tähendas see, et väljastati arvud 0, 2, 3, 4, 6, 7, 9, 5, 1, 15, 16, 17, 18, 19, 10, 12, 14, 8. Nagu näed, 11 ja 13 on puudu, sest need lõimed olid juba surnud, aga 0 kuni 10 on kindlalt olemas.

Vastupidiselt sellele katkestab Stop() silmuse töö, sõltumata sellest, millisele tasemele teised lõimed on jõudnud. Seega, kui Stop() juhtub lõimes, mis on teistest parasjagu ees, võivad mõned väärtused vahemikust 0 kuni 10 isegi puudu jääda.

Break() ega Stop() ei garanteeri, et ei käivitada rohkem tsükleid kui vaja, ja see on täiesti loomulik, sest kõik lõimed hakkavad kohe täisvõimsusel hagu andma.

Eeltoodud näidet võiks kiirema pidamasaamise huvides muuta siis nii:

if (i >= 10)
state.Stop();

Kui jadaprogrammis on garanteeritud, et i ==10 ja seejärel i ==11, siis rööpes võib vabalt juhtuda, et esiteks i > 10 ja alles seejärel i==10.

Rubriigid:Alustus Sildid:, , ,

AsParallel()

IEnumerable<T> meetod AsParallel() tagastab ParallelQuery<T>, millele saab LINQi teha nagu tavaliselt. See on eriti mõnus, sest kasutada võib sisseharjunud lähenemist, samas kui kõik päringud tehakse rööpselt.

Katsetame seda asja pisut. Siin on meie eelmisest korrast tuttav rakendus. Loome massiivi ja teeme talle sama päringut nii jadas kui rööbis.

class Program

{

static void Main(string[] args)

{

double[] values = new double[0xFFFFFF];

Parallel.For(0, values.Length, i => values[i] = i);

DateTime start;

start = DateTime.Now;

values.Count();

Console.WriteLine((DateTime.Now – start).TotalMilliseconds.ToString(“0”));

1

start = DateTime.Now;

values.AsParallel().Count();

Console.WriteLine((DateTime.Now – start).TotalMilliseconds.ToString(“0”));

8

Console.ReadLine();

}

}

Mida me näeme? Seda, et rööpselt võtab töö 8 korda kauem, mis pole ka ime, sest sellist operatsiooni nagu Count() on mõttetu rööpselt teha.

Proovime nüüd midagi natuke keerukamat, võtame näiteks ruutjuure:

values.Select(s => Math.Sqrt(s)).Count();

550

values.AsParallel().Select(s => Math.Sqrt(s)).Count();

133

Ahaa, rööplemine on 4 korda kiirem. (Count() oli vajalik selleks, et päringut reaalselt käivitataks, nimelt on IEnumerable nii kaval, et ei hakka tõmblema, enne kui kirjeid tegelikult vajatakse.)

 

Nagu näete, on AsParallel() mõnus lisa, mis võimaldab juba olemasolevatele ja sissseharjunud päringutele rööplemise lisada, muutmata päringute koodi rohkem kui ühe sõna võrra. Loomulikult toimib see ka sellisel viisil:

 

from s in values.AsParallel() select Math.Sqrt(s)

 

Ja tänase katsetuse õppetund oli see, et päris igale poole ei tasu rööplemist lisada, aga isegi väiksemate tööülesannete puhul võib rööplemine märkimisväärselt aega kokku hoida.

Parallel.For()

Rööplemise katsetamiseks loo uus käsurearakendus. Sul läheb vaja Visual Studio 2010 ja .NET Framework 4. Võta menüüst File/New/Project ja sealt Visual C#/Windows/Console Application. Pane talle nimeks näiteks Rööp.

Paralleelprogrammeerimise vahendite namespace on System.Threading.Tasks.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Rööp
{
class Program
{
static void Main(string[] args)
{
Parallel.For(0, 100, i => Console.WriteLine(i));
Console.ReadLine();
}
}
}

See on sinu esimene rööprakendus. Sama asi jadas oleks

for (int i = 0; i < 100; i++) Console.WriteLine(i);

Milles on siis erinevus? Rööplemise korral kaasab .NET ülesande teostamisse kõik protsessorid. Proovi mõlemaid variante käivitada ja sa näed, et rööbeldes algab arvude loetelu küll ühest, kuid järjestus on suvaline (kuigi üldjoontes kasvav).

Samuti võid täheldada, et reeglite vastu pole eksitud (iga i väärtus esineb ainult ühe korra).

Ja veel võid ilmselt täheldada, et algus läheb üsna järjest 1, 2, 3, 4… kuni tööle hakkavad teised lõimed.

Kui nii rööplemine kui ka jada annavad sul täpselt sama tulemuse, on sul mingi veeuputusaegne arvuti, millel on võimalik ainult üks lõim Smile.

See lihtne katse tegi selgeks rööplemise kasu

Kujutle, et tegemist on tõeliselt aeganõudva ülesandega. Selle asemel et oodata, kuni üks prosetuum 100% peal seda krõmpsutab, võid kõik 8 tuuma tööle panna, millele peatselt järgneb ventilaatori pöörete tõus.

Kogu asja ilu on selles, et rööplemine saab läbi täpselt sel hetkel kui kõik lõimed on lõpetanud (ja nad lõpetavadki enam-vähem üheaegselt). Selle teostamine käsitsi tähendaks parajat portsu koodi, aga nüüd kulub selleks sama vähe vaeva kui jadakoodi puhul.

Vinge, kas pole? Stay tuned for more…

Rubriigid:Alustus Sildid: