Torben Mogensen header

Swift: Apples nye programmeringssprog

Sammen med den nye version af MacOS X "Yosemite" og IOS8 har Apple også lanceret et nyt programmeringssprog Swift, der betragtes om en efterfølger til Objective C som hovedsproget til at skrive applikationer til både MacOS og IOS.

Jeg har set på beskrivelsen af sproget, og synes egentlig, at det ser fornuftigt ud. Der er f.eks. lånt mange elementer fra funktionsprogrammeringssprog: Anonyme funktioner (closures), tupler, sum-typer med parametre og pattern-matching (enumerates), option-typer, delvis typeinferens og polymorfi (generics).

Ligesom C# har Swift både structs og klasser, og igen ligesom i C# er structs værdityper, mens klasser er referencetyper. Det betyder, at der ikke er behov for spildopsamling (garbage collection) til structs, da de kopieres ved paramereroverførsel og -retur, så man kan nedlægge lokale kopier, når en funktion forlades. Klasser har til gengæld behov for spildopsamling, og her har Apple truffet det lidt usædvanlige valg at bruge reference counting, som dels ikke er specielt effektiv og dels ikke kan håndtere cykliske strukturer. Det sidste kan dog håndteres med weak references, men det lægger en byrde over på programmøren. Man bør derfor nok undgå cykliske strukturer, med mindre det er strengt nødvendigt. Reference counting er dog lidt nemmere at distribuere over flere CPUer med lokalt lager end tracing collectors såsom mark-sweep og copying collection.

Noget andet Swift har lånt fra funktionssprog er let-erklæringer. En let-erklæring definerer en variabel, der ikke kan gives en ny værdi senere, altså en immutable variabel.

Swift har også protocols, som svarer til interfaces i Java og C#, signaturer i SML og til typeklasser i Haskell. De bruges blandt andet til at pålægge type constraints til typeparametre, sådan at man kan specificere, at en instans af en typeparameter skal overholde en protokol. Man kan endvidere pålægge ækvivalenskrav til elementer af to forskellige typeparametre. Hvis for eksempel den ene typeparameter overholder en protokol, hvori der indgår en elementtype og den anden typeparameter overholder en protokol, der definerer en nøgletype, kan man erklære at elementtypen og nøgletypen skal være den samme, uden at specificere præcis, hvilken type dette er. Det svarer til sharing constraints i Standard MLs signaturer. I protokoller kan funktioner på værdityper såsom structs per default ikke ændre i denne værdi, men man kan eksplicit erklære funktionen mutable, så den kan.

Alt i alt ser sproget fornuftigt ud, selv om jeg stadig savner f.eks. den mere komplette typeinferens, man får i funktionelle sprog som for eksempel ML, Haskell og F#. Og Swift er endnu et eksempel på, at de ideer, der blev introduceret med funktionssprog som ML, breder sig ud i andre programmeringssprog. Eller som en (jeg husker ikke hvem) engang sagde: "Over time, any language will evolve to look more and more like ML".

Kommentarer (62)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Morten Andersen

Hej Torben

Tak for gennemgangen. På hvilke måder er typeinferensen i ML mere komplet end i f.eks. Swift? Kan man give nogle eksempler på inferens som ML kan lave som Swift ikke kan lave? Og ville en sådan udvidelse kunne laves uden at det koster på performance (på runtime) eller vil fuld inferens altid have en omkostning?

  • 1
  • 0
Uffe Seerup

Et array er en value type. Men elementerne er delt med andre som har fået tildelt det samme array - dvs at når man ændrer en array position så ændrer det sig for alle. Undtagen når ændringen til array'et påvirker størrelsen af array'et. Så bliver der taget en kopi og positionerne er ikke længere delt (copy-on-write).

  • 1
  • 0
Torben Mogensen Blogger

Kan man give nogle eksempler på inferens som ML kan lave som Swift ikke kan lave?

I Swift skal du angive typerne på parametrene til en funktion, inklusive evt. typeparametre til generiske typer. Det behøver du ikke i ML, så i ML kan du skrive en funktion til at sammensætte generiske/polymorfe lister blot som

fun append [] ys = ys  
  | append (x::xs) ys = x :: append xs ys
  • 3
  • 0
Daniel Fairchild

Torben, har du set nogen tegn i specifikationen på at man kan overdrage heap referencer sikkert mellem processer, på samme måde som man kan i microsofts Sing# ( http://en.wikipedia.org/wiki/Spec_Sharp#Sing_Sharp ) , som de brugte til deres eksperimentele Singularity operativsystem ?

Den slags sikre zero-copy overførsler mellem processer kunne jeg godt tænke mig at se understøttelse for i flere programmeringssprog, mhp at optimere performance.

Det er selvfølgelig mindre vigtigt, hvis sproget kun skal bruges til énkelt-applikationer med ét enkelt adresserum.

  • 0
  • 0
Daniel Fairchild

Blev helt forvirret da du skrev "Google Rust", jeg er helt sikker på at du mente "Mozilla Rust".

http://en.wikipedia.org/wiki/Rust_(programming_language)

Mit problem med Rust er at det ikke har Apple's muskler til at få det løbet i gang, som vi så Microsoft gøre det med C#, da min oplevelse med programmeringssprog er at de aldrig er bedre end summen af de kræfter der skubber bag på dem, mht. værktøjer, compilere og lignende.

Du fremhæver f.eks. selv ML som en god ting, og ideerne bag er sikkert sunde, men min oplevelse er at det lider under at være et niché sprog af primært akademisk interesse, som derfor ikke får tilstrækkelig opmærksomhed til at blive rigtig finpudset til en grad hvor en af dets mange implementationer kan blive det bedste valg til at løse en given opgave.

Tænk bare på de mange ressourcer IBM har brugt på at forbedre Java, både ved at skabe Eclipse og ved hårdt arbejde med at tune den underliggende virtuelle maskine. Hvis de nu ikke havde gjort det, kunne jeg sagtens forestille mig at vi i dag kunne have været lykkeligt fri for det lort, og at C# var kommet til at se meget anderledes ud ;)

  • 1
  • 0
Morten Andersen

Torben, OK men jeg synes ikke dit eksempel antyder en grundlæggende forskel i typeinferens... er det ikke bare et spørgsmål om at netop lister er en "first class citizen" som ML har indbygget syntax for? Dog kan jeg godt se at "pattern matching" delen i eksemplet er unik for ML ift. Swift, men det er vel ikke som sådan relateret til typeinferens? Swift har vel også typeinferens for de indbyggede typer, number, string literals osv., og hvis lister havde været indbygget muligvis også lister?

  • 0
  • 0
Troels Henriksen

Torben, OK men jeg synes ikke dit eksempel antyder en grundlæggende forskel i typeinferens... er det ikke bare et spørgsmål om at netop lister er en "first class citizen" som ML har indbygget syntax for? Dog kan jeg godt se at "pattern matching" delen i eksemplet er unik for ML ift. Swift, men det er vel ikke som sådan relateret til typeinferens? Swift har vel også typeinferens for de indbyggede typer, number, string literals osv., og hvis lister havde været indbygget muligvis også lister?

Det har ikke noget at gøre med at SML har en smule syntaktisk sukker for lister. Så vidt jeg kan se, så er den fundamentale forskel at SML laver typeinferens på tværs af et helt modul - f.eks. to gensidigt rekursive funktioner - hvor Swifts inferens er intra-procedural.

Jeg synes dog Torben ignorerer Swifts i mine øjne største fordel: At værdier ikke kan være "null" med mindre de eksplicit er angivet som værende af en option-lignende type. Det betyder at man undgår de mange null-reference-fejl sprog som C# og Java plages af.

... Når det så er sagt, så er stadigvæk Swift ikke særligt imponerende i forhold til forskningssprogene.

  • 4
  • 0
Troels Henriksen

@Troels: Hvad mener du med "forskningssprogene"? Er det de gamle travere SML og Haskell, eller har du noget andet nyt og spændende i tankerne?

SML og Haskell er faktisk ret gamle designs, men de er stadigvæk mere avancerede end de fleste industrisprog. Man kan kigge på de mere eksotiske udvidelser Haskell (f.eks. GADTer), eller sprog der har indbyggede bevissystemer, som f.eks. Agda eller Epigram. Især sidstnævnte er interessante, idet man sideløbende med programmet udvikler et bevis for visse korrekthedsegenskaber - det er en utroligt pragmatisk teknik der er langt nemmere at arbejde med end de fleste andre formelle verifikationssystemer. Særligt interessant er det også, at sådanne teknikker ikke har nogen omkostning ved køretid.

  • 4
  • 0
Baldur Norddahl

Det er givetvis ligesom med Scala: Der er lokal typeinferens men ikke global typeinferens. Programmøren er nødt til at hjælpe lidt til ved at angive typer visse steder, f.eks. i funktionsargumenter.

Jeg er ikke inde i teorien bagved, men har læst at det er en teoretisk udfordring at lave global typeinferens i et objektorienteret sprog.

  • 0
  • 0
Mogens Hansen

... og her har Apple truffet det lidt usædvanlige valg at bruge reference counting, som dels ikke er specielt effektiv ...

Såvel Microsoft (med WinRT - oktober 2012) som Apple (Garbage colection deprecated i OS X 10.8 - juli 2012) er skiftet til reference counting.
Det er mit indtryk at performance (ikke mindst på mobile enheder) såvel i termer af hukommelsesforbrug og CPU (og dermed batteri) er årsagen til skiftet.

Det ville have undret mig hvis Apple ikke havde baseret Swift på ARC, så kort tid efter de har frarådet brugen af garbage collector.

På hvilken måde mener du at reference counting ikke er specielt effektivt (i forhold til garbage collector) ?

  • 1
  • 0
Troels Henriksen

På hvilken måde mener du at reference counting ikke er specielt effektivt (i forhold til garbage collector) ?

Det kræver at man forøger referencetælleren hver gang man overgiver/opgiver en reference til objektet. Det kan være ganske ineffektivt, hvis det medfører cache misses. Til gengæld er ydelsen mere forudsigelig end for en traditionel spildopsamler, idét man ikke har langvarige pauser.

Det er endnu værre i en flertrådet situation, hvor ændringer til referencetælleren skal være atomisk.

  • 2
  • 0
Baldur Norddahl

Til gengæld er ydelsen mere forudsigelig end for en traditionel spildopsamler, idét man ikke har langvarige pauser.

Men ikke helt så forudsigelig som mange tror. Traditionel hukommelseshåndtering har problemer med hukommelsesfragmentering, som kan medføre at programmet bruger meget mere hukommelse end forventet. En "copying garbage collector" har som sideeffekt at den defragmenterer hukommelsen. Det er iøvrigt også cache venligt.

Både "malloc" og "free" er relativ komplekse og dermed dyre operationer. Igen har en "copying garbage collector" en allokering der typisk består af 2-3 maskinkodeinstruktioner og ingen "free" operation.

Man kan også få forudsigelig ydelse, med små eller ingen pauser, hvis man vælger en garbage collector med disse egenskaber.

Med det i tankerne, så finder jeg denne bevægelse væk fra GC og over til ARC lidt besynderlig. Hvorfor ikke i stedet bruge lidt kræfter på at implementere en bedre GC?

  • 2
  • 1
Steffen Postas

Jeg må indrømme jeg stadig står lidt i en tåge af forvirring når det angår alle de nyudkomne programmeringssprog inden for de sidste 5 års tid. Ganske vidst har der været nogle få af de manger der kan udnyttes rent praktisk, og som også har brugbarhed på tværs af platforme (her mener jeg eksempelvis Dart som kan bruges som client side web scripting, såvel som backend), men indtil videre er det ekstremt få der har kunne snakke mit sprog: Ydelse.

Langt de fleste af de nye sprog der er udkommet og efterhånden også færdige eller færdigspecificerede, er i deres design opbygget på en sådan måde at man ikke kan hive en særlig god ydelse ud af dem, desværre.
Rust har klaret sig okay, Dart er også ved at være der (men er der ikke endnu), men Go er nok det eneste jeg med min egen gode vilje ville kunne beskrive som et sprog der er nået til et punkt hvor det kan bruges i produktion, uden at man flår hår ud i ventetiden.

Selvfølgelig skal det være sprog hvor man kan udtrykke sig i på fleksible metoder, og der er også gode grunde til at sprog med metaprogrammering har vundet sig popularitet de sidste 50 år.
Men udover dette, virker der til at være en mængde af sprog der bræger sig frem med features der skulle være fantastiske, men som i realiteten ender med at dræbe ydelsen både pga. dårlige implementering, og/eller grundet at designet i sit konceptuelle basis simpelthen ikke er noget der kan lade sig gøre på en effektiv nok måde til at det kan retfærdiggøres.

Jeg synes ærlig talt det er en anelse trist.

Disclaimer: Jeg er C systemprogrammør.

  • 0
  • 0
Baldur Norddahl

Go er nok det eneste jeg med min egen gode vilje ville kunne beskrive som et sprog der er nået til et punkt hvor det kan bruges i produktion, uden at man flår hår ud i ventetiden.

Måske du skulle tjekke den påstand op imod benchmarks, f.eks. Computer Language Benchmarks Game: http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang...

Hint: Scala er hurtigere end Go til de fleste ting.

Haskell er ligeledes hurtigere end Go: http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang...

Der er ikke nogen af dem der slår C, men det er også et sprog hvor man ikke viger tilbage for at lave maskinkode når det er nødvendigt for at "vinde". De hurtige sprog er generelt halvt så hurtige som C, hvilket er fint til rigtig mange formål. Ofte er korrekthed vigtgere end at vride den sidste hertz ud af maskinen.

  • 6
  • 0
Sune Marcher

Med det i tankerne, så finder jeg denne bevægelse væk fra GC og over til ARC lidt besynderlig. Hvorfor ikke i stedet bruge lidt kræfter på at implementere en bedre GC?


Jeg studsede også noget over at man har valgt at skifte fra GC til RC (har dog kun læst headline, så ved ikke om der er nogle snedige grunde). Men hvis man primært targeter platforme med få kerner, optimeret atomic inc/dec, og uden dyr bus-kommunikation og cache-sync, så kan RC gøres ret effektiv... om det er en god ide at bygge et sprog op om den slags hardware-antagelser vil jeg lade andre om at kommentere på.

Underligt at din kommentar har fået downvote, hukommelsesfragmentering er et ret stort issue i pointer-baserede sprog. Man kan selvfølgeligt godt undlade at have pointere selvom man bruger RC, men hvis man skal lave heap compaction, så får free-operationen ikke-deterministisk performance.

Der er dog en bestemt ting, der gør at jeg hælder lidt mere til RC end GC: deterministiske destructors. Memory leaks er trælse, men resource leaks (window handles, sockets, database connections, ...) er typisk meget værre end at glemme at free'e et par memory allocations hist og her - og jeg har endnu ikke set et GC-sprog der hjælper mod resource leaks.

En kombination af GC og RC (eller whatever anden mekanisme man kunne bruge for at sikre deterministisk destruction) kunne være interessant, men det lader til at være svært at lave. Rust er muligvis et godt bud, men har ikke fået kigget nærmere på det.

(Jeg voksede op med Pascal, C/C++ og x86 assembly, så jeg kan ikke lade være med at tænke på performance, når jeg hører om et nyt sprog... selvom performance er tæt på irrelevant til langt de fleste programmeringsopgaver efterhånden.)

  • 0
  • 0
Troels Henriksen

Haskell er ligeledes hurtigere end Go:

Det hører dog til historien af denne Haskell-kode er umådeligt vederstyggelig - mange af programmerne er reelt bare C med Haskell-syntaks.

Jeg giver Steffen Postas ret i at ydelse ikke er et parameter disse moderne sprog konkurrerer så meget på, og det synes jeg også er lidt synd. Men oversætteroptimeringer er så også mit felt, så jeg er nok miljøskadet...

  • 0
  • 0
Jens Jakob Jensen

Ang. effektivitet af RC i forhold til GC i Swift, så bemærk at LLVM kun foretager nødvendige opdateringer af referencetælleren (efter bedste evne); resten bliver optimeret væk. Så det forekommer mig at sammenligning af performance mellem (optimal) RC og (optimal) GC ikke er så simpelt endda.

Personligt er jeg stor tilhænger af ARC; også i betragtning af ulemperne ved GC.

  • 2
  • 0
Mogens Hansen

Det kræver at man forøger referencetælleren hver gang man overgiver/opgiver en reference til objektet. Det kan være ganske ineffektivt, hvis det medfører cache misses.

Ja - men det er værd at bemærke at det netop er når man overgiver/opgiver en reference.
Det er f.eks. ikke nødvendigt blot fordi man overfører en reference til en funktion - reference countet vil være "ejet" nederst på kaldestakken.
Det vil sige at det ikke er nødvendigt at ændre reference count så hyppigt som man måske umiddelbart skulle tro.
Det er Jens Jakob Jensen også inde på, med LLVM optimerer overflødige opdateringer væk.

Det er endnu værre i en flertrådet situation, hvor ændringer til referencetælleren skal være atomisk.

At tælle et heltal op og ned atomisk er effektivt understøttet på mange moderne CPU arkitekturer.

  • 1
  • 0
Torben Mogensen Blogger

Memory leaks er trælse, men resource leaks (window handles, sockets, database connections, ...) er typisk meget værre end at glemme at free'e et par memory allocations hist og her - og jeg har endnu ikke set et GC-sprog der hjælper mod resource leaks.

Her tænker du nok på destructors/deinitialisers, som kan aktiveres, når reference count når 0. Det kan sagtens fungere sammen med tracing collectors som f.eks. mark-sweep. I mark-sweep kan destructors f.eks. aktiveres i sweep-fasen. De aktiveres dermed ikke helt så hurtigt som ved RC, hvor destructors udføres i samme øjeblik, som den sidste reference forsvinder. Men forsinkelsen er højest til næste GC. I copying collection er det lidt mere krævende, da man skal lave et sweep af from-space for at aktivere destructors.

Men uanset GC-metode så synes jeg at ressourcer såsom file handles, sockets, osv. bør håndteres med lineære typer (ligesom i Rust).

Hvad effektivitet angår, så er de ekstra omkostninger ved RC ikke voldsomme, hvis der sjældent er mere end en reference til et objekt, da det at sætte og slette reference count kun er en lille del af omkostningerne ved at allokere og frigøre objekter (specielt, hvis der bruges C-style malloc/free til dette, da den er ret dyr). Omkostningerne kommer, hvis referencer kopieres. Med tracing collection koster en kopiering af en reference kun en registerflytning, men i RC koster det fire lagertilgange (to læs og to skriv), to aritmetiske operationer (inc og dec) samt et svært forudsigeligt betinget hop (på om tælleren er 0). Selv om der er atomiske instruktioner til dette, forhindrer det ikke lagertilgangene, da operationerne ikke kan ske ude i lageret. Men hvis de fleste objekter kun har en reference (altså er lineære), så er en bedre ide at lave en statisk analyse, der genkender lineære objekter på compiletid og frigør eller genbruger dem med det samme (uden runtime check), når de bruges. Så kan GC klare alle ikke-lineære objekter med små omkostninger.

Det med, at reference counting undgår lange pauser er i øvrigt kun en halv sandhed: Hvis man for eksempel har en lang hægtet liste (eller træstruktur), hvor alle elementer kun har en reference, og man fjerner den sidste reference til hovedet af denne liste, så skal man gennemløbe hele listen for at tælle referencer ned og sætte elementerne på frilisten. Hvis denne liste er stor, kan det tage lang tid at gøre dette. Man kan mindske pauserne ved at fordele dette gennemløb over efterfølgende allokeringer, men så er forskellen fra en inkrementel tracing collector ikke stor.

Den primære fordel ved reference count er, at man ikke behøver at holde styr på et rodsæt (registre og stakelementer, der peger ind i hoben). Men det er der en enkel løsning på: Hoballoker alle aktiveringsposter (frames). Dermed er registrene (inklusive pegeren til den øverste aktiveringspost) de eneste rødder. Hoballokerede aktiveringsposter gør endvidere concurrency nemmere. Hvis man ikke har call with current continuation eller lignende kontroloperationer i sproget, er aktiveringsposter altid lineære, så selv om de allokeres på hoben, kan de sagtens frigøres med det samme ved funktionsretur.

  • 1
  • 0
Uffe Seerup

At tælle et heltal op og ned atomisk er effektivt understøttet på mange moderne CPU arkitekturer.

Ja - selve operationen er ofte direkte understøttet. Men hvis det er i et flertrådet miljø så skal der også være en "memory barrier" - værdien skal skrives/læses igennem lokale cachelagre for at blive synlig for andre tråde. Der skal altså involveres memory der er fælles mellem CPU'er/cores. Denne type memory er ofte maget langsommere end den lokale cache.

Skrivning (optælling og nedtælling) kan evt. ske asynkront - men skal dog stadig koordineres og serialiseres (CPU'en behøver ikke behøver at afvente operationen er gennemført før den går til næste instruktion).

Så vidt jeg kan se, vil det ved i hvert fald nedtællingen være nødvendigt tilsvarende at læse igennem cache - for at kunne undersøge om den sidste reference er sluppet.

Det forekommer mig, at det lige netop er denne type operationer der ellers er meget fokus på at fjerne i øjeblikket - fx ved at benytte ikke-muterende datastrukturer som ikke behøver at blive koordineret over langsomt arbejdslager - simpelthen fordi de ikke skal koordineres.

  • 2
  • 0
Frej Soya

Med det I tankerne, så finder jeg denne bevægelse væk fra GC og over til ARC lidt besynderlig. Hvorfor ikke i stedet bruge lidt kræfter på at implementere en bedre GC?

Mon ikke det er et fravalg pga. andre tilvalg. Jeg antager swift skal kunne bruge eksisterende obj-c biblioteker (nemt). Det er simplere hvis begge dele af programmet bruger samme spildopsamlingsmetode, både for den der skriver programmet og dem der ellers skulle have skrevet en ny GC og få en kald konvention til at fungere som ikke begrænser andre optimeringer.

Men det er ren spekulation.... men de har sparet en masse tid :)

  • 1
  • 0
Finn Schiermer Andersen

Jeg kan se to gode grunde til at foretrække RC over GC:
- soft-realtime krav (brugergrænseflade "smoothness"). Selv med inkrementel GC kan man blive ramt af en pause.
- max lager forbrug. Selvom GC almindeligvis virker godt, er der masser af scenarier, hvor GC fører til markant større lagerforbrug end RC.

  • 1
  • 0
Jakob Damkjær

er hukommelses ikke ubegrænset der virker det som om man ikke altid har den margin på 5x plads som der kræves for at GC er en fordel sammenlignet med ARC.

"In particular, when garbage collection has five times as much memory as required, its runtime performance matches or slightly exceeds that of explicit memory management. However, garbage collection’s performance degrades substantially when it must use smaller heaps. With three times as much memory, it runs 17% slower on average, and with twice as much memory, it runs 70% slower. Garbage collection also is more susceptible to paging when physical memory is scarce. In such conditions, all of the garbage collectors we examine here suffer order-of-magnitude performance penalties relative to explicit memory management."

http://sealedabstract.com/rants/why-mobile-web-apps-are-slow/

Sammenlignet med desktop og laptop er der i en batteribegrænset sammenhæng (og ikke bateribegrænset som laptop) ikke plads til voldsomt overkill for at få ting til at køre jævnt.

  • 2
  • 1
Torben Mogensen Blogger

Memory overhead for effektiv GC med tracing collectors mindskes drastisk med generationelle collectors. Den yngste generation skal ganske rigtigt helst have højest 20% levende objekter ved GC, men de ældre generationer kan sagtens have en langt højere fyldningsgrad. Dertil kommer, at sammenligningen er mellem eksplicit memory management, hvilket ikke er det samme som reference counting. Eksplicit management er malloc/free som i C. Reference counting bruger typisk malloc/free når objekter allokeres og frigøres, men der er et yderligere overhead til at vedligeholde reference counts. Dette er primært et performance overhead, men reference counts tager også plads, typisk et maskinord per objekt, hvor tracing collectors kan nøjes med et markeringsbit per objekt.

  • 0
  • 0
Baldur Norddahl

@Jakob Damkær

Prøv at læse nogle af kommentarerne. Analysen er for ensidig. Specielt overser han (og du) at ARC også har problemer (citat fra samme publication som du citerer):

"For example, on the gc-bench benchmark, the performance of the Boost “intrusive pointer” that embeds reference-counting within an existing class is up to twice as slow as the Boehm-Demers-Weiser collector".

Påstanden ser således hellere ikke ud til at holde vand med virkligheden. I artiklen henviser han til Computer Language Benchmarks Game, så lad os gå derhen og se hvor meget hukommelse C programmerne bruger i forhold til sprog med GC: http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang...

Her ser vi at Scala bruger cirka det samme hukommelse som C programmet i de fleste test. I den værste test bruger Scala 3 gange så meget. Men vi er slet ikke i nærheden af de påståede 5 gange ekstra hukommelse.

  • 2
  • 0
Jakob Damkjær

Jeg har læst kommentarene på artiklen og min pointe med at linke til den artikel var ikke at sige at ARC er en magisk løsning der løser alle ens problemer.

Men at selv hvis man benytter GC så virker det som om der er en performance omkostning der er svær at ignorere hvis man skal lave noget bare lidt avanceret hvis man læser de udtalelser fra udviklere der er med i artiklen... og når man tænker over de resourcer som Facebook har kunne kaste efter det problem som de havde med javascript facebook appen så virker det ikke som en problemstilling der kan løses nemt.

  • 3
  • 1
Baldur Norddahl

Handler det ikke om at GC performer daarligere naar der er mindre hukommelse til raadighed? (her angivet som under 5x minimum required mem). Ikke at C bruger mindre hukommelse.

Jo men hvis begge programmer bruger X og der er X hukommelse til rådighed, så er alt fint. Hvis der er mindre end X til rådighed, så er det muligt at GC kan finde noget hukommelse. Men C programmet crasher. Modsat GC, så har malloc ikke mulighed for at defragmentere hukommelsen for lige at finde noget ekstra.

Husk at det er performance test. Med et forbrug på X var GC programmet ikke langsomt. Der har altså været det fornødne overskud til at performe fornuftigt, uden at bruge mere hukommelse end et tilsvarende program skrevet i C. Hvor efterlader det argumentet med at man ikke kan bruge GC fordi det bruger for meget hukommelse?

  • 2
  • 0
Sune Marcher

Her tænker du nok på destructors/deinitialisers, som kan aktiveres, når reference count når 0. Det kan sagtens fungere sammen med tracing collectors som f.eks. mark-sweep. I mark-sweep kan destructors f.eks. aktiveres i sweep-fasen. De aktiveres dermed ikke helt så hurtigt som ved RC, hvor destructors udføres i samme øjeblik, som den sidste reference forsvinder. Men forsinkelsen er højest til næste GC. I copying collection er det lidt mere krævende, da man skal lave et sweep af from-space for at aktivere destructors.


Yep, destructors/deinitializers/finalizers - kært barn har mange navne.

Når vi snakker ikke-memory resources er "næste sweep" bare ikke godt nok - der er behov for deterministisk deallokering af disse ressourcer. Min erfaring med GC sprog er primært C# og Java/JVM-sprog, men på disse kan du (afhængig af VM-parametre og tilgængelige ressourcer) være ude for at finalizers først bliver kaldt meget senere end du gerne vil have, eller i værste fald aldrig bliver kaldt. Derfor kan de ikke anvendes som en pålidelig måde at frigive ressourcer.

Database connections og (specielt på Windows, pga. file hardlocks) file descriptors er meget dyre/problematiske ressourcer at holde fast på, og det virker så fjollet at skulle huske at kalde close/dispose/release/hallelujah metoder, når hukommelsen håndteres af GC :)

Men uanset GC-metode så synes jeg at ressourcer såsom file handles, sockets, osv. bør håndteres med lineære typer (ligesom i Rust).


Jeg gad godt jeg havde tid til at sætte mig ind i Rust, for de blog-indlæg jeg har set om det, har virket ret interessante - mit indtryk er, at der er taget nogle meget velovervejede beslutninger mht. hukommelses-håndtering, pointer-dereferencing sikkerhed, og multithread performance/safety i forbindelse med referencer.

Men hvis de fleste objekter kun har en reference (altså er lineære), så er en bedre ide at lave en statisk analyse, der genkender lineære objekter på compiletid og frigør eller genbruger dem med det samme (uden runtime check), når de bruges. Så kan GC klare alle ikke-lineære objekter med små omkostninger.


Dogmatisk set synes jeg det virker en smule farligt at basere hukommelsesmodel på den slags statisk analyse - men i den virkelige verden er det nok en ganske udmærket idé. Hvis du kan se at lifetime for et objekt aldrig overskrider den frame du er i (ikke bliver return'ed, ikke bliver sat som instansvariabel, ikke bliver assigned til global variabel), så ser jeg ikke umiddelbart nogen grund til at det behøver at være heap, men kan leve på stack... men det kræver nok et sprog hvor man ikke bruger (C/C++ style) pointers, eller har en virkeligt magisk optimizer :)

  • 0
  • 0
Sune Marcher

At tælle et heltal op og ned atomisk er effektivt understøttet på mange moderne CPU arkitekturer.


Én ting er at du har dedikerede CPU-instruktioner (som fx LOCK INC/DEC, XADD, CMPXCHGxx på x86), men som Uffe Seerup skriver er der andre omkostninger - på x86 involverer ovenstående instruktioner ret dyr bus lock og cache-sync - hvis der ikke er mulighed for at compileren kan optimere disse ud hvor de ikke er nødvendige, får du elendig performance, hvis den typiske anvendelse af sproget er at have en masse små short-lived objekter.

(Jeg har ikke erfaring med andre arkitekturer end x86, men jeg går ud fra at der er tilsvarende multi-core issues dér.)

  • 1
  • 0
Steffen Villadsen

Lækkert du vil gennemgå sproget og det lyder bestemt til at du er inde i det.

Efter at have læst har svært ved helt at placere sproget. ... ok det skal selvfølgelig bruge stil æble-platformene, men herudover mister jeg overblikket.

Vil du have mulighed for at fremhæve de fordele og ulemper du ser ?
Evt. en overbliks tabel, men sammenligninger af de andre sprog du henviser til?
Wikipedia er blevet bedre siden du skrev dit indlæg, men alligevel.

  • 0
  • 0
Torben Mogensen Blogger

Dogmatisk set synes jeg det virker en smule farligt at basere hukommelsesmodel på den slags statisk analyse - men i den virkelige verden er det nok en ganske udmærket idé. Hvis du kan se at lifetime for et objekt aldrig overskrider den frame du er i (ikke bliver return'ed, ikke bliver sat som instansvariabel, ikke bliver assigned til global variabel), så ser jeg ikke umiddelbart nogen grund til at det behøver at være heap, men kan leve på stack... men det kræver nok et sprog hvor man ikke bruger (C/C++ style) pointers, eller har en virkeligt magisk optimizer :)

Der er ganske rigtigt en vis fare ved statisk analyse: En forholdsvis lille ændring i programmet kan forvirre analysen så meget, at optimeringen ikke kan anvendes, selv om det objektivt set skulle kunne lade sig gøre. Det gælder dog alle former for automatisk optimering såsom inlining, løkkeudrulning, fælles deludtrykseliminering, osv. Hvis man vil være robust overfor den slags, skal man programmere i assembler eller i et sprog, hvor man selv angiver, hvor optimering ønskes og de egenskaber, der gør optimeringerne mulige, og får en advarsel, hvis oversætteren ikke kan verificere egenskaberne (så man ikke af vanvare kommer til at ødelægge en optimering ved opdatering af koden). Det kan for eksempel være lineære typer, der muliggør umiddelbar frigørelse af ressourcer efter sidste brug.

En mindre drastisk mulighed er at bruge statisk analyse, hvor det er muligt, og supplere med køretidsanalyse, hvor den statiske analyse ikke kan garantere noget. Det kan for eksempel være at kombinere lineære typer med GC (uanset om det er reference counting eller tracing collection). Der er for eksempel lavet en compiler for ML, hvor statisk analyse sørger for så meget af lageradministrationen, at mange programmer kører fint uden eksplicit GC, og langt de fleste programmer kan "masseres" til at gøre det (ved at bruge feedback fra den statiske analyse til at ændre lidt i programmet). Men for at få den sidste smule programmer med (og af hensyn til de programmører, der ikke vil massere programmerne af hensyn til den statiske analyse) er der tilføjet almindelig GC, som håndterer de tilfælde, som den statiske analyse ikke klarer.

Den statiske analyse (kaldet regionsinferens) er groft sagt en udvidet stakabilitetsanalyse, hvor man kan allokere et objekt ikke bare i den øverste stack frame, men i enhver tidligere frame.

  • 0
  • 0
Torben Mogensen Blogger

Hvis du kan se at lifetime for et objekt aldrig overskrider den frame du er i (ikke bliver return'ed, ikke bliver sat som instansvariabel, ikke bliver assigned til global variabel), så ser jeg ikke umiddelbart nogen grund til at det behøver at være heap, men kan leve på stack

Der findes analyser, der gør dette (og mere til, se herover). Men nogen gange kan stakallokering give senere frigivelse end GC: Den sidste reference til et objekt kan sagtens forsvinde, inden den funktion, der allokerede objektet, returnerer. Men selv om der er referencer til et objekt, kan det sagtens være spild i den forstand, at man aldrig følger referencerne til objektet. Det sker for eksempel ofte, at man har en reference til en struct eller object, hvor man senere kun tilgår nogle af felterne. Hvis de andre felter peger på store hoballokerede strukturer, vil disse blive ved med at være allokerede længe efter deres sidste brug. Statisk analyse (f.eks. linearitet eller regionsinferens) kan fange nogle af disse tilfælde, men ikke alle.

Groft sagt findes ingen ideel metode at lave automatisk lagerhåndtering. Men man skal ikke derfra konkludere, at manuel lagerhåndtering er bedre -- 99.9% af alle programmører er dårligere til lagerhåndtering end selv en simpel automatisk metode, og risikoen for at lave fejl ved manuel lagerhåndtering eksploderer, når en anden programmør end den oprindelige skal rette i et program.

  • 1
  • 1
Mogens Hansen

99.9% af alle programmører er dårligere til lagerhåndtering end selv en simpel automatisk metode, og risikoen for at lave fejl ved manuel lagerhåndtering eksploderer, når en anden programmør end den oprindelige skal rette i et program.

Det lyder som en helt urimeligt påstand. Har du noget dokumentation for det ?
Det svarer absolut ikke til hvad jeg gennem mange år har oplevet blandt mine kollegaer - og ja vi måler på om vi har problemer med resource håndtering (ikke blot lagerhåndtering).

Det lyder bekymrende hvis det er den slags unuanceret information studerende på DIKU bliver præsenteret for i forbindelse med undervisningen.

  • 0
  • 0
Torben Mogensen Blogger

Det lyder som en helt urimeligt påstand. Har du noget dokumentation for det ?

Nej, jeg tror ikke, at der er lavet nogen statistik over antallet af memorymanagementfejl, programmører laver. Jeg har set tal om, at ca. 10% af alle fejl i Windowsprogrammer skyldes heap corruption, som typisk betyder, at man følger pointere til deallokeret data. Men man kan også anskue det som følger:

Automatisk memory management undgår helt, at man følgere pointere til deallokeret data, og undgår memory leaks, hvor data, der ikke længere refereres til, ikke bliver deallokeret.

Så heraf kan man konkludere, at automatisk memory management er bedre til lagerhåndtering end alle programmører pånær dem, der aldrig laver fejl af ovenstående type. Og det er de færreste programmører, der aldrig laver fejl.

O.K., man kan argumentere for, at programmører, der aldrig bruger hoballokeret data, heller ikke laver den slags fejl. Men det betyder ikke, at de er lige så gode til lagerhåndtering som automatiske metoder. Snarere tværtimod.

Men det kunne være meget interessant at lave et eksperiment. Det kunne for eksempel ske på følgende måde:

  1. En programmør laver et (ikke alt for stort) C-program, der bruger mange hoballokerede objekter med ikke-trivielle levetider, og gør dette med brug af Boehm-Demers-Weiser garbage collection (http://hboehm.info/gc/), altså uden brug af eksplicitte free() kald.

  2. Andre programmører sættes til at indsætte eksplicitte kald til free(), så programmet kan køre uden GC.

  3. Man tæller, hvor mange programmører, der gør dette fejlfrit (målt på, om programmet giver samme resultat som med BDW GC) i første forsøg (altså uden at prøvekøre programmet, rette fejl baseret på kørslen, osv.) og uden brug af værktøjer såsom Valgrind til at analysere programmet.

  4. Af dem, der klarer dette, måler man performance og memoryforbrug og sammenligner med det oprindelige (kørt med BDW GC). Hvis programmet klarer sig bedre (med en passende vægtning mellem tids- og pladsforbrug), erklæres denne programmør bedre til lagerhåndtering end BDW GC (som vel at mærke er en ret simpel og ikke speciel effektiv automatisk memory manager).

Mit gæt er, at det næppe er mere end en ud af tusind programmører, der kan klare denne test, deraf mit estimat på 99.9%.

  • 0
  • 0
Peter Stricker

Mit gæt er, at det næppe er mere end en ud af tusind programmører, der kan klare denne test, deraf mit estimat på 99.9%.


Det er muligt, at du har ret, men jeg tror nu, at du skyder langt ved siden af.

For det første, så vil det kun være fair, at lade erfarne C programmører deltage i eksperimentet, når opgaven går ud på at lave et program i C. De programmører, der allerede er nået til den erkendelse, at GC er en fordel, skal vel ikke vurderes på deres evner til at bruge malloc. De er allerede nået videre.

For det andet, så skriver du ikke, at formålet med eksperimentet skal holdes skjult for C programmørerne indtil forsøget er overstået. Og det ville heller ikke være fair, når du vil finde ud af, hvor mange der kan klare testen. Her tror jeg, at du undervurderer effekten af en travl hverdag samt almindelig sjusk og slendrian.

  • 0
  • 0
Torben Mogensen Blogger

Hvor meget vil valgrind og lign. kunne opfange?... eller er det snyd ?

Nu var spørgsmålet manuelle versus automatiske metoder til lagerhåndtering, så jeg vil mene, at brug af Valgrind eller lignende automatiske værktøjer vil være snyd, hvis man som forsøgsperson repræsenterer de manuelle metoder.

Som nævnt tidligere i tråden, findes der statiske analyser, der helt eller delvist kan erstatte køretidsspildopsamling. Selv om Valgrind ikke er i den kategori, så vil argumenter, der tillader brug af Valgrind, nemt kunne strækkes til at tillade andre statiske analyser. Og så er spørgsmålet ikke længere mellem manuelle og automatiske metoder men mellem statiske (før kørsel) og dynamiske (under kørsel) metoder.

  • 0
  • 0
Mogens Hansen

Nu var spørgsmålet manuelle versus automatiske metoder til lagerhåndtering, så jeg vil mene, at brug af Valgrind eller lignende automatiske værktøjer vil være snyd, hvis man som forsøgsperson repræsenterer de manuelle metoder.

Den præmis forstår jeg ikke, medmindre formålet med forsøget er at påvise en bestemt tese, som ikke har noget med virkeligheden at gøre.

Jeg mener at det vil være rimeligt at tillade metoder som er almindeligt brugte til udvikling af programmet. Herunder anvendelsen af debuggere, statiske og dynamiske analysatorer.
Det vil så være rimeligt at måle på programmør produktivitet, programkorrekthed osv.
Hvad med f.eks. en kommandolinie option til compileren - som "-fsanitize=address" til clang (og gcc) ?

Alternativt kunne man lave en opgave hvor man måler programmørers evne til at skrive ikke-trivielle programmer uden at oversætte, køre, teste og debugge dem.
Der tror jeg gerne at man vil finde at 99.9% ikke vil være i stand til det - men hvad giver det os af nyttig viden ?

  • 0
  • 0
Mogens Hansen

Nej, jeg tror ikke, at der er lavet nogen statistik over antallet af memorymanagementfejl, programmører laver.

Ok - så er det afklaret.

Jeg har set tal om, at ca. 10% af alle fejl i Windowsprogrammer skyldes heap corruption, som typisk betyder, at man følger pointere til deallokeret data. Men man kan også anskue det som følger:

Automatisk memory management undgår helt, at man følgere pointere til deallokeret data, og undgår memory leaks, hvor data, der ikke længere refereres til, ikke bliver deallokeret.

Så heraf kan man konkludere, at automatisk memory management er bedre til lagerhåndtering end alle programmører pånær dem, der aldrig laver fejl af ovenstående type. Og det er de færreste programmører, der aldrig laver fejl.

Kun under antagelse af at automatisk memory management ikke levner mulighed for programmørfejl - hvilket ikke er tilfældet.
Hvad sker der hvis man (fejlagtigt) holder en reference til noget man ikke længere har brug for ? Man har et leak, omend i en lidt anden form. Konsekvensen er den samme, nemlig at programmets hukommelsesforbrug stiger uden nogen grund og på et tidspunkt ikke længere kan fungere korrekt.
Hvad med fænomenet "resurrection" ?
Hvad med cykliske referencer i et ACR miljø ?

Men det kunne være meget interessant at lave et eksperiment. Det kunne for eksempel ske på følgende måde:

Bestemt meget interessant - men hvorfor så tendentiøs, snæver problemformuling ?
Hvorfor ikke stille en opgave der skal løses i sprog som falder i én af 3 kategorier:
* Manuel resurse håndtering - C er en mulighed, men hvorfor et krav ? F.eks. er assembler velkommen hvis nogen måtte mene det er et godt bud.
* Et garbage collected sprog - f.eks. Java eller C#
* Et sprog der baserer sig på reference counting - f.eks. Swift eller Python

Man kan så måle programmerne på en række egenskaber:
* Opfylder programmerne kravene - altså fungerer de
* Er programmerne formelt korrekte - f.eks. indeholder C programmer "undefined behavior", som kan gøre at programmet faktisk ikke virker selvom det ser sådan ud
* Er der resource leaks - eller moralske ækvivalenter
* Hvor stor en del af programmet bruges på frigivelse af resourcer
* Hvor lang tid har det taget at skrive programmerne
* Hvor meget hukommelse bruger programmerne
* Hvor hurtigt kører programmerne
* Hvor mange linier fylder programmerne
* Hvor mange platforme kan programmerne køre på
Der kan sikkert være mere at måle på mere - jeg er åben for forslag.
Læg det helt åbent frem at det er de parametre, der vil blive målt på, inden forsøgpersonerne begynder.

En programmør laver et (ikke alt for stort) C-program, der bruger mange hoballokerede objekter med ikke-trivielle levetider, og gør dette med brug af Boehm-Demers-Weiser garbage collection (http://hboehm.info/gc/), altså uden brug af eksplicitte free() kald.

Hvorfor begrænsning til C ?

Andre programmører sættes til at indsætte eksplicitte kald til free(), så programmet kan køre uden GC.

Hvorfor det meget specifikke krav om kald af free. ?

En sammenligning af programmeringssprog i den stil blev lavet i 1999 på University of Karlsruhe under ledelse af Lutz Prechelt. Det er en af de mere seriøse undersøgelser jeg kender til.
Opgaven var at finde sætninger, der kan repræsentere en mængde telefonnumre. Såvel de mulige ord som telefonnumrene ligger i filer, der skal læses. Programmerne kan ikke laves uden heap allokering - testen var lavet så det med god sandsynlighed ville blive afsløret.
Der blev lavet ca. 80 løsninger på opgaven i sprogene C, C++, Java, Perl, Python, Rexx og Tcl der blev sammenlignet.
Man kan læse om forsøget på
http://page.mi.fu-berlin.de/prechelt/phonecode/
ligesom der blev skrevet flere artikler om forsøget, bl.a.
http://page.mi.fu-berlin.de/prechelt/Biblio/jccpprt_computer2000.pdf

Desværre - i denne sammenhæng - blev spørgsmålet om resource leaks og tilsvarende ikke behandlet. Ydermere er kildekoden til løsningerne ikke tilgængelige - af juridiske grunde - så vi kan ikke lave analysen idag.
Men forsøget kan "sagtens" gentages - opgaven er god.

Vi kan formodentlig blive enige om at C++ hører til gruppen af sprog, som har manuel resource håndtering.
Nedenstående findes en løsning på opgaven skrevet i C++. Der er en masse heap allokering, men ingen eksplicit kode til frigivelse af resurser - det er håndteret samtidig med resursen blev erhvervet. Al resurse frigivelse foregår helt deterministisk. Vel at mærke er det ikke kun hukommelse, men også åbne filer der bliver taget hånd om.
Det er også værd at bemærke at programmet er komplet i forhold til fejlhåndtering - f.eks. filerne ikke findes eller out of memory.
Programmet er først og fremmest skrevet med henblik på at være simpelt, og til at vedligeholde. Det er ikke skrevet for at være optimalt effektivt.
Den måde at skrive programmer på, skalerer fint til store programmer.

Rimeligvis skal det også bemærkes at den måde at løse problemet ikke forhindrer at man holder pointere til frigivet hukommelse. Konkret har programmet ikke den slags problemer.

Hvad er det der forhindrer 99.9% af programmører i at få resurse håndtering rigtigt i det program ?
(Det er 0% af mine kollegaer)
Hvorfor skulle det eksplodere hvis en anden programmør skal vedligeholde det ?

#include <map>  
#include <vector>  
#include <string>  
#include <fstream>  
#include <stdexcept>  
#include <iostream>  
#include <iterator>  
#include <cstdlib>  
#include <algorithm>  
#include <utility>  
   
   
std::map<char, char>   letter2digit =  
    {  
        {'E', '0'}, {'e', '0'},  
        {'J', '1'}, {'j', '1'}, {'N', '1'}, {'n', '1'}, {'Q', '1'}, {'q', '1'},  
        {'R', '2'}, {'r', '2'}, {'W', '2'}, {'w', '2'}, {'X', '2'}, {'x', '2'},  
        {'D', '3'}, {'d', '3'}, {'S', '3'}, {'s', '3'}, {'Y', '3'}, {'y', '3'},  
        {'F', '4'}, {'f', '4'}, {'T', '4'}, {'t', '4'},  
        {'A', '5'}, {'a', '5'}, {'M', '5'}, {'m', '5'},  
        {'C', '6'}, {'c', '6'}, {'I', '6'}, {'i', '6'}, {'V', '6'}, {'v', '6'},  
        {'B', '7'}, {'b', '7'}, {'K', '7'}, {'k', '7'}, {'U', '7'}, {'u', '7'},  
        {'L', '8'}, {'l', '8'}, {'O', '8'}, {'o', '8'}, {'P', '8'}, {'p', '8'},  
        {'G', '9'}, {'g', '9'}, {'H', '9'}, {'h', '9'}, {'Z', '9'}, {'z', '9'}  
    };  
   
   
std::string encode_word(std::string const& word)  
{  
    std::string      encoded_word;  
    for(auto letter: word)  
        if(letter2digit.find(letter) != letter2digit.end())  
            encoded_word += letter2digit[letter];  
    return encoded_word;  
}  
   
std::string strip_phone_number(std::string const& phone_number)  
{  
   std::string      stripped_phone_number;  
   for(auto letter: phone_number)  
      if('/' != letter && '-' != letter)  
         stripped_phone_number += letter;  
   return stripped_phone_number;  
}  
   
std::multimap<std::string, const std::string> read_dictionary(const char* filename)  
{  
   std::ifstream    dictionary_file(filename);  
   if(!dictionary_file)  
      throw std::runtime_error("unable to open dictionary file");  
   
   std::multimap<std::string, const std::string>   dictionary;  
   std::string      word;  
   while(dictionary_file >> word)  
      dictionary.insert(std::make_pair(encode_word(word), word));  
   return dictionary;  
}  
   
bool print_number_words(std::multimap<std::string, const std::string> const& dictionary, std::vector<std::string> sentence,  
      std::string const& phone_number, std::string const& stripped_phone_number, bool allow_digit)  
{  
   if(stripped_phone_number.empty() && !sentence.empty())   {  
      std::cout << phone_number << ": ";  
      for(auto const& word : sentence)  
            std::cout << word << ' ';  
      std::cout << std::endl;  
      return true;  
   }  
   
   sentence.push_back(std::string());   // allocate one elements  
   bool        has_found_word = false;  
   for(std::string::size_type i = 1; stripped_phone_number.length()+1 != i;++i)  
      for(auto equal_range = dictionary.equal_range(stripped_phone_number.substr(0, i)); equal_range.first != equal_range.second; ++equal_range.first)  {  
         has_found_word = true;  
         sentence.back() = equal_range.first->second;  
         print_number_words(dictionary, sentence, phone_number, stripped_phone_number.substr(i), true);  
      }  
   
   if(allow_digit && !has_found_word)   {  
      sentence.back() = stripped_phone_number.substr(0, 1);  
      has_found_word |= print_number_words(dictionary, sentence, phone_number, stripped_phone_number.substr(1, stripped_phone_number.length()), false);  
   }  
   
   return has_found_word;  
}  
   
void print_number_words_from_file(std::multimap<std::string, const std::string> const& dictionary, const char* phone_number_file_name)  
{  
   std::ifstream    phone_number_file(phone_number_file_name);  
   if(!phone_number_file)  
      throw std::runtime_error("unable to open phone number file");  
   
   std::string      phone_number;  
   while(phone_number_file >> phone_number)  
      print_number_words(dictionary, std::vector<std::string>(), phone_number, strip_phone_number(phone_number), true);  
}  
   
int main(int argc, char* argv[])  
{  
    try   {  
        if(3 != argc)   {  
            std::cerr << "Unexpected number of parameters" << std::endl;  
            return EXIT_FAILURE;  
        }  
   
        const auto  dictionary = read_dictionary(argv[1]);  
        print_number_words_from_file(dictionary, argv[2]);  
    }  
    catch(const std::exception& x)  {  
        std::cerr << "Error:\n"  
                     "  " <<  x.what() << "\n"  
                     "phonecode program terminates" << std::endl;  
        return EXIT_FAILURE;  
    }  
    catch(...)  {  
        std::cerr << "Unexpected error detected\n"  
                     "phonecode program terminates" << std::endl;  
        return EXIT_FAILURE;  
    }  
}
  • 3
  • 0
Baldur Norddahl

Dit C++ program holder referencerne længere end højest nødvendigt. Det gælder både hukommelse og io handles. Stak allokerede objekter frigives først når funktionen afsluttes, hvilket kan være længe efter at en ressource ikke længere bruges.

Der er desuden mange ting der bare ikke kan laves på den måde og som nødvendigvis må ud på hoben.

  • 0
  • 0
Sune Marcher

<b>Mogens Hansen</b>:

Manuel resurse håndtering - C er en mulighed, men hvorfor et krav ? F.eks. er assembler velkommen hvis nogen måtte mene det er et godt bud.

>
"An Assembler Assembles Assembly code" - undskyld, jeg kunne ikke lade være, jeg er pedantisk (også) på det område :)

Man kan så måle programmerne på en række egenskaber:


Spændende, hvis det blev gjort! Og en ret stor opgave. Det kan nok ikke bruges til at bedømme sprogene i sig selv, da det ville kræve en ekstremt stor gruppe deltagere indenfor alle sprog - men det ville immervæk være et interessant datagrundlag at reflektere over. Og hvis man gav helt frie tøjler udfra en kravspec, ville det også kunne vise andre egenskaber ved sprog/platforme. Jeg ville dog foreslå at man som minimum indførte et "kun brug af core sprog/library funktionaliteter" krav.

Vi kan formodentlig blive enige om at C++ hører til gruppen af sprog, som har manuel resource håndtering.


Der er jeg ikke enig - hvis du programmerer idiomatisk C++ har du "semi-automatisk" resource håndtering. Så længe en variabel har block scope er det automatisk, derefter skal du tage stilling til om det er unique eller shared (og så undlader jeg behændigt cykliske referencer... dem kan vi ikke lide i C++ ;-))

NB: jeg har ikke kigget dit kode-eksempel igennem, så ingen kommentarer dér.

  • 0
  • 0
Sune Marcher

både hukommelse og io handles. Stak allokerede objekter frigives først når funktionen afsluttes, hvilket kan være længe efter at en ressource ikke længere bruges.


Destructors kaldes når scope er færdig - så selvom du har stak-allokerede objekter, kan du (C++) godt frigive dem før funktionen returnerer, hvis du introducerer et nyt scope (en ny blok) - det er en af de dér funky ting C++ kan, du kan smide tuborg-krøller ind hvis du har lyst til det. Derudover har compileren meget frie hænder, hvis den kan bevise der ikke er side-effekter.

Dette er både en blessing og en curse ved C++ - det kan være svært at give performance-garantier på tværs af compilere. Der er til gengæld også ret interessante optimeringer der kan laves, på grund af alt det dér "undefined behavior" i standarden. (Og hvis der ikke var det, som sprog+stdlib ser ud, så ville performance være helt af helvede til.)

Der er desuden mange ting der bare ikke kan laves på den måde og som nødvendigvis må ud på hoben.


Der er mange ting en optimizing compiler kunne gøre mere effektivt, men ikke bør gøre effektivt, fordi C/C++ er defineret som et meget snævert core language, og en helvedes masse library code (specielt for C++) - std::string brug burde fx kunne optimeres ret voldsomt, men man er underlagt at en bruger skal kunne swappe implementationen ud, hvis han har lyst.

Also: "hoben"? Hvor bliver man opdraget til ikke at bruge det internationalt anerkendte "heap"? Det er ikke nedladende ment, før jeg tog uddannelse var jeg autodidakt og lærte derfor de engelske termer, men under uddannelse og i det professionelle liv har jeg aldrig hørt folk der bruger (for)dansk(ede) termer for comp.sci. udtryk.

  • 1
  • 0
Baldur Norddahl

Destructors kaldes når scope er færdig

Det er i principet ligegyldigt. Det er stadig dig der skal huske at lave scopes, så at ressourcerne frigives effektivt. Selvom oversætteren kan bevise at en variabel ikke længere bruges, så kan den ikke kalde en deconstructor før tid, da det lige netop er en sideeffekt. Hvis der ikke var deconstructorere, så kunne den principielt frigive hukommelsen.

  • 0
  • 0
Mogens Hansen

Dit C++ program holder referencerne længere end højest nødvendigt. Det gælder både hukommelse og io handles.

Kan du være mere specifik ?
Jeg kan ikke se at det skulle være tilfældet

Filen med ordene åbnes i starten af funktionen "read_dictionary" og lukkes ved udgangen, umiddelbart efter behandlingen er færdig.
Tilsvarende åbnes filen med telefonnumre i starten af funktionen "print_number_words_from_file" og lukkes ved udgangen, umiddelbart efter behandling.
På hvilken måde er det længere end nødvendigt, under hensyntagen til at programmet er skrevet med henblik på at være simpelt ?

Stak allokerede objekter frigives først når funktionen afsluttes, hvilket kan være længe efter at en ressource ikke længere bruges.

Næsten - objekter nedlægges når de går ud af scope.
Det kan også være et lokalt scope inde i funktionen - f.eks. i en if statement.

Der er desuden mange ting der bare ikke kan laves på den måde og som nødvendigvis må ud på hoben.

Data i viste program ligger (typisk) på heapen. Hukommelsen er blot ejet af noget (f.eks. std::string, std::vector og std::map objekter), som har ansvaret for at frigive hukommelsen. De objekters levetid er så styret af scope.

Hvis vi siger, at for at et C++ program skal være fri for leaks, skal der være ryddet op når main returnerer (hvilket ikke er helt præcist rigtigt), så kan ansvaret for nedlæggelse af alle resurser være styret af objekter hvis levetid er styret af scope i main.
Hvilke problem ser du i det ?

  • 0
  • 0
Mogens Hansen

Og hvis man gav helt frie tøjler udfra en kravspec, ville det også kunne vise andre egenskaber ved sprog/platforme. Jeg ville dog foreslå at man som minimum indførte et "kun brug af core sprog/library funktionaliteter" krav.

I den omtalte undersøgelse krav specifikation stod der: "Please make sure your program runs on Perl 5.003, Python 1.5.2, Tcl 8.0.2, or Rexx as of Regina 0.08g, respectively. It will be executed on a Solaris platform (SunOS 5.7), running on a Sun Ultra-II, but should be platform-independent."

Det er tæt på det krav du formulerede. Men det kunne være en udemærket præcisering, så længe man ikke vælger en opgave der favoriserer nogen sprog urimeligt (f.eks. skriv en Windows device driver)

  • 0
  • 0
Mogens Hansen

Det er i principet ligegyldigt.

Nej

Det er stadig dig der skal huske at lave scopes, så at ressourcerne frigives effektivt.

Netop - det er manuel resurse styring.

Det er ikke anderledes end for garbage collected sprog, hvor en reference enten skal gå ophøre med at eksistere eller man skal sætte den til at referere til ingenting for at garbage collectoren har lov til at frigive hukommelsen.

  • 0
  • 0
Sune Marcher

Det er i principet ligegyldigt. Det er stadig dig der skal huske at lave scopes, så at ressourcerne frigives effektivt. Selvom oversætteren kan bevise at en variabel ikke længere bruges, så kan den ikke kalde en deconstructor før tid, da det lige netop er en sideeffekt. Hvis der ikke var deconstructorere, så kunne den principielt frigive hukommelsen.


Enig - eller, compileren kan self. bevise at den KAN kalde en side-effect-free destructor, men det er ligegyldigt i det store løb.

Den vigtige ting er at, IMHO, memory leaks er ligegyldige ifht. resource leaks - og du kan ikke beskytte dig mod resource leaks ved garbage collection. (påstand!) GC-tilhængere glemmer ofte resource leaks fordi de får memory-cleanup gratis.

Det er en DEL lettere at lave et (ellers tomt) scope hvor du introducerer en mængde resource allocators, og så afhænger af at deres destructors (om det så er scope eller exceptions) laver cleanup, end de faciliteter C# og Java stiller til rådighed... men det koster så når du har shared objekter, hvor du skal tage stilling til om ejerskab er shared eller transferred.

  • 0
  • 0
Sune Marcher

Hvis vi siger, at for at et C++ program skal være fri for leaks, skal der være ryddet op når main returnerer (hvilket ikke er helt præcist rigtigt), så kan ansvaret for nedlæggelse af alle resurser være styret af objekter hvis levetid er styret af scope i main.
Hvilke problem ser du i det ?


Jeg er ikke helt enig - for mange programmer kan vi antage at main() aldrig returnerer (med mindre systemet lukker ned) - resourcer er nødt til at blive frigivet før dét punkt.

Resourcer skal frigives så snart de ikke længere er nødvendige - end of discussion. hukommelse som resourcer bruger kan frigives lazily, det er helt OK - lige så snart vi ikke snakker en ren hukommelsesblok, skal den underliggende resource frigvises ASAP. Det er virkeligt vigtigt ved graphics-surfaces, sockets, file handles (specielt på OS'er hvor der er hardlocks!), og så videre. Og den garanti får du ikke på de typiske GC sprog - deres finalizers kører "på et eller andet belejligt tidspunkt, eller måske aldrig."

  • 0
  • 0
Jesper Louis Andersen

Et paper at Bacon et.al. Det er interessant fordi det beskriver hvordan ARC og Mark/Sweep GC er hinandens duale og hvorledes implementeringen af den ene type vil forsøge at implementere den anden.

F.eks. er et problem med ARC store strukturer der frigives. Det kan tage meget pausetid at frigive alt data. Det kan man undgå ved at køre frigivelsen i baggrunden. Og så nærmer man sig det en Mark/Sweep collector gør. Omvendt kan man i en Mark/Sweep collector lave hacks hvor man analyserer lifetime og derved frigiver data tilbage hurtigere. Og så nærmer man sig en ARC-implementation.

Jeg tror ikke der er så stor forskel på de to metoder i praksis.

Bemærk at C++ RAII-style er scope-styret og derfor virker det ikke generelt som en metode.

  • 0
  • 0
Mogens Hansen

Resourcer skal frigives så snart de ikke længere er nødvendige - end of discussion.

Jeg er meget enig - ihvertfald er det et ideal som bør tilstræbes.
Det program jeg viste er meget tæt på det ideal.

Min formulering vedr. main, var nok lidt uklar.
I det program jeg viste, er alle resourcer styret i scope af main, omend alle resurcer undtaget "dictionary" har et væsentligt mindre scope end main.

  • 0
  • 0
Baldur Norddahl

Jeg har kodet opgaven i Scala, for at vise hvordan man håndtere det i et moderne sprog med GC og uden deconstructor. Men jeg bemærker at opgaven er triviel med hensyn til begge dele. De to steder hvor der skal håndteres IO er der tale om one-linere uden behov for eksplicit håndtering.

object Phonebook {  
  type DictType = Map[String, List[String]]  
  val letter2digit = List("e", "jnq", "rwx", "dsy", "ft", "am", "civ", "bku", "lop", "ghz")  
   
  def encodeWord(word: String) =  
    word.  
      map(letter => letter2digit.indexWhere(_.contains(letter.toLower))).  
      filter(_ != -1).  
      mkString  
   
  def stripPhoneNumber(phoneNumber: String) =  
    phoneNumber.replaceAll("[^0-9]", "")  
   
  def readDictionary(filename: String): DictType =  
    io.Source.fromFile(filename).getLines.toList.groupBy(encodeWord)  
   
  def printNumberWords(dictionary: DictType, phoneNumber: String) = {  
    def search(strippedPhoneNumber: String, allowDigit: Boolean): List[List[String]] = {  
      if (strippedPhoneNumber == "") List(Nil)  
      else {  
        val solutions = for {  
          i <- (1 to strippedPhoneNumber.length).toList  
          wordList <- dictionary.get(strippedPhoneNumber.substring(0, i)).toList  
          if wordList.nonEmpty  
          solution <- search(strippedPhoneNumber.substring(i), true)  
          word <- wordList  
        } yield word :: solution  
        if (solutions.isEmpty && allowDigit)  
          for {  
            sentence <- search(strippedPhoneNumber.substring(1), false)  
          } yield strippedPhoneNumber.substring(0,1) :: sentence  
        else solutions  
      }  
    }  
    for {  
      sentence <- search(stripPhoneNumber(phoneNumber), true)  
    } println(s"""$phoneNumber: ${sentence.mkString(" ")}""")  
  }  
   
  def printNumberWordsFromFile(dictionary: DictType, phoneNumberFileName: String) =  
    for {  
      phoneNumber <- io.Source.fromFile(phoneNumberFileName).getLines  
    } printNumberWords(dictionary, phoneNumber)  
   
  def main(argv: Array[String]) = try {  
    argv match {  
      case Array(dictionaryFileName, numbersFileName) =>  
        printNumberWordsFromFile(readDictionary(dictionaryFileName), numbersFileName)  
   
      case _ => println("Unexpected number of parameters")  
    }  
  } catch {  
    case exc: Throwable => println(s"Unexpected error: $exc")  
  }  
}
  • 0
  • 0
Log ind eller Opret konto for at kommentere