Min artikel i Communications of the ACM om min B-heap sparker stadig emails af sig og der er en tendens til at jo ældre korrespondenten er, desto senere kommer emailen.
På nuværende tidspunkt kan korrespondancen opdeles i nogle helt klare klasser:
CS undervisere der siger "Virtual Memory er ikke relevant, de studerende skal lære at analysere en algoritme under de givne forudsætninger".
CS studenter der spørger "Hvor kan jeg lære mere ?"
CS forskere der henviser til et obscurt paper de eller andre har skrevet om cache-oblivious algoritmer.
Og endelig folk af forskellig art der takker mig for at påpege problemet.
I den sidste kategori ankom en email igår aftes hvor indledningen lyder:
Citat:
I was interested in your CACM article about "You're doing it wrong". You have artfully documented the flaws in one of the virtual memory myths – that the flat address space is equivalent to a flat physical memory.
Jeg var på vej til at lave "I'm not worthy! I'm not worthy!" da jeg så at afsenderen var Peter Denning.
'nuff said.
phk
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 ;)
@Carsten: Klik på Peter Dennings navn i blogindlægget og læs hvad der står om ham.
Poul-Henning
@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.
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.
Martin,
Du har fuldkommen ret.
Bortset fra den lille detalje, at de antagelser og forudsætninger man, stadig, bruger i Datalogien, er uden relevans for computere der er bygget de sidste 20-30 år.
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.
Poul-Henning
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 :)
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.
... og så håber de at deres obscure papers på magisk vis diffunderer ud i det omkringliggende samfund.
Min kritik går på undervisningen og formidlingen, ikke på forskningen.
Vis mig den lærebog der hjælper praktikere til at vælge algoritmer på virkelighedens computere og jeg skal gerne promovere den her på min blog.
Poul-Henning
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.
Ja, det er præcis hvad jeg skrev.
Hvilken del af det er det du ikke forstår ?
Mener du det er nok at vifte med nogle få obskure papers om "Cache-Oblivious Algorithms" der alle er publiceret i tidsskrifter som dårligt nok eksisterer og så sige man har gjort sin del ?
Prøv eventuelt at spørge Google Trends om hvordan det går med "cache oblivious algorithms": http://www.google.com/trends?q=cache+oblivious+algorithms
Sammenlig så med hvad de har på "binary heap": http://www.google.com/trends?q=binary+heap
Flot, ikke ?
Og hvis disse Cache-Oblivious Algorithems virkelig er så fantastiske, hvorfor bliver de så ikke brugt over det hele allerede ?
De burde jo spredes som løbeild, burde de ikke ?
Kunne det være fordi de også er bygget på en abstrakt model af den virtuelle computer programmet afvikles på, som stadig ikke har ret meget med virkeligheden at gøre ?
Jeg er glad for at der, trods alt, forskes i emnet, men jeg er ikke imponeret over forskningen og formidlingen kan jeg slet ikke få øje på.
Lige her og nu, er der sandsynligvis flere programmører der har hørt om C.O.A igennem debatten om min artikkel, end via nogen anden kanal.
Er det ikke lidt pinligt ?
Poul-Henning
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/ .
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.
Jep, det er også mit indtryk.
Her kunne man så anføre:
The getpagesize() function appeared in 4.2BSD.
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...
Poul-Henning
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 forstår jeg ikke.
Roger that.
Men Peter Denning forstod det, og det tæller meget for mig.
Poul-Henning
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.
Morten,
Tak fordi du på ypperste vis dokumenterer min påstand.
Stort set alt hvad du skriver er den slags datalogvrøvl jeg kritiserer:
Jeg kritiserer ikke forskningen, jeg ønsker blot at der kom noget mere relevant ud af den.
Jo, jeg har tydeligvis forstået hvad COA er: Stort set uanvendeligt i praksis. Se 1.
Men når det er nødvendigt at optimere, ville så ikke forvente at datalogien kunne hjælpe ?
En af de problemstillinger jeg tror de flest forventer dækket er: "programmet afvikles på en nutidig computer". Hvilken literatur søger han i ? Ingen af hans lærebøger "spilder" tid på emnet.
Vis mig eksemplerne, jeg har ikke kunnet finde dem.
Uhm, du har ikke læst artiklen, vel ? Dette træ er "satellit data" der netop ikke skal bidrage mere til "working set" end højest nødvendigt.
Poul-Henning
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?
Jeg har svært ved at forholde mig til dine punkter, når det ikke fremgår hvad de er svar på.
De svarer på dit indlæg ovenfor, afsnit for afsnit.
Poul-Henning
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.
Men ærligt talt, det er ikke rocket science.
Jeg formoder du mener:
"Men ærligt talt, det er ikke datalogi."
Poul-Henning
OK, så kunne du måske besvare mit indlæg? :)
Det mener jeg så rigeligt jeg har gjort, nu er vi vist bare ude i flueknepperi fra din side. F.eks har jeg aldrig påstået at det jeg har lavet var en COA.
Istedet kunne du måske besvare følgende spørgsmål:
Har valg og optimering af datastrukturer i forhold til virkelige computere noget med datalogi at gøre ?
Såvidt jeg læser dine indlæg kan du ikke se sammenhængen...
Poul-Henning
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 ?
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?
Nej det gør jeg ikke.
Jeg undrer mig bare over at du henviser til COA forskningen som bevis på at der sker noget, for snart efter at indrømme at COA er obskurt og stort set ubrugeligt i praksis.
Hvor er så den forskning der kan bruges til noget ?
Poul-Henning
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.
Algoritmer og maskinarkitektur er blot to forskellige adskildte discipliner, og det er meningen, at forskere, studerende og udviklere selv sammenkobler det.
Det er en meget præcis opsummering af min kritik: Sikke da en tåbelig måde at indrette et studie på.
Poul-Henning
PS: dine links giver 404
Hvor er så den forskning der kan bruges til noget ?
Helt overordnet kan forskning deles i 2 lejre:
Grundforskning: Forskningen har ikke et bestemt anvendelsesformål for øje. I stedet er formålet blot at opnå viden.
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.
