C++ er svaret - men hvad var egentligt spørgsmålet?

45 kommentarer.  Hop til debatten
C++ er svaret - men hvad var egentligt spørgsmålet?
Illustration: Julia Kryuchkova.
Bjarne Stroustrup giver et omfattende tilbageblik på sprogets nylige historie og udvikling.
23. juli 2020 kl. 02:52
errorÆldre end 30 dage
Manglende links i teksten kan sandsynligvis findes i bunden af artiklen.

35 år efter, at den danske datalog Bjarne Stroustrup officielt lancerede C ++, er det stadig blandt verdens mest anvendte og populære programmeringssprog. Dette til trods for, at der er skabt en række andre programmeringssprog i eftertiden.

Årsagen kan være, at de ikke er skabt med samme formål som C++. For hvis C ++ er svaret, hvad var så spørgsmålet?

Bjarne Stroustrup svarer på dette i en artikel, han har offentliggjort i ​​tidsskriftet Proceedings of the ACM on Programming Languages.

Log ind og få adgang
Du kan læse indholdet ved at logge ind eller oprette dig som ny bruger.
45 kommentarer.  Hop til debatten
Debatten
Log ind for at deltage i debatten.
settingsDebatindstillinger
45
30. juli 2020 kl. 13:49

Thjaa, tråden er kommet langt væk fra C++, men er da stadig interessant læsning.

@Jens D Madsen, når du skriver:

Hvis du ser på mine beskrivelser af hardware, så er det noget helt andet end en PC. Selv en computers registre er på harddisken, og computere har ingen ram, andet end cache.

så er det godt nok meget forskelligt fra de servere, hvor Oracle og andre tilsvarende produkter kører. Selvom de afgjort heller ikke er PC'er (hvilket jeg ikke på noget tidspunkt har antydet) så er de meget traditionelle med nogle CPU'er med cache, RAM, netværk, I/O, diske osv.

Du skriver også - helt korrekt - at de velkendte relationelle databaser ikke er realtid. Nej, sådan er de ikke designet. De er designede som flerbruger systemer, i virkeligheden helt i samme ånd som f.eks. mainframes og det tidlige VMS hardware, jeg har linket til et godt stykke oppe. Så vi kan ikke garantere eksekveringstider, men vi kan bygge meget komplekse systemer, hvor vi går efter regler, som at et vist antal procent (måske 95, 98, 99) af ekseveringerne af en bestemt operation er hurtigere end en bestemt grænse. Uanset om du spørger telefonselskaber, banker, detail handel, internet forretninger, produktionsvirksomheder, flyselskaber, eller stort set hvilken som helst anden type kunder, så er det det, der efterspørges. Det er så systemer, der kan understøtte tusindvis, ti-tusindvis, ja hundred-tusindvis af samtidige brugere. Det er det vi kalder skalering, og du har allerede nævnt, at en af de mange værktøjer vi har i kassen til at skalere er at lade flere systemer arbejde sammen. I princippet er det nemt: Hvis en operation tager 1ms på en CPU, så kan en server med 100 CPU'er klare 100.000 operationer per sekund.

Men kom nu på banen med konkrete eksempler på systemer, hvor den hardware du beskriver anvendes.

44
29. juli 2020 kl. 18:46

Hvilken computer er det du taler om? Dem du bygger? En computer har ikke registre, det har en CPU. En computer har heller ikke nødvendigvis en harddisk, men den kan godt have en CPU med registre - hvordan forklare du det?

Jeg syntes også, at vi er kommet ud i en del der ikke hører hjemme i tråden. Det, som jeg syntes hørte hjemme under C++, var at det vil være en stor fordel for sproget, at have tilføjet køer, så at sproget blev parallelt, og at klasser kunne betragtes som parallele. Jeg har aldrig syntes at C++'s indkapslede tilstandsmaskiner havde noget med objekter at gøre.

Derudover er vi kommet ind på cache og optimering. Hvordan det gøres bedst i softwaree ved jeg ikke, men i HW laver vi ofte frekvensanalyse, og det medfører at flerdimmensionelle array får index for deres bits swappet sammen, og at områder hvor der bruges binær søgning, får reverseret bit addressen, så at højeste bit er lavest.

Om computere har registre og harddisk, syntes jeg er at gå for vidt i diskussionen, men jeg beklager at jeg har formuleret mig dårligt.

43
29. juli 2020 kl. 17:12

Selv en computers registre er på harddisken, og computere har ingen ram, andet end cache. Computeren har f.eks. en kopieringsmaskine, der kan kopiere data på harddisken, eller opbevare gentagne strukturer, uden det tager tid at udføre operationen. Og ram'en er ikke andet end en fil der åbnes. Og det samme med CPU'ens registre. Databaser er en integret del, af den måde som en computer arbejder, og en del af computerens hardware og operativsystm. Det, som du gør, når du laver din egen database, det er ikke andet, end at lave en database på en computer, som allerede har effektive databaser som del af hele dens funktion

Hvilken computer er det du taler om? Dem du bygger? En computer har ikke registre, det har en CPU. En computer har heller ikke nødvendigvis en harddisk, men den kan godt have en CPU med registre - hvordan forklare du det?

Som jeg tidligere har beskrevet, så mener jeg, at PC'er er en opfundet løsning, for at gøre alt så besværligt som muligt.

Mener du virkerlig det? Der er nok en del der er uenige med dig i det.

42
29. juli 2020 kl. 14:56

Det, som vi lavede i sin tid var realtids software og vi skulle derfor garantere meget hurtige svartider, og også garantere at softwaren svarede indenfor meget strenge tidskrav. Kunderne havde eksternt udstyr med lamper der lyste, hvis vores udstyr ikke opfyldte timing, og så fik vi balade. I praksis kunne det kun løses, ved at vi helt selv havde styr på kodningen, og sikrede os, at de opbevarede data lå i ramlager. Kunden have imidlertid krav til at det skulle virke sammen med en SQL database, men den blev kun anvendt til at opdatere, søge informationer mv. og var ikke så tidskritisk. Dog, så var krav til, at der ikke måtte gå mere end nogle få sekunder, fra at data var indtastet i SQL databasen, og til at de var skrevet og blev brugt i vores software. Denne forsinkelse, var ikke direkte under realtidsdelen, men var alligevel svær at garantere. Indenfor mange opgaver er der tidsmæssige krav, der aldrig må overskrides - hvis de overskrides, så går hardware, eller meget dyre anlæg i stykker.

I den forbindelse, savnede vi data over SQL databaserne som havde garenterede svartider Typiske svartider kunne vi ikke bruge. Men, så vidt jeg ved, fantes ingen SQL databaser, der kunne garantere en svartid. Der fantes kun oplysninger om statistiske svartider og ingen worst-case svartid. Jeg ved at SQL databaser er blevet mange gange hurtigere end den gang og sekunder virker i dag som en evighed i databaser. Men, findes egentligt worst-case svartider oplyst for SQL databaser i dag?

41
29. juli 2020 kl. 13:42

Re: Teori og praksis</p>
<p>Jeps, vi skriver vores egen... Jeg har arbejdet for Oracle i 25+ år!</p>
<p>Ok tak, så giver det jo meget mere mening, for der hvor jeg (og sikkert hovedparten af alle programmører) befinder mig giver det jo lige præcis ikke mening at gå ned i den detaljeringsgrad, men stole på at du og dine kollegaer laver et godt stykke arbejde :-)

Det du skrev giver langt større mening nu - jeg havde lidt svært ved at forstå dit problem fra starten. Normalt, kan man opsætte flere identiske synkrone databaser med samme indhold, hvis man bare har brug for en større læsehastighed, og så vil man ikke gå så meget i dybde med at optimere. Eller, som vi gjorde i sin tid, have vores egen kopi af nødvendige data i vores eget software/ram.

Jeg kan godt se, at problemet er noget lidt andet, når man arbejder med at udvikle selve databaser. Jeg mener, at den rette måde at gøre det, er at udvikle såvel hardware som operativsystem til at løse opgaven, og at det ikke er en opgave for brugersoftware, men en opgave for hardwaren og operativsystem.

40
29. juli 2020 kl. 13:34

Filformater? Harddisk?
@Jens D Madsen: Jeg taler overhovedet hverken om filformater eller harddisk. Jeg forsøger blot at sige, at Oracle ikke kunne skrives med en generisk hardware abstraktion. Af gode grunde kan jeg ikke fortælle detaljer om vores software; men jeg har givet en række eksempler, der er lidt i den rigtige retning, og som viser, at det er nødvendigt for os at lave hardware specifikke tilpasninger.</p>
<p>Antallet af computer og operativ system typer er i dag mindre, end da jeg startede i slut firserne, men dengang som nu var netop hardware tilpasning en vigtig del af vores software.

Hvis du ser på mine beskrivelser af hardware, så er det noget helt andet end en PC. Selv en computers registre er på harddisken, og computere har ingen ram, andet end cache. Computeren har f.eks. en kopieringsmaskine, der kan kopiere data på harddisken, eller opbevare gentagne strukturer, uden det tager tid at udføre operationen. Og ram'en er ikke andet end en fil der åbnes. Og det samme med CPU'ens registre. Databaser er en integret del, af den måde som en computer arbejder, og en del af computerens hardware og operativsystm. Det, som du gør, når du laver din egen database, det er ikke andet, end at lave en database på en computer, som allerede har effektive databaser som del af hele dens funktion. Mange af de funktioner som er nødvendige, er det en stor fordel er en del af computerens hardware. Ved at lave computerne og compilere korrekt, så er det meget nemmere at programmere. En forsker bruger ikke tid på at finde gode algoritmer for at løse et problem hurtigt, uden de også bruger tid på at finde ud af hvordan at det pågældende problem normalt kodes, og ikke mindst at finde ud af ligningerne der bringer systemet fra den normale kode og over til den effektive kode. Det, som er udfordringen, er ikke kun at finde den nye algoritme - det er i højere grad, at kunne beskrive hvordan at man løser problemet, ved at gå skridtvis fra problemet som det typisk formuleres, og over til den effektive løsning. Dette gælder både ved optimering af store O funktioner og parallelisering. Når man løser et problem, så begynder man ikke at optimere programmer. Ingen programmer skal omskrives. Det man gør, er at man tilføjer til databasen der optimerer kode, hvordan den skal optimere koden, så de nye metoder tages i brug, og alt software i verden omksrives til at anvende de nye metoder samtidigt. Det er så her, at der kan være problemer - for man skal helst ikke downloade opdateringer til automatikken fra USA, som får alt software til at gå langsommere.

Som jeg tidligere har beskrevet, så mener jeg, at PC'er er en opfundet løsning, for at gøre alt så besværligt som muligt. Og så er korrekt, at du skal side og nørde med småting, fordi at din hardware simpelthen fra bunden er udviklet helt forkert. Anvender man kataloget over dårlige løsninger, og ophæver det til den rette, så får man de problemer man har ønsket sig.

39
29. juli 2020 kl. 12:58

Re: Teori og praksis</p>
<p>Jeg har ikke kendskab til SQL databaser, men</p>
<p>... alligevel føler du et behov for at udtale dig om noget du ikke ved en bønne om, og dermed skaber en frygtelig masse støj - især fordi spørgsmålet var ret konkret, stillet til Bjørn!

Jeg beskrev det som vi gjorde, i en virksomhed jeg var ansat for en del år siden. De mennesker, som jeg arbejdede sammen med, havde stor kendskab til SQL databaser. De valgte at have en synkroniseret cache, til de oplysninger der skulle udlæses hurtigt, og som var del af programmet. Den var ikke større, end der var plads til alle dataene i rammen, da det kun var en brøkdel af SQL databasens data, der var nødvendigt kunne læses hurtigt. De blev så udskiftet, når SQL databasen blev ændret/opdateret - og SQL databasen havde nogle features, som kunne holde en kopidatabase synkroniseret. Jeg kan ikke se, at mit kendskab til SQL databaser har betydning, når det jeg beskriver er, hvordan at andre eksperter jeg har arbejdet sammen med har løst opgaven.

37
28. juli 2020 kl. 18:28

@Jens D Madsen: Jeg taler overhovedet hverken om filformater eller harddisk. Jeg forsøger blot at sige, at Oracle ikke kunne skrives med en generisk hardware abstraktion. Af gode grunde kan jeg ikke fortælle detaljer om vores software; men jeg har givet en række eksempler, der er lidt i den rigtige retning, og som viser, at det er nødvendigt for os at lave hardware specifikke tilpasninger.

Antallet af computer og operativ system typer er i dag mindre, end da jeg startede i slut firserne, men dengang som nu var netop hardware tilpasning en vigtig del af vores software.

36
28. juli 2020 kl. 18:13

Sådan en gang til for Prins Knud, skal det forstås som at I ikke bruger en eller anden standard SQL motor (efter hvad man nu kan lide), men har hårdkodet jeres helt egen DB motor?

Jeps, vi skriver vores egen... Jeg har arbejdet for Oracle i 25+ år!

35
28. juli 2020 kl. 18:02

Jeg har ikke kendskab til SQL databaser, men

... alligevel føler du et behov for at udtale dig om noget du ikke ved en bønne om, og dermed skaber en frygtelig masse støj - især fordi spørgsmålet var ret konkret, stillet til Bjørn!

34
28. juli 2020 kl. 03:09

Sådan en gang til for Prins Knud, skal det forstås som at I ikke bruger en eller anden standard SQL motor (efter hvad man nu kan lide), men har hårdkodet jeres helt egen DB motor?

Jeg har ikke kendskab til SQL databaser, men for mange år siden var jeg hos en virksomhed hvor vi anvendte en SQL database - det er noget af det sløveste jeg nogensinde har oplevet. Måske 100-1000 gange sløvere, end det burde være. Men det er nok bedre i dag. De bruges jo ofte på Internet, og her har jeg ikke haft problem med hastigheden. Mener, at vi kunne abonnere på data, og gemme dem i vores egen ram cache, og bede til, at data var synkrone. (Så var hastigheden nanosekunder - og en oplevelse!) Ved ikke om der var en tjeksum eller lign fra SQL databasen, der sikrede data var synkron med ram. Det er nok et fornuftigt krav til en SQL database.

33
28. juli 2020 kl. 01:15

Det jeg forestiller mig, er at C++ kan gøres parallelt, ved at tilføje køer. Jeg har valgt at definere køer med << som unær oprator i det følgende. Måske kan vælges en anden (bedre) syntax.

// --- //

Eksempel 1:

// --- //

// I dette eksempel gemmes først tegnene 'T' 'e' 'x' 't' sekventielt i en kø.

// Herefter udskrives den.

// Normalt sker det i rækkefølge.

// På en god computer, gemmes 'T' 'e' 'x' 't' samtidigt (parallelt) med udskrivning da det er uafhængigt og kan køre i to tasks.

// Vi kan ikke se forskel på opførslen, da det funktionsmæssigt er identisk.

// Kode eksempel 1:

char<< txtstr; // define txtstr som char stream (<< angiver kø deffination her)

char c; // Definer char

main {

txtstr << 'T' << 'e' << 'x' << 't'; // Put T e x t ind i stream af char

for(i = 1; i<=4; i++ ) { // Gennemløb 4 gange

c << txtstr; // Læs et tegn fra txtstr til c

cout << c; // Udskriv char c, "Text"

}

}

// --- //

Eksempel 2:

// --- //

// Dette svarer til eksempel 1, men er med tal

// Normalt gemmes først tallene i køen, og herefter udskrives.

// På en god computer sker det parallelt - derfor kan køerne også være uendeligt store og behøver ikke at få defineret størrelse.

// Når en fysisk kø er ved at blive fyldt, så vil den skifte til den task som læser ud. Det er kun den task der skubber data ind, som går i wait, når der ikke er plads i køen. Udskrivningen foregår stadigt, og der bliver plads til nye data.

// Kode eksempel 2:

int<< intqueue;

int i, j;

main {

for(i = 1; i<=10; i++ ) {

intqueue << i; // Tilføj i (1,2,3,4,5,6,7,8,9,10) til intqueue

}

for(i = 1; i<=10; i++ ) {

j << intqueue; // Hent værdi fra kø

cout << j; // udskriv værdi på skærm (1 2 3 4 5 6 7 8 9 10)

}

}

// --- //

Eksempel 3:

// --- //

// Dette eksempel kan ikke køre i rækkefølge.

// Men, det kører fint parallelt. Her kører de to task parallelt, da der ikke er analyseret afhængighed.

// Vi kan således godt have tasks i koden, der behandler uendelige mængder data via køer.

// Kode eksempel 3:

int<< intqueue;

int i, j;

main {

i = 0;

while (true) do { // Fortsæt uendeligt

i++;            // Læg tallene ind i rækkefølge

intqueue << i;  // Tilføj i (1,2,3,4,5,6,7,8,9,10...) til intqueue

}

while (true) do { // Fortsæt uendeligt

j << intqueue; // Hent værdi fra kø

cout << j; // udskriv værdi på skærm (1 2 3 4 5 6 7 8 9 10...)

}

}

// --- //

Eksempel 4:

// --- //

// Dette eksempel viser at når det er uafhængighed, så kan vores kode godt køre omvendt.

// Kode eksempel 4:

int<< intqueue;

int i, j;

main {

i = 0;

while (true) do { // Fortsæt uendeligt

j << intqueue; // Hent værdi fra kø

cout << j; // udskriv værdi på skærm (1 2 3 4 5 6 7 8 9 10...)

}

while (true) do { // Fortsæt uendeligt

i++;            // Læg tallene ind i rækkefølge

intqueue << i;  // Tilføj i (1,2,3,4,5,6,7,8,9,10...) til intqueue

}

}

// --- //

Eksempel 5:

// --- //

// Her et eksempel med testvektorer

// Kode eksempel 5:

int<< intqueueA; // Opret stream intqueueA af integers

int<< intqueueB; // Opret stream intqueueB af integers

int<< intqueueY; // Opret stream intqueueY af integers

int i,a,b,j;

main {

intqueueA << 2 << 3 << 5 << 7 << 11 << 13 << 17 << 19 << 23 << 29;

intqueueB << 31 << 37 << 41 << 43 << 47 << 53 << 59 << 61 << 67 << 71;

for(i = 1; i<=10; i++ ) {

a << intqueueA; // Hent værdi fra kø A

b << intqueueB; // Hent værdi fra kø B

intqueueY << a+b; // Læg tal sammen og gem i kø Y

}

for(i = 1; i<=10; i++ ) {

j << intqueueY; // Hent værdi fra kø Y

cout << j; // udskriv værdi på skærm (33 40 46 50 58... )

}

}

// ---

Eksempel 6:

// ---

// Da tilføjelsen af data til køerne, beregningen af køerne, og udskrivningen ikke indeholder nogen trådning, så kan rækkefølgen også byttes om

// Kode eksempel 6:

int<< intqueueA; // Opret stream intqueueA af integers

int<< intqueueB; // Opret stream intqueueB af integers

int<< intqueueY; // Opret stream intqueueY af integers

int i,a,b,j;

main {

// Vi udskriver først, bare for demontrationens skyld:

for(i = 1; i<=10; i++ ) {

j << intqueueY; // Hent værdi fra kø Y

cout << j; // udskriv værdi på skærm (33 40 46 50 58... )

}

// Vores beregningsprocess

for(i = 1; i<=10; i++ ) {

a << intqueueA; // Hent værdi fra kø A

b << intqueueB; // Hent værdi fra kø B

intqueueY << a+b; // Læg tal sammen og gem i kø

}

while true do {}; // Her skulle man tro at vi venter, men det gør vi ikke. Det kører parallelt, og udføres reelt aldrig - vi har en "file13" ALU som den slags køres på... Hvis der var sket noget i løkken, vil den desuden blive træt efter mange gennemløb, så der sker nedprioritering ved ensartethed.

// Vi har valgt vores testvektorer i bunden

intqueueA << 2 << 3 << 5 << 7 << 11 << 13 << 17 << 19 << 23 << 29;

intqueueB << 31 << 37 << 41 << 43 << 47 << 53 << 59 << 61 << 67 << 71;

}

// ---

// De sidste eksempler kan automatisk paralleliseres, da vi kan anvende at pipelining er ækvivalent med parallelisering.

// Udregningen af 2+31, 3+37, 5+41 kan således udføres parallelt.

// Selve løkken der bestemmer antallet, er i princippet sekventiel - men den kan deles i to.

// Den deles i en masterløkke med den variabel som er bestemmende for betingelsen. Og i slaveløkker med indholdet der kan paralleliseres.

// Dermed er det to parallele processer. Men, da at masterløkken ikke indeholder input, så kan den klares statisk, allerede ved kompileringen. Og derfor forstår compileren 10 parallele processer.

// Havde der været en betingelse, der ikke kunne udregnes på forhånd, vil det dog også kunne paralleliseres, men antallet vil dukke op under udregningen.

// Ofte udruller vi en løkke flere gange, og så kan vi derved også opnå parallelisme, og antallet af gennemløb kan ofte reduceres til et simplere udtryk.

// Vi kan forestille os det sådan, at der vil blive sendt små mærker af sted fra master loopen, der fortæller at løkken skal køre flere gange, så master loopen køres parallelt med slave løkkerne, og sender mærker til dem, eventuelt run-length kodet.

// ---

Jeg håber, at det fremgår af ovenstående, at et almindeligt sekventielt sprog, også fint fungerer som deterministisk parallelt sprog, såfremt det håndterer køer. Og i mange sammenhænge, gør det parallel kodning nemt, fordi at en stor del af paralleliseringen sker automatisk. Der findes mange omskrivninger, der paralleliserer sekventielt kode til parallelt.

Ofte, er det største problem, ikke at parallelisere - men det modsatte. At bagefter, mappe alle vores milliarder af parallle processer ind på nogle få, som vi skal udføre i gunstig rækkefølge.

Det kræver prioriteringer af processerne i den helt rigtige rækkefølge, så at data kommer ud hurtigst muligt. F.eks. så kan gamle løkker blive trætte i forhold til friske nye løkker, da de sikkert er i gang med noget, der alligevel ikke giver et svar (foreløbigt).

Ofte, så prioriterer vi vores outputs og inputs, så vi angiver ikke i koden prioriteter. I stedet, så er det den som modtager data, der har prioritet. Som regel er det brugeren (skærm/lyd/tastatur/mus) på et brugersystem, bortset fra real-time kode.

Når vi laver sekventiel/parallel programmering, så er det vigtigt at vi ikke selv bestemmer graden af parallelisme. Det skal automatikken. Ellers bliver vores kode ikke hurtigere, når vi får en nyere computer med større massiv parallelisme.Og så hænger vi på at udvikle versionsnumre resten af livet.

Ovenstående er kun egnet til parallelisme der er deterministisk. Derudover kan tilføjes tidsstempling, og mulighed for optimale tilfældige funktioner, der vælger teoretisk alle tal på en gang, og vælger den mest optimale. Den slags funktioner medfører naturligvis tilfældighed og kaos. Så det undgår vi helst. Alle funktioner, der kan medføre noget tilfældigt hedder noget med random eller tilsvarende. Og brugen rapporteres under egenskaber for programmet, så der kan ses koden ikke er bevist og kaotisk.

Lidt meget tekst, men syntes ikke jeg kunne vise tanken kortere.

32
28. juli 2020 kl. 00:34

Og uden at jeg skal komme helt i detaljer med, hvordan vores software er opbygget, kan jeg dog sagtens fortælle om en situation, hvor kendskab til størrelsen på cpu cache er relevant: Vi forsøger at lave samspil mellem compiler og linker, således at objekter vi ved anvendes "samtidig", anbringes så de med stor sandsynlighed kan være i cachen; det kan (så vidt jeg husker) give mindst en faktor ti forbedring i access tiden. Noget andet hardware vi også tager hensyn til i vores software design er forskellige C-states, og så som allerede nævnt numa eller flat memory. Alt dette er forfinet gennem flere årtier og samtidig fulgt med udviklingen i hardware, og der er absolut intet "galt". Og mit hovedsynspunkt er stadig det samme: Alt dette kan vi kun gøre, fordi vi tilpasser softwaren til den aktuelle hardware; det ville ikke fungere optimalt såfrem vi blot anvendte en given compilers abstaktion af hardwaren.

Automatikken begynder ikke at ændre rækkefølgen på filformater som du har specificeret. Så dermed har den begrænsede muligheder for at optimere det. Er det specificeret, så er nødvendigt, at compileren opfylder specifikationen, uanset om det er en god eller dårlig specifikation. Så du undgår nok ikke helt, at skulle gøre det, som du gør nu. Jeg tror godt man vil kunne lave automatik, som kan løse opgaven - men det vil kræve, at du overlader det til compileren, at finde ud af, hvordan data skal opbevares på harddisken. Og det tror jeg ikke er gjort endnu, og det bliver nok ikke foreløbigt.

Det som automatik kan, er i højere grad at parallelisere, så at computeren kan anvende hardwaren så effektivt som muligt. Men, når det drejer sig om båndbredde fra harddisken, så er det en fordel, hvis man kan undgå at læse unødige data ind, da båndbredden er begrænset.

Antager vi som eksempel, at du kan beskrive din opgave parallelt, eller automatikken kan lave beskrivelsen super parallelt, og arbejder de parallele tasks med data på harddisken, så kan ske de venter på data fordi der er cache miss. Computeren vil så hente data fra harddisken, og når de er til stede i cachen, så kan alle de processer der anvender de pågældende data bruge dem. Der kan således tages hensyn til den rækkefølge som tasks udføres i, afhængigt af hvad der er læst ind i computerens cache. Som jeg tidligere har skrevet, så er en af de svære opgaver i ligeså høj grad finde den rette rækkefølge, som de mange tasks udføres, som at parallelisere jobbet.

31
27. juli 2020 kl. 23:42

Her er mønstereksemplet quicksort der på papiret er en dårligere algoritme end heapsort og merge sort, men alligevel performer meget bedre på grund cachen. Vi har altid måtte tage hensyn til hardwaren hvis det skal køre hurtigt.</p>
<p>Sortering er også et godt eksempel på at parallisering ikke er en magisk tryllestav der løser alle dine problemer. Hvis du møder op med din paralliserede merge sort så taber du med en faktor 10 til 100 til ham der bruger en algoritme der tager hensyn til cache, simpelthen fordi dit system ikke har uendelig hukommelsebåndbredde.</p>
<p>En optimal strategi er ofte en blanding af algoritmer. Eksempelvis opdeling af opgaven i lige store dele, som fra merge sort, men med quicksort på noderne og herefter merge trinet fra merge sort til at samle resultatet. Også kendt som MapReduce.

Hvis jeg laver det i hardware kunne jeg ikke drømme om at bruge quicksort - det er kaotisk, og ikke muligt at analysere. I hardware angiver vi aldrig typiske data, men kun worst-case data. Du finder ikke typisk i noget hardware datablad. Fletsort og heapsort kan fint implementeres i hardware med brug af cache, og brug direkte på harddisk uden problemer. Det eneste problem der er, er at kompleksiteten ikke er så god - for man har ikke regnet på den tid, som selve compare tager. I hardware skal vi som regel også tage hensyn til hver eneste byte/char compare. Og det betyder, at hver compare ikke er O(1) men kan være op til O(n), hvor n er længden for hver tekst. Derfor, kan vi i hardware også finde på at bruge en form for sortering, der tager hensyn til det, men som regel kombinerer den med fletsort/heapsort. Hvis det vi sorterer er tilfældigt, og ikke indeholder mange ens tegn, så er det dog stort set ligegyldigt. Men, igen vi angiver altid worst case, og den kan blive dårlig ved meargesort/fletsort, fordi vi i princippet skal gange kompleksiteten med antallet af bytes i hver streng. Vi har algoritmer hvor maksimum kompleksiteten er O(n) hvor n er tekstens samlede længde. Men, de er så til gengæld ikke gode på harddisk. Her er varianter over fletsort/heapsort gode, men bestemt ikke varianter med quicksort.

Jeg har et hardwareeksempel, hvor at cache betyder noget. Forestiller vi os, at vi har to løkker og data der gemmes 2-dimmensionelt, så vil vi normalt først have y, og inde i en x løkke. Vi ønsker nu at vende data, således at [x,y] koordinater ombyttes til [y,x] i vores tabel. Vi kan sammenligne det med at vende et skærmbillede på siden. Her løber vi ud i store problemer, hvis vores datamængde ligger på harddisk. Den vil stå og seeke konstant. Dette kan løses ved at bytte ledningerne rundt på vores cache, så vi fletter x og y sammen, altså skiftevis tager en bit fra x, og en bit fra y. Nu viser det sig, at alle data de ligger i store blokke, fint på harddisken, og det kan laves med opslag af højst 4 sammenhængende blokke. Derfor, vil man netop ofte gemme n-dimmensionelle arrays, med bit-swappede index, altså så en [x,y] array gemmes med skiftevis bit fra x og y, og en [x,y,z] array, gemmes med bit fra x,y,z skiftevis. Reelt, så er det man gør, at man for opgaven laver frekvensanalyse af brugen af bits. Nogle bruger også en hash funktion, der for nogle typer cache er yderst effektivt. Mange typer caches er lavet til at være effektive ved tilfældige opslag. Nogle cacher anvender en hash funktion, for at sikre addresser er tilfældige.

29
27. juli 2020 kl. 21:29

Normalt er ikke mening at brugeren skal tænke på computerens L1, L2 og L3 cache. Så er et eller andet galt. Har du massivt paralle strukturer, så betyder cache ikke meget, da man har mange processer at vælge imellem, og derfor er også lang tid til at finde de data som skal hentes frem.

Her er mønstereksemplet quicksort der på papiret er en dårligere algoritme end heapsort og merge sort, men alligevel performer meget bedre på grund cachen. Vi har altid måtte tage hensyn til hardwaren hvis det skal køre hurtigt.

Sortering er også et godt eksempel på at parallisering ikke er en magisk tryllestav der løser alle dine problemer. Hvis du møder op med din paralliserede merge sort så taber du med en faktor 10 til 100 til ham der bruger en algoritme der tager hensyn til cache, simpelthen fordi dit system ikke har uendelig hukommelsebåndbredde.

En optimal strategi er ofte en blanding af algoritmer. Eksempelvis opdeling af opgaven i lige store dele, som fra merge sort, men med quicksort på noderne og herefter merge trinet fra merge sort til at samle resultatet. Også kendt som MapReduce.

28
27. juli 2020 kl. 18:31

Normalt er ikke mening at brugeren skal tænke på computerens L1, L2 og L3 cache. Så er et eller andet galt.

Som du måske har gættet, så er jeg software ingeniør...

Og uden at jeg skal komme helt i detaljer med, hvordan vores software er opbygget, kan jeg dog sagtens fortælle om en situation, hvor kendskab til størrelsen på cpu cache er relevant: Vi forsøger at lave samspil mellem compiler og linker, således at objekter vi ved anvendes "samtidig", anbringes så de med stor sandsynlighed kan være i cachen; det kan (så vidt jeg husker) give mindst en faktor ti forbedring i access tiden. Noget andet hardware vi også tager hensyn til i vores software design er forskellige C-states, og så som allerede nævnt numa eller flat memory. Alt dette er forfinet gennem flere årtier og samtidig fulgt med udviklingen i hardware, og der er absolut intet "galt". Og mit hovedsynspunkt er stadig det samme: Alt dette kan vi kun gøre, fordi vi tilpasser softwaren til den aktuelle hardware; det ville ikke fungere optimalt såfrem vi blot anvendte en given compilers abstaktion af hardwaren.

27
27. juli 2020 kl. 17:41

@Jens D Madsen: Du er stadig ekstremt teoretisk. Kan du ikke komme med nogle faktiske eksempler på software, hvor din teoretiske udredning er det, som får det hele til at fungere (og performe) i praksis?</p>
<p>Og når jeg omtaler L1, L2, L3 cache og numa (som du ikke svarer på), er det naturligvis hardwaren.

Nu er jeg harware ingeniør, og har ikke megen kendskab til det software som findes på markedet. Men vi anvender mange af metoderne i forbindelse med automatisk syntese af hardware, f.eks. VHDL syntese, automatisk analyse og design af asynrkone computere ud fra software, osv. Metoderne bag kan også fint anvendes i parallel programmeringssprog. Generalt består det af en række regler vi har for parallelisme, og vi kan f.eks. ændre fra pipeline til parallel, øge parallelismen ved noget beskrevet sekventielt og lignende. Vi har også en række regler omkring data-lagre som ram'er, rom'er, og cacher foran disse, samt hvordan de fungerer i parallel sammenhæng - dette gør, at vores compilere som eksempel kan arbejde med mange data samlet, og skrive dem samlet.

Normalt er ikke mening at brugeren skal tænke på computerens L1, L2 og L3 cache. Så er et eller andet galt. Har du massivt paralle strukturer, så betyder cache ikke meget, da man har mange processer at vælge imellem, og derfor er også lang tid til at finde de data som skal hentes frem. Det tyder på, at der er fejl i den computerakitektur du anvender, eller at du ikke anvender tilstrækkeligt antal parallele rutiner, til at formulere opgaven.

Jeg ved ikke om du deler opgaven ud på flere computere, men automatiske værktøjer vil ofte søge at finde disjunkte data, og dele dem ud på separate databaser/ram lagre. Kan de udføres uafhængigt af hinanden, så giver det både en mere optimal hardwarestruktur, plus mere "elastik" i koden. Selv sekventielle opgaver, kører totalt out-of order, også over gigabytes af instrukioner. Det er nemmest at opnå, når der anvendes højniveausprog som er lavet til det - maskinsprog kan også nemt paralleliseres, men det sker ofte kun mellem programudfletninger, altså indenfor instruktioner der kører i et huk.

26
27. juli 2020 kl. 17:01

Nu kender jeg ikke dit setup, men vil det ikke være smartest at lade selve databasemotoren (med mindre det selvfølgelig er lige præcis det du laver) håndtere samtidighed?

Det er det, jeg laver, og det er præcist det vi gør. Hele min argumentation på den del er, at vi kun kan gøre det (så det performer), hvis vi på hver eneste platform udnytter kendskab til hardware. Jeg tror ikke, det kan lade sig gøre med en generisk hardware abstraktion.

@Jens D Madsen: Du er stadig ekstremt teoretisk. Kan du ikke komme med nogle faktiske eksempler på software, hvor din teoretiske udredning er det, som får det hele til at fungere (og performe) i praksis?

Og når jeg omtaler L1, L2, L3 cache og numa (som du ikke svarer på), er det naturligvis hardwaren.

25
26. juli 2020 kl. 17:31

Bl.a. kan det være vigtigt for programmøren at have kendskab til om memory er numa eller ej eller til størrelsen og placeringen af L1, L2 eller L3 cachen. Det vil på ingen måde kunne skrives, hvis man overlader forståelsen og abstraktionen til compileren.

Jeg er ikke helt sikker på om det er computerens L1, L2 eller L3 cache du mener, eller om det er cache på databaserne. Under alle omstændigheder, er det normalt ikke et problem, hvis du beskriver dine tasks parallelt. Antag, at vi har en række parallele tasks som vi ønsker udfyldt. Så vil du opstarte disse tasks på computeren, Men, er hukommelsen ikke ledig, herunder harddisken, så går computeren i wait - det betyder ikke, at multitaskingen stopper. I gamle dage lå en yield() instruktion i enhver wait. Altså multitaskingen fortsætter og arbejder bare videre med de andre parallele tasks. Antager vi som eksempel at du starter 200 parallele processer, så vil de ligge indtil data kommer ind. Vi antager, at vi allerede har nogle data i hukommelsen. De bliver udført straks, for de er der - så der bliver ikke lavet nogen wait, når der står en wait. Data er tilgængelige, og bliver behandlet øjeblikkeligt. For de opgaver, at data ikke er tilgængelige, der ventes på de kommer. Der bliver så hentet nye data ind i cachen, og nu kører så alle de processer, der derved får adgang til data. Lader du paralleliteten overgå til automatikken, så tages i de fleste tilfælde de rette beslutninger. Dog, naturligvis ikke på computere, hvor hele parallel conceptet er kodet forkert (PC'er, linux osv). Så må vi i gang med det manuelle arbejde, og se hvad vi kan finde i værktøjskasser. Som eksempel, så kan en PC ikke engang finde ud af, at udføre de paralle processer i gunstig rækkefølge. Det er heller ikke nogen enkel ting, da man i princippet skal automatisk undersøge grafer og finde ud af sammenhæng, samt prioritere dem, afhængigt af hvor data anvendes, og i nogle tilfælde skal tages hensyn til prioriteter for forbindelser/io, og prioritering skal ofte tage højde for, hvilke data der først skal ud (timing). Vi kan tage et eksempel: Du kopierer to filer på din harddisk. Ud over at det ikke burde tage tid, så står harddisken og skiftevis udfører den ene task og den anden task. Det kan vises, at enhver form for tidsmæssigt opsplitning af tasks reducerer evnen til at paralellisere effektivt, og en rigtig computer må ikke anvende et interrupt for parallelisering. I stedet skal den regne ud, i hvilken rækkefølge at de pågældende task udføres, for at opnå den optimale svartid. I de fleste tilfælde, f.eks. ved filkopiering, er det oftest at kopiere den lille fil først, og herefter den store. Begynder man at løbe frem og tilbage, så bliver det til løbeture. Og ikke andet. Når mange parallele processer skal mappes ind på en sekventiel computer, så sker det ikke med tidsmæssigt interrupt. Det sker ved, at computeren udregner, i hvilken rækkefølge at de pågældende processor skal udføres, for at give størst ydelse. Her tages højde for, f.eks. hvor meget parallelitet der løses op for, ved at udføre en process. Og det betyder, at en udførsel i den rette rækkefølge, også kan åbne for udførsel af større parallelisme samtidigt.

24
26. juli 2020 kl. 15:51

Nu kender jeg ikke dit setup, men vil det ikke være smartest at lade selve databasemotoren (med mindre det selvfølgelig er lige præcis det du laver) håndtere samtidighed?

Jeg kunne forestille mig, at det er en fordel at splitte databasen ud på flere computere med netværk for at øge hastigheden. Er data uafhængige, f.eks. forskellige kunder eller andre disjunkte datagrupper, så kan data fint splittes ud på forskellige computere. Der kan skrives til flere databaser samtidigt, for at øge parallelismen, eller for redundans. De disjunkte datagrupper kan eventuelt samles i en hoveddatabase, hvor data overføres automatisk til, når der er tid.

22
26. juli 2020 kl. 14:38

Mine eksempler er alle meget praktiske, og de anvendes i hundreder af tusindvis af systemer dagligt. Et enkelt eksempel er håndtering af kreditkorttransaktioner, som er en meget typisk oltp applikation. Den har en database (som er mit felt), hvor hundreder eller tusinder af processer eller tråde skal arbejde sammen og en del af dette foregår via shared memory. Det kan efter min bedste overbevisning kun gøres fordi programmørerne er enige om semantikken og eksplicit anvender hardware mekanismer på det aktuelle hardware. Bl.a. kan det være vigtigt for programmøren at have kendskab til om memory er numa eller ej eller til størrelsen og placeringen af L1, L2 eller L3 cachen. Det vil på ingen måde kunne skrives, hvis man overlader forståelsen og abstraktionen til compileren.

Automatik kan arbejde med koden, og også optimere den med henblik på anvendelse af cachen. Uanset om kode er sekventielt eller parallelt, så kan automatik anvendes til at øge parallelismen, eller reducere den.

Og så for lige at vende tilbage til mit første indlæg: Der er rigtig langt fra tjenerens håndterminal, hvor du holder dit kreditkort hen for at betale, eller fra den hjemmeside, hvor du betaler for en vare, og til databasen der skal klare kreditkorttransaktionen. Og det er præcist den meget lange vej, der efter mine 30+ års erfaring på området nemt bliver helt unødigt kompliceret, lang eller resourcekrævende, når de anvendte programmeringssprog bliver for abstrakte og for indkapslende. Det er præcis der lag, på lag, på lag blive decideret kontraproduktivt. Og det er præcis der objektfokuserede sprog som C++ nærmest opfordrer til den lag på lag tankegang. Hvis du vil kende bilens farve, så spørg mig. OK, men hvad koster så det? Øhh, er det dig eller mig, der kender bilens farve?

Jeg er ikke så stor tilhænger igen af C++. En gang kaldte jeg det for misforstået objektorienteret. Og C++ klasser, kan måske nærmere kaldes omvendt indkapsling, forstået sådan, at de alle er "tilstandsmaskiner". I modsætning til en funktion, så husker de således en tilstand. Jeg foretrækker parallele klasser - dem kan du have i C++ med de køer som jeg omtaler. Her har klasserne også deres egne variable, men de er nu at betragte som parallele processer, som du sender data mellem ved hjælp af køer. Dette er designet til at rede C++. Men C++ er bare ikke redet endnu. Det som er genialt, er at du ved at tilføje køer, får C++'s måde at håndtere klasser, og multitasking, til at gå op i større enheder. Uden ændring på sproget, så bliver det til multitasking. Selv stream operatorer (køer) er i sproget. De skal dog forbedres. Med simple køer tilføjet C++ så bliver sproget til massiv multitasking, og du kan opfatte alle klasserne som selvstændige processer, som du kommunikere med via beskedkøer. Denne metode, er endda deterministisk.

C++'s måde at håndtere indkapsling på, hvor at man har en metode der håndterer lokale variable for processen, ser måske umiddelbart ineffektiv ud - i midlertid, så kan vi også med automatiske metoder reducere kode bort, så det ofte ikke er overhead. Selvom du har et dybt hiraki af kald instruktioner, og koden teoretisk set suser rundt alle steder i hukommelsen, så vil det oftest i den oversatte kode, blive skrevet en MOV - præcist som i maskinkode. Så det bliver egentligt ikke nødvendigvis sløvere. Om der så er så stor fidus ved at have kode til at ændre en tilstandsmaskine ved jeg ikke. Jeg syntes selv dårligt om at have en bunke af tilstandsmaskiner til at flyde rundt - det er for mig ustruktureret. Og jeg foretrækker brugen af procedurer og funktioner. Jeg foretrækker indkapsling som den vi kender fra COMAL 80 - alstå hvor man laver alle variable lokale. Og ingen tilstandsmaskiner. Altså, kan vi gøre det proceduralt, med funktioner, så er det et plus fremfor klasser, fordi at vi undgår lokale variale/tilstandsmaskiner. Anvender vi C++ uden at bruge klasser som tilstandsmaskiner, så er det efter min mening bedre. Der, hvor vi har brug for at gemme lokale variable, der er det bedre at anvende en parallel process. Denne kører med sine egne variable og kommunikerer via køer. Tilstandsmaskiner er noget pokkers lort. De tvinger rækkefølge. Men, som sagt, C++ kan redes. De skal bare have en kø-operator. Dette er egentligt det geniale i C++. Selvom at sproget er designet efter misinformationsprincippet, så skal der kun en krølle på, for at det er i orden. Vi venter stadigt på "krøllen" implementeres, som gør C++ til et ordentligt deterministisk parallelt sprog, som er egnet for parallel processering. Som nævnt, kræver det kun at det udføres på en computer, der automatisk parallelsiere sekventielle koder. Og, at man indfører at køerne kan kommunikere op og ned i sproget, og gøre klasser parallele, ved at data overføres med køer i stedet for funktioner til sætte/resette bit/bytes.

21
26. juli 2020 kl. 13:40

Mit eksempel med den røde bil er ikke (helt) taget ud af den blå luft. Jeg havde vel for mindst 25 år siden en performance opgave hos en belgisk kunde, hvor man jo har to sprog, så applikationen skal skrive alle prompts på enten flamsk eller fransk. Og programmøren havde skrevet noget i retning af:</p>
<p>if employee.language() = 'French' then<br />
print "bon jour"<br />
else<br />
print "goede morgen"<br />
end if;
som blev udført hver gang noget skulle skrives på skærmen. Hvad programmøren ikke vidste var, at language() metoden i employee klassen spurgte databasen hver gang.

Det er jo så et spørgsmål om det er et problem at spørge databasen hver gang - hvis du ser det jeg skriver om processorakitekturer (https://www.version2.dk/blog/moores-forbandelse-1091012), så kan såmend selve CPU'ens registre sagtens ligge på harddisken, eller på en harddisk på internettet. Der er en cache (eller flere) over, som gør dem ligeså hurtige, som hvis de lå i ram, eller internt i CPU'en. Og dataene skal jo hentes - så jo, hvorfor ikke hente dem fra databasen? Det væsentlige er, om det er hurtigt at hente data fra databasen.

Generalt gælder, at vi må læse data i tilfældig rækkefølge herunder parallelt mellem vores skrivninger. Vores skrivninger skal ske i ordnet rækkefølge. Vi kan forbedre det, ved at sætte en cache foran, da vi så reducerer skrivningerne og dermed tillader mere uordentlig/parallel tilgang til hovedlager. Skrivninger til cachen skal ske i ordnet rækkefølge, og læsning kan ske i vilkårlig rækkefølge og parallelt. En cache forhindrer, at data vi umiddelbart har skrevet læses fra hoveddatabasen, og da det er skrivninger der forhindrer vilkårlig rækkefølge og parallelisme, så er en god idé med en cache foran. Cacher er en meget vigtigt del af lager og databaseprincipper. Også inde i en CPU er cache vigtigt, og har en vigtig sammenhæng mellem pipelining. Pipelining virker som cache, og cache som pipelining - skriver vi til hukommelsen, og læser umiddelbart efter, så vil data tages fra vores pipelining (forwarding), eller vores cache (også en slags forwarding). Designes vores cache som forwarding, så kan den diffundere ind i CPUen med automatiske metoder, og øge pipelinens dybde.

Hvis jeg skulle designe et massivt parallelt system, hvor der er adgang til en fælles database, så vil det bestå dels af en hoveddatabase og en/flere cacher. De pågældende cacher kan være splittet ud i mange, ligesom direct mapped cacher, således man bruger en hash funktion, til at vælge den tilfældige cache. Dette kræver at de forskellige cacher indeholder uafhængige data, f.eks. forskellige addresser eller kunder. På den måde, så kan man have mange parallele cacher, om en fælles stor lager. Sandsynligheden for, at samme cache anvendes er lille, men afhænger af antal og godheden af hash funktionen. Cacherne rummer de senest skrevne data, og de kan så fyldes i hoveddatabasen når det er tid. Er der cache-miss, så læses data fra hoveddatabasen. Hoveddatabasen kan eventuelt deles op i mange, så der skrives til flere databaser samtidigt - dette giver mulighed for parallel læsning. Måske kan vi også helt undgå en hoveddatabase, og bare nøjes med en række små databaser, hvor vi f.eks. vælger hvilken vi ønsker at anvende, via en god hash funktion. I de fleste tilfælde, tror jeg man dog gerne vil have en hoveddatabase, som man kan opdatere indimellem med de data der er i vores cache/cacher. Under opdateringen kan man eventuelt bruge en backup af hoveddatabasen hvis den skal kunne læses samtidigt. Så længe at data er i en cache, og det er tilstrækkeligt cache, så opstår ikke læse/skrive-hazarder. Man kan anvende flere backup cacher, og backup databaser, og skrive til dem alle samtidigt, så man har en anden der kan læses fra, hvis en database er gået ned.

Når jeg programmerer - jeg programmerer mest VHDL, Pascal og C++, så er hastigheden og store O funktionen, altid vigtigt. Og vi må også tage hensyn til de begrænsninger, som vores computere har. Som eksempel, så skriver jeg at maskinerne skal have en kopi-maskine indbygget, så vi kan kopiere data, incl. data på vores harddisk, og for den sags skyld databaser, uden det koster tid (andet end 1 cpu cycle). Desværre, så er det jo ikke lige de computere, at vi har adgang til. Og så må vi bruge de forhåndenværende søms princip. I dag, er det jo nok dette princip, der er mest brugbart, fremfor matematik og datalogi - desværre. Men det skyldes primært, at vores computere, databaser osv. er lavet forkert. De er baseret på fakta om hvordan det skal gøres forkert, og disse fakta, er sat i system og gjort til doktrin.

Jeg vil ikke påstå at automatik altid kan klare vores problemer. Det som automatik kan, er at sikre vi ikke gør forkert. Men, desværre kan det ikke sikre, at vi gør det optimalt endnu.

19
26. juli 2020 kl. 12:04

Det er nok spørgsmålet på det svar!

Jeg forstår udmærket ironien i det svar (eller var det et spørgsmål?).

Men jeg mener afgjort ikke, at jeg har spildt mit arbejdsliv gennem de sidste 30+ år på at arbejde med netop den slagt problemer, som er skitseret i mine indlæg.

I mit spæde arbejdsliv, da objektorientering generelt og C++ specifikt var det nye og hotte, fik jeg overbevist min daværende arbejdsgiver om, at jeg skulle på et C++ kursus. Det var meget lærerigt, idet jeg ret hurtigt indså, at det mest var kejserens nye klæder. Og ingen har i de forløbne 30 år kunnet overbevise mig om det modsatte.

Mit eksempel med den røde bil er ikke (helt) taget ud af den blå luft. Jeg havde vel for mindst 25 år siden en performance opgave hos en belgisk kunde, hvor man jo har to sprog, så applikationen skal skrive alle prompts på enten flamsk eller fransk. Og programmøren havde skrevet noget i retning af:

  1. if employee.language() = 'French' then
  2. print "bon jour"
  3. else
  4. print "goede morgen"
  5. end if;

som blev udført hver gang noget skulle skrives på skærmen. Hvad programmøren ikke vidste var, at language() metoden i employee klassen spurgte databasen hver gang.

Det mest morsomme ved den historie var at den gentog sig i en lidt mere avanceret form omkring 10 år senere i Canada.

18
26. juli 2020 kl. 11:46

@Jens D Madsen:

Du bliver ekstremt teoretisk, og det kunne være rart at høre nogle praktiske eksempler på applikationer eller programmer, der (kun) virker via de abstraktioner, du omtaler, og hvor programmøren således får noget forærende ved at skrive C++.

Mine eksempler er alle meget praktiske, og de anvendes i hundreder af tusindvis af systemer dagligt. Et enkelt eksempel er håndtering af kreditkorttransaktioner, som er en meget typisk oltp applikation. Den har en database (som er mit felt), hvor hundreder eller tusinder af processer eller tråde skal arbejde sammen og en del af dette foregår via shared memory. Det kan efter min bedste overbevisning kun gøres fordi programmørerne er enige om semantikken og eksplicit anvender hardware mekanismer på det aktuelle hardware. Bl.a. kan det være vigtigt for programmøren at have kendskab til om memory er numa eller ej eller til størrelsen og placeringen af L1, L2 eller L3 cachen. Det vil på ingen måde kunne skrives, hvis man overlader forståelsen og abstraktionen til compileren.

Og så for lige at vende tilbage til mit første indlæg: Der er rigtig langt fra tjenerens håndterminal, hvor du holder dit kreditkort hen for at betale, eller fra den hjemmeside, hvor du betaler for en vare, og til databasen der skal klare kreditkorttransaktionen. Og det er præcist den meget lange vej, der efter mine 30+ års erfaring på området nemt bliver helt unødigt kompliceret, lang eller resourcekrævende, når de anvendte programmeringssprog bliver for abstrakte og for indkapslende. Det er præcis der lag, på lag, på lag blive decideret kontraproduktivt. Og det er præcis der objektfokuserede sprog som C++ nærmest opfordrer til den lag på lag tankegang. Hvis du vil kende bilens farve, så spørg mig. OK, men hvad koster så det? Øhh, er det dig eller mig, der kender bilens farve?

17
25. juli 2020 kl. 18:23

Som jeg skrev i det ovenstående, så er ethvert almindeligt sekventielt programmeringssprog parallelt, hvis vi tilføjer køer, så vi kan kommunikere mellem uafhængige programdele. Her skal vi være opmærksom på udfletninger. Vi skriver i en kø i rækkefølge, og udlæser den i rækkefølge. Med en kø, kan vi således ikke lave udfletninger. Det kræver flere køer. Som eksempel, kan vi skrive samme data i to køer, og en process læser den ene kø, og en anden læser den anden - de får så samme data. En anden mulighed, er at lave en kopi af selve køen. Derved kopieres alle køens data fra starten. Og vi får eksakt den samme sekvens ud af flere køer. Dette svarer til en udfletning af en kø. Altså, ved læsning, læser vi på hianden følgende data, og udfletning er ikke muligt. Selvom køen læses i en uafhængig del senere, så er den så ikke mere uafhængig, da køen tvinger afhængighed, fordi at udlæsning er altid trådet. Der sker ikke nogen pludselig og unkontrolabel kopiering af data. Kopierer vi derimod køen, får vi to sæt data, vi kan bruge indviduel, og sende til to indviduelle paralle processer. Vi kan sammenligne det med, at hvis vi har en procedure og overføre parametrene som reference, så påvirker de efterfølgende anvendelse af parameteren. Mens, hvis vi kopierer, så har det ikke betydning for efterfølgende brug. En kopieret kø, svarer til at det ikke er reference, mens at en identisk kø, kræver trådning.

I køer, kan vi ikke kun skrive data, men enhver type datastruktur vi kan definere, herunder også klasser med kode.

16
25. juli 2020 kl. 15:25

Et parallelt sprog, er derfor også sekventiel. Rækkefølgen som angiver koden, angiver netop den ordning som der sker ved adgang til samme position i lageret, og sekventiel kode er derfor også parallelt.

Det skal forstås sådan, at i et deterministisk parallelt sprog, vil du altid kunne angive sekventiel kode der opfattes sekventielt, og det udføres i den rækkefølge det står, selvom det udføres parallelt. Det eneste som adskiller et sekventielt og et parallelt deterministisk sprog, er at du i et parallelt sprog, har muliighed for at kommunikere mellem dele af koden. Det vil sige, at du har fifoer/streams, så du kan kommunikere. Du kan så at sige, hvis du opfatter dit sprog som almindeligt sekventielt, skrive data gennem fifoer tilbage tidligere i programmet, som hvis det var kommunikation tilbage i tiden. Det er dog reelt ikke kommunikation på tværs af tidsgrænser. Skriver du noget i en fifo med efterfølgende instruktioner, så er der også en trådning, hvis det er samme fifo, og det fungerer derfor sekventielt, fordi at vi angiver en rækkefølge/orden, når vi laver såvel skriveoperationer som læse operationer til en fifo.

Vi kan tage et simpelt eksempel. Du laver et almindeligt program, der henter nogle data ind fra en kø 1, og skriver dem ud i en kø 2. De data der kommer ind er måske test vektorer. Du kan herefter godt lave koden bagefter, som skriver test vektorerne ind i køen 1. Og herefter igen, koden efter dette, som læser data fra kø 2 ud, og udskriver på skærmen. Du vil så have en parallel process, der står og smider test vektorer ind i en kø. En anden, der læser og behandler dem. Og en tredie der læser de behandlede data, og skriver ud. Så man kan kommunikere op og ned i koden, og derved implementere parallelisme, så det er deterministisk.

Ønsker man, at det ikke skal være deterministisk, så anvendes tilfældighedsfunktioner. Det kan vises, at enhver type ikke deterministisk parallelisme kan skrives i sådan et sprog, ved anvendelse af tilfældighedsfunktioner. Normalt, vil man undgå tilfældigheder, og i stedet anvende tidsstempling. I mange tilfælde, kan man ikke acceptere ikke determinisme. Det kan simpelthen ikke godkendes. Derfor, så kan man også altid se under et programs egenskaber, om der er anvendet ikke determisme, som f.eks. tilfældighedsfunktioner, eller "optimale" tilfældighdsfunktioner. De optimale tilfældighedsfunktioner kan envidere også opdeles i forskellige typer, afhængigt af hvor stor tilfældighed de kræver, eller om man har foretrukne tilfældige svar. Det væsentlige er, at en tilfældighedsfunktion altid svarer tilfældig, og at programmet skal fungere uanset svar. Anvendes f.eks. tilfældigheder med foretrukne svar, så kan det være ekstra farligt i forbindelse med tests. Derfor undgås det.

15
25. juli 2020 kl. 15:07

Læs <a href="http://h30266.www3.hpe.com/odl/axpos/opsys/vmsos84/5841/5841pro_018.htm…; som lidt historisk ganske præcist beskriver, hvad jeg mener. Og bemærk, at der flere gange står "read your compiler manual".

Har du en shared variabel, så er den almindelige regel, at du må læse fra den i vilkårligt rækkefølge, mens skrivningen skal foregå i veldefineret rækkefølge. Har vi en rækkefølge af instruktioner der alle er skrive instruktioner, så skal de - i princippet - udføres i rækkefølge. Har vi herefter en rækkefølge læse instruktioner, så må vi udføre disse i tilfældig rækkefølge. Når jeg skriver i princippet, så er det fordi, at der i visse tilfælde - kan findes matematiske regler, så vi må bytte dem.

Når man sikrer sig at ens programmering er deterministisk, så kan du reelt ikke anvende sharede resourcer, uden at rækkefølgen er veldefineret. Den bedste måde at definere rækkefølgen på, er ved at definere den i sproget. Det gør man ved, at det som udføres først står øverst, og det som udføres bagefter, står under. Det ser derfor ud som om, at tingene udføres normalt i rækkefølge, fordi at hvis der er afhængigheder, så udføres de i den rækkefølge som er formuleret i sproget. Et parallelt sprog, er derfor også sekventiel. Rækkefølgen som angiver koden, angiver netop den ordning som der sker ved adgang til samme position i lageret, og sekventiel kode er derfor også parallelt.

Ok, det er rigtigt, at der findes mange dårlige algoritmer, som det kan være svært at parallelisere. Her får computerne ofte hjælp manuelt. F.eks. har vi "bad programmers dictionary" der slår løsninger op på traditionelle problemer. Når at kodeanalysen viser, at noget gøres på en "dårlig måde", både med hensyn til store O funktion, og parallelisme, så vil det erstattes af optimal kode. Derfor er kunsten oftere at skive kode, som compileren forstår, end kode som er optimal.

14
25. juli 2020 kl. 14:54

Jeg skal selvfølgelig ikke nægte, at en overordentlig smart compiler kan finde ud af enten at lave den nødvendige lås eller at anvende en atomisk hardware operation; men jeg tror ikke på det. Koden til de to processer/tråde kan jo være skrevet helt uafhængigt af hinanden, og hvordan skulle compileren finde ud af det? De to progammører taler sammen og er enige om semantikken; men de bliver efter min bedste overbevisning begge nød til at fortælle compileren, hvordan den skal håndtere det. Og så er vi netop der, hvor en generel hardware abstaktion kommer til kort. Tag f.eks.

Det som man gør er at anvende matematik i den type tilfælde. Det vil sige, at compileren reelt omskriver koden lidt. I det pågældende tilfælde, kan vi anvende en omskrivning, hvor at summationen laves for begge processer, og herefter adderes. Det er et spørgsmål om, at bytte rundt på operatorer. Programmer opfattes ikke sekventielt, men i dataflow grafer, og hvis data ikke bruges, så behøver de ikke at eksistere. Vi vil ikke tilgå samme addresse, hvis dette kan undgås.

Det som jeg beskriver er dog stadigt noget lidt andet. Her har du et programmeringssprog, der er helt uden parallele features tilføjet i sproget, andet end køer. Alle køer virker ved, at der ventes, hvis der ikke er data i dem. Det kan bevises, at man ikke må vide, om der er data i en kø. Altså en instruktion eller ordre, der tjekker på om en kø er tom er ulovlig. Svaret til en sådan instruktion er altid, at der er data i køen. Og ellers så opprioriterer vi de processer, som der ventes svar på. Vi behøver ikke at udføre en instruktion der siger der ingen data er, og det fører kun til problemer, da den svarer tilfældigt. Dog, så findes mulighed for at anvende særlige random generatorer, der giver svar som er tilfældige, men hvor svar er optimeret efter, hvad som er hurtigst at udføre. Vi kan forestille os den slags tilfældighedsgeneratorer, som en slags kvantemekanik, hvor flere muligheder prøves samtidigt, og vi får et helt tilfældigt svar, men der vælges det tilfældige svar som medfører hurtigst udført kode, altså den tilfældighed, hvor svaret udregnes tidligst.

Det er korrekt, at det kan være svært at finde ud af om noget kan paralleliseres. Og i visse tilfælde, kan vi gøre det, selvom at automatik måske har svært ved det. Det betyder dog ikke meget. Det som betyder mest er egentligt determinismen, og at vores software er i stand til at kunne bevise determinismen. Hvis den ikke kan gennemskue, at det er deterministisk, så må vi skrive koden på en anden måde.

Et godt programmeringssprog, er designet sådan, at vi KUN kan beskrive vores opgave deterministisk, så der er garanti for dette - med mindre, at vi altså anvender en tilfældighedsfunktion, eller f.eks. den tilfældighedsfunktion som jeg omtalte, hvor vi tillader at computeren selv vælger den tilfældighed, som den mener giver den bedste udførsel.

13
25. juli 2020 kl. 14:07

Det er nok spørgsmålet på det svar!

11
24. juli 2020 kl. 11:54

Derfor virker konstruktionen ikke deterministisk. [...]. Typisk ender det hele med at ikke fungere.</p>
<p>Metoden er ganske enkelt forkert. Jeg anvender i det som jeg beskriver ikke låsning af hardware.

Mit eksempel viser med al tydelighed, at rækkefølgen sagtens kan være ligegyldig. Hvis to processer/tråde med adgang til shared memory skal holde styr på, hvor mange gange "noget er sket", skal de begge blot udføre ++(*p). Det er helt ligegyldig om rækkefølgen er deterministisk, men selve operationen skal være atomisk.

Jeg skal selvfølgelig ikke nægte, at en overordentlig smart compiler kan finde ud af enten at lave den nødvendige lås eller at anvende en atomisk hardware operation; men jeg tror ikke på det. Koden til de to processer/tråde kan jo være skrevet helt uafhængigt af hinanden, og hvordan skulle compileren finde ud af det? De to progammører taler sammen og er enige om semantikken; men de bliver efter min bedste overbevisning begge nød til at fortælle compileren, hvordan den skal håndtere det. Og så er vi netop der, hvor en generel hardware abstaktion kommer til kort. Tag f.eks.

  1. ++(*p)
  2. ++(*q)

hvor programmøren ved at p er shared memory medens q er private memory. Hvordan skulle compileren finde ud af at det er nødvendigt at den første skal være atomisk med en passende hardware abstraktion, og den anden ikke behøver det?

10
23. juli 2020 kl. 21:40

kan vi så ikke blive enige om, at vi for længst er forbi det punkt, hvor det vil komme til at performe? Eller sagt på anden vis: Der kræves aktiv indsats fra programmøren, for at resultatet har den ønskede performance?

Netop dette er muligt at opnå automatisk.

Det som du omtaler som parallelt er et lidt andet problem. Her går vi den omvendte vej, og har en masse parallele processer, som vi har svært ved at håndtere. Det, som jeg omtaler er sekventielt, og omdannes automatisk til at være parallelt.

Vi har mulighed for at lave noget der er parallelt, ved at anvende køer mellem parallele processer. Men, der er en del ting, som vi ikke kan kode. Som eksempel, nævner du reservering af hardware. Her opnår du adgang til hardware for forskellige parallele processer i tilfældig rækkefølge. Dette er ikke muligt, da det ikke er deterministisk. Jeg har bevidst gået udenom enhver form for ikke deterministisk kodning, fordi det giver anledning til problemer.

Tager vi f.eks. en statisk variabel, og sætter en lås på, og en parallel process skriver nogle data i den, herefter låser op, så reserverer en anden parallel process den, skriver data og låser op, og så reserverer vi den med en 3. process, og låser op, og svaret vil så altid være tilfældigt, da det afhænger af rækkefølgen som de parallele processer er udført i. Enhver parallel process, skal altid have lov til at blive udført i den rækkefølge som den har lyst til, fordi at vi intet kender til timingen internt i computeren. Derfor virker konstruktionen ikke deterministisk. Har processen f.eks. gemt et nummer, og er de forskellige, får vi at vide hvilken process der er udført sidst. Og dette er en hardwareiinformation som er ulovlig at få oplyst. Dette fortæller noget om hvordan vores computer arbejder internt, hvor lange printbaner er og den type informationer. Typisk ender det hele med at ikke fungere.

Metoden er ganske enkelt forkert. Jeg anvender i det som jeg beskriver ikke låsning af hardware. Vi har altid defineret rækkefølge, fordi den tages efter den rækkefølge som der står nævnt i koden, hvis der anvendes en fælles enhed.

Har du eksempelvis en lydenhed, så kan du ikke dele den mellem to forskellige tråde i min kodning. Dog, kan det lade sig gøre, hvis du sætter en attribut på enheden, der fortæller at den gerne må bruges i tilfældig rækkefølge, og ikke overleverer data til efterfølgende brug af enheden, for at undgå der opstår tilfældigheder. Programmeringssproget forbyder det af hensyn til sikkerhed.

Som eksempel, så må vi godt anvende en disk der er read only. Denne overleverer ikke informationer. Så den kan vi godt dele. Men, er den skrivebar, så er det umuligt at anvende den i flere parallele tråde. For så bliver resultatet ikke deterministisk, og så må det ikke kunne programmeres. Hvis vores tråde er tidsstemplet, så må vi dog godt, for så er der defineret rækkefølge.

9
23. juli 2020 kl. 21:09

Hej Jens

Det er næsten paradoksalt, at du bruger så meget plads på at beskrive, hvad det er compiler skal forstå omkring hardware, og samtidig generelt fortæller, at (sådan lidt groft sagt) programmøren ikke skal bekymre sig. Jeg har i stort set hele min professionelle karriere beskæftiget mig med software, der kører med mange parallele tråde og delt memory. Jeg har endda være med til at portere softwaren til nye platforme, og præcist mit eksempel med ++(*pp) har vi aldrig kunnet overlade helt til compileren. Det er slet ikke nok at skrive volatile (som vel reelt også ville være imod dit princip om at "compileren forstår det hele"), og hver ny hardware har sin nye implementering.

Og det er faktisk ikke blot nok at sikre at sådanne operationer bliver atomiske: Det skal også sikres, at såfremt en proces midt i denne operation skulle forsvinde (som i kill -9 hvis vi taler UNIX), at der stadig kan ryddes op. Den atomiske operation bruges jo typisk til at sikre at et objekt (åh nej, nu bruger jeg det ord, jeg selv er så arg modstander af) ikke modificeres, så den atomiske operation laver en lås eller mutex. Men hvis processen, der har låsen dør, så skal de resterende processer kunne rydde op alligevel. Og nu er vi vist helt sikkert derude, hvor compileren ikke har en jordisk chance for alene at forstå sammenhængen.

Når du skriver:

Den vil i princippet reservere hele lageret, hvis der ikke er styr på addresseområdet. I nogle tilfælde, kan vi analysere det, ved at behandle koden, og arbejde med mulige intervaller for alle variable.

kan vi så ikke blive enige om, at vi for længst er forbi det punkt, hvor det vil komme til at performe? Eller sagt på anden vis: Der kræves aktiv indsats fra programmøren, for at resultatet har den ønskede performance? Det er programmøren, der må fortælle compileren, hvilke objekter, der skal beskyttes af hvilken type mutex/lås, og hvornår der skal låses eller låses op. Måske kan compileren finde ud af det hvis dens opgave er at parallelisere en algoritme. Men hvis to programmører skriver hver deres kode som skal køre parallelt mod delt memory, vil compileren alene ikke have en chance, så i den situation er abstraktion af hardware utilstrækkeligt såfremt man også skal sikre performance.

I "gamle" dage, da alt ikke var Intel, var det meget forskelligt fra system til system. Noget hardware havde atomisk test-and-set, andet havde atomisk compare-and-swap, på nogle var det bytes, på andre words, og andre igen anvendte O/S interrupts til at lave user-space atomiske operationer. Jeg tror det vil være særdeles svært at lave som en one-size-fits-all hardware abstraktion, i hvert fald så længe den skal være så billig som mulig.

8
23. juli 2020 kl. 21:05

Re: Abstraktion uden overhead, men ....</p>
<p>++(*p)</p>
<p>Tænker på, om du mener problematikken med at p er ukendt, og at anvendelsen af pointervariable derfor medfører en tvungen rækkefølge brug af enhver pointer variabel?

Antages at der ikke er fejl som memory leaks, så kan du kun få adgang til den del af lageret som koden anvender, ved at få udleveret informationer fra koden som har reserveret lagerpladsen. Og så opstår en tvungen rækkefølge, på de dele af lageret, du derved kan få adgang til. Udleveres ikke informationer der kan give adgang til samme lagerpladser, så er lagerområderne ikke overlappende, og koden udføres parallelt igennem køer.

7
23. juli 2020 kl. 20:44

</p>
<p>++(*p)</p>
<p>

Tænker på, om du mener problematikken med at p er ukendt, og at anvendelsen af pointervariable derfor medfører en tvungen rækkefølge brug af enhver pointer variabel?

Ofte kan vi analysere hvilke mulige værdier at p kan få, ved analyse af koden, og dermed sikre, at der ikke opstår konfligt. Det er lidt svært i c++, fordi vi f.eks. kan lægge en til, og ikke ved hvor mange vi lægger til - det kræver, at det er styring af, at p ikke kommer udenfor sit område. Ellers, kan vi ikke automatisk parallelisere koden. Den vil i princippet reservere hele lageret, hvis der ikke er styr på addresseområdet. I nogle tilfælde, kan vi analysere det, ved at behandle koden, og arbejde med mulige intervaller for alle variable. Anvender vi inkompatible pointer variable, altså pegere til forskellige typer, så er vi sikker på, at de ikke kan komme i konfligt, såfremt at programmeringssproget er sikkert.

6
23. juli 2020 kl. 20:15

Kan en compiler finde ud af, at to tråde, der begger laver</p>
<p>++(*p)</p>
<p>skal have det koordineret uden at programmøren på nogen måde fortæller om det og uden at det bliver dyrere, hvis den stump kode ikke kører samtidig i flere tråde?

Ja, det er netop spørgsmålet, som enhver der laver computerprogrammeringssprog skal kunne svare.

For det første - så skal compileren kunne se hvilke tråde det er parallele. Det er ikke helt så godt, hvis vi bare hopper ned i en eller anden instruktion med et interrupt og opstarter en parallel task, uden at programmeringssproget ved det.

Herefter kan et programmeringssprog godt finde ud af, hvilke tasks der er parallele. Anvender to tråde samme lageraddresse, altså en shared variabel, så skal compileren give en fejl, og må ikke oversætte det, med mindre at addressen er defineret som shared, f.eks. med "volatile".

Har vi nu to tråde, der kører helt adskilt af hinanden, og anvender ++ på en shared volatile addresse, så ved vi i princippet intet om rækkefølgen. Dette er en af teorierne bag parralel processing, at processoren skal altid have lov at udføre processerne når den har lyst. Derfor, så er her ikke tilladt at lave ++ på den pågældende addresse, med mindre vi på en måde definerer rækkefølgen. Det kan f.eks. ske ud fra tidsstempling af data.

Jeg er ikke helt sikkert på, om det var det du spurgte om. Jeg skrev også noget om, hvordan at compileren automatisk skulle parallelisere, og fungere med et normalt sekventielt program. Her skal det naturligvis fungere, at selvom der er to tråde, der begge arbejder på samme variabel, så skal koden fungere på den måde, og i den rækkefølge, som der står skrevet i programmet. Et sekventielt program er altid sekventielt, og hvis rækkefølgen i koden er veldefineret, så skal den vedblive at være veldefineret, selvom koden udføres parallelt.

Analytisk set, så har computeren ikke nogen ram, men der arbejdes med en stor bus, der indeholder hele computerens ram. Der kan tages udsnit af denne bus, f.eks. modificeres en byte. Når vi ændrer en byte, så anvender vi en blok, der modificerer en byte på lager bussen. Og når vi læser data, så læser vi data ud med en blok, der læser data på lager bussen. Det ses nemt, at det at læse data ud sker på bussen, og lager informationen går ikke igennem blokken, da der ikke sker nogen modifikation. Den splittes ud, og læsning kan altid ske parallelt. Derimod skrivning, det modificerer lagerbussen, så de informationer der kommer ud af en skriveblok, er andre end dem der kom ind. Når vi arbejder med dataflows, så vil begge vores parallele koder arbejde på samme lagerbus, og den tvinger således en rækkefølge. I praksis deler vi ofte lagerbussen op i mange, da der kun påtvinges en rækkefølge, hvis det er samme addresse. Men, vi påtvinger en rækkefølge, og det kan ses ud fra dataflow grafen, som er det vi bruger ved analyseringen.

I nogle tilfælde, så kan vi anvende funktioner der øger parallelismen, ved at f.eks. kopiere kode, f.eks. kan ske, at vi kan opnå samme funktion, ved at skrive to ++'er i den ene tråd, og også gøre det i den anden tråd, og alligevel have den helt adskilt. Det er muligt at automatisk analysere programmet for, om vi kan trække tråde fra hinanden, også hvor de umiddelbart i koden ser ud til at have afhængighed.

Så alt i alt, så vil koden normalt blive tvunget sekventiel ved adgang til samme lageraddresse. Men, der kan ofte udføres operationer, så det ikke sker, og de kan køre helt adskilt.

I alle tilfælde, så er det ikke noget du skal tænke på. Det er compilerens opgave. Den sikrer, at det fungerer præcist som ved normal sekventil kode, og virker som om det kører sekventielt. Enhver sekventiel kode virker stadigt sekventielt.

Der hvor parallelisme opstår fra et brugerniveau, er hvor du har to dele af koden, som ikke anvender samme lageraddresser, og derfor er uafhængige. Her, kan du kommunikere mellem dem, f.eks. med en fifo, og anvende parallelisme fra softwaresiden. Der behøves ikke at blive kodet specielle parallele funktioner ind, for at udføre software parallelt. Her er det dog lidt svært, hvis der ikke er særlige operatorer i sproget til at håndterer køerne - så får man netop det problem du omtaler. Og så skal vores automatik kunne løse det.

5
23. juli 2020 kl. 18:31

Jeg kan se på din kommentar, at det ikke fremgår tydeligt at jeg taler om hardware abstraktion.</p>
<p>Software abstraktion er også vigtigt - og som du nævner kan der være problemer, når der er mange lag af abstraktion. Dette er ikke et problem ved hardware abstraktion.

Jeg tror nu slet ikke vi er uenige, selvom jeg mere ser det hele fra software siden. Især er jeg absolut enig med dig i, at det skal være compileren, der genererer maskinkoden. Men når det er sagt, så er hardware jo meget andet end CPU; helt nær ved er der cache, lidt længere væk memory, måske numa, der er roterende og solid state diske, og der er netværk med meget variende latency. Hver af disse kunne - principielt - have sin egen hardware abstraktion med sin egen compiler feature. Hvis den ideelle compiler du beskriver, f.eks. kan lave kode, der eksempelvis automatisk finder ud af, at dit parallelle program ikke må læse og skrive samtidig til de samme bytes i memory, så ville det være fantastisk. Men mon det er muligt? Kan en compiler finde ud af, at to tråde, der begger laver

++(*p)

skal have det koordineret uden at programmøren på nogen måde fortæller om det og uden at det bliver dyrere, hvis den stump kode ikke kører samtidig i flere tråde?

Når vi så kommer til hele stakken, lige fra brugerens enhed, gennem adskillige lag af netværk, cpu og ram, for til slut at ramme noget ikke volatilt som en roterende disk, så er det at abstaktionen (indrømmet, især software) nemt giver problemer. Jeg mener reelt, at abstraktionen af software (med den stort set altid manglende beskrivelse af omkostningen) decideret forhindrer effektiv udnyttelse af resourcer, og det er uanset hvor smart compileren er i de mange lag. Det bliver aldrig til andet end lag, der ikke forstår de andre lag.

4
23. juli 2020 kl. 17:26

Jeg kan se på din kommentar, at det ikke fremgår tydeligt at jeg taler om hardware abstraktion.

Software abstraktion er også vigtigt - og som du nævner kan der være problemer, når der er mange lag af abstraktion. Dette er ikke et problem ved hardware abstraktion.

En god måde at hjælpe til bedre store O funktioner, og bedre implementeringer, er ved at fast implementere metoder i sproget, som ofte anvendes. Det er her vigtigt, at disse metoder er optimale, med hensyn til både hukommelsesforbrug, stabilitet, og store O funktionen, samt selv lille O må også gerne være optimeret. Denne optimers dog ofte af compilerens optimering. Endeligt gør det kodningen mere kompakt, hvis sædvanlige konstruktioner er implementeret på en bestemt måde, så der ikke bruges 117 forskellige metoder for at gøre det samme, fordi at hver programmør har sin egen foretrukne. Naturligvis så kan automatikken i dag ofte opdage og indse hvad der sker, og erstatte metoden med den der er indbygget i sproget. Men, det er mere overskueligt for programmørerne, hvis de almindelige konstruktioner, hvor vi kender de mest effektive implementeringer er bygget ind.

Hvisvi i et sprog har en funktion som "+", så er relativt nemt at implementere den effektivt. Hvis vi ikke har "+" og skal lave et bibliotek der beskriver det ved hjælp af if/then på binært niveau, så risikerer vi at det ikke implementeres optimalt. I dag har vi algoritmer, der næsten altid kan opdage hvad det er som vi laver, hvis vi bare gør det "dumt". Og nogen mener, at det er fremtiden. Gør det dumt og nemt, og lade automatikken om at programmere ordentligt.

3
23. juli 2020 kl. 17:02

Abstraktion uden overhead, men ....
Abstaktion uden overhead er naturligvis godt, og det er naturligvis også godt, at sproget sikrer, at man ikke ved "håndkodning" havde kunnet skrive mere effektiv kode. Men der er alligevel en hage ved det, nemlig at abstraktionen meget ofte skjuler implementeringen fra brugeren.

Måske kan du godt ved håndkodning skrive mere optimal kode, men ofte er det omvendt. Du har hverken overskud, eller resourcer, til at levere et så godt resultat som automatikken opnår. Derudover medfører det at det du laver låses fast, så dit fremtidige liv ikke bliver andet end at lave nye udgaver og versioner. Derudover, så mener jeg at man netop skal anvende abstraktion der, hvor at vi har algoritmer og metoder, der faktisk kan noget - altså som giver det effektive og optimale valg. I tilfældet jeg nævner, er det et spørgsmål om, at lade compileren oversætte til hardwaren uden at diktere hvordan hardwaren skal være opbygget - altså, f.eks. tal skal kunne repræsenteres i hardwarens talsystem, der sjældent er binær. I dag sætter computeren automatisk tomme bytes ind for at alligne til f.eks. words. Det er faktisk i familie med det. Vi kan opfatte det sådan, at en byte erstattes med en 16-bit word tal, hvor de første 8 bits altid er 0, og at softwaren derved tilpasser talsystemet til hardwaren. I unions, hvor data overlejrer hinanden, er det aldrig tilladt at indsætte bits eller bytes. Her skal talsystemerne ikke styres af hardwaren, men af definationer, fordi vi bruger det alene til at omsætte vores data til bestemte formater. Dette er formålet med unions, herunder bit-unions. Det er ikke for at reducere pladsforbruget, for det kan ikke gøres sikkert på den måde - det skal vi lade compileren ordne selv. Den kan selv overlejre data og genbruge addresser, hvor det er sikkert for den.

Hvis alt jeg får at vide er, at her en en klasse med de-og-de metoder, så aner jeg ikke, om de metoder er dyre eller billige. Hvis jeg har en klasse, "bil", med en metode "farve", og jeg kun er interesseret i røde biler, så tjekker jeg om bil.farve()=='rød' uden at jeg har nogen som helst anelse om, hvordan dette er implementeret. Det er måske fint nok, at lave tjekket på en bil i minuttet, men er en per sekund ok? Tusind per sekund?

Egentligt er det en stor fejl ved programmering, at det ikke er almindeligt at skrive prisen på koden. Selv store O funktionen er normalt ikke nævnt. Dette viser - i mine øjne - bare at koden er ubrugeligt. Ingen pris, ingen anvendelse. Indenfor hardware, har vi intet datablad, uden vi kan se prisen - der er timing datasheet, der er strømforbrug og energiforbrug, og enhver anden form for pris på komponenten. Men, indenfor software kan programmørerne ikke engang finde ud af skrive kompleksiteten på.

Jeg har gennem min lange karierre set utallige eksempler på dårlig performance, hvor det reelt har være et problem som dette, der var det underliggende problem. Abstraktionen gør, at der laves lag på lag på lag, så den samlede stak bliver prohibitivt stor, også selvom de enkelte lag er "abstraktion uden overhead".

Jeg kender godt problemet, og jeg har også haft store problemer med at overbevise mange om store O funktionens betydning. Ikke mindst i dag, hvor automatiken er blevet så optimal, at hvis man skriver sin kode på en måde, så automatikken kan gennemskue det, så ændrer den det automatisk til at bruge hardwaren, og at anvende optimale store O funktioner. Men, hvis man derimod udvikler sin egen højeffektive algoritme, så bliver hardwarefeatures ikke udnyttet, da automatikken ikke kan gennemskue algoritmen. I dag ser vi ofte, at en dårlige algoritme med dårlig store O funktion, faktisk implementeres bedre end en god algoritme, fordi at den dårlige algoritme står nævnt i compilerens katalog over typiske dårlige metoder, og derfor forstås og implementeres optimalt, med optimal store O funktion i forhold til kodens.

Det som jeg syntes er vigtigt, er at tilpasningen til hardwaren sker i compileren. Vi skal ikke kode i maskinkode. Hardwarelaget skal være helt usynligt for kodelag. Vi kan ikke forvente, at vi alligevel kan se hardwarelaget på fremtidens computere - f.eks. er maskinkoden udskiftet til Java Byte kode, eller andet operativsystem sprog, så ved vi intet om hvordan det er kodet i hardwaren. Faktisk kan vi spå om, at fremtidens computere fysisk ikke vil være i stand til at udlevere hardware informationer, og hvis sproget sætter krav til dette, så kan det ikke oversættes til fremtidige akitekturer.

Nogle computere er delt op i flere parallele computere, således at addresseudregning foregår for sig selv, på sin egen computer. Det betyder, at vi på vores datacomputer, ikke kan få adgang til pointers. Det er simpelten umuligt, da de er fysisk placeret et andet sted. I et godt programmeringssprog, må vi ikke kunne aflæse hardwaredetaljer, som f.eks. adressen af en variabel. Vi må gerne bruge den, men vi må ikke kunne få adgang til den fysiske kodning. For dette vil diktere vores hardware hvordan den skal fungere, og det må vi ikke. Hardwaren kan simpelthen ikke laves optimal, hvis det er softwarefolk der skal bestemme. De har ikke hovedet til det... Det giver meget langsommere computere, hvis man ikke kan tage addresseudregningstråden og trække ud af datatråden, og udføre dem på særskildt hardware. Har vi adgang til hardware informationer i kode medfører det også at programmeringssproget bliver afhængigt af hardware, hvilket er det samme som det ikke er deterministisk, da det laver noget andet, hvis vi ænder længden af printbanerne. Determinisme betyder, at det skal altid ske det samme, uanset hardware, uanset compiler, uanset fysiske forhold som længden af printbaner, udførslen af rækkefølge i parallle processer, osv. Kun i tilfælde,hvor der anvendes deciderede tilfældighedsfunktioner, eller funktioner til generering af abitrære værdier, er det lovligt at der kan opstå noget ikke deterministisk. Og i disse tilfælde, skal vi kunne se det under programmets egenskab, at det ikke er deterministisk, men anvender tilfældige valg.

I øvrigt, så er det mange gange nemmere at overskue og teste, hvis det sker det samme hver gang, og man ikke skal bekymre sig om, at der måske er flyttet en bane, der gør at et andet interrupt kommer først.

2
23. juli 2020 kl. 16:03

Abstaktion uden overhead er naturligvis godt, og det er naturligvis også godt, at sproget sikrer, at man ikke ved "håndkodning" havde kunnet skrive mere effektiv kode. Men der er alligevel en hage ved det, nemlig at abstraktionen meget ofte skjuler implementeringen fra brugeren.

Hvis alt jeg får at vide er, at her en en klasse med de-og-de metoder, så aner jeg ikke, om de metoder er dyre eller billige. Hvis jeg har en klasse, "bil", med en metode "farve", og jeg kun er interesseret i røde biler, så tjekker jeg om bil.farve()=='rød' uden at jeg har nogen som helst anelse om, hvordan dette er implementeret. Det er måske fint nok, at lave tjekket på en bil i minuttet, men er en per sekund ok? Tusind per sekund?

Jeg har gennem min lange karierre set utallige eksempler på dårlig performance, hvor det reelt har være et problem som dette, der var det underliggende problem. Abstraktionen gør, at der laves lag på lag på lag, så den samlede stak bliver prohibitivt stor, også selvom de enkelte lag er "abstraktion uden overhead".

1
23. juli 2020 kl. 14:13

Her er jeg helt på linje med Bjarne - sproget skal være:

  • Væsentligt lettere at bruge og lære end C eller dagens C++.
  • Helt typesikker - ingen implicitte typeovertrædelser og ingen 'hængende' pointere.
  • Helt ressourcesikkert - ingen lækager og intet behov for en garbage collector.
  • Relativt let at opbygge værktøjer til - ingen makroer.
  • Så hurtigt som dagens C++ - princip om nul 'overhead.'
  • Forudsigelig ydelse - velegnet til integrerede systemer.
  • Ikke mindre udtryksfuld end i dag - håndterer hardware godt.

Der er ingen tvivl om, at vi ser på det på samme måde. Problemet er imidlertid, at han med ovenstående "antyder" fejl som sproget har i dag...

Dertil har jeg et par tilføjelser, som jeg syntes er utroligt vigtige:

  1. Determinisme.
  2. Determinisme
  3. Determinisme.

Altså, sproget skal gøre det samme hver gang, og ikke have "tilfældigheder" indbygget. Compileren må ikke have valgfriheder, så det afhænger af kommentarer og opsætning, hvordan at programmet fungerer. Der må ikke kunne opstå tilfældigheder fordi at tingene er dårligt indtastet. Der må heller ikke være tilfældigheder på grund af uinitialiserede variable - compilerne skal f.eks. opdage, hvis de ikke initialiseres og bruges. Det er også vigtigt, at det er overvejet parallelisme, da C++ hvis det skal fungere sammen med hardware, også reelt fungerer parallelt - hardwaren kører parallelt i forhold til softwaren, og derfor er vigtigt at have kendskab til parallelisme ved design at sproget. Et eksempel er interrupts, der helt svarer til et parallelt program. Her går det ikke med "volatile" der hvis det mangler, kan medfører at softwarens opførsel afhænger af vejr og vind. Vi kan diskutere om løsningen er at volatile skal sættes på automatisk - jeg går mere ind for, at compileren skal være i stand til at tjekke om der er volatile hvor det skal være. Altså, at man specificerer sharede variable, og forsøges en variabel at blive anvendt som shared, uden at være mærket volatile, så må compileren ikke kunne oversætte det - dette kræver, at compileren har styr på, hvad der kører parallelt, og at man forstår interrupts parallelt.

Jeg er selv af typen der "hader" garbage collectors. Måske vil jeg kunne acceptere det i nogle tilfælde, men jeg syntes det er et rigtigt godt udgangspunkt, at det ikke er noget vi syntes er godt. Specielt hader jeg, når at jeg er midt i noget, og så tager det ligepludseligt masser af tid, fordi at oprydningen kommer på besøg.

Et fjerde punkt jeg gerne vil tilføje, er at have styr på timingen. Det kan gøres på mange måder, og behøver ikke nødvendigvis nogen ændring i sproget, men timing problematikken er værd at overveje.

Og så endeligt, er også vigtigt med abstraktion. Måske er det så selvfølgeligt, at Bjarne har glemt det på listen... Men, det mangler faktisk i C++. Skal man lave et sprog så hardware compatibelt som muligt, så skal det faktisk helst være så abstrakt fra hardwaren som muligt - for det skal være muligt for compileren at oversætte til den pågældende hardware. Man skal ikke skrive programmet til hardwaren.

Dette medfører et par små ændringer i et sprog som C++. I dag er alle typer "defineret", med både bits og positioner af bits i de forskellige typer. Dette er ofte en ulempe, fordi det forbyder hardwaren at selv vælge hvordan den vil gemme data. Vi må ikke vide noget om hvor mange bits der bruges, og hvor mange bytes der bruges på at gemme et tal. Det er compileren der afgør det, når den oversætter til vores hardware. Det er også hardwaren der bestemmer både talsystem, og hvordan at data opbevares. Vi må intet vide. Det eneste vi angiver, er det område som f.eks. en integer variabel skal være defineret over, og dette område må ikke have nogen nedre eller øvre grænser.

Dog, så er det meget vigtigt for et sprog, at det er nemt at kommunikere med hardware. Derfor, har vi også brug for taltyper der gemmer data på samme måde som hardwaren gør. Derved er vi fri for, at lave lange besværlige rutiner, for at regne de enkelte bits ud, når vi skal sende noget til hardware. Her har vi unions i C++ som er værktøjet. For unions skal data altid gemmes pakket. Det giver ingen mening, med en union, hvor at compileren kan vælge at sætte bytes eller bits ind tilfældigt. Dette ødelægger determinismen. Så der må kun findes pakkede unions. En unions formål, er ikke at pakke variable, så de fylder mindre plads i lageret - det kan compileren selv gøre med normale variable. En unions formål er, at beskrive en struktur på bit niveau, og sikre sig at det er muligt at få binær adgang til bittene, således at unions anvendes når at man beskriver hardware datatyper. I en union kan kun anvendes typer, hvor at positionen af bits er beskrevet eksakt, og det er veldefinerede typer. Mens at normale variable skal være abstrakte. Her ved vi intet om hvilket talsystem der anvendes, og hvor dataene opbevares, eller hvor mange bytes de fylder. Og vi må ikke kunne få det at vide, for at program er ikke deterministisk, hvis det kan hente oplysninger om en tilfældig hardware. Til gengæld, så må compileren af samme årsag også gerne indsætte tomme bytes for allignment.

Parallelisme er en meget vigtig ting at forstå - og ikke mindst, hvordan det gøres bedst. Dette er nødvendigt, fordi at hardwaren fungerer parallelt med softwaren. Og fordi at alt hardwarenært også skal fungere med f.eks. interrupts. Determinisme kravet gælder også for parallelisme. Det må ikke være muligt, at skrive et program, hvor det er tilfældigt hvad der kommer først. Det betyder, at det skal altid virke ens, uanset hvilken rækkefølge at trådene kører. De må køre som de vil, men det må ikke have betydning for resultatet, og det må ikke være muligt at se fra hverken hardwaren eller brugeren hvad der sker inde i computeren. Computerens indmad er dens egen. I nogle tilfælde, så kan ikke undgås at man får brug for "komponenter" der tager stilling til, hvilke data der kommer først. I så fald, så kræves teknisk set en tidsstempling af data, der hvor de kommer ind, fordi at det aldrig må afhænge af interne forsinkelser i computeren eller i koden. Det skal være 100% deterministisk. Men, vi må gerne sætte en tidsstempling på, hvor f.eks. at data indtastes, og bruge denne tidsstempling, hvis at to indtaster noget i en database samtidigt, til at afgøre rækkefølgen og dermed resultatet. Det vigtige er, at uanset forsinkelser i netværk og hardware, så skal det altid fungerer ens. Computerens indmad, og forsinkelser i printbaner, tråde og rækkefølge af eksekvering af parallele processer, må aldrig have betydning for resultatet. Dette er vigtigt at forstå, hvilke krav at dette stiller.

Endeligt er væsentligt, at vide hvordan man opnår parallelisme, uden at det står specifikt skrevet i sproget. Vi skal gerne kunne anvende den parallelisme der er til rådighed, uden at skulle specificere det i kode. Uanset, om vi udfører koden på en supercomputer med milliarder af samtidige processer og tråde, så skal koden være identisk, med den som kører på vores PC med en CPU og en tråd. Altså, paralleliseringen af den sekventielle kode, er derfor også en del af compileren. Og det at sekventiel kode forstås parallelt muliggør, at vi kan kommunikere mellem sekventielt skrevet kode, ved hjælp af fifoer, så det opfattes parallelt. Har vi sekventiel kode i et program, hvor der ikke er dataafhængigheder, kører det parallelt, og vi kan kommunikere mellem disse sekventielle koder, ved hjælp af beskedkøer. Altså, har vi sekventiel kode, og fifoer / beskedkøer, så kan vi opfatte den sekventielle kode både parallelt, fordi at vi kommunikerer med den kode der ligger tidligere ved hjælp af køer. Det er måske i starten lidt svært at begribe, og ligner at man sender data baglands i tiden. Det væsentlige er, at man laver programmeringssproget, så det er nemt at angive både sekventielle og parallele opgaver, mens at det ikke må betyde noget, hvordan man angiver det, når det ses på hvordan at computeren udfører det. Vi skal ikke i koden beskrive hvad der skal ske, men hvad vi ønsker.

Det, som gør et sprog hardwarenær, er features som bit unions, hvor vi har mulighed for at konvertere datatyper til hardwaretyper på en smuk måde. Og, vi bør også have mulighed for, at kunne definere nye typer, hvor vi selv bestemmer bitplaceringen for typerne. Det betyder ikke så meget om det er hurtigt eller langsomt. Det som betyder noget, er at det gemmes korrekt, så det beskriver det vi ønsker ved vores data kommunikation med f.eks. hardware.

Jeg håber bestemt at det lykkedes Bjarne at få løst problemerne han angiver. Men, som nævnt, er det ikke helt nok. Et par væsentlige ting - specielt determinismen - mangler. Hverken hardware, CPU, compileren, delays, eller parallelisme, må tilføre tilfældigheder til et sprog. Der skal altid ske det samme med samme kode. De eneste tilfældigheder, er dem som specificeres - f.eks. brug af en random funktion. Og det skal man gerne kunne se, og administrere under et programs egenskaber, om man ønsker accept af tilfældigheder.