email fra Sct. Peter

Jeg forstod ikke helt den sidste del af bloggen. Hvis jeg ellers har forstået det rigtig, kan jeg kun sige:

Du er da for sej! Fantastisk at du kan holde fast i din egen overbevisning, trods alle fortæller, at du er helt på afveje. Jeg gratulerer og håber det kan være til inspiration for andre med store tanker.

Det er da lidt sejt :-)

Jeg fandt også din artikel meget interessant og pointen er lige i skabet. En ting er matematisk teori, noget andet er praktisk afvikling på et konkret OS og noget konkret hardware med de faktorer det afstedkommer.

Det er super sejt.

PHK har en pointe: Når man laver en eller anden matematisk model, så skal man også kende grænserne for modellen. Og der skal undervises i grænserne.

Grunden til at vi, som regel, kan komme af sted med modellerne er fordi de er nogle forfærdeligt gode indikatorer for køretiden i praksis. Med andre ord giver de et hurtigt overslag over hvor hurtigt en given algoritme kører. Men modellen har en grænse - og når den overskrides, så falder modellen sammen i praksis. For store-o-notation er problemet som regel det at den konstante faktor bliver så stor at "langsommere" algoritmer viser sig at være hurtigere i praksis. Og skæringspunktet i inputstørrelsen, N, bliver så stor at det ikke er relevant for praktiske problemer. "Algoritme A er hurtigere end Algoritme B hvis inputtet er større end antallet af IPv6 adresser".

Et rigtigt godt heap-eksempel på dette er Fibonacci-hoben. Amortiseret er denne hobtype totalt overlegen på alle punkter. Men i praksis er det næppe den hurtigste type heap vi har. Den har muligvis en chance i forbindelse med MERGE-operationer, men jeg tvivler på at den kan slå en binomialhob. Køretiderne på Fib-hoben ser meget imponerende ud. Og skindet bedrager.

Jeg mener ikke umiddelbart at PHKs observation giver grund til helt at forkaste køretidsanalyser. For langt størstedelen af diverse algoritmer er det en ufatteligt effektiv metode til at "skille fårene fra bukkene" og få et hurtigt overblik. Man skal bare være opmærksom på at man kan blive snydt. Grusomt snydt.

Også et stort tillykke til PHK herfra!

Jeg mener ikke umiddelbart at PHKs observation giver grund til helt at forkaste køretidsanalyser.

Det tror jeg heller ikke ville være den korrekte konklusion.

Så vidt jeg forstår har Poul-Henning påpeget en uhensigtsmæssig [i]antagelse[/i] i de hidtidige køretidsanalyser - nemlig antagelsen om at VM-kald havde en "flad" struktur.

Korrigerer man denne antagelse til at stemme overens med de faktiske forhold - inklusive VMs "ikke-flade" struktur - bør man vha de klassiske værktøjer til køretidsanalyse kunne bevise overlegen efficiens i PHK's tilgang.

En model er ikke virkelighed. Som navnet antyder er en model, blot en model over virkeligheden. Eller rettere: En model er en forsimpling af virkeligheden.

Jeg skal ikke gøre mig klog på modeller for kørselstid og Poul-Hennings nye opdagelse. Der er dog nogle fundamentale sammenhænge mellem modeller og virkeligheden.

På samme måde som Newtows love jo ikke er forkert, er modeller for kørselstid formegentelig heller ikke forkerte. Sagen er nærmere, at modellen aldrig er meget præcis end indflydelsen fra de bortabstraherede faktorer, er ligegyldige.

Hvad Newton ikke vidste, var at et legemes hastighed påvirker det masse. Det opdagede Einstein derimod. Herved kunne der pudsig sættes ord på en af de faktorer som Newtons model abstraherede bort fra. Samtidig kunne man nu forklare observationer som ellers var uforklarlige i det situationer hvor det bortabstraherede ikke længere var ligegyldigt, planeternes bevægelse etc.

En Model vil altid være en forsimpling af virkeligheden. Hvis ikke den var det, ville den ikke længere være en model, men være virkelighed. Beregninger ville kræve input på universets nederste niveau og skulle indkludere samtlige fysiske love, både de kendte og de ukendte.

Selv i fremtiden med næsten uanede muligheder i regnekraft, målepræcision og viden om naturen, vil kun et afgrænset enhed, i fysikken en rum, kunne modeleres i det påvirkninger uden for enheden nødvendigvis må bortabstraheres.

Bottom Line er: En model er aldrig mere præcis en de forudsætning den bygger på.

Selvfølgelig skal man da ikke forkaste køretidsanalysen og nogle gange ER N mega stort ;) Det er jo ikke for sjov, når gmplib implementere FFT til multiplikation med store tal (http://gmplib.org/manual/FFT-Multiplication.html#FFT-Multiplication).

Jeg sidder f.eks. med en køretid på O(NM), hvor N=2^20 og M=10^5 i mit værste tilfælde. Alt for langsomt. Det har jeg ved lidt tricks fået skrevet om til O(Nsqrt(M)), hvilket jo teoretisk set er meget hurtigere. Men fordi det er 2sqrt(M) og fordi det tilføjer overhead, siger min intuition mig, at det kun er omkring dobbelt så hurtigt, og det er ikke nok. Jeg skal nok nærmere bruge 100 gange så hurtigt. Køretid er ikke nok, men det er konstanttids optimeringer heller ikke.

Ps. Der er pænt mange IPv6 addresser ;)

@PHK - Jeg har set Wayne's World. Jeg har også læst om Peter Denning. Jeg må tilstå jeg ikke kendte ham i forvejen. Jeg blev blot i tvivl om det virkelig kunne passe eller om der var en der lavede sjov med dig. Men den er altså god nok :-)

Mon ikke det lige så meget er overstående opdagelse som MD5, du nu vil blive kendt for ude i den store verden? Jeg syntes stadigvæk det er for vildt trods din egen ydmyge tilgang. Men, vi er jo danskere underlagt Janteloven ;-)

CS forskere der henviser til et obscurt paper de eller andre har skrevet om cache-oblivious algoritmer.

PHK der henviser til et obskurt paper han har skrevet om brug af VM.

;-)

(Personligt gør PHK's "populær-skrivestil", at jeg ikke rigtigt har lyst til at diskutere - altså stilen fjerner fokus fra indhold, det er synd)

Mvh,

Jeg kan ikke helt se hvordan nogle kan tro at store O notation kan benyttes til at beskrive en algoritmes ydeevne. Store O kan jo kun give et [b]groft estimat[/b] af hvorledes en algoritme skalerer i forhold til størrelsen af dens indput.

Dette har jo intet med den faktiske ydeevne at gøre!

Problemet i denne sag er at lidt for mange har glemt hvad de enligt lærte tilbage på skolebænken (hvis de overhoved har været der). Jeg tror lidt litteratursøgning ville have været sundt for alle.

http://queue.acm.org/detail.cfm?id=1814327

Hans-Kristian Bjerregaard:

Jeg kan ikke helt se hvordan nogle kan tro at store O notation kan benyttes til at beskrive en algoritmes ydeevne. Store O kan jo kun give et groft estimat af hvorledes en algoritme skalerer i forhold til størrelsen af dens indput.

Værktøjerne til analyse af køretidskompleksiteter (store-O, store-Theta, store-Omega, ...) kan bruges til matematisk at bevise egenskaber ved de analyserede algoritmer.

Matematik er et universelt sprog - det afhænger ikke af om PHK sidder med FreeBSD på en ARM-processor med SSD-diske, mens du sidder med Windows 7 på en x86 og en båndstation. Derfor gør en matematisk analyse det lettere at kommunikere påvisninger af en algoritmes overlegenhed ift andre, uden at man skal spilde tid på indvendinger om at "jamen jeg bruger system XYZ..."

Vi behøver med andre ord ikke at købe det samme system som PHK, jagte de uvedkommende processer på maskinen og stoppe dem, opstille statistiske tests og køre dem det nødvendige antal gange, for at kommunikere at den ene algoritme outperformer den anden under de givne omstændigheder. Vi kan afdække grundlæggende egenskaber ved algoritmer, uden brug af hardware.

Matematisk analyse af køretidskompleksiteter vha store-O & friends, bekæftiger sig alene med algoritmers efficiens på et matematisk plan, og kan derfor bruges til f.eks. på forhånd at udvælge de algoritmer der ser ud til at klare opgaven bedst, [i]inden[/i] man begynder implementeringen.

Dette har jo intet med den faktiske ydeevne at gøre!

Jo. Men det er ikke [i]altafgørende[/i] for den faktiske ydeevne - der er også andre faktorer der spiller ind på den - din båndstation fra før f.eks.

Humlen er jo at du kobler algoritmers matematiske natur, med matematikkens værktøjer indenfor bevisførelse, og derved kan levere uomtvistelige fakta omkring algoritmer. I matematik kan man nemlig ikke bevise noget der er matematisk forkert - man kan kun lave et et matematisk bevis forkert.

Og som al anden matematik, kræver det korrekt anvendelse af værktøjerne, før man kan bruge resultaterne til noget.

Hvis man derimod ikke formår at anvende kompleksitetsanalyseværktøjerne korrekt, vil man sagtens kunne havne i en situation hvor man konkluderer, at resultaterne ikke er anvendelige, eller i modstrid med observerbare forhold.

Jeg har ikke på noget tidspunkt slået tromme for at vi ikke skulle analysere algoritmer, men alene for at vi skal gøre det under forudsætning af at de afvikles på noget der ligner en rigtig computer.

Mit indlæg var bestemt heller ikke en reaktion på noget du havde sagt.

Der var bare optræk til at andre ville spænde dig og dit fine arbejde for en vogn, der sagde noget i retning af at "nu er det bevist at store-O ikke virker".

Og det syntes jeg ville være en helt forkert drejning.

Det er muligt at der ikke undervises så meget som der burde i algoritmers ydeevne når de køres under virtuel hukommelse. Men jeg synes kritikken i din artikel er uberettiget, idet du ikke blot kritiserer undervisningen, men hele CS feltets tilgang til algoritmer!

Sagen er at der er mange i CS der har haft samme overvejelser som dig og lavet algoritmer i stil med det du har lavet. I din artikel citerer du kun artikler fra '60erne og ikke de mange artikler siden der har beskæftiget sig med problemstillingen. Som der også var en der bemærkede, hvis du gik 5 år mere tilbage kunne du også begynde at tage æren for Quicksort :) Jeg er jævnligt stødt på algoritmer der forholder sig til problemstillingen, f.eks. da jeg kiggede på suffix arrays, hvor en stor fordel i.f.t. suffix trees netop ligger i lokalitetseffekter.

Endeligt skal man huske at det jo kun er i visse situationer (store datasæt) og med visse algoritmer disse effekter for alvor kommer til udtryk, så det er måske lidt bredt at skyde mod al analyse af algoritmer :-)

Desuden undrer det mig at problemet ikke bare kunne løses ved at holde selve B-heap/tree datastrukturen i memory og kun lade selve "sidedata" blive swappet ud. Jeg kan ikke tro index data fylder ret mange % af maskinens samlede hukommelse, men måske tager jeg fejl?

Iøvrigt er gengivelsen af kritikken af din artikel - som du fremstiller den i dette blotindlæg - ikke retfærdig. De fleste kommentarer jeg har set går ikke på at du har en relevant pointe, men mere at den er fuldstændigt velkendt - både problemstillingen og løsningen :)

Min kritik går på undervisningen og formidlingen, ikke på forskningen.

OK, hvad så med:

The past 30 or 40 years of hardware and operating-systems development seems to have only marginally impinged on the agenda in CS departments' algorithmic analysis sections, and as far as my anecdotal evidence, it has totally failed to register in the education they provide.

MARTIN BØGELUND:
Præcis hvad jeg beklager at de fleste har glemt.

Min pointe er mere at store O kun kan bruges til en meget naiv sammenlgning af algoritmer og hvis man alene benytter den til at træffe beslutninger i praksis går det selvfølgeligt galt. Man kunne jo f.eks. komme til at fravælge quicksort som et eksempel.

MORTEN ANDERSEN:
Helt enig i din kritik.

POUL-HENNING KAMP:
Problemet er din generelt manglende forståelse for at dit arbejdsområde kun beskæftiger en meget lille delmængde af programmørere i verden. De fleste andre har jo tiltro til at operativsystem samt grundliggende biblioteker og deres datastrukturer udnytter maskinen effektivt.

Den abstraktion er nødvendig for overhoved at få udviklet de programmer som datamaterne bruges til. Uden dem er datamaten blot et sjovt stykke legetøj.

Algoritmer er jo generelle og uafhængie af hvorledes de bliver afviklet (de kunne jo også afvikles af mennesker) men det er deres implementation ikke. Det er bare ikke implementeringen der er relevant på et generelt niveau.

Men når du påstår at der ikke bliver undervist i deres afvikling på maskinen er det jo noget vås da Jyrki allerede på mandag om en uge afholder et 2 måneders kursus kun om datatyper hvor fokus lige præcis er hvorledes de fungerer på en moderne datamat: http://sis.ku.dk/kurser/viskursus.aspx?knr=120861

Ærgrer mig at du altid mister alle former for omtanke og selvkritik når du får chancen for at slå på datalogien, blot fordi du ikke forstår den verden.

PHK,

Den algoritme du har lavet er ikke en cache-oblivious algoritme. Det er en IO-effektiv algoritme.

Cache-oblivious algoritmer er nogle (som regel ret komplicerede) algoritmer, som under nogle rimeligt realistiske antagelser kan optimere antallet af cache-misses i HELE hukommelseshierarkiet uden at page-size og cache-size for de forskellige caches er kendt. Under disse betingelser er selv noget forholdsvist banalt som sortering en ret kompliceret sag. Fælles for alle disse algoritmer er, at der er et relativt højt konstant overhead, og at det konstante overhead som regel er så stort, at algoritmerne ikke har nogen praktisk interesse. Det kan selvfølgelig ændre sig hvis hukommelseshierarkiet får endnu større betydning for performance.

IO-effektive algoritmer optimerer antallet af page faults på ét hukommelsesniveau, og antager, at programmet kender pagesize. IO-effektive algoritmer har stor praktisk interesse. Check eksempelvis STXXL: http://stxxl.sourceforge.net/ .

Det er fint at i forsvarer jeres universiteter/uddannelser/papers, men faktum er at der stort ikke er nogen der har lært på deres uddannelse hvordan man får noget der ligner 30% af teoretisk ydelse ud af VM hardware...

Det forstår jeg ikke. Den teoretiske ydelse er netop ikke afhængig af praktiske gøremål. Du kan passende antage at samtlige VM-pagereferencer giver paging fra en båndstation. Resultatet er at den praktiske algoritme kører langt hurtigere end forventet da visse pages ender med at have en meget bedre access-tid.

Det er fedt når folk der er store inden for deres felt ikke er for fine til at blive klogere og give positiv respons til andre der gør et godt stykke arbejde.

Jo, det var præcis hvad du skrev. Citatet illustrerer at du i din artikel ikke blot kritiserer undervisningen, men også forskningen, i modstrid med hvad du netop hævdede.

Du har tydeligvis slet ikke forstået hvad COA er. Som andre skrev, er COA nogle meget specielle algoritmer, der ikke har vundet stor udbredelse. Din algoritme er ikke en COA, men en optimering af layout af datastrukturer for at forbedre locality i tilgangen, hvilket har stor udbredelse.

Jeg har læst mange papers der har anvendt lignende tricks (d.v.s. ikke COA) indenfor alle mulige datastrukturer. Der findes dog utvivlsomt algoritmer der ikke er optimeret i denne henseende, men det er jo heller ikke altid det er nødvendigt.

Ang. undervisningen så er der jo givetvis mange problemstillinger man kan rende ind i der ikke undervises i. Jeg mener ikke man kan forlange at alle scenarier er dækket, og det er heller ikke realistisk eller nødvendigt. For at tage dit eksempel. Antag at en nyudklækket studerende skulle skrive Varnish. Han starter med at bruge et standard B-tree. Da han så går i gangt med at teste på større/realistiske datamængder, opdager han at alt kører ad h til. Mon ikke han hurtigt opdager at disken seeker helt vildt ved simple operationer? Og enten selv lægger to og to sammen eller spørger andre hvad der kan være galt? Måske søger i litteraturen? Selve det underliggende fænomen - trashing - og mekanismen bag, er jo helt velkendt.

Du slår meget på at Varnish er et "moderne program" fordi det udnytter det store, flade adresserum og overlade prioritering af sider m.m. til operativsystemet. Er dette så unikt? Der kan da være modeksempler, men jeg tror da de fleste (non-legacy) programmer har arbejdet sådan efter 32-bit kom til.

Hvorfor var det egentlig du ikke bare hintede til operativsystemet at træstrukturen skulle holdes i hukommelsen (jeg går ud fra FreeBSD har et kald hertil - ellers er der andre måder), så det kun var satellit data der blev swappet ud. Der er også ulemper herved men under nogle loads vil det giver bedre performance end "B*tree" løsningen.

Jeg har svært ved at forholde mig til dine punkter, når det ikke fremgår hvad de er svar på.

2) Vi er enige om at COA er uanvendeligt - og at det du ikke har lavet er CAO? Godt så.

3) Det kan den også! Har du hørt om Citeseer?

4) Ditto

5) Eksempler på?

6) Jo jeg har læst artiklen. Forstår ikke hvad du mener med "Dette træ er "satellit data", med mindre du har "træer i træer" eller lignende. Men da hele emnet jo handler om en praktisk problemstilling, kan du så give nogle mere konkrete tal? Hvor mange entries er der i dette træ i en praktisk load? Hvad fylder hvert entry (i.e. ikke bare pointerne osv. men det som entry'et står for: satellit data)? Hvor meget RAM er der (ca./typisk) i maskinen?

Men Peter Denning forstod det, og det tæller meget for mig.

Ehm...

Det giver ikke mening at snakke om 30% af teoretisk ydelse lige meget hvordan du end vender eller drejer det, sorry. PD eller ej. Dit argument må bero på at man ikke lærer at skrive optimeret kode. Men ærligt talt, det er ikke rocket science.

OK, så kunne du måske besvare mit indlæg? :)

Har valg og optimering af datastrukturer i forhold til virkelige computere noget med datalogi at gøre ?

Ja, men det er kun en meget lille del af hvad datalogien omfatter.

Bemærk: Som med så meget andet der tangerer til humaninsme (defenitionen af hvad der ligger i begrebet datalogi) er det noet der ikke kan siges absolut og derfor diskuteres meget. Dette er bare min ydmyge tolkning.

Har valg og optimering af datastrukturer i forhold til virkelige computere noget med datalogi at gøre ?

Ja. http://www.madalgo.au.dk/index.html

Det har det da i høj grad! Jeg har aldrig påstået at dette ikke lå indenfor datalogiens problemfelt. Tværtimod har jeg påpeget, at der er forsket en del i det! Blander du mine indlæg sammen med en andens eller hur?

Hvor har jeg henvist til COA forskningen som argument for at 'der sker noget' på dette område? Så vidt jeg kan se er det kun dig der har henvist til COA-forskningen på denne måde. Det eneste jeg har sagt er at det du har lavet ikke er COA! Og det er snarere end en ros end en kritik - har ikke set noget COA der havde den store praktiske relevans endnu (derfor kan det jo være interessant nok).

Den forskning der kan bruges er spredt i forskellige artikler, indenfor de områder hvor det er relevant. F.eks. hvis man anvender suffix trees og søger på det på Citeseer, så finder man hurtigt ud af at der er noget der hedder suffix arrays som er meget smartere, bl.a. pga. den forbedrede locality.

Nu var det binary trees i dit eksempel - jeg Googlede lidt og et oplagt sted at starte kunne være:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.9069
(Memory Reference Locality and Periodic Relocation in Main Memory Search Trees)

www.cs.hut.fi/~cessu/papers/msc.ps
(Memory Reference Locality in Binary Search Trees)

Min pointe er at problematikken skam er blevet behandlet, men det er selvfølgelig ikke noget hver eneste CS forsker arbejder med :)

Hej PHK,

Caching og virtuel memory er trivielt og alle dataloger kender det.

Algoritmer og maskinarkitektur er blot to forskellige adskildte discipliner, og det er meningen, at forskere, studerende og udviklere selv sammenkobler det.

Det, du fejlagtigt gør, er at henvise til algoritmebøgerne alene, og påpeje, at hardwaren ikke indgår.

Derfor har jeg gang på gang linket til undervisningesbøgerne i hardware, fx i mine tråde på http://www.version2.dk/artikel/15212-jeg-har-vaeret-jer-utro#post72384

Disse links har du hver gang ignoreret.

Hvor er så den forskning der kan bruges til noget ?

Helt overordnet kan forskning deles i 2 lejre:

1. Grundforskning: Forskningen har ikke et bestemt anvendelsesformål for øje. I stedet er formålet blot at opnå viden.

2. Anvendelsesrettet forskning: Forskning med et konkret anvendelsesformål for øje og ofte betragtet som erhvervsrettet forskning.

Uden 1. ville 2. hurtigt komme til kort. Alle store opdagelse inden for videnskaben er opstået med udgangspunkt i grundforskningens resultater.

Algoritmer og maskinarkitektur er blot to forskellige adskildte discipliner, og det er meningen, at forskere, studerende og udviklere selv sammenkobler det.

I så fald er det netop årsagen til den manglende viden på området. På laveste niveau kan viden deles ind i kasser. Men efterhånden som vidensniveauet stiger, må kassernes afgrænsninger brydes og erstattes af helhedstænkning. Det kaldes i nogle sammenhænge tværfaglighed. I virkligheden er det blot niveauet over kassetænkning.

Det er en meget præcis opsummering af min kritik: Sikke da en tåbelig måde at indrette et studie på.

Det virker fint. Jeg selv skrev bacheloropgave i noget, hvor jeg kombinerede det. I flere kandidatkurser forventes det at kombinere det (Klyngearkitekturer, bl.a.). At lære at kombinere viden fremfor at ske-fodres er en god ting.

PS: dine links giver 404

Så var det godt, at du klikkede på de Google Books dengang jeg pastede dem.[quote]

Min pointe er at problematikken skam er blevet behandlet, men det er selvfølgelig ikke noget hver eneste CS forsker arbejder med :)

Og jeg kan da supplere med http://cphstl.dk/ som to fra DIKU, jeg kender, skrev bachelorprojekt i.

De optimerede rød/sort søgetræer ved at bruge laveste bit i pointere (som alligevel har større end byte grannularitet) som farveindikator.

Jeg opgiver, det er umuligt at diskutere med PHK som - forståeligt nok - foretrækker at diskutere med sin egen stråmand. F.eks. hævder han at jeg skulle have lovprist COA, hvilket er noget være sludder, hvad alle jo straks kan forvisse sig om. Han har heller ikke svaret på mine indvendinger, men har skrevet direkte vrøvl. Desuden gengiver hans blogindlæg ikke den primære kritik af hans artikel (You are doing it wrong). Slut herfra.