Lära sig programmering, vilket språk?

Permalänk

Som svar på den ursprungliga frågan ...

... tycker jag att det finns två sätt att se det. Tycker du programmering och hårdvara är kul ska du fundera på att välja ett språk med lägre nivå. C är ett bra ställe att börja. Jag började själv med Basic sedan Fortran och sedan assembler. Sedan blev det PL/M och assembler igen. Sedan 20 år tillbaka är det mest C men assemblern har jag stor nytta av i t ex debugging och för att interfacea mina C-program mot speciell CPU-funktionalitet som t ex blockinstruktionerna. Jag arbetar både mot IT-branschen och mot inbyggda system.

Tycker du hårdvara är jobbigt så välj ett språk som är lite längre bort som t ex C# och Java.

Sedan 10 år kan jag inte längre skriva assemblerkod som är snabbare än vad min kompilator (OpenWatcom) kan generera :(. Däremot tror jag att jag vet jag hur jag ska uttrycka mig i C för att kompilatorn ska kunna göra snabbast möjliga assemblerkod av det :). Med detta sagt menar jag inte att jag skriver program som inte går att förstå eller underhålla.

Det är lättare att bli riktigt duktig i C än i C++. Jag kan ärligt säga att jag bara träffat en riktig superstar i C++, samma sak i C (tyvärr inte jag ). Men steget under är det betydligt mer tunnsått på C++ folk.

À propos algoritm kontra programmeringsteknik. För ett tag sedan skulle jag implementera en multitrådad RAM-baserad sorteringsalgoritm som skulle exekvera på ett multikärnesystem. Jag fann, ev felaktigt, att en Shell-sort skulle vara lättare att implementera än en Quick-sort. I enkeltrådad form är det inte jättestor skillnad i prestanda mellan dem, några tiotals procent.

Mitt testdata bestod av en miljon unika poster sorterade i stigande ordning. Testet var att sortera den (logiskt, med index) i fallande ordning alltså sista posten ska vara först och tvärtom.

Sagt och gjort. Jag började med att dela upp Shell-sorten så att varje kärna sköter en del av arbetet. Körde med tidtagning och vad fann jag? Att den multitrådade versionen behövde 32% längre tid att exekvera än den enkeltrådade.

Eftersom jag inte gärna ville tro att en multitrådad Shell-sort inte kunde vara snabbare än en enkeltrådad började jag analysera. Det visade sig att ett problem hade med sorteringstatistiken att göra: trådarna krockade när de skulle inkrementera samma statistikvariabler (ncompares och nswaps). En annan sak var att jobben som fördelades ut till resp tråd inte var cacheanpassade och dessutom på två olika sätt.

Jag har nu en snabb Shell-sort som blir snabbare ända upp till tre samtidiga trådar, sedan blir den långsammare igen. På en Core 2 Quad Q9300 och tre trådar sorterar den en miljon poster på 0,7 sekunder vilket jag är nöjd med.

Vad vill jag säga med detta? Jo hade jag inte varit intresserad och kunnig i assembler, hårdvara och prestanda hade jag inte vetat var jag skulle börja angripa multitrådningsproblematiken. Att sorteringstatistiken var en bov i sammanhanget var en riktig slamkrypare.

Bara för att man har en bra algoritm att utgå ifrån betyder det inte att vem som helst kan göra en kompetent implementation av den. Det omvända är också sant: det går att göra programmeringstekniskt och prestandamässigt mycket kompetenta implementationer av dåliga algoritmer. Vitsen är att göra en kanonimplementation av en bra algoritm.

Så gosh, var du än är, så har du mer rätt än du får credit för.

Permalänk
Avstängd

Hmmm.... Jo men om du hade studerat teori för parallella algoritmer, så hade du verkligen inte försökt göra en parallell version av shell sort. Istället hade du läst i böckerna och valt en sorteringsalgoritm som t.ex. går i O(logn log logn), vilket är marginellt långsammare än O(logn), dvs extremt snabbt. Så jag tycker snarare att ditt inlägg bevisar mitt påstående, att om man bara tutar och kör med en egen algoritm så kan det strula ordentligt. Nu råkar din metod ge bra prestanda för små indata (1 miljon tal) så det gick bra i ditt fall. Men kanske skulle du sparat tid om du haft mycket stora data, typ så mycket data som Google försöker hantera, eller om du jobbat med gen sekvensiering för biomedicinska forskare, eller nåt sånt. Då hade antagligen din metod säckat ihop totalt och man hade fått vänta bra många år på att få att få ett svar.

Det är ungefär som att försöka göra en egen krypteringsmetod, istället för att välja att implementera en känd säker metod. Det är antagligen mycket enkelt att knäcka en egen hembakad kryptoalgoritm - och en inte vidare bra ide att göra så.

Permalänk

You, det är intressant och läsa ju !

Visa signatur

Anything that can go wrong will go wrong.

Permalänk
Citat:

Ursprungligen inskrivet av saddam
Hmmm.... Jo men om du hade studerat teori för parallella algoritmer, så hade du verkligen inte försökt göra en parallell version av shell sort. Istället hade du läst i böckerna och valt en sorteringsalgoritm som t.ex. går i O(logn log logn), vilket är marginellt långsammare än O(logn), dvs extremt snabbt. Så jag tycker snarare att ditt inlägg bevisar mitt påstående, att om man bara tutar och kör med en egen algoritm så kan det strula ordentligt. Nu råkar din metod ge bra prestanda för små indata (1 miljon tal) så det gick bra i ditt fall. Men kanske skulle du sparat tid om du haft mycket stora data, typ så mycket data som Google försöker hantera, eller om du jobbat med gen sekvensiering för biomedicinska forskare, eller nåt sånt. Då hade antagligen din metod säckat ihop totalt och man hade fått vänta bra många år på att få att få ett svar.

Det är ungefär som att försöka göra en egen krypteringsmetod, istället för att välja att implementera en känd säker metod. Det är antagligen mycket enkelt att knäcka en egen hembakad kryptoalgoritm - och en inte vidare bra ide att göra så.

Från Wikipedia:

"Sorting algorithm
... Main article: Shell sort ...
... Although this method is inefficient for large data sets, it is one of the fastest algorithms for sorting small numbers of elements."

Givet att Wikipedia inte alltid har rätt, vad är problemet? Jag vill minnas att jag nämnde att det handlade om ett RAM-baserat data set (dvs begränsad storlek), dessutom hade jag begränsat med tid.

"Den råkar ge bra prestanda för små indata (1 miljon tal - jag vill minnas att jag skrev poster, det är liksom mera verklighet då) ..." för att den råkar vara en av de bästa algoritmerna för de förutsättningarna sedan den uppfanns (50 år sedan). Den står dessutom "i böckerna." Om jag hade försökt teoretisera fram en egen sorteringsalgoritm som är bättre än de som finns "i böckerna" hade man inte behövt vänta "bra många år på svaret (på sorteringen)," man hade inte haft någon algoritm överhuvudtaget! Jag är som du förstår varken Donald Shell eller Tony Hoare eller saddam och jag har aldrig trott det heller.

"... så det gick bra i alla fall." Jag vet att det var rena rama slumpen att jag lyckades göra en (tror jag) snabb implementation av den, kanske alldeles särskilt utifrån mitt förfarande att "tuta och köra." Hur visste du det? Kan du göra dig osynlig så att du suttit bredvid mig och sett hur jag gjort? Mycket kusligt.

Men om jag verkligen inte hade försökt göra en parallell version av Shellsort vilken algoritm borde jag verkligen ha försökt göra en parallell implementation av? Alla de riktigt vassa implementationerna av algoritmer och - gissar jag - även de vassaste algoritmerna är hemliga dvs NSA sitter på dem eller IBM eller någon annan.

Just det, frågan: vilken algoritm borde jag verkligen ha försökt göra en parallell version av givet förutsättningarna (du som vet menar jag)?

Permalänk
Avstängd

Nu gick det bra för dig ändå, så det spelar ingen roll nu. Du klarade dig bra med dina surt förvärvade kunskaper. Men om du hade jobbat på google där de försöker lagra hela internet så hade det antagligen varit kört om de bett dig sortera större datamängder.

Angående vilken algoritm som du borde försökt göra en parallell version utav, så borde du inte försökt alls. Det finns sorteringsalgoritmer som redan är parallella. Du borde försökt implementera en sådan. Parallell algoritmteori är mycket svårare än vanlig algoritm teori för 1 cpu. Det är nog bara att leta lite på nätet. Du kan googla på t.ex. "CRCW PRAM sort" eller nåt sånt.

Permalänk
Medlem
Citat:

Ursprungligen inskrivet av oforshell
...

Det är min åsikt att Shellsort inte är det bästa valet som en "generell" parallell sorteringsalgoritm.

Om man har små objekt och skalar upp antalet trådar/kärnor så känns det som att "gapen" kommer att trigga massiva problem med false sharing. Om kärnorna dessutom inte har delade cachar (t.ex. om man använder sig av multi-socket CPUs) så kommer "gapen" och de små objekten att göra så att endast en relevant nykel finns per cache-line, vilket leder till att Shellsort spenderar mindre tid med relevanta datamängder (per tråd) som är cachebara (d.v.s. hårdare tryck på systembussarna).

För rimliga mängder kärnor så skulle jag personligen föreslå en mergsort/"STL sort"-hybrid. D.v.s. att använda mergesort från början för att (jämt) partionera upp jobben för varje individuell tråd och sedan "STL sort" i varje tråd för att sortera dem individuella delmängderna.

Visa signatur

"Nothing is impossible because impossible itself says I M Possible..."

Permalänk

Mina kunskaper har inte varit surt förvärvade, jag har haft roligt nästan hela tiden.

Om jag hade arbetat på Google och försökt lagra hela internet hade jag inte heller valt Shellsort, problemet var av begränsad omfattning som jag skrivit.

Ja, parallell algoritmteori är rimligen svårare än seriell. Det finns dessutom en extra knorr och det är att den helst ska vara effektiv på flera kärnor vilket för in ett praktiskt moment i det hela.

Permalänk
Citat:

Ursprungligen inskrivet av Weeblie
Om man har små objekt och skalar upp antalet trådar/kärnor så känns det som att "gapen" kommer att trigga massiva problem med false sharing. Om kärnorna dessutom inte har delade cachar (t.ex. om man använder sig av multi-socket CPUs) så kommer "gapen" och de små objekten att göra så att endast en relevant nykel finns per cache-line, vilket leder till att Shellsort spenderar mindre tid med relevanta datamängder (per tråd) som är cachebara (d.v.s. hårdare tryck på systembussarna).

Det du beskriver är det jag stötte på. Men jag hade en processor med flera kärnor. Det fanns två problem: det ena att jag delade upp jobben jämnt (istället för i stycken som var multiplar av cachelinjerna) så att trådarna började slåss om samma cachelinje. Det andra att jag utförde en omgång sorteringar (x[i] med x[i+k] med x[i+2k] ...) istället för cachelinjevis (x[i] med x[i+k], x[i+1] med x[i+k+1] för att sedan gå vidare (x[i+k] med x[i+2k] ...) när linjerna uttömts.

Ha! Fick just en idé jag ska pröva!

Permalänk

Denna tråd är ju rätt komplett, men om jag vill lära mig programmering för att underlätta i mitt arbete inom administrera Windows-miljörer. Jag har naturligtvis börjat lära mig om batch och såleds även Powershell till dom nyare operativsystemen.

Det jag vill helst är att utveckla verktyg kring Active directory / server miljön,

Jag har dom senaste dagarna kollat igenom Både Java och Visual Basic, både användarböcker och tutorials.
Ingen av dessa har passat mina behov någonstans, och framför allt vill jag inte börja med C++/C då det är på tok avancerat för mig i nuläget. (Det kan dock ändras med rätt argument och om det finns lättare böcker för dessa språk)

Så någon som har en idé om vad man ska börja titta på?

Permalänk

Utan att ha arbetat med det tycker jag det är lite konstigt att du inte kommer åt AD via VB. Det du kan göra i C, C++ ska du kunna göra i VB. Det borde egentligen bara vara en frågan om att du har rätt (administratör) behörighet.

C i all ära men ska du ha interaktivitet (knappar, menyer, inmatningsfält) blir det mycket otympligt. Då föreslår jag ett "produktivt" språk som C#.

Om du däremot arbetar mot AD i batchmiljö (kommandorad) med enstaka parametrar tror jag C kan vara enklare. Men då får du sätta dig in i programmering genom deklarationer dvs att du bygger upp strukturer med data som ditt batchprogram kör igenom på ett generellt sätt, annars blir det bökigt.

Hoppas jag bidrog till att lösa ditt dilemma.

Felstavn
Permalänk
Medlem

Powershell som du börjat kolla på räcker väldigt långt. Om det bara är administration av windows du vill få ut av programmeringen tycker jag powershell räcker bra (förutsatt att det finns på miljöerna du ska administrera då). Powershell är ett helt språk, och du kommer åt hela .NET så allt du kan göra med C#, VB och övriga .NET-språk kan du göra med powershell mer eller mindre (fast det är givetvis inte det bästa valet för allt, powershell är ju designat för att underlätta administration, inte underlätta att skriva 3d-spel eller webbsidor)

Eventuellt skulle du kunna lära dig något mer språk för att få lite perspektiv på programmeringen, men för att koda admin-grejer är det nog minst lika bra att du försöker fördjupa dina powershell-kunskaper istället.

Permalänk
Skrivet av oforshell:

Utan att ha arbetat med det tycker jag det är lite konstigt att du inte kommer åt AD via VB. Det du kan göra i C, C++ ska du kunna göra i VB. Det borde egentligen bara vara en frågan om att du har rätt (administratör) behörighet.

C i all ära men ska du ha interaktivitet (knappar, menyer, inmatningsfält) blir det mycket otympligt. Då föreslår jag ett "produktivt" språk som C#.

Om du däremot arbetar mot AD i batchmiljö (kommandorad) med enstaka parametrar tror jag C kan vara enklare. Men då får du sätta dig in i programmering genom deklarationer dvs att du bygger upp strukturer med data som ditt batchprogram kör igenom på ett generellt sätt, annars blir det bökigt.

Hoppas jag bidrog till att lösa ditt dilemma.

Tackar, absolut det blir att kolla på C# lite djupare, samt kan man få det som grund att sedan möjligen lära sig andra språk.

Skrivet av vb:

Powershell som du börjat kolla på räcker väldigt långt. Om det bara är administration av windows du vill få ut av programmeringen tycker jag powershell räcker bra (förutsatt att det finns på miljöerna du ska administrera då). Powershell är ett helt språk, och du kommer åt hela .NET så allt du kan göra med C#, VB och övriga .NET-språk kan du göra med powershell mer eller mindre (fast det är givetvis inte det bästa valet för allt, powershell är ju designat för att underlätta administration, inte underlätta att skriva 3d-spel eller webbsidor)

Eventuellt skulle du kunna lära dig något mer språk för att få lite perspektiv på programmeringen, men för att koda admin-grejer är det nog minst lika bra att du försöker fördjupa dina powershell-kunskaper istället.

Jag tror du lyckades svara på min fråga rätt bra, det är nog att man ska få lite mer perspektiv på programmering, kolla hur dom binära koderna fungera och hur man styr variabler.

Jag kommer kolla på C# dels för att det verkar vara som en bra grund för mina ändamål samt att det är besläktat med både Java och .NET som inte alls är omöjligt att man tar upp i framtiden.

Tackar för svaren.

Permalänk
Medlem

Ett klargörande bara så du slipper bli förvirrad i framtiden:
C# är ett programmeringsspråk precis som powershell, Java, C, C++ osv.

.NET är ett ramverk som innehåller två saker, dels ett stort bibliotek av färdigskriven kod som kan göra en massa grejer, dels en runtime som kan köra .NET kod. När du kompilerar C#-kod så översätts den till .NET-kod, och kan därefter köras av .NET-runtimen.

Ungefär på samma sätt fungerar det med Java, bara att där heter ramverket Java, precis som språket Java alltså. Det är inte bara C# som kan kompileras till .NET-kod och köras i .NET-runtimen, även tex Visual Basic.NET körs där. Samma sak på är det med Java-ramverket, exempel på andra språk man kan använda är Scala och Groovy.

Om vi jämför med C++ så har inget stort ramverk på samma sätt. Det finns bara ett litet bibliotek av färdigskriven kod som standard, och du kör inte kod i en runtime på samma sätt, när du kompilerar C++-kod översätts den direkt till maskininstruktioner och kan köras direkt på datorn utan någon runtime.

Permalänk
Skrivet av vb:

Ett klargörande bara så du slipper bli förvirrad i framtiden:
C# är ett programmeringsspråk precis som powershell, Java, C, C++ osv.

.NET är ett ramverk som innehåller två saker, dels ett stort bibliotek av färdigskriven kod som kan göra en massa grejer, dels en runtime som kan köra .NET kod. När du kompilerar C#-kod så översätts den till .NET-kod, och kan därefter köras av .NET-runtimen.

Ungefär på samma sätt fungerar det med Java, bara att där heter ramverket Java, precis som språket Java alltså. Det är inte bara C# som kan kompileras till .NET-kod och köras i .NET-runtimen, även tex Visual Basic.NET körs där. Samma sak på är det med Java-ramverket, exempel på andra språk man kan använda är Scala och Groovy.

Om vi jämför med C++ så har inget stort ramverk på samma sätt. Det finns bara ett litet bibliotek av färdigskriven kod som standard, och du kör inte kod i en runtime på samma sätt, när du kompilerar C++-kod översätts den direkt till maskininstruktioner och kan köras direkt på datorn utan någon runtime.

Tackar för förklaringen.

Blev lite förundrad när jag letade böcker med C# och fann kombinerade böcker med C# och .NET.

Permalänk
Medlem

Vilket/vilka språk ska man kunna om man vill kunna göra iphones och android apps?

Visa signatur

Stationär: Ingen just nu, men snart.

Telefon: Iphone 3GS

Bärbar: MacBook Pro från 2011.

Permalänk
Medlem
Skrivet av Wiland:

Vilket/vilka språk ska man kunna om man vill kunna göra iphones och android apps?

Objective-C: Objective-C - Wikipedia, the free encyclopedia
Jag antar att du redan har en Mac dator, för det behövs om du vill kunna köra Apple's SDK.

Visa signatur

Citera eller nämn gärna mig (@ToJa92) om du svarar på något jag skrivit.
Uppskattar du eller blir hjälpt av ett inlägg jag skrivit är jag tacksam om du gillar det.

Permalänk
Medlem
Skrivet av Wiland:

Vilket/vilka språk ska man kunna om man vill kunna göra iphones och android apps?

Obj-C för iPhone, Java (för det mesta) för Android.

Det är dock fullt möjligt att skriva program i C eller C++ för iPhone också, bara det att många interface är i Obj-C. Android har också ett C-api om man behöver prestanda (som för spel).

Visa signatur

void@qnet
teeworlds, stålverk80, evil schemer, c, c++
Languages shape the way we think, or don't.

Permalänk
Medlem

Är lite konfunderad.. Jag sitter på en mac och är sugen på att börja programmera.. Vad ska man börja med egentligen? Har funderat på java, även C# och möjligen Python.. Men nu huttade jag något program som heter Eclipse(?). Vad är det här egentligen ? tips osv uppskattas

Permalänk
Medlem

Eclipse är en IDE, ett program där du skriver, kompilerar och felsöker koden. Eclipse används mest till java, men det stödjer så gott som alla vanliga språk. Det finns massor av IDE:r.
Min slutsats av den här tråden är i alla fall att det inte spelar någon jätte stor roll var du börjar, det viktiga är att du börjar. Det värsta som kan hända är att du inte trivs med språket, då är det bara att prova ett annat. Det är ju inte ett äktenskap man ingår.

Visa signatur

citera!

Permalänk
Medlem
Skrivet av Dosshell:

Eclipse är en IDE, ett program där du skriver, kompilerar och felsöker koden. Eclipse används mest till java, men det stödjer så gott som alla vanliga språk. Det finns massor av IDE:r.
Min slutsats av den här tråden är i alla fall att det inte spelar någon jätte stor roll var du börjar, det viktiga är att du börjar. Det värsta som kan hända är att du inte trivs med språket, då är det bara att prova ett annat. Det är ju inte ett äktenskap man ingår.

Okej! Tackar för tipsen och informationen.

Permalänk
Medlem

Tänkte låna tråden lite:

Jag vill börja programmera och kommer HT 13 börja på Dataingenjörsutbildningen på Chalmers (förutsatt att intagningspoängen ökas fatalt!). Vilket språk bör jag lära mig om jag ska kunna dra nytta av det i min kommande utbildning. Som jag har förstått det så börjar de från scratch med kullarna för att alla ska ha möjlighet att ligga på samma nivå men jag skulle gärna se till att jag inte är helt grön.

Visa signatur

:(){ :|:& };:

🏊🏻‍♂️   🚴🏻‍♂️   🏃🏻‍♂️   ☕

Permalänk
Hedersmedlem
Skrivet av YGLeXz:

Som jag har förstått det så börjar de från scratch med kullarna för att alla ska ha möjlighet att ligga på samma nivå men jag skulle gärna se till att jag inte är helt grön.

Brukar de inte köra Haskell på chalmers (jag är dock inte säker på om det gäller även för dataingenjörer)?

Permalänk
Medlem
Skrivet av gosh:

C++ är bra för där lyckas aldrig dumma programmerare ens få gjort något så man silar effektivt bort personer som förmodligen skulle vara till mer besvär än nytta för projektet.

Haha var bara tvungen o kommentera detta, just biten med att dumma programmerare inte får nått gjort, enligt Linus Torvalds tycker ju han detta om c++ : "C++ is a horrible language. It's made more horrible by the fact that a lot of substandard programmers use it, to the point where it's much much easier to generate total and utter crap with it. Quite frankly, even if the choice of C were to do *nothing* but keep the C++ programmers out, that in itself would be a huge reason to use C."

Om jag ska svara på topic skulle jag föreslå C# eller java, vanligt använda språk. Det är ju inte så vanligt när man försöker lära sig nått nytt att gå på det svåraste först och sedan gå mot det lätta, jag tycker i alla fall att det är bättre att skaffa sig en grundkunskap om programmering med ett enklare språk och när du väl har grundförståelsen kan du lättare gå vidare till andra språk.

Permalänk
Medlem
Skrivet av Elgot:

Brukar de inte köra Haskell på chalmers (jag är dock inte säker på om det gäller även för dataingenjörer)?

Jo, verkar vara så fortfarande (läste D för länge se). Iof vill man vara säker så är det lätt att kolla introkursen i programmering på linjen så ser man, förra årets kurshemsida brukar kunna ge ganska bra tips.

Haskell är annars en bra start, kan du lite Haskell sen innan kommer du ha ett stort försprång. Nästan alla kan 0 Haskell när dom börjar, och för en hel del blir det ganska tungt i början. (Iof kanske det blir lite tråkigt om man redan kan det, blir ju inte samma gemenskap med övriga klasskompisar då kanske?)

Förutom Haskell är det Java som gäller. Är inte heller så dumt att lära sig lite i förväg, då blir första java-kursen superenkel. Java är nog lite enklare att plocka upp från nätet tror jag. Fast egentligen kommer man långt på att kunna något liknande språk så blir Javan väldigt enkel i början.

Permalänk
Medlem
Skrivet av vb:

Jo, verkar vara så fortfarande (läste D för länge se). Iof vill man vara säker så är det lätt att kolla introkursen i programmering på linjen så ser man, förra årets kurshemsida brukar kunna ge ganska bra tips.

Haskell är annars en bra start, kan du lite Haskell sen innan kommer du ha ett stort försprång. Nästan alla kan 0 Haskell när dom börjar, och för en hel del blir det ganska tungt i början. (Iof kanske det blir lite tråkigt om man redan kan det, blir ju inte samma gemenskap med övriga klasskompisar då kanske?)

Förutom Haskell är det Java som gäller. Är inte heller så dumt att lära sig lite i förväg, då blir första java-kursen superenkel. Java är nog lite enklare att plocka upp från nätet tror jag. Fast egentligen kommer man långt på att kunna något liknande språk så blir Javan väldigt enkel i början.

Haskell är också hyfsat lätt att plocka upp från nätet: http://learnyouahaskell.com/

Permalänk
Datavetare
Skrivet av oforshell:

Jag har nu en snabb Shell-sort som blir snabbare ända upp till tre samtidiga trådar, sedan blir den långsammare igen. På en Core 2 Quad Q9300 och tre trådar sorterar den en miljon poster på 0,7 sekunder vilket jag är nöjd med.

Här ser vi vikten av att välja rätt algoritm, shellsort har dels relativt dålig algoritmisk komplexitet men värst är att det orsakar extremt mycket false-sharing om man gör den parallel då elementen för t.ex. gap 3 används som N,N+3,N+6... av tråd 1, N+1,N+4,N+7... av tråd 2 samt N+2,N+5,N+8... av tråd 3 (om man kör med 3 trådar). Element N, N+1 och N+2 lär ligga på samma cacheline men används av tre olika trådar == extrem false-sharing.

Testade att slänga ihop en quick-sort algoritm och sedan göra den parallel, kod nedan (går säker att optimera mera). Quick-sort är dels enkel att göra någorlunda parallel (men långt ifrån optimal för detta) och den är väldigt cache-snäll.
Den sortera 1M poster på 0.14s på 1 tråd, 0.10 på 2 trådar på min Core2Duo (2.4GHz) laptop.
10M poster går på 1.29s på en tråd och 0.70s på två trådar.

Måste kompileras med en kompilator som stödjer OpenMP. På Linux kan man kompilera programmet med så här om filen heter qsort.cpp. För de som inte känner till språket så är det C++. En stor fördel, enligt mig, med C++ över Java och C# är att C++ inte tvingar dig att använda objekt orientring. I detta fall så ger OO absolut ingenting så det är bara låta bli att använda det i C++ (inga klasser behövs definieras).

$ make CPPFLAGS="-O2 -fopen" qsort

och köras med

$ ./qsort <antal poster>

Det är möjligt att sortera alla typer av poster som har en copy-constructor samt har operator< och operator>= definierad.

#include <algorithm> #include <iostream> #include <sstream> #include <memory> #include <cstdlib> #include <sys/time.h> using namespace std; static unsigned long millis() { struct timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec * 1000 + tv.tv_usec / 1000; } template <typename T> static void fill_array(T a[], int n, int seed) { srand(seed); while (n-- > 0) a[n] = rand(); } template <typename T> static T * partition(T a[], int alen) { T pivot = a[0]; T *front = a + 1; T *back = a + alen - 1; for (;;) { while (front < back && *front < pivot) ++front; while (front < back && *back >= pivot) --back; if (front == back) break; swap(*front, *back); } /* move the pivot element into place */ --front; a[0] = *front; *front = pivot; return back; } template <typename T> static void my_qsort(T a[], int alen) { if (alen > 1) { T *snd = partition(a, alen); if (alen < 100000) { my_qsort(a, (snd - a) - 1); my_qsort(snd, (a + alen) - snd); } else { #pragma omp task my_qsort(a, (snd - a) - 1); my_qsort(snd, (a + alen) - snd); #pragma omp taskwait } } } int main(int argc, char *argv[]) { int n; unsigned long start; stringstream is(argv[1]); is >> n; auto_ptr<int> sort_me(new int[n * sizeof(*sort_me)]); fill_array(sort_me.get(), n, n); start = millis(); #pragma omp parallel #pragma omp single my_qsort(sort_me.get(), n); cout << "Took " << (millis() - start) / 1000.f << "s to sort " << n << " elements\n" << endl; }

Edit: testade lite på en Corei7 2600. Detta program blir snabbare hela vägen till dess att alla 8 CPU-trådar används
Här är resultatet att sortera 50M poster för 1, 2, 3, 4 och 8 CPU-trådar. taskset är ett program som låser ett program till visa CPU-trådar. taskset 0x1 låser programmet till första CPU-tråden, taskset 0xf låser programmet till det 4 första trådarna. Corei7 2600 numrerar CPU-trådarna så tråd 1-4 ligger på olika fysiska CPU-kärnor och tråd 5-8 är den andra HT på respektive fysisk kärna.

$ taskset 0x1 ./qsort 50000000
Took 4.264s to sort 50000000 elements

$ taskset 0x3 ./qsort 50000000
Took 3.95s to sort 50000000 elements

$ taskset 0x7 ./qsort 50000000
Took 2.362s to sort 50000000 elements

$ taskset 0xf ./qsort 50000000
Took 2.068s to sort 50000000 elements

$ taskset 0xff ./qsort 50000000
Took 1.377s to sort 50000000 elements

Så ett till interessant test är detta där vi använder två trådar, båda ligger på samma fysiska kärna men olika HT.

$ taskset 0x11 ./qsort 50000000
Took 4.039s to sort 50000000 elements

Att två HT ligger så nära fallet där två fysiska kärnor används + att fallet med 4 fysiska kärnor jämfört med fallet där alla 8 trådar används visar så pass stor effekt visar att hastigheten på sorteringen beror en hel del på minnesbandbredd och latens mot RAM. HT är som absolut mest effektivt när båda trådarna jobbar på samma data-set och där latens är en stor flaskhals. Detta är något som ofta är fallet i servers men i princip aldrig i spel och de flesta andra desktop-applikationer.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk

Jag gjorde den här grafen av dina siffror:

Jag argumenterar följande: det vore bättre att försöka hitta fler helt parallella uppgifter (tasks) att utföra samtidigt, låt säga 4st helt separata listor att sortera, än att parallellisera på det här viset. Då kommer du få bättre utnyttjandegrad.

Det finns såklart fall där att bli klar tidigare (latensen) är viktigare än hög effektivitet, och i så fall vill man såklart använda en så snabb parallell algoritm som möjligt. Men om man har många parallella uppgifter att utföra och inte har någon hård deadline så är en sekventiell algoritm antagligen mera effektiv.

För personer som är intresserade av algoritmer kan jag rekommendera den här fria (gratis) online-kursen som ges av en professor på Stanford och håller mycket hög kvalitet: http://www.algo-class.org/

Permalänk
Datavetare
Skrivet av VirtualIntent:

Jag argumenterar följande: det vore bättre att försöka hitta fler helt parallella uppgifter (tasks) att utföra samtidigt, låt säga 4st helt separata listor att sortera, än att parallellisera på det här viset. Då kommer du få bättre utnyttjandegrad.

Som jag skrev tidigare, quick-sort är extremt enkelt att köra parallellt på det sättet jag gjorde ovan, men det är långt ifrån optimalt. Finns sätt att även göra "partition" delen parallel.

Då det ändå är lördag och en av mina största hobbyn (vid sidan om jobbet som programmerare) är just att programmera så kunde jag inte låta bli att testa skriva en liknande variant med shell sort

#include <algorithm> #include <iostream> #include <sstream> #include <memory> #include <cstdlib> #include <sys/time.h> using namespace std; static unsigned long millis() { struct timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec * 1000 + tv.tv_usec / 1000; } template <typename T> static void fill_array(T a[], int n, int seed) { srand(seed); while (n-- > 0) a[n] = rand(); } template <typename T> static void insert_sort(T a[], int alen, int stride=1) { int l = ((alen + stride - 1) / stride) * stride; for (int i = stride; i < l; i += stride) { T key = a[i]; int j = i - stride; while (j >= 0 && key < a[j]) { a[j+stride] = a[j]; j -= stride; } a[j+stride] = key; } } template <typename T> static void shell_sort(T a[], int alen) { // Marcin Ciura's gap sequence int gap[] = {701, 301, 132, 57, 23, 10, 4, 1}; int i = 0; do { #pragma omp parallel for for (int j = 0; j < gap[i]; j++) insert_sort(a+j, alen-j, gap[i]); } while (gap[i++] > 1); } int main(int argc, char *argv[]) { int n; unsigned long start; stringstream is(argv[1]); is >> n; auto_ptr<int> sort_me(new int[n * sizeof(int)]); fill_array(sort_me.get(), n, n); start = millis(); shell_sort(sort_me.get(), n); cout << "Took " << (millis() - start) / 1000.f << "s to sort " << n << " elements\n" << endl; }

Har aldrig implementerat vare sig insert sort eller shell sort tidigare, så det finns garanterat förbättringar att göra. Det man kan konstatera direkt är två saker: shell sort är rejält mycket långsammare rent algoritmiskt, men den kan faktiskt utnyttja två kärnor klart mer effektivt jämfört med min qsort. Dock haverar den när man går från 4 till 8 trådar... Och HT gillar inte alls denna lika mycket. Fick köra med 2M poster i stället för 50M för att få ungefär samma wall-clock time på testerna. Detta är kört på min Core i7 2600 (som ej är överklockad då det är min jobbdator...)

$ taskset 0x1 ./shell_sort 2000000
Took 5.748s to sort 2000000 elements

$ taskset 0x3 ./shell_sort 2000000
Took 2.969s to sort 2000000 elements

$ taskset 0x7 ./shell_sort 2000000
Took 2.043s to sort 2000000 elements

$ taskset 0xf ./shell_sort 2000000
Took 1.695s to sort 2000000 elements

$ taskset 0xff ./shell_sort 2000000
Took 1.842s to sort 2000000 elements

Och här är två HT på samma kärna

$ taskset 0x11 ./shell_sort 2000000
Took 6.186s to sort 2000000 elements

Edit: den kanske inte är såå usel i alla fall. Testade den på min Core2 laptop på 1M poster och får ungefär samma resultat som oforshell

$ taskset 0x1 ./shell_sort 1000000
Took 1.334s to sort 1000000 elements

$ taskset 0x3 ./shell_sort 1000000
Took 0.783s to sort 1000000 elements

Kan tyvärr inte testa med fler än två trådar då jag bara har en Core2Duo...

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Datavetare
Skrivet av VirtualIntent:

Jag argumenterar följande: det vore bättre att försöka hitta fler helt parallella uppgifter (tasks) att utföra samtidigt, låt säga 4st helt separata listor att sortera, än att parallellisera på det här viset. Då kommer du få bättre utnyttjandegrad.

Verkar som OpenMP tyvärr är en ganska stor flaskhals för min qsort. Testade att skriva om den lite snabbt med Intel Cilk+ i stället

template <typename T> static void my_qsort(T *a, int alen) { if (alen > 1) { T *snd = partition(a, alen); if (alen < 100000) { my_qsort(a, (snd - a) - 1); my_qsort(snd, (a + alen) - snd); } else { cilk_spawn my_qsort(a, (snd - a) - 1); my_qsort(snd, (a + alen) - snd); } } }

och från att få en prestandaökning på x1.6 med OpenMP när jag går från en till två trådar så får jag x1.9 med Cilk+. Har tyvärr inte Cilk+ på Core i7 maskinen då det än så länge bara finns till ICC och har ingen ICC licens för kommersiellt bruk. ICC är dock gratis för personligt bruk så har ICC installerad på Core2 laptopen, så var den jag använde.

Edit: tyckte 1.9 lät bekant. Det är faktiskt väldigt nära teoretiskt max man kan få på det sätt jag valt att använda flera CPU-kärnor (låta "dived" steget dela upp de parallella bitarna) när man kör med en N*log(N) algoritm. Nu var min beräkning jag gjorde här baserad på 1M poster, men parallelismen skalar som log(N) där N är antal poster så det går bara att, teoretiskt sätt, få ut 20% mer parallelism ur 20M poster än 1M givet det angreppssätt jag använt.

Så det man kan konstatera här är att det är betydligt mycket viktigare att välja rätt run-time (Cilk+ i stället för OpenMP) i mitt fall än att sätta igång och ändra i hur algoritmen är implementerad.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Skrivet av Yoshman:

Som jag skrev tidigare, quick-sort är extremt enkelt att köra parallellt på det sättet jag gjorde ovan, men det är långt ifrån optimalt. Finns sätt att även göra "partition" delen parallel.

Då det ändå är lördag och en av mina största hobbyn (vid sidan om jobbet som programmerare) är just att programmera så kunde jag inte låta bli att testa skriva en liknande variant med shell sort

Jag tycker det var bra gjort! Jag bara menar att det finns begränsningar med hur mycket man kan parallellisera en algoritm, och ifall man kan hitta task-parallellism istället så kan det vara mera effektivt.

Kapitel 9 i boken Introduction to Parallel Computing 2nd ed, http://www.amazon.com/Introduction-Parallel-Computing-Ananth-..., handlar om parallella sortingsalgoritmer, så det kanske kan intressera dig. Du verkar förvisso redan ha bra koll på området!