Dette indlæg er alene udtryk for skribentens egen holdning.

Jeg har været jer utro...

59 kommentarer.  Hop til debatten
Blogindlæg15. juni 2010 kl. 11:07
errorÆldre end 30 dage

Min gode ven George Neville-Neil har været efter mig i nogen tid, for at afpresse mig en artikel til ACM's Queue magazine.

Den kom til at hedde "You're doing it wrong" og har allerede været på både Reddit og Slashdot.

Hvor der på reddit har været et antal intelligente kommentarer, heraf nogle få rigtig insigtsfulde, er jeg forbavset over at se at de sidste tegn på intelligens på Slashdot er blevet kirugisk fjernet.

Jeg skrev bevidst artiklen lidt skarpt i tonefaldet, for at skille bukkene fra fårene: Dem der hurtigt bliver fornærmede afslører sig selv ved ikke at ane hvad der egentlig står i artiklen, mens dem der har noget at have det i, finder tonen enten underholdende, eller svagt irriterende.

Artiklen fortsætter efter annoncen

Artiklen bliver også trykt i juli nummeret af CACM, så kommer der utvivlsomt lidt flere intelligente replikker.

Jeg er sikker på at GruppenFührer Torben allerede sidder med morgenkrydderen solidt på tværs i halsen og tekstbehandlingen indstillet på 30pt Helvetica-Bold og jeg ser frem til hans svar.

Han glemmer næppe at påpege at pengene til DIKUs algoritmegruppe forsvandt under nedskæringerne.

Men jeg ville meget hellere høre, fra ham og andre dataloger, om det er på tide at "rigtige dataloger" opgraderer deres hardware fra "Viking nummer 2" til computere som dem vi andre bruger ?

phk

59 kommentarer.  Hop til debatten
Debatten
Log ind for at deltage i debatten.
settingsDebatindstillinger
2
15. juni 2010 kl. 11:49

Han glemmer næppe at påpege at pengene til DIKUs algoritmegruppe forsvandt under nedskæringerne.

Egentlig ikke. Før nedskæringerne bestod DIKUs algoritmegruppe af to mennesker, der lavede kombinatorisk optimering + en, der lavede dette samt bioalgoritmer + to, der lavede numeriske beregninger. Der var sådan set allerede dengang ikke nogen, der lavede klassisk algoritmik i gruppen. Efter nedskæringen forsvandt de to numerikere (den ene dog ikke længere end over til NBI). En af optimeringsfolkene fik tilbudt et professorat på DTU, som han tog imod.

Tilbage er altså en optimeringsmand (som er institutleder) og en, der laver optimering og bioinformatik. På grund af den lille størrelse, blev gruppen slået sammen med programmeringssprogsgruppen, som allerede have en halvalgoritmiker (som primært laver templatebiblioteker til C++). Han vil måske være interesseret i din B-heap struktur -- han har arbejdet med [i]cache-oblivious algorithms[/i], som ser ud til at have en vis lighed med din ide om at udnytte lagerhierarkiet.

5
15. juni 2010 kl. 13:30

Jeg har taget kurset der omtales, nemlig "Advanced Data Structures: Theory and Practice". Der er nærmest ingen fokus på C++ i løbet af kurset - det afsluttende projekt bruger C++ templates, men konceptet introduceres kun kortvarigt.

I kurset gennemgås diverse datastrukturer, inklusiv B-tree og Van Emde Boas tree. Ligeledes introduceres både external memory model og cache oblivious data structures.

I det afsluttende projekt implementeres en eller flere effektiv(e) datastrukture, men her måles effektiviteten i form af klassisk O(n) køretid. Konstanter ignoreres.

Men ja, de emner der diskuteres i artiklen introduceres i kurset og har man taget det bliver man næppe overrasket over at se en B-heap ;-)

Det er dog ikke obligatorisk.

3
15. juni 2010 kl. 12:10

Den er tilpas provokerende til at få omtale og den er tilpas interessant til at holde folk fast. Den forholder sig til et reelt problem: Køretidskompleksitet tager ikke højde for konstante faktorer - og konstante faktorer er voldsomt grumme i praksis (og ikke lineære pga, paging/cache). Og samtidigt skriger den: "Hvorfor lærer i ikke folk det her?". Der findes faktisk forskere på DIKU som lærer deres studerende at det hænger sådan sammen - men det er som regel de mere praktisk orienterede forskere (go figure :).

Det samme problem manifesterer sig i forbindelse med caches. I dag koster et cache hit (ikke et miss!) forholdsvist mange klokcykler og det forventer jeg ikke bliver billigere foreløbigt. Den hurtigste datastruktur er som regel den som laver færrest cache-misses - hvilket er jævnt underholdende. Det kan betale sig at komprimere data, hive det over memorybussen og så udpakke det på CPU'en. Det lyder som et sjovt forskningsområde. Måske man skulle skrive speciale om funktionelle sprogs cache-misses mod imperative sprogs ditto :)

DIKUs algoritmegruppe har traditionelt beskæftiget sig en del i områder hvor konstante faktorer er ligegyldige. At vinde en faktor 4-8 betyder bare at du kan tilføje 3 variable mere til dit problem. At finde en smart algoritme kan give dig 200 variable mere på de problemer (diverse NP-hårde problemer, naturligvis).

6
15. juni 2010 kl. 13:55

PHK har ret: Ja, det er rigtigt at mange "kanoniske lærebogsalgoritmer" ikke forholder sig til lagerhierarkiet. Og ja, mange programmer/systemer kan optimeres en pæn sjat ved kigge nærmere på disse problemer. Og man skal teste performance, og gøre det kritisk og løbende.

Men PHK tager fejl: For det første er det noget som der både forskes og undervises i (som dokumenteret ovenfor). Måske ikke på første år som datastrukturer, men jeg mener bestemt at have ramt hele det emne på 2. eller 3. år på DIKU. Nej, verden har ikke stået stille siden Knuths "The Art of Computer Programming"! At udvikle real-world systemkomponenter såsom kerner eller specialiserede serverprogrammer kræver jo mere end begynderviden, så hvorfor tro at begynderlærebøgerne er nok?

For det andet er der stadig i denne verden alt for mange programmører, der stadig ignorerer deres kanon, og skriver programmer, der ikke virker, eller er ufatteligt sløve når de bliver kørt i den virkelige verden. At kode i blinde fordi algoritmerne er "forkerte", eller kode med øjne alene for VM arkitekturen, er meget mere forkert end at vælge en fornuftig algoritme.

Og så bygge videre derfra. Og måle. Og optimere. Og måle igen.

7
15. juni 2010 kl. 14:39

Tjaa, for os århus dataloger er der ikke noget nyt i den historie ;)

Vi har madalgo centeret, som forsker i

I/O-efficient algorithms cache-oblivious algorithms streaming algorithms

og der er rig mulighed for at kaster sig over ovenstående emner i diverse kurser..

8
15. juni 2010 kl. 16:25

Jeg har ikke helt fanget hvorfor det lige er datalogerne PHK er ude efter. Sandheden er jo at langt de fleste programmører, dem vi ville kalde "jævne", ikke har forståelse for komplicerede sammenhænge i køretidsberegninger.

Så er det ligemeget om de er selvlærte, datamatikere, software ingeniører eller dataloger.

Og de slipper godt afsted med det, fordi der er masser af opgaver hvor det ikke er vigtigt. Varnish er en type opgave, hvor man har sat sig for at gøre det så hurtigt som overhovedet muligt, uanset hardwaren. I mange andre projekter er projektmanageren ligeglad, så længe opgaven løses til tiden og det virker.

En gang i mellem kommer der en COWI/skoletest fadæse ud af det. Men som regel går det godt. Bare programmørerne i det mindste husker at vælge algoritmer der har basale køretidsegenskaber. Det er ikke quicksort vs heapsort der vælter læsset for disse projekter. Men bubblesort vil måske være et skidt valg.

11
15. juni 2010 kl. 17:01

Jeg har ikke helt fanget hvorfor det lige er datalogerne PHK er ude efter. Sandheden er jo at langt de fleste programmører, dem vi ville kalde "jævne", ikke har forståelse for komplicerede sammenhænge i køretidsberegninger.

Fordi datalogerne, i modsætning til de andre, har et eksamensbevis der siger at de kan finde ud af den slags ?

Poul-Henning

12
15. juni 2010 kl. 17:40

Fordi datalogerne, i modsætning til de andre, har et eksamensbevis der siger at de kan finde ud af den slags ?

Og datalogerne gav dig svaret, nemlig at andre, herunder DIKU-folk, havde forsket og undervist i dette problem og offentliggjort en tilsvarende løsning i 1999.

Når det så er sagt så er den maskinnære forskning kun én retning ud af flere på f.eks. DIKU: Du kan sagtens finde en datalog, der ikke ved så meget som lagerhierarkier fordi han/hun har haft snuden i f.eks. HCI eller semantik. Men det beviser næppe at alle dataloger skriver ineffektive programmer.

Eller må dataloger ikke specialisere sig?

9
15. juni 2010 kl. 16:46

For dem som interesserer sig for IO-effektive heaps, så eksisterer der altså en artikel om emnet:

Heaps and Heapsort on Secondary Storage. R.Fadel, K.V. Jakobsen, J. Katajainen, J. Teuhola. TCS 220 (2), 1999.

13
16. juni 2010 kl. 09:19

Nu må Poul-Henning fortælle os, om hans B-heaps er en bedre løsning til hans problem end de external heaps, der er beskrevet i den nævnte artikel.

Det burde jo være en smal sag for Poul-Henning at implementere dem og lave de samme forsøg, som han gjorde i sin egen artikel -- eller kræves der en datalog til det?

14
16. juni 2010 kl. 09:50

Jamen det kan jeg da hurtigt svare på:

Det er de (external heaps) ikke.

Ikke alene skal man implementere en masse kode for at lave I/O scheduling, men man skal også leve med I/O overhead, selvom man har RAM nok til at holde det hele deri.

Det smukke ved VM ideen er netop at du ikke skal skrive to programmer: et til at køre i RAM og et andet til at køre i RAM og på disk.

Poul-Henning

20
16. juni 2010 kl. 11:13

Det er de (external heaps) ikke.</p>
<p>Ikke alene skal man implementere en masse kode for at lave I/O scheduling, men man skal også leve med I/O overhead, selvom man har RAM nok til at holde det hele deri.

Hvis du synes external heaps er for komplicerede, kan du se på local heaps, som ligner dine B-heaps en del:

http://cphstl.dk/Report/Local-heaps/cphstl-report-2006-1.pdf

21
16. juni 2010 kl. 11:49

Jamen den er da muligvis sød -- hvis man har brug for at sortere ting i RAM på en maskine med en velkendt cache-linie bredde.

Så vidt jeg lige kan gennemskue, jvf. den totale mangel på omtale af VM/disk/etc, er alle disse benchmarks gennemført 100% resident i RAM, så med mindre der er opfølgende arbejde der kigger på opførslen under VM pressure har jeg svært ved at se relevansen ?

Hvis man definerede cachelinie-bredden til VM pagesize, sørgede for alignment, og lavede to-træer-per-page tricket fra B-heap, ville den muligvis ende næsten samme sted som min algoritme.

Det svarer dog lidt til at sige at hvis Nicholai Tessla havde brugt Jævnstrøm var han havnet samme sted som Edison.

Jeg synes faktisk blot at de to papers understreger min pointe: Dataloger aner ikke hvad virtuel hukommelse er, eller hvordan det skal bruges.

Poul-Henning

PS: Det faktum at flere af kurverne knækker i intervallet omkring 30k-100k elementer burde have givet dem et vink med en vognstang om at de overså noget: Jeg er temmelig sikker på at knækket i kurverne skyldes at de falder ud af TLB'en på deres SGI maskine...

23
16. juni 2010 kl. 12:24

"Jeg synes faktisk blot at de to papers understreger min pointe: Dataloger aner ikke hvad virtuel hukommelse er, eller hvordan det skal bruges."

Jeg synes det er fint at være kritisk i forhold til om det som dataloger går rundt og forsker i nu også er tilstrækkeligt tæt på virkeligheden til at være brugbart i praksis.

Men faktum er, at der i blandt forskere har været masser af opmærksomhed på at udvikle nye modeller som tager højde for hukommelseshierarkiet i en moderne computer. Der er som bekendt IO-modellen og også den Cache-Oblivious model. Faktum er, at der I århus er et forskningscenter, som ikke laver andet end at forske i netop dette emne.

Faktum er også, at stof der bl.a. omfatter hvordan virtuel hukommelse virker er obligatorisk på datalogiuddannelsen (i hvert fald i århus). Mere specifikt kurset om operativsystemer, hvor lærebogen mig bekendt stadig er Tanenbaums klassiker om emnet.

Faktum er også, at der er kurser der handler om hvordan man lave IO-effektive algoritmer og Cache-Oblivous algoritmer, og at for enhver datalog som har taget kursus i IO-effektive algoritmer vil være fuldstændig åbenlyst at

  1. En binær heap vil performe ekstremt dårligt såfremt hele heap'en ikke ligger i hukommelsen, samt
  2. At man kan bruge en helt standard teknik (blocking) til at løse dette problem, præcis som du har gjort.

Hvis du ikke tager mine ord for gode varer, så kan du selv se de slides der er brugt i kurset: http://www.daimi.au.dk/~large/ioS09/Lecture2.pdf , samt det undervisningsmateriale der hører til: http://www.daimi.au.dk/~large/ioS06/ionotes.pdf . Jeg vil også anbefale dig at læse artiklen om Cache-Oblivous prioritetskøer:

Cache-Oblivious Priority Queue and Graph Algorithm Applications. L. Arge, M. Bender, E. Demaine, B. Holland-Minkley and I. Munro. SICOMP, 36(6), 2007.

Jeg skal bestemt ikke afvise der er masser af dataloger der får deres eksamen uden at ane noget som helst om hukommelseshierarkier og virtuel hukommelse. Der findes elvfølgelig både dygtige og mindre dygtige dataloger, ingen tvivl om det - og jeg skal bestemt heller ikke udelukke, at der qua. taxameterordningen slippes flere igennem nåleøjet end der tidligere har gjort. Men lige nu er det mit indtryk at du slet ikke har sat dig ind i forskningen på området, og at du derfor er i gang med at genopfinde den dybe tallerken.

26
16. juni 2010 kl. 13:01

Men faktum er, at der i blandt forskere har været masser af opmærksomhed på at udvikle nye modeller som tager højde for hukommelseshierarkiet i en moderne computer.

Som jeg tidligere har sagt: Jeg ville være blevet meget skuffet hvis der overhovedet ikke foregik nogen forskning i dette område overhovedet.

Jeg ved ikke hvad du mener med "masser af opmærksomhed", men jeg deler bestemt ikke din opfattelse: der er nogle få spredte papers fra hist og her, samt en sprit ny indsats på MIT.

Men hvis der er "masser af opmærksomhed", hvor finder jeg da de nye lærebøger, hvor O() ikke bare gælder for ZX81 ?

Faktum er, at vi har haft VM i 30+ år, men datalogerne er i bedste fald begyndt at interessere sig for det indenfor de seneste 2-5 år og langt de fleste CS uddannelser har stadig ikke fået memo'et...

Poul-Henning

42
16. juni 2010 kl. 23:51

Faktum er, at vi har haft VM i 30+ år, men datalogerne er i bedste fald begyndt at interessere sig for det indenfor de seneste 2-5 år

Hvis ikke der er tygget drøv nok på dette kan man jo starte med Aggarwal og Vitter fra 1988 (Communications of the ACM) og tygge sig fremad.

43
17. juni 2010 kl. 00:12

Hvis ikke der er tygget drøv nok på dette kan man jo starte med Aggarwal og Vitter fra 1988 (Communications of the ACM) og tygge sig fremad.

... 24 år efter VM blev opfundet.

... 16 år efter IBM/370 gjorde VM mainstream

... 11 år efter VAX/11 gjorder det rigtig mainstream.

Og idag, 12 år senere, er det stadig ikke med i O() funktionen i CS-bachelor niveau ?

Jeg er godt klar over at computer-hardware har udviklet sig specielt sig hurtigt, i forhold til andre teknologier, men burde den tilhørende software disciplin, ikke være i stand til at følge lidt hurtigere trop end det vi ser her ?

Poul-Henning

55
17. juni 2010 kl. 14:52

PHK:

[quote]
Hvis ikke der er tygget drøv nok på dette kan man jo starte med Aggarwal og Vitter fra 1988 (Communications of the ACM) og tygge sig fremad.

... 24 år efter VM blev opfundet. ... 16 år efter IBM/370 gjorde VM mainstream ... 11 år efter VAX/11 gjorder det rigtig mainstream.

Og idag, 12 år senere, er det stadig ikke med i O() funktionen i CS-bachelor niveau ? [/quote]

Først: 1988 er toogtyve år siden, ikke tolv. Altså:

... 12 år efter VM blev opfundet
... 4 år efter IBM/370 gjorde VM mainstream
... -1 år efter VAX/11 gjorder det <em>rigtig</em> mainstream.

I dag, 22 år senere, hvad mener du så, når du siger, VM skal "med i O() funktionen i CS-bachelor niveau"? Det er ikke en sætning, som umiddelbart giver mening for mig.

Hvis jeg må gætte på, hvad du mener:

  • "Der bør undervises i flerniveaulager og VM, samt deres effekt på køretid". Check, det undervises der i på de obligatoriske kurser maskinarkitektur" og "operativsystemer", i hvert fald da jeg tog dem for (uha!) 10 år siden.

  • "Der bør undervises i, hvordan man analyserer programmers asymptotiske køretid mhp. flerniveaulager og VM." Dette gøres til dels i de to nævnte kurser og (SVJV) stadig i "algoritmik"-kurset. Til sammen bør det give studerende værktøjer nok til at inddrage VM og lagerhierarki i køretidsanalyse, skulle det være nødvendigt.

  • "Der bør undervises i, hvordan nye algoritmer designes mhp. nær-optimal kørsel på flerniveaulager under en VM." På DIKU gør Jyrkki dette, men som kandidatkurser og projekter frem for obligatoriske kurser. Jeg synes egentlig, det er fair nok. Det er kun vigtigt for nogle, og der er et utal af mindst ligeså vigtige (ja, EMM vigtigere!) datalogiske emner, som ligeledes må henføres til uddannelsens valgfrie del. Det vigtigste er, at alle på den obligatoriske del får begrebsapparatet til at at se, hvilke redskaber er nødvendige til en given opgave og til hurtigt at læse op på dem, når de skal bruge dem.

Det sagt, har jeg virkelig svært ved at rede trådene ud i dine mange anklager mod datalogerne, hvilket gør det sværere at svare dig fornuftigt. Vil du ikke prøve at sammenfatte, så utvetydigt som muligt, hvad du helt præcis mener, vi gør, som er helt forkert?

Og - jeg tror det næppe, men: Når folk nu har givet dig en spandfuld artikler fra 90'erne som beskriver den dybe tallerken før du kom med din, vil du så ikke give een eller anden form for anerkendelse af, at det ikke er noget man først er begyndt at se på "for 2-5 år siden"?

57
17. juni 2010 kl. 15:22

Først: 1988 er toogtyve år siden, ikke tolv. Altså:</p>
<pre><code>... 12 år efter VM blev opfundet
... 4 år efter IBM/370 gjorde VM mainstream
... -1 år efter VAX/11 gjorder det _rigtig_ mainstream
</code></pre>
<p>

Æv, edit udløber for hurtigt. Ak! Min tåbelige DIKU-uddannelse lærte mig aldrig at trække fra. Rettelse:

... 14 år efter VM blev opfundet
... 6 år efter IBM/370 gjorde VM mainstream
... 1 år efter VAX/11 gjorder det <em>rigtig</em> mainstream

Men resten står jeg ved - og vil forsvare til min dødsdag!

58
20. juni 2010 kl. 12:03

Hvem opfandt homogene koordinater til hurtige transformationer i Maya 3D og computerspil?

Hvem finder på at bruge lazy products til at optimerer query træer i SQL engines?

Hvem udvikler monte carlo og branch and bound algoritmer til brug i proteinfoldning i Medicon Valley?

Det er i hvert fald ikke kernel hackere!

Nej, det er PhD'erne. De er toppen af fødekæden og har langt større værdi for Danmark end de commodity udviklere, som PHK gerne vil have, og som ethvert land kan producere.

Så jeg vil gerne tale for to ting:

  1. Flere optagende på datalogistudiet
  2. Flere arbejdspladser i Danmark som kan bruge PhD'er
60
20. juni 2010 kl. 12:37

Nej, det er PhD'erne. De er toppen af fødekæden og har langt større værdi for Danmark end de commodity udviklere, som PHK gerne vil have, og som ethvert land kan producere.

For det første har jeg ikke på noget tidspunkt har sagt eller skrevet at der ikke skulle forskes mere.

For det andet er der ikke mange phd'er der kan prale med at have gjort en forskel på statsbudgettet med 100 mio kroner.

Men en eller flere inkompetent personer har af ren skræk for hvad der kunne ske, forsøgt at feje en besparelse på 100 mio kroner i politiets IT systemer ind under gulvtæppet.

Det er et meget tungtvejende argument for at Danmark mangler operationelle IT kompetancer, helt uanset hvad situationenen måtte være med hensyn til phd'ere.

Poul-Henning

64
20. juni 2010 kl. 15:35

@Poul-Henning:

Men en eller flere inkompetent personer har af ren skræk for hvad der kunne ske, forsøgt at feje en besparelse på 100 mio kroner i politiets IT systemer ind under gulvtæppet.</p>
<p>Det er et meget tungtvejende argument for at Danmark mangler operationelle IT kompetancer, helt uanset hvad situationenen måtte være med hensyn til phd'ere.

Uenig, det er ikke IT kompetencer, de har fejlet hér: Det er et manglene overblik i de administrative og politiske lag her i landet.

Og det er ikke kønt (men en helt anden diskussion)

61
20. juni 2010 kl. 13:47

For det andet er der ikke mange phd'er der kan prale med at have gjort en forskel på statsbudgettet med 100 mio kroner.

Hæh, jeg tror faktisk, det er omvendt - at de fleste PhD'er i datalogi gør en forskel på over 100 mio kroner.

En jeg kender arbejder fx hos Resound med at forstærke tale og svække andre lyde, som giver dem fordele i forhold til udenlandske konkurrenter.

Hvis vi nu antager, at han er ansat i 30 år og Resound har en omsætning på 3 mia kr hvert år. Og at han tilhører en gruppe på 50 ud af i alt 500 ansatte, som har 90% af den intellektuelle værdi i firmaet. Altså bare for at opstille nogle proportioner.

Det er ikke fordi, jeg vil regne sådan med tal (det kan man finde nogen, som er meget bedre til end jeg) - jeg vil bare illustrere pointen.

Nåja, og du kommenterede aldrig på den moderne lærebog, jeg linkede til. Og jeg kan fortælle dig, at den som bruges i det obligatoriske kursus Netværk er lige så moderne.

63
20. juni 2010 kl. 13:52

Nu er denne tråd ved at være lige lovligt lang men tillad en "grumpy old" programmør at tilføje nogle ting.

Jeg synes at der er brug for både PhD'ere og "commodity" programmører.

Desværre er det således at skolerne p.t. uddanner programmører der løber hjem til mor når de ser en pointer. Programmører som PHK, Linus Torvalds, Ritchie, Kernigan, Thompson, Bill Joy og Pike, bare for at nævne få, er uhyre svære at finde. Og det er lige meget om de haver en PhD i bunden.

De fleste får arbejde hvor man koder for virtuelle miljøer som .NET og Java. De er nutidens Cobol programmører. Se bare den rameskrig når Apple lavede om i udvikler betingelserne for iPhone/IPad. Ikke noget galt i det at mange udvikler til en mer udvikler venlig platform. Måske er det endda et sunhedstegn.

Jeg arbejder på en arbejdsplads hvor vi beskæftiger os med textanalyse for personer med svær dyslexi. Vi har to PhD'ere. Den ene indenfor statistik og den anden indenfor lingvistik. Våres produkt skulle ikke findes uden dem. Selv arbejder jeg med den del der berør de intime dele af OSX/Cocoa. Det er dejligt at vide at Mach kernen kommer fra PhDere i Carnegie Mellon og FreeBSD delen kommer fra folk af kaliber som PHK.

Jeg vil ikke ind i den politiske dimension fordi den forstår jeg ikke. Min hjerne er forkert skruet sammen til den slags. Og det er måske der vi har det største problem.

Med venlig hilsen fra Sverige, Björn Sveinbjörnsson

62
20. juni 2010 kl. 13:48

Hæh, jeg tror faktisk, det er omvendt - at de fleste PhD'er i datalogi gør en forskel på over 100 mio kroner.

En svale gør ingen sommer, du har kun først sandsynlighedsbevis min påstand ("der er ikke mange...")

Du er meget langt fra at løfte din bevisbyrde: "at de fleste..."

Et interessant filosofisk spørgsmål er, på hvilken side af opgørelsen skal vi regne alle de phd'er der rendte af landet, fordi der intet var for dem at lave i Danmark ?

Poul-Henning

65
21. juni 2010 kl. 00:08

... og i kurset om research fik han: -3!

Du er meget langt fra at løfte din bevisbyrde: "at de fleste..."

Og stadig er jeg milevidt længere med at løfte den end dig. Men PhD'er sidder jo netop med hænderne dybt inde i virksomhedens forretningsgrundlag på denne måde.

Nå, men nu til sagen. Hvorfor ignorerer du konsekvent mine beskrivelser af nutidige lærebøger med realistiske hands-on opgaver, som bruges på bachelordelen i datalogi?

Klik på SIS linket ud for hvert kursus på http://diku.dk/For_studerende/kurser/

Så kan du fx se følgende for Maskinarkitektur:

Kunne differentiere mellem RISC og CISC akitektuter. Kunne programmere på assembler niveau. Resonere omkring fordele og ulemper ved pipelining. Administrere cache og hukommelses hierakier Reflektere over fordele og ulemper ved bus-implementationer.

Netværk:

HTTP, FTP, UDP, TCP, IMAP, POP3, DNS, IPv4, IPv6, RSVP, TDM, FDM, Aloha, slotted ALOHA, CSMA, CSMA/CD, Token Ring, Ethernet, WiFi, og WEP ... denial-of-service attacks ifm. TCP... flow control og congestion control og kunne vise eksempler på disse ifm. TCP. Beregne båndbredde og latenstider for en række forskellige netværksforbindelser herunder via fiber, mikrobølge, alm. telefonmodem, ADSL, og satellit. Anvende en packet sniffer ... error detection og error correction herunder gennemgå et ikke-trivielt eksempel på error correction... spoofing, de-nial-of-service, packet sniffing

Jeg har også givet dig copy/paste fra opgavetekster fra bøger og links til bøgerne (hurra for Google Books!).

Der er et direkte mismatch mellem hvad du påstår i dine blogindlæg og hvad, der undervises i. Fx omkring lagerhierakier.

Der hvor datalogi så adskiller sig fra fx datamatikere og andet er, at vi får en masse formler og teori med oveni, som tillæg.

Men gæt, om ufejlbarlige Poul-Henning Kamp ikke også bare vil ignorere dette indlæg totalt.

50
17. juni 2010 kl. 11:22

Og idag, 12 år senere, er [VM] stadig ikke med i O() funktionen i CS-bachelor niveau ?</p>
<p>Jeg er godt klar over at computer-hardware har udviklet sig specielt sig hurtigt, i forhold til andre teknologier, men burde den tilhørende software disciplin, ikke være i stand til at følge lidt hurtigere trop end det vi ser her ?

Store-O-notation er [i]ikke[/i] en softwarediciplin!

O() anvendes i algoritmiske sammenhænge, algoritmer anvendes i software - OK. Men det nytter ikke noget at inficere O() med sager der lugter af hardware, for O() har mange anvendelser i områder der ikke er relateret til hardware og IT, men er rent teoretiske.

O() er en [i]matematisk[/i] tilgang til algoritmer, ikke datalogisk.

Dit forslag om at datalogien nu skal bemægtige sig O() ved at inficere det med VM, fortjener derfor kun én reaktion: "[b][i][sneering and aiming his gun] Get off my lawn![/i][/b]"

:-)

PS Jeg håber jeg har misforstået noget et sted i dine udsagn, Poul-Henning, for VM-bindinger i O() virker rigtig bizart for mig at se...

53
17. juni 2010 kl. 13:01

O() anvendes i algoritmiske sammenhænge, algoritmer anvendes i software - OK. Men det nytter ikke noget at inficere O() med sager der lugter af hardware, for O() har mange anvendelser i områder der ikke er relateret til hardware og IT, men er rent teoretiske.</p>
<p>O() er en matematisk tilgang til algoritmer, ikke datalogisk.

Notationen er der ikke noget galt med som jeg ser det. Hele ideen med O() notationen er at beskrive et ubekendt leds asymptotiske udvikling når N bliver stor (lettere uformelt sagt). Det handler om hvad du bruger notationen til og hvor du bruger den.

De fleste algoritmebøger (CLRS - Introduction to algorithms inklusive) starter ud med at nævne den model de arbejder i. Som regel hedder den model RAM (Random Access Machine) og i den model er der ikke noget cache-hieraki. Derudover bliver stort set hele algoritmens køretid smadret sammen under een stor store-Oh tilnærmelse. Grunden herfor nævnes også: I langt de fleste tilfælde er det tilstrækkeligt til at afgøre forskelle på algoritmernes køretid i praksis. Med andre ord er det en forbandet god indikator - set i forhold til hvor svær den er at udrede.

Du kan sagtens skifte maskinverden til noget andet end RAM, eller medtage så mange faktiske led som muligt og gøre det asymptotiske O()-led minimalt. Derved opnår du en bedre viden om køretid, teoretisk set. Men det er i praksis nemmere at måle sig frem til hvad der virker på den givne maskine med det givne workload.

I det konkrete tilfælde med B-heap versus en traditionel binary heap har notationen ikke fejlet. Den siger, så vidt jeg lige kunne sjusse mig frem til, at kompleksiteten på de to algoritmer er ens. Hvilket jo også er rigtigt nok, givet begrænsningerne af at have et enkelt asymptotisk led til stede, og kun det. Med andre ord: Kører du algoritmen på den mytiske RAM-maskine med uendeligt meget hukommelse forventes det at de to algoritmer performer ens, påvirket af en konstant faktor i forskel, når N bliver tilstrækkeligt stor.

Papversionen for tl;dr: O()-notationen gør det forventede, man skal bare kende dens begrænsninger for at vide hvornår den ikke kan benyttes.

48
17. juni 2010 kl. 09:29

Og idag, 12 år senere, er det stadig ikke med i O() funktionen i CS-bachelor niveau ?

Kender du i det hele taget forskellen på O() og o()?

47
17. juni 2010 kl. 08:49

[quote]Hvis ikke der er tygget drøv nok på dette kan man jo starte med Aggarwal og Vitter fra 1988 (Communications of the ACM) og tygge sig fremad.

... 24 år efter VM blev opfundet.

... 16 år efter IBM/370 gjorde VM mainstream

... 11 år efter VAX/11 gjorder det rigtig mainstream. [/quote]

Det er jo dig som siger at der kun er forsket i emnet de sidste 2-5 år. Jeg påstår ikke at VM's ikke opstod før algoritmikerne begyndte at studere dem.

Iøvrigt kikker Knuth også på hukommelseshierarkier i volume 3 (1973). På side 5 fx.

Og idag, 12 år senere, er det stadig ikke med i O() funktionen i CS-bachelor niveau ?

Jeg kender ikke undervisningen rundt omkring. Men jeg er enig i at det er vigtigt.

45
17. juni 2010 kl. 01:49

Og idag, 12 år senere, er det stadig ikke med i O() funktionen i CS-bachelor niveau ?

Ja undskyld, men du er simpelt hen håbløs til at lave forarbejdet før du kommer med påstande. Gør venligst følgende:

  1. Klik på http://sis.ku.dk/kurser/viskursus.aspx?knr=120835 - dette er et obligatorisk bachelorkursus.

  2. Scroll ned til lærebøgerne. Der står "Computer Organization and Design". I pensum og til eksamen indgår kapitlerne om L1 og L2 cache, RAS/CAS lines, paging og swapping. I detaljer, dvs. statisk memorys opbygning af flip/flops, paging tabellen, formler for betydning og optimal størrelse af L1's størrelse, osv, osv.

  3. Klik nu på http://sis.ku.dk/kurser/viskursus.aspx?knr=110935 og scroll ned til lærebøgerne. I Introduction to Algorithms lærer vi bl.a. om tidskompleksitet, herunder store-O notation. Igen et obligatorisk bachelorkursus.

Søgetræer er også obligatorisk pensum på bachelordelen, og clustered, balancerede, whatnot, er valgfrit.

Nu skriver du, og lad mig gentage:

Og idag, 12 år senere, er det stadig ikke med i O() funktionen i CS-bachelor niveau ?

Tror du ikke, den studerende selv kan kombinere lærdommen fra kurset Maskinarkitektur med lærdommen fra kurset Algoritmer?! Eller brokker du dig over, at man ikke ske-fodres ved at stoppe O-konstant-leddet ind i søgetræet fra bogforfatternes side?

Der er tonsvis af ting, som studerende selv forventes at kombinere fra forskellige kurser. Matricer i et matematikkursus bruges i grafikkurset. Rekursive datatyper fra kurset Funktionsprogrammering bruges i Oversættere.

Hvis deres speciale har med performance at gøre, så skal de nok kombinere dette også. Ellers har de nok et speciale, hvor performance ikke har betydning.

46
17. juni 2010 kl. 02:31

Åh ja, og en quote mere fra dig:

Men jeg ville meget hellere høre, fra ham og andre dataloger, om det er på tide at "rigtige dataloger" opgraderer deres hardware fra "Viking nummer 2" til computere som dem vi andre bruger ?

Men tag et kik på lærebogen på et obligatorisk bachelorkursus: http://tinyurl.com/342gzgp

Copy/paste fra en opgave om cache:

Assume there are three small caches, each consisting of four one-word blocks. One cache is fully associative, a second is two-way set associative and the third is direct mapped. Find the number of misses for each cache organization given the following sequence of block addresses: 0, 8, 0, 6, 8. Use word addresses.

Copy/paste om virtual memory:

In virtual memory systems, only a write-back policy is practical because of the long latency of a write to the lower level of the hierarchy (disk). The rate at which writes are generated by a processor generally exceed the rate at which the memory system can process them, even allowing for physical and logically wider memories and burst modes for DRAM. Concequently, today lowest-level cache typically use write-back.
The rate at which writes are generated may also be less than the rate at which the memory can accept them, and yet stalls may still occur.

I bogen findes virkelig detaljerede formler og beregninger og eksempler hvor man virkelig går i dybden. Og det er som sagt obligatorisk på bachelordelen.

Og som jeg læser din kritik ønsker du, at man sammenfletter kurserne Maskinarkitektur med Algoritmer. Well, igen, det er jo en opgave for de studerende, hvis deres speciale kræver, at man presser det sidste konstantled ud af deres O-notation.

Dernæst må du gerne æde dine ord om Viking II og for en gang skyld indrømme, at du tog fejl :-p

44
17. juni 2010 kl. 01:07

Come back here and take what's coming to you! I'll bite your legs off!!

At fortsætte dit rant svarer jo til at klage til sin matematiklærer som har demonstreret at at tips giver bedre odds end lotto, såfremt man kan sige noget om det sandsynlige udfald af fodboldkampene -- uden at fortælle at fodbold handler om at score flest mål (i tiltro til at gymnastiklæreren klarer denne side af sagen).

Din kæphest er ventet på limfabrikken.

29
16. juni 2010 kl. 14:00

Faktum er, at vi har haft VM i 30+ år, men datalogerne er i bedste fald begyndt at interessere sig for det indenfor de seneste 2-5 år og langt de fleste CS uddannelser har stadig ikke fået memo'et...

Ud over at det ikke passer, så har der været andre faktorer som har gjort det mindre interessant. Det er eksempeltvist først da 64-bit arkitekturer bliver hvermandseje at man kan tillade sig blindt at mmap(2)'e store filer ind i hukommelsen. Jeg giver dig helt klart at det er en superlækker model at arbejde under.

En anden ting er hvor elendigt forskellige UNIX-kernels behandler MADV_DONTNEED/MADV_FREE til madvise(2). Jeg ville give meget for at få ordentlig styr på det - for damn det ville hjælpe een når man skriver Garbage Collectors.

Hele VM-laget har en historie på 30+ år og den historie skal tages med når man kigger på konkret hvor meget der var brug for det. Det er vistnok folklore at man tilbage i 1985 kunne vinde meget ved at undgå page-faults (der som regel blev paget ind fra disk den gang), men det er før min tid.

30
16. juni 2010 kl. 14:06

@Torben:

Siger du oprigtigt, at lærebøger ikke behøver at forholde sig til ændringer der er sket de sidste 30+ år ?

Så groft ville jeg ikke have turdet formulere min pointe...

@Jesper:

Jeg er ikke enig i at det kun er 64bit der har gjort VM interessant, det har det været hele tiden, men vi kan hurtigt blive enige om at 64bit har taget lidt for lang tid med at slå igennem.

Poul-Henning

PS: Du ved godt hvem der opfandt MADV_DONTNEED og MADV_FREE, ikke ? :-)

28
16. juni 2010 kl. 13:22

Men hvis der er "masser af opmærksomhed", hvor finder jeg da de nye lærebøger, hvor O() ikke bare gælder for ZX81 ?

I de fleste områder dækker lærebøger kun en svindende del af den viden, der findes. Derfor bruges der typisk artikler i de avancerede kurser.

Så hvis du baserer din opfattelse af, hvad dataloger ved og ikke ved, udelukkende ud fra at se på lærebøger, så går du grumme galt i byen. Lærebøgerne bruges til de introducerende kurser, og der er det fint nok, at man simplificerer problemerne og løsningerne lidt -- man skal jo lære at kravle før, man kan gå.

49
Indsendt af Anonym (ikke efterprøvet) den tor, 06/17/2010 - 10:50

I de fleste områder dækker lærebøger kun en svindende del af den viden, der findes. Derfor bruges der typisk artikler i de avancerede kurser.

Ja det er også, hvad jeg oplevede på DTU.

Men... kan du anbefale en god lærebog om I/O-effektive og cache-oblivious algoritmer eller findes der "kun" artikler om emnet?

54
17. juni 2010 kl. 13:21

Men... kan du anbefale en god lærebog om I/O-effektive og cache-oblivious algoritmer eller findes der "kun" artikler om emnet?

Mig bekendt er der ikke nogen deciderede lærebøger, men Lars Arge har skrevet nogle gode forelæsningsnoter, som jeg vist også har linket til tidligere:

http://www.daimi.au.dk/%7Elarge/ioS06/ionotes.pdf

De giver en god introduktion til emnet.

27
16. juni 2010 kl. 13:21

Faktum er, at vi har haft VM i 30+ år, men datalogerne er i bedste fald begyndt at interessere sig for det indenfor de seneste 2-5 år og langt de fleste CS uddannelser har stadig ikke fået memo'et...

Det er jo direkte forkert - du har f.eks. fået serveret link på link fra 1990'erne om dette.

Du skrev en artikel med et fint budskab, brug VM'en med omtanke, den er til for det samme, men skrev dig så varm undervejs at artiklen blev et 'rant', mens du glemte du at checke om andre havde været der før, hvad der havde været (måske formuleret lidt anderledes): http://tinyurl.com/32x9orj

Vejen tilbage var ikke køn.

22
16. juni 2010 kl. 12:10

Jeg synes faktisk blot at de to papers understreger min pointe: Dataloger aner ikke hvad virtuel hukommelse er, eller hvordan det skal bruges.

Så læs ordentligt efter:

The second simulates virtual memory and applies the LRU (Least Recently Used) page-replacement algorithm.
In this environment the programmer can use the memory as if it were an internal array. The simulator keeps track of the pages in primary memory and counts the number of page transfers.

Godt nok er det virtuelle lager simuleret, men det gør du jo også:

The VM system is simulated with dirty tracking and perfect LRU page replacement.

25
16. juni 2010 kl. 12:45

Jeg vil blot bidrage med et par papers mere som med al tydelighed viser at der er dataloger, der har tænkt over dette.

Cache-Oblivious Algorithms in Practice, speciale fra 2002: http://www.dunkel.dk/thesis/thesis.ps

Data structures and algorithms in a two-level memory, speciale fra 1997http://www.diku.dk/forskning/performance-engineering/Publications/fadel-jakobsen96.ps

Begge analyserer algoritmer, herunder prioritetskøer, ud fra et virtual memory synspunkt Og der er flere, selvfølgelig også udenfor DIKU.

(bortredigerer de spidse kommentarer - da jeg havde krydset med Poul-Hennings beklagelse)

24
16. juni 2010 kl. 12:43

beklager, det overså jeg.

Men så er det da kun endnu mere forkasteligt at de ikke undersøgte hvad VM pressure betød for deres resultater...

Poul-Henning

17
16. juni 2010 kl. 10:16

IO modellen kræver ikke nødvendigvis at man laver IO-scheduling manuelt. Det er helt fint at anvende operativsystemets io-scheduling, dvs. implementere algoritmen som en helt traditionel in-memory datastruktur og så ellers lade operativsystemet page sider ind og ud efter behov. Det kræver selvfølgelig at operativsystemet leverer fornuftig caching hvis man skal kunne lave worst-case analyse af algoritmen, men anvendes eksempelvis LRU til at expire pages, så er det fuldt tilstrækkeligt til at give worst-case garantier på antallet af page swaps.

19
16. juni 2010 kl. 10:40

Jeg vil i øvrigt lige tilføje, at for enhver som har har taget kurset i IO-effektive algoritmer, så burde det være helt trivielt at beskrive en algoritme til at lave en IO-effektiv heap der nøjes med O(log_B(N)) IO'er pr. operation, hvis man ellers har fulgt med i kurset. Det er samme worst-case bound som et B-træ. En heap er dog noget nemmere at implementere, da man ikke behøver at rebalancere en heap.

Den algoritme til IO-effektive heaps der beskrives i ovennævnte artikel er langt mere effektiv (ca. en faktor B) i worst case, men kræver til gengæld også en stor mængde hukommelse til rådighed.

Tilføjelse: B er i ovenstående sammenhæng størrelsen på en page.

16
16. juni 2010 kl. 10:01

Torben:

... om hans B-heaps er en bedre løsning til hans problem end de external heaps, der er beskrevet i den nævnte artikel.

Poul-Henning:

Det er de ikke.

Mente du ikke det modsatte? Altså at din B-heap er bedre?