Verona: Nyt sikkert sprog fra Microsoft skal løse problemer med gammel C og C++

I modsætning til Rust kan Verona med 'regioner' håndtere ejerskab til grupper af objekter. Illustration: Version2/Skærmdump
Verona er et kommende open source-bud fra software-kæmpen med dansk islæt. Det skal gøre gammel usikker kode sikker.

Det fungerer ikke, det der med at spise elefanten én bid ad gangen.

I hvert fald når elefanten hedder software-fejl i gammel kode, som skal vedligeholdes.

Det synes Matthew Parkinson, som er forsker hos Microsoft, med en fortid som datalog på Cambridge-universitetet i England.

Han mener, at fremgangsmåden med at fikse enkelte fejl én af gangen i en stor kodebase ikke skalerer. Det fortalte han i et foredrag afholdt i sidste uge, arrangeret af UK Research and Innovation, som er et britisk partnerskab af universiteter, forskningsorganisationer, regering med mere.

Antallet af CVE-sårbarheder i Microsofts produkter stiger mere end lineært år for år, så der skal nye boller på suppen, mener forsker Matthew Parkinson. Illustration: Version2/Skærmdump

Som man kan se på slidet til højre, stiger antallet af CVE-sårbarheder i Microsofts produkter år for år. Der er en mere end lineær stigning, og det skyldes ikke mindst, at firmaet forvalter en stor mængde gammel kode, skrevet i C og C++.

70 procent af sårbarheder er usikker hukommelse

Omkring 70 procent af de sårbarheder, Microsoft udstyrer med et CVE-nummer, skyldes problemer med usikker hukommelse. Det tal har ligget stabilt i de seneste 12 år.

Når Microsoft øger sin kodebase og benytter mere open source-software i sin kode, bliver dette problem ikke bedre, men værre.

Andre producenter, der også arbejder med C og C++, oplever det samme. Men de nye it-kæmper, som Google, Facebook og Amazon, har ikke helt samme problemer som Microsoft, hvis kode går mange tiår tilbage.

Der findes hukommelsessikre sprog som C# og Java, men C og C++ kan nogle tricks, som de sikre sprog ikke kan tilbyde i helt samme omfang.

C++ har nemlig dyder, der gør det attraktivt og undertiden helt uomgåeligt. Sproget er hurtigt, det kan køre med begrænset hukommelse og diskforbrug, det er et modent sprog, det har forudsigelig afvikling, og dets platform-uafhængighed er næsten uden sidestykke.

Endelig kræver det ikke nødvendigvis installation af andre biblioteker eller komponenter. Men som nævnt fører det også til fejl, der ofte handler om håndtering af hukommelse.

Microsoft har eksperimenteret med Rust til nye komponenter. Og det sprog byder på de fordele, som C og C++ har, men på en sikker facon. Men man har også kig på helt nye initiativer.

Læs også: Microsoft: Rust kan løse hukommelsesproblemer i C og C++

Dansk islæt

Firmaet kan ikke bare lægge den gamle kode bag sig, men ser i stedet på, hvordan koden kan gøres mere sikker.

Der findes nogle simple kneb til at rette fejl. Det kan eksempelvis være compilere, der initialiserer alle variable i kode skrevet i C og C++, beretter Matthew Parkinson i foredraget.

En anden fremgangsmåde er at se på sprogdesign og hvad Matthew Parkinson kalder for ‘compartmentalisation’.

Det vil sige at skære den gamle kode i bidder og putte dem i kasser, så sårbarhederne er skærmet af. Det kræver nyt sprogdesign, og det er her, projekt Verona kommer ind i billedet.

Det er et samarbejde mellem Microsoft og Cambridge-universitetet, og foredraget i sidste uge er første gang, Matthew Parkinson løfter sløret for projektet.

Han karakteriserer det som ‘et nyt sprog til sikker infrastruktur-programmering.’ Med i projektet er danske Mads Torgersen, der er den nuværende chefdesigner bag C# og tidligere datalog på Aarhus Universitet. Han har har bidraget til Verona med ideer til, hvorledes et godt sprog designes, fortæller Matthew Parkinson.

Læs også: Nej til null: Her er nyhederne i C# 8

Regioner i stedet for Rust

Problemfeltet hedder system-programmering, og det kan karakteriseres ved finkornet kontrol i forhold til resurser og følsomhed i forhold til latency, altså den tid, det tager at udføre en proces.

Det foregår tæt på maskinen, uden en abstraktion over hukommelsen, og uden typesikkerhed. Disse to forhold er usikre som udgangspunkt.

Løsningen er ifølge Matthew Parkinson at sige farvel til fælles adgang fra tråde til at ændre hukommelse, ‘samtidigt ejerskab’, der er en ny model til asynkron koordinering samt ‘lineære regioner’, som er et nyt bud på hukommelseshåndtering. De ikke så nemme koncepter er illustreret i grafikken øverst i denne artikel.

»Ejerskabsmodellen i Verona er baseret på ‘regioner,’ grupper af objekter. Det er ikke som i Rust, hvor den er baseret på et enkelt objekt. I C ++ har du pointers, og det er baseret på objekter, og det er stort set pr. objekt. Men det er ikke, hvordan jeg tror om data og programmer. Jeg tænker på en datastruktur som en samling af objekter. Og den samling af objekter har et livsforløb,« forklarer Matthew Parkinson.

Læs også: Rust: Sådan vil Mozilla genstarte Firefox med sikker og hurtig kode

»Så ved at tage ejerskab på niveauet for ejerskab af objekter kommer vi meget tættere på det abstraktionsniveau, som folk bruger, og det giver os muligheden for at opbygge datastrukturer uden at gå uden om sikkerheden.«

Der er endnu ingen offentlige eksempler på Verona, men koden vil blive frigivet som open source i løbet af de kommende uger, siger Matthew Parkinson.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Følg forløbet
Kommentarer (21)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#1 Simon Lodal

I C++ er der ikke rigtig nogen undskyldning for lække. Alle allokeringer på stakken, eller indkapslet i objekter som delete'r i destructor (RAII). Og smart pointers. Men selvfølgelig kan man gøre det galt, hvis man virkelig vil.

Verona lyder som om det løser ét specifikt problem på én specifik måde.

Eller en løsning på jagt efter et problem.

Jeg kan ikke se hvorfor det skulle være interessant (nok) - der er så mange andre facetter i et sprog.

  • 4
  • 3
#2 Michael Cederberg

Jeg kan ikke se hvorfor det skulle være interessant (nok) - der er så mange andre facetter i et sprog.

Nu er jeg ikke specielt aktiv C++ udvikler længere så det kan være jeg har overset noget i C++ 17, men i hvad jeg kender til så er C++ modellen stadigvæk ikke god nok i et multithreaded miljø. Enten vælger man smart pointers med reference counting ud over det hele med de omkostninger det giver eller også holder man tungen lige i munden med de fejl det kan give.

Rust forsøger at løse problemerne omkring pointere i C++ men har ikke regionsbegrebet. Regionsbegrebet synes at være en form for letvægts actor-model uden alt det overhead som ses i sprog som Erlang. En måde af opdele koden i områder hvor man kan køre uden multithreading-sikkerhedssele i dele koden (fordi den er sekventiel) og med sikkerhedssele andre steder hvor det er nødvendigt.

Spændende!

  • 6
  • 0
#6 Michael Cederberg

Måske man skulle give Rust en chance :)

Venona og Rust handler ikke om hvorvidt performance er bedre end C++/C. Ønsket er blot nogenlunde samme performance. Det handler om at gøre det nemmere at skrive programmer der ikke crasher pga. fejl som sproget kunne beskytte mod ... specielt når det gælder multithreadede programmer.

Personligt kan jeg sige at når jeg ikke længere gider C++, så er det fordi jeg har brugt for mange dage af mit liv på at debugge C++ kode som har overskrevet memory. Min egen erfaring er at top-tier developers er ca. 3-4 gange så produktive på sprog som Java/C# (selvom de også godt kunne bruge region begrebet). Den hellige gral er i mine øjne at få samme developer produktivitet for sprog der ikke kører i en garbage collected VM og har samme performance som C++.

  • 2
  • 1
#7 Palle Simonsen

Performance af Rust ser i Benchmark ud til at være bedre end C på en række målinger, bedre end C++ på de fleste målinger og langt bedre end Java på alle målinger.

Produktivitet tenderer oftest til at blive en subjektiv størrelse.

  • 2
  • 1
#8 Michael Cederberg

Produktivitet tenderer oftest til at blive en subjektiv størrelse.

Tjaa ... hvis man ser på moderne programmeringssprog så synes der at være enighed om følgende:

  • Når alle pointere/referencer kan være NULL så er det en rigtig dårlig ide. Dette er den største fejl i C, C++, Java, C#, m.fl.
  • At debugging af fejl der kommer af overskrivning af hukommelse er meget dyrt. Når programmeringssproget kan undgå samme så giver det produktivitetsstigninger.
  • Generics/templates er en god måde at genbruge kode på en typestærk måde.
  • Multithreaded programmering er svært. Programmeringssprog der hjælper udvikleren med multithreaded programmering hjælper på produktiviteten. Af samme grund er vi lige så stille gået fra semaphorer og tråde til meget mere avancerede primitiver.

Derfor er der brug for nye sprog. De nye bygger på erfaringerne fra de gamle.

  • 2
  • 0
#10 Troels Henriksen

Performance af Rust ser i Benchmark ud til at være bedre end C på en række målinger, bedre end C++ på de fleste målinger og langt bedre end Java på alle målinger.

Rust er et udmærket sprog, men den indbyrdes ydelse for rimeligt ækvivalente sprog (her C/C++/Rust) er ofte mest et tegn på hvor energisk brugersamfundet er. Hvis vi f.eks. kigger på et af de problemer hvor Rust vinder, n-body, så bruger begge sprog ca. samme fremgangsmåde (og eksplicit SSE2-vektorisering). Jeg kan se at Rust-udgaven inverterer gennemløbene af visse af løkkerne, hvilket jeg tror giver bedre cache-adfærd i de konkrete tilfælde (men iterationsantallet er så lille at det er svært at forudsige). Mit gæt er at Rust-udgaven er blevet udsat for flere eksperimentelle transformationer, og at dem der har givet ydelsesforbedringer så er blevet beholdt. Det siger ikke så meget om hvilket sprog der er hurtigt, eller hvem der har den bedste oversætter.

Der findes dog tilfælde hvor Rust og C++ har ydelsesfordele ift. C. Det er især når man arbejder med generisk kode, f.eks. sortering, som i C typisk gøres ved at arbejde med void* og funktionspegere (f.eks. qsort()). Her kan både C++ og Rust i stedet generere monomorfisk specialiserede sorteringsfunktioner til konkrete typer og sammenligningsfunktioner. Det resulterer i at der genereres mere kode (hvilket i nogle tilfælde kan påvirke ydelsen negativt), men som regel tillader det bedre optimering.

  • 4
  • 0
#11 Michael Cederberg

Rust er et udmærket sprog, men den indbyrdes ydelse for rimeligt ækvivalente sprog (her C/C++/Rust) er ofte mest et tegn på hvor energisk brugersamfundet er.

Netop. Pointen med Rust (eller Venona) er ikke bedre performance. Performance skal bare være ca. ligesom C/C++. Når Rust eller Venona bringes ind i billedet så er det for at hæve kvalitet/produktivitet.

På samme måde som C++ ikke gav performance forbedringer over C - C++ tillod bedre reusability gennem OO og senere templates (C++ fik også et stærkere typesystem for at hæve kvalitet/produktivitet). Men der er ikke noget man kan skrive i C++ som ikke kan skrives i C med samme performance.

Når det gælder performance af programmeringssprog for generelle single-threaded programmer så løste C det problem i begyndelsen af 70'erne. Det er nok også grunden til at Linux er stadigvæk skrevet i C.

  • 1
  • 0
#12 Kim Madsen

tydeligt at det er det også for dem der laver sideboksen til artiklen.

De forskellige måder at holde rede på allokeret hukommelse, som listes (GC, ARC m.m.) løser jo IKKE problemerne med multitrådet programmering.

Multitrådet programmering er en udfordring, når eksakt samme data i hukommelse eller på disk eller i enhver anden storage skal behandles samtidigt fra flere tråde.

Helt basalt set kunne data være en kylling. Den ene tråd vil gerne se status på kyllingen, er den død/levende/plukket, og den anden vil gerne plukke den, men kun hvis den er død. Hvis begge tråde kører eksakt samtidigt (potentielt muligt i multicore systemer), og de ikke er enige om hvordan man afklarer scope af død, levende og plukket, så kan det godt være at den ene tråd opdager kyllingen er levende, mens den anden tråd er i gang med at plukke den.

Den faktiske status af kyllingen kan svæve hen i det uvisse.

Det er derfor basale ting som låsninger (i mange forskellige varianter... men det koger sammen til det samme) eksisterer, således det er muligt at få en fuldstændig klar status for et hukommelses område, og ingen andre ændrer i data indtil der gives lov.

At lave korrekt trådet programmering vil altid kræve et fantastisk godt kendskab til det processuelle i det man ønsker gjort (domænet). Bank handlinger, vejninger, bevægelser i robotter etc.. Præcist hvor kan man opdele ens processer i delprocesser som hver i sær kan leve umiddelbart uafhængigt af hinanden.

Altså er trådhåndtering domæne specifikt, hvorfor det aldrig bliver nemt at lave trådprogrammering.

  • 0
  • 1
#13 Michael Cederberg

Multitrådet programmering er svært... og det er... tydeligt at det er det også for dem der laver sideboksen til artiklen.

De forskellige måder at holde rede på allokeret hukommelse, som listes (GC, ARC m.m.) løser jo IKKE problemerne med multitrådet programmering.

Men når man laver massivt parallelle programmer så bliver memory management nemt en bottleneck. I en naiv implementering er der en lås på heapen som tages når der allokeres og frigives hukommelse. Denne lås vil alle tråde pille ved hele tiden og dette vil effektivt ødelægge parallelismen.

Derfor har alle moderne sprog/runtime environments optimeringer nede under overfladen. Fx. vil heap-allokeringer typisk ske fra en thread-local heap sådan at man ikke behøver låse noget når man allokerer.

Når det handler om at frigive memory på heapen, så kan det basalt set enten ske eksplicit (e.g. memfree, delete, smart-pointers) eller gennem garbage collection. Porblemet for eksplicit memory management er at finde ud af hvornår objekter skal frigives. En simpel måde at gøre det på er at lave reference counting på alle objekter.

Det virker rigtigt godt i et singlethreaded miljø - der er stort set ingen performance omkostninger. Desværre er reference counting i et multithreaded miljø meget dyrt - basalt set er det sammenligneligt performance-wise med at tage en lås hver gang counteren ændres.

Derfor førsøger både Rust og C++ at udnytte stakken til at "låne" ejerskab af objekter ud uden at man behøver at pille ved reference counteren. Det løser problemet til en hvis grad, men der er stadigvæk performance problemer. Derfor Venona.

Mere kuriøst er det værd at notere at hvis man har meget memory så giver garbage collection bedre performance end traditionelt memory management. Det er fordi allokeringer er næsten gratis men garbage collections er dyre. Hvis man har tilstrækkeligt meget memory så når man aldrig til et punkt hvor man skal lave garbage collection. Ydermere er det sådan at det kun er "overlevende" objekter der koster performance. Derfor vil selve garbage collection i mange tilfælde heller ikke være dyrt hvis der er lang tid imellem. Men problemet for GC løsninger er selvfølgeligt "stop-the-world" pauser - der er mange steder hvor dette ikke er acceptabelt.

  • 1
  • 0
#14 Kim Madsen

Hej Michael,

Problemet er, efter min mening, ikke flertråede applikationer som bruger hver sit sæt af data.

Der kan være implementerings ting der gør at separate processer måske ville performe bedre, f.eks. hvis man har en elendig memory manager som bottleneck, og applikationen ikke selv præallokerer nok hukommelse for at undgå gentagne allokationer/deallokationer.

Men som udgangspunkt er der ikke et problem, sålænge alle trådene er enige om ikke at have noget med hinanden at gøre.

Problemet opstår når der er overlap i forhold til data input eller output.

Og der har diverse memory allokerings mekanismer ikke nogen som helst relevans.

Der er (for nuv.) kun 2 måder at løse det på:

  • Låsninger, så kun een tråd/process kan tilgå data af gangen. Der er forskellige optimeringer for at lave ikke låste låsninger, f.eks. ved læsninger (MREW... multiple read exclusive write). Men det er låsninger.

  • Duplikering. Lav kopier af data således der aldrig rettes i originale data, men kun i kopierne.

Der findes måske mentalt også en 3. løsning, hvor man udnytter lockfree algoritmer som lister, stakke etc. som fælles storage mellem tråde, og det har også sin klare berettigelse, men når alt kommer til alt, og noget fælles skal merges sammen, så ender det altid med en låsning.

Det er kun et spørgsmål om hvorlangt man kan trække den og vente med at lave låsningen.

De to ovenstående løsninger har hver sine fordele og udlemper.

Normale "block all" låsninger er forholdsvis nemme, hvor lette låsninger (MREW og andre varianter) er langt mere komplekse at kode. Omvendt er memory allokeringsbehovet ikke stort.

Som duplikerings metoden temmelig kraftigt antyder, stilles der krav til brug af mere hukommelse, og det er i praksis egentlig bare en mere fintmasket løsning end den hvor hver tråd simpelthen bare præallokerer al den hukommelse de nogensinde måtte have brug for, og derfor "aldrig" kommer i slagsmål med andre tråde vedr. data. Det er faktisk metoden som GPU'er benytter sig af og een af årsagerne til at de er rasende hurtige til specifikke ting.

I virkeligheden, hvor RAM stadig findes i afmålte mængder, vil en god software udvikler vælge at kombinere metoderne i forhold til opgaven. Og opgaven afhænger af domænet, så der skal altså domæne forståelse til.

Og denne forståelse findes ikke i et programmeringssprog uanset valg.

  • 1
  • 1
#15 Michael Cederberg

Problemet er, efter min mening, ikke flertråede applikationer som bruger hver sit sæt af data.

Enig. Der er der heller ikke nogen der har skrevet.

Der kan være implementerings ting der gør at separate processer måske ville performe bedre, f.eks. hvis man har en elendig memory manager som bottleneck, og applikationen ikke selv præallokerer nok hukommelse for at undgå gentagne allokationer/deallokationer.

Separate processer er et andet problem. Det snakker vi om en anden dag.

Og ja, man kan preallokere memory. Men så har vi pludselig en programmeringsmodel der sætter begrænsninger på hvilke libraries man kan bruge og i det hele tages en anderledes programmeringsmodel end den sproget umiddelbart lægger op til (e.g. man skal til at bruge placement new).

Men med mindre man har signifikant mere memory end man har brug for, så vil en generaliseret memory manager skulle bruge en del tid på at håndtere memory (balancere mellem tråde, defragmentere, etc.). Nogle af disse ting sker under lås.

I øvrigt er de fleste "lock-free-algoritmer" i praksis ikke låsefrie. For CPU'en er nødt til at lave en form for lås for at implementere compare-and-swap lignende operationer. Disse operationer er dyre (200-300 gange langsommere end almindelige operationer) når samme lokation tilgås fra forskellige tråde.

Men som udgangspunkt er der ikke et problem, sålænge alle trådene er enige om ikke at have noget med hinanden at gøre.

Hvis tråde er helt uafhængige så er der intet problem. Så kunne de køre i separate processer, evt. på forskellige maskiner. Men det er sjældent sådan programmer ser ud.

Og der har diverse memory allokerings mekanismer ikke nogen som helst relevans.

Jo, for hvis der er en mulighed for at to forskellige tråde hverisær kan være den sidste til at "frigive" et stykke memory, så skal der være en synkroniseringsmekanisme omkring objektet. Denne er som jeg tidligere har skrevet dyr.

Og denne forståelse findes ikke i et programmeringssprog uanset valg.

Der er mange dicipliner i parallel programmering og forskellige sprog hjælper brugeren på forskellige måder.

Men diskussionen her handler om Rust og Verona (vs. C og C++). Når memory management kommer ind i billedet så er det fordi der er behov for at finde ud af hvornår memory skal frigives (bortset fra i en GC verden).

Eksempel: C++ fik referencer (i forhold til C) selvom de funktionelt svarer til en const pointer. Det fik C++ for at fortælle at ejerskab til et objekt (og dermed styring af lifetime) ikke overgives sammen med referencen. I en ref-countet verden betyder det at ref-count ikke skal ændres.

Ref-count er som tidligere beskrevet dyrt i en multithreaded verden og derfor bliver det specielt vigtigt at overføre smart-pointers by reference når det er muligt. C++ kunne have undgået referencer og overladt til brugeren at håndtere ejerskab.

I C++ og Rust ejer man et enkelt objekt ad gangen. Det betyder lifetime styring for hvert enkelt object. I Verona ejer man en gruppe af objekter og der er en overordnet lifetime for hele gruppen (jeg har ikke set så mange detaljer) og management af lifetime er således på gruppe niveau.

Når det stadigvæk er interessant at snakke memory model, så er det fordi en GC verden slet ikke har problemer med styring af ownership ifbm. deallokering.

  • 2
  • 0
#16 Kim Madsen

Enig. Der er der heller ikke nogen der har skrevet.

well... det har du jo... ved at referere til allokeringer på stakken og ikke i heap. Hvis alt memory til en tråd kan allokeres på stakken, så er der ikke overlap mellem forskellige trådes hukommelse, og derfor ikke noget problem. Tilsvarende hvis alt allokeres i hver sin pænt separarede del af heap, så er der heller ikke et problem.

I øvrigt er de fleste "lock-free-algoritmer" i praksis ikke låsefrie. For CPU'en er nødt til at lave en form for lås for at implementere compare-and-swap lignende operationer.

Jep.

I C++ og Rust ejer man et enkelt objekt ad gangen. Det betyder lifetime styring for hvert enkelt object. I Verona ejer man en gruppe af objekter...

Men det ændrer stadig ikke en tøddel ved min kommentar.... at memory manager metodikken kun er eet lille (men dog vigtigt) element i at kunne kode trådsikkert.

De største problemer i multitrådet programmering har sjældent direkte noget med allokering/deallokering at gøre da det oftest sker forholdsvist veldefinerede steder (der er masser af undtagelser), men snarere delingen af brugen af allokerede objekter mellem flere tråde, hvor man nødvendigvis ender op med at skulle vælge mellem een af de 2(3) metoder til sikring af objektet/hukommelsens stabilitet.

Det er derfor jeg anfægter oplistningen af diverse memory manager teknikker (som i sig selv selvf. er interessant viden), i sammenhæng med nyheden om et sprog som skulle have teknikker til at kunne løse det at lave trådsikret programmering. Og desuden anfægter jeg også denne påstand... altså at sproget egentlig giver løsninger.

Jeg ser det mere i dette tilfælde, at sproget leverer syntaktisk sukker, som stadig ikke er en magisk løsning... ensige en løsning.

Der findes sprog som har leveret løsninger, men de har alle leveret dem med forskellige forudsætninger... F,eks Erlang (og for den skyld i mere moderne termer Node.js) hvor alt kører i een tråd og der derfor aldrig vil blive tråd konflikter, men hvor man så skal benytte andre teknikker hvis man ønsker en slags multitasking i den ene tråd.

Og der er GPU orienterede sprog, hvor man heller ikke har tråd udfordringer fordi hver "tråd"... (core i GPUen) får tildelt sit helt eget hukommelses område, som så er dyrt i hukommelse, men lader coren køre ved fuld speed.

Jeg siger ikke at man ikke må hjælpe udviklerne i at lave god kode, men det er forkert at forsøge at "sælge" et nyt sprog som en løsning på noget som det i praksis ikke løser.

Vi skal STADIG have domæne kendskab, og desuden være gode programmører for at slippe afsted med bare halv komplicerede ting i flertrådet kode, og vi slipper ikke for at skulle tage stilling til duplikering eller låsning i de relevante sammenhænge med mindre vi er ligeglade med RAM forbrug eller performance.

  • 1
  • 1
#17 Kim Madsen

I øvrigt er de fleste "lock-free-algoritmer" i praksis ikke låsefrie. For CPU'en er nødt til at lave en form for lås for at implementere compare-and-swap lignende operationer.

Jep.

Jeg bør måske (for folk som måske ikke kender meget til lockfree algoritmer), at det er helt korrekt, at en lockfree metode ikke findes. Der vil være låsninger i spil, som Michael korrekt fortæller.

Men historien er lidt længere end som sådan, fordi de bedste såkaldte lockfree algoritmer forsøger, f.eks. via hashing metoder, at sprede indekseringen ind i lister/arrays over hele listens/arrayets hukommelses areal, for at nedbringe antallet af situationer hvor to tråde rammer præcist samme hukommelses celle, og en reel låsning træder i kraft.

I traditionelle trådsikrede arrays, vil der ofte være kodet een låsemekanisme for hele array'et, hvilke netop laver en flaskehals hvis arrayet tilgås ofte fra mange tråde.

I den distribuerede låsnings mekanisme, som hashing indekserings metoden udnytter, vil hver enkelt celle i array'et reelt fungere som sin egen lås, hvorfor mange tråde sagtens kan arbejde uden reelle låsninger samtidig på arrayet, med mindre de lige netop rammer den samme celle samtidigt.

Det er absolut langhåret arbejde at kode stabile hurtige multi tråede algoritmer. Jeg har selv spenderet mange timer på mine lockfree arrays og dynamisk sizable lockfree arrays for at de kører stabilt og effektivt. De kan så udnyttes af andre udviklere så de ikke også skal opfinde den dybe tallerken, men det vil stadig ikke løse opgaven med at sikre samtidigheden på større mængder data som jo er den reelle opgave.

  • 1
  • 1
#18 Sune Marcher

I traditionelle trådsikrede arrays, vil der ofte være kodet een låsemekanisme for hele array'et, hvilke netop laver en flaskehals hvis arrayet tilgås ofte fra mange tråde.

Plus de "traditionelle" metoder ofte bruger super tunge os/kernel-level synkroniseringsprimitiver... og godt nok er en CMPXCHG instruktion meget tungere end et simpelt move, men det er stadig oceaner hurtigere end kernel/user context switching osv. (Og ja, der findes critical sections, futexes osv... men en udvikler der ikke kender til lock-free algoritmer har måske heller ikke det store kendskab til forskellen på en critical section og en full-blown mutex).

  • 1
  • 0
#19 Michael Cederberg

Men det ændrer stadig ikke en tøddel ved min kommentar.... at memory manager metodikken kun er eet lille (men dog vigtigt) element i at kunne kode trådsikkert.

Men pointen er at memory management er en af de få ting som en udvikler ikke rigtigt kan ændrer på. For selv hvis han kan kode sin egen så mister han ofte muligheden for at bruge standard libraries. Og memory management er ofte et chokepoint for massivt parallelle programmer.

Jeg ser det mere i dette tilfælde, at sproget leverer syntaktisk sukker, som stadig ikke er en magisk løsning... ensige en løsning.

Det er jeg ganske uenig i. Som tidligere beskrevet så er referencer det samme som const pointers ... blot med anden sematik omkring ejerskab. Det hjælper udvikleren. Rust har fjernet null-pointers. Verona introducerer regioner. Det bliver alt sammen til maskinkode, men disse ting hjælper udvikleren til at lave færre fejl.

Der findes sprog som har leveret løsninger, men de har alle leveret dem med forskellige forudsætninger... F,eks Erlang

Og som jeg ser det tager Microsoft inspiration fra Erlang og putter ind i Rust i verona projektet.

Men historien er lidt længere end som sådan, fordi de bedste såkaldte lockfree algoritmer forsøger, f.eks. via hashing metoder, at sprede indekseringen ind i lister/arrays over hele listens/arrayets hukommelses areal, for at nedbringe antallet af situationer hvor to tråde rammer præcist samme hukommelses celle, og en reel låsning træder i kraft.

. . .

I traditionelle trådsikrede arrays, vil der ofte være kodet een låsemekanisme for hele array'et, hvilke netop laver en flaskehals hvis arrayet tilgås ofte fra mange tråde.

Det har intet at gøre med lock-free. Men nogen gange har folk troet at de blot kan tage en eksisterende implementation og så smide en lås udenom og så forvente at de nu har en fornuftig løsning.

Et godt eksempel på en stupid implementation er Java's synchronized collections. De er tæt ved ubrugelige fordi interfacet til en collection der tillader multithreaded adgang naturligt vil være anderledes end for en der ikke gør. Af samme grund har de lock-free implementation af collections altid et anderledes interface, men det har ganske lidt at gøre med at de er lock-free og rigtigt meget at gøre med at de tillader multithreaded adgang.

Som kuriosum kan nævnes at nogle lock-free algoritmer på x64 (det er længe siden jeg har rørt andre platforme) ofte vil have dårligere performance end en traditionel lås, såfremt man tilgår algoritment to gange lige efter hinanden i en situation hvor mange tråde tilgår algoritmen på samme tid (i så fald putter man en traditionel lås udenom de to tilgange sådan at låsen kun tages en gang).

Plus de "traditionelle" metoder ofte bruger super tunge os/kernel-level synkroniseringsprimitiver... og godt nok er en CMPXCHG instruktion meget tungere end et simpelt move, men det er stadig oceaner hurtigere end kernel/user context switching osv.

Jeg tror ikke rigtigt der er nogen der i dag skriver kode direkte mod OS primitiverne hvor performance er vigtigt (hvis en mutex tages 10 gange i sekundet så er det ligegyldigt om den er implementeret med OS primitiver). Hvis man skal have ordentlig performance ud af multithreaded kode så er det essentielt at man ikke holder låse længe og i så fald er spinlocks næsten altid den rigtige løsning (evt. med fallback til OS primitiver).

  • 0
  • 0
#20 Sune Marcher

Af samme grund har de lock-free implementation af collections altid et anderledes interface, men det har ganske lidt at gøre med at de er lock-free og rigtigt meget at gøre med at de tillader multithreaded adgang.

Det lyder lidt vrøvlet. Altså, visse operationer kan kræver et anderledes interface hvis de skal gøres effektivt, men ting som put og get kan da laves med fuldstændigt samme interface for collections som sets og maps?

Hvis du tillader multithreaded adgang uden lockfree algoritmer vil du typisk være nødt til at have noget locking, ja, og så bliver interfacet noget anderledes.

(hvis en mutex tages 10 gange i sekundet så er det ligegyldigt om den er implementeret med OS primitiver).

Arh, der er da noget forskel på om man kan nøjes med et par CPU instruktioner og noget inter-CPU cache synkonisering, eller om man skal hele vejen igennem user/kernel switch, privilegie checks, måske TLB flushing og hvad der ellers hører med...

Hvi man skal have ordentlig performance ud af multithreaded kode så er det essentielt at man ikke holder låse længe og i så fald er spinlocks næsten altid den rigtige løsning (evt. med fallback til OS primitiver).

Spinlock + kernel fallback (hej, Win32 CRITICAL_SECTION) er OK til at beskytte en lidt større kodeblock, omend jeg ville prøve at designe systemer task/message-orienteret så meget som muligt, i stedet for at deale med explicit locking. Og til manipulation af collections ville jeg langt hellere benytte lockfree algoritmer end spinlocking, hvor muligt.

  • 0
  • 0
#21 Michael Cederberg

Det lyder lidt vrøvlet. Altså, visse operationer kan kræver et anderledes interface hvis de skal gøres effektivt, men ting som put og get kan da laves med fuldstændigt samme interface for collections som sets og maps?

Jo, men det er meget sjældent man blot har brug for put og get. Funktioner som containsXXX eller isEmpty kan sjældent bruges til noget fordi resultatet kan have ændret sig siden.

Eksempel:

   if (!collection.contains(xxx))  
     collation.put(xxx,yyy);

Ovenstående giver meget lidt mening for en synchronized collection der tilgås af flere tråde. I java tilføjede Oracle derfor funktioner som putIfAbsent til Map interfacet, men de gjorde det først i version 1.8. Jeg synes at huske at synchronized map dukkede op i 1.2 og det har i praksis været ubrugeligt indtil 1.8.

Hvis du tillader multithreaded adgang uden lockfree algoritmer vil du typisk være nødt til at have noget locking, ja, og så bliver interfacet noget anderledes.

Min pointe er at selv lock-free algoritmer indeholder låse der koster ligeså meget som en traditionel spin-lock. Og at det vigtige er at få den korrekte lock-granularitet fordi lock-aquisition der bouncer frem og tilbage mellem tråde er meget dyrere end at holde låsen dobbelt så længe.

Arh, der er da noget forskel på om man kan nøjes med et par CPU instruktioner og noget inter-CPU cache synkonisering, eller om man skal hele vejen igennem user/kernel switch, privilegie checks, måske TLB flushing og hvad der ellers hører med...

Som jeg skrev: Hvis du har en lock-aquisition frekvens på 10Hz så er det fuldstændigt ligegyldigt om det er et OS primitiv eller in-process. Omkostningerne kan ikke ses i praksis - de drukner i de milliarder af cycles du har tilrådighed. Hvis frekvensen er 10MHz er det selvfølgeligt en helt anden sag, men i 10Hz tilfældet er det vigtigere at ende med kode der kan testes nemt og fungerer korrekt end at eliminere OS kald.

Spinlock + kernel fallback (hej, Win32 CRITICAL_SECTION) er OK til at beskytte en lidt større kodeblock, omend jeg ville prøve at designe systemer task/message-orienteret så meget som muligt, i stedet for at deale med explicit locking. Og til manipulation af collections ville jeg langt hellere benytte lockfree algoritmer end spinlocking, hvor muligt.

Men når du putter data på din lock-free kø, så er der en CAS operation. Den koster ca. det samme som en spin-lock som også indeholder en CAS operation. Derfor: så snart man har to kald til en lock-free algoritme lige efter hinanden så skal man overveje om man i stedet skulle skifte til en lås udenom det hele.

Som jeg skrev tidligere så er den vigtigste opgave at lade være med at holde låse i lang tid. Hvis man først begynder at holde låse i mere end ca. 1000 cycles (+/- en størrelsesorden), så laver man noget galt og så kan man ligeså godt stoppe. Hvis altså man er ude på at få max throughput på systemet (og hvis man ikke er så skal man lade være med at tænke performance i disse baner). Der er selvfølgeligt andre scenarier hvor låsning i længere tid giver mening.

  • 0
  • 0
Log ind eller Opret konto for at kommentere