Basic personligt

Daniel Brahneborgs blogg

Dags för nästa nivå

Tidigare i höstas konstaterade jag att det inte kommer bli någon masterexamen för min del. Att sluta plugga kändes däremot inte aktuellt, att lära sig nya saker är alldeles för kul. En idé jag funderat på ganska länge är att komplettera med mer matte, för att åtminstone komma upp i en kandidat där. Examina i flera ämnen är kul. Tyvärr skulle det kräva både en rejäl repetition av derivator och integraler, samt fler kurser om det. Jag kanske hamnar där förr eller senare ändå, men just nu kändes det inte speciellt lockande.

En av lärarna på testkursen jag gick i våras pratade under en rast om konceptet industridoktorand, och jag lyckades aldrig riktigt släppa det. Min uppfattning om forskarutbildning var innan dess att det krävde att man var anställd som lärare på ett universitet, samtidigt som man gjorde vad man nu mer behövde göra. Nog för att det är kul att prata om saker som jag tycker är intressanta, men det är ett ganska stort steg därifrån till att vara någon typ av någorlunda pedagogisk lärare.

Tydligen finns en annan lösning, och det är att bli just industridoktorand. Ens normala jobb krymper då till 20%, medan forskarutbildningens fyra år tar de övriga 80%, så totalt är det ett projekt på fem år. Tricket som gör att man inte även får en lönesänkning på 80% (det vore en smula suboptimalt) är att man fokuserar kurser och forskning på områden som arbetsgivaren har nytta av. Företagets produkter kan bli bättre, man kan hålla interna seminarier för sina kollegor, och så vidare. I en del fall sker även viss sponsring från någon stiftelse.

Många mail senare är det därför exakt det jag ska göra, med start nu vid nyår. Det återstår viss formalia, men nu finns tillräckligt många påskrivna papper och dokumenterade planer för att risken att det inte ska bli av ska vara försumbar. De närmaste åren kommer därmed bestå av kurser, en väldig massa läsande, skrivande av några vetenskapliga artiklar, diskuterande, resande, och en del annat. Därefter, vilket alltså blir någon gång i början på år 2022, kan jag använda titeln doktor. Ämnet är datavetenskap, området någonstans mellan test och nätverk. Jag kommer börja med ett testrelaterat problem, så får jag se vad som händer sedan. Eftersom jag har gått senaste kurserna på MDH i Västerås är det där jag kommer ha mina handledare.

När jag började på universitetet i Umeå 1989 visste jag ungefär vad jag skulle göra fram till 1993. Det är lite samma situation nu, men med en signifikant skillnad. Nu vet jag, efter NaNoWriMo, magisteruppsatsen och de kurser jag gått sedan dess, att mycket av det jag kommer lära mig är saker jag varken vet att de finns eller ens kan föreställa mig. Både om datavetenskap i sig, men kanske ännu mer om andra ämnen och hur jag själv fungerar och vad jag tycker är kul och intressant. Jag vet att de där sekundära insikterna alltid kommer, men också att de alltid är oförutsägbara. Numera är de min drog, och jag ska få jaga dem i fem år framåt.

Jobbigt? Tja, kanske. Ordet “förmodligen” ligger nog närmare sanningen, men jag föredrar total förnekelse på just den punkten. Skitkul? Definitivt.

November 18th, 2016 Posted by Daniel Brahneborg | blogg | no comments

Studier

Ju mer jag tittar på och förstår av min lista på avklarade kurser, desto mer förvirrad blir jag. Både ämnen, nivåer och antal är så knäppa att jag borde skämmas. Att nivåerna helt har ändrats mellan när jag började plugga och nu, gör det i och för sig inte enklare. När jag började plugga fanns nivåerna A-E, som var och en representerade en termin. För en fyraårig magisterexamen skulle man då ha 30 poäng (dvs en termin) på varje nivå mellan A och D, plus lika mycket till av andra ämnen. Jag har länge trott att av de återstående 120 poängen ska 60 poäng vara inom ett sidoämne, matte i mitt fall, och 60 poäng helt valfritt (hej finska, evolutionsbiologi osv).

Så tittar jag på mina kurser, och där ser det väldigt annorlunda ut. 30 poäng A-data i och för sig, heja mig. Fast sedan bara 21 poäng B. Hur har jag då fått behörighet till massa kurser på högre nivå? Sedan har jag 60 jäkla poäng på C-nivå. Därefter blir det fint igen med 30 poäng på D-nivå, plus 30 poäng för D-uppsatsen. Nackdelen med alla de där C-poängen, är att jag då bara hann med 45 poäng matte, nästan allt på A-nivå. Det är inte alls samma sak som 60 poäng varav hälften A och hälften B. SÅ mycket matte kan jag i alla fall.

Numera har de ändrat lite, så att A-C räknas som grundnivå, dvs upp till en kandidatexamen, och D-E är avancerad nivå för magister och master. Som tur var så räknades 3 av C-kurserna nu som avancerade, vilket gjorde att jag faktiskt har just 30 poäng på avancerad nivå istället för bara 7,5.

För den masterexamen som jag siktar på att nå fram till någon gång nästa år, behövs utöver magisterexamen 15 poäng till på avancerad nivå och 15 poäng uppsats/exjobb, samt 30 poäng valfritt. Vårens kurs i testning gav mig 7,5 poäng, och 22,5 poäng av de där 30 jag har nu jobbat ihop (affärsredovisning, Androidprogrammering, evolutionsbiologi). Att jag kommer ha 216 poäng data av 300 gör förhoppningsvis ingenting, eftersom det inte gjorde något att jag hade nästan 180 poäng av 240 för magistern.

Problemet är det där med matten. Jag har länge tänkt att eftersom jag alltid har sagt att programmering och matte är samma sak, och jag redan har massa mattepoäng, borde en mattekandidat vara ett överkomligt nästa steg. Tyvärr skulle det alltså kräva 22,5 poäng B-kurser, 15 poäng C-kurser och 15 poäng C-uppsats innan jag var klar. De övriga 90 poängen kan jag återanvända från mina andra kurser, vilket är väldigt praktiskt. På kvartsfart, med en kurs på 7,5 poäng per termin, har jag då att göra i 5 terminer, plus en för uppsatsen (som jag antar inte skulle kräva ett helt år). Tre år är lång tid, för något jag trodde skulle vara nästan gratis. Fan också.

Edit: Med samma logik som för datapoängen kanske det skulle räcka med 15 poäng B-matte, men det är ändå 4 hela terminer plus ett exjobb.

Hade jag varit lite intelligentare och mer strategisk, skulle jag ha valt bort hälften av de där poängen i C-data och lagt dem på B-matte stället. Jag hade fortfarande haft tillräckligt med poäng för en dataexamen, men då hade det räckt med 30 poäng C-matte för att få ihop en kandidat nu. Någon får gärna uppfinna en tidsmaskin så jag kan åka tillbaka till 1990 och visa det här blogginlägget för mig själv.

Alternativet att sluta plugga efter masterexamen är inte med på skalan. Det finns minst två alternativ till, men vilka de är får vänta till ett senare inlägg.

Edit 2: Efter en kontroll på antagning.se såg jag att jag faktiskt hade läst en C-kurs i matte också, “Abstrakt Algebra”. Med bara 7.5 poäng på B-nivå i ryggen, plus att den kursen nu dessutom ligger på avancerad nivå, hamnade den på listan med kurser jag hoppade av.

June 18th, 2016 Posted by Daniel Brahneborg | blogg | no comments

Multitrådad statemaskin

Statemaskiner (ja, det heter säkert “tillståndsmaskiner” på svenska, men datorer ska prata engelska och det där ordet blir alldeles för svenskt) har länge varit ett av mina favoritverktyg för att implementera komplexa beteenden. En sådan består av ett antal tillstånd varav ett är det man startar i. Varje indata gör att man flyttar till ett annat tillstånd. Indatat kan vara ett tecken, en händelse som en nytt inkommande data, eller något annat. I varje tillstånd vet man exakt vilket indata som är giltigt, och när indatat tar slut är det enkelt att veta om sekvensen var ok genom att kolla om tillståndet man är i är godkänt som sluttillstånd.

I en multitrådad värld blir det lite mer komplicerat. Till att börja med krävs en mutex, så att man inte får flera trådar som pillar på statemaskinens fält samtidigt. Lämpligen har man då en handle_event(), som kollar vilket tillstånd man är i och uppdaterar maskinen till dess nya tillstånd, allt inom en låst mutex.

I vissa övergångar ska det hända någonting. Socketar ska öppnas eller stängas, data ska hämtas eller skickas iväg, eller vad det nu är. Inga problem, det är ju bara att lägga in det i handle_event? Nej, för vissa saker kan ta lång tid att utföra. Om det görs av handle_event, kommer det ske i den tråd som triggade eventet, och låsa den tråden så att den inte kan göra någonting annat.

Istället kan man då ha en loop i en separat tråd, som bara anropar statemaskinens run() tills den har nått ett sluttillstånd. Eventet “connect” flyttar maskinen till tillståndet “do_connect”, och när run() körs nästa gång, kommer den utföra uppkopplingen. När den är klar, går den vidare till tillståndet “connected”. På det sättet görs uppkopplingen bara en gång, och av rätt tråd. Å andra sidan gör det att andra trådar som vill skicka något event till den här statemaskinen kommer stanna tills uppkopplingen är klar, och så är vi tillbaka ungefär där vi började. Fast bara nästan.

Här kan man använda asynkrona funktioner istället, som antingen kan polla med jämna mellanrum eller få en callback från när de är klara. När anropet är gjort, stannar man i ett väntetillstånd tills dess att callbacken kommer. Frågan är vad man gör i den tråden under tiden. Den kan ju inte anropa run() hela tiden, för då har vi en busywait som stjäl cpu i onödan.

Den enklaste lösningen på detta är en “condition variable”. Statemaskinens tråd (den som anropar run-funktionen) hänger då på en sådan när den inte har något bättre för sig. När det kommer ett nytt event, avslutas handle_event med att väcka den som väntar på variabeln (dvs run-tråden). Det listiga är att anropet som gör att run-tråden börjar vänta, samtidigt släpper maskinens mutex, för annars skulle ju de andra trådarna inte komma in i handle_event. Efteråt är mutexen låst i run-tråden igen. I handle_event får man då: lock, update state, signal cond, unlock.

I run är det lockande att göra ungefär likadant: lock, check state, do stuff, kanske wait on cond, unlock. Symmetriskt och bra. Tyvärr fungerar det inte, eftersom det där “do stuff” kan resultera i ett man postar något event tillbaka till sig själv. Det går inte, eftersom maskinens lås redan är taget. Alltså flyttar man allt “do stuff” till efter “unlock”. Låset är då taget bara under den tid det tar att tilldela en variabel eller två, och sannolikheten blir exakt noll att låset är inblandat i någon form av deadlock.

En annan lösning, om huvuddelen av ens event kommer via sockets, är att använda något som libevent. Istället för att hänga på en cond, hänger man då i epoll eller liknande. Tyvärr går det inte att hänga i epoll och på en cond samtidigt, så för att handle_event ska kunna väcka huvudtråden använder man en intern pipe. Huvudtråden väntar på sina vanliga sockets och den här pipen, och om andra trådar vill att maskinen ska vakna så skriver de en byte på pipen efter att ha uppdaterat maskinens tillstånd. Maskinen vaknar då, läser det nya datat, gör det som behövs för dess nya tillstånd, och så hänger den igen.

June 5th, 2016 Posted by Daniel Brahneborg | blogg | no comments

Testning utan droger

För ungefär 15 år sedan hamnade jag för första gången på ett företag som hade en speciell grupp människor som primärt arbetade med att testa den kod som vi programmerare producerade. Efter att ha fixat koden så att de inte längre hittade några fel, rapporterades exakt noll buggar i fält. Det var uppenbart att det inte bara handlade om slump vilket data man testade med, men längre än så kom jag inte. Jag hade länge en misstanke om att det involverade droger.

Till min framtida Master-examen behöver jag ytterligare två kurser (eller 15 hp, mer exakt) i datavetenskap på avancerad nivå, så nu under våren går jag en kurs i just testing hos MDH i Västerås. Några månader med föreläsningar, vetenskapliga artiklar och egna uppgifter har bilden klarnat rejält. Istället för att hela området är en vit yta har jag åtminstone en översiktlig karta nu.

Första pusselbiten är att se utvecklingsprojekt ur tre perspektiv. Först har man omvärldens önskemål på systemet. De formaliseras i en specifikation, som i sin tur implementeras i kod. De tre har en exakt överlappning varje gång som en enhörning och en flygande gris tillsammans får en fertil avkomma.

Nästa pusselbit är synen på program som funktioner som omvandlar indata till utdata. Att skapa testfall handlar då om att hitta bra och minimala subset av det där indatat. T.ex. brukar det vara mer intressant att skicka in -1, 0 och 1 än 2, 3 och 4. Testar man med 2 och 3, behöver man förmodligen inte testa med 4 och 5 också.

Även processen att skapa testfall kan ses som en sådan här funktion. När indatat är kod, består funktionen av verktyg som Valgrind och kompileringsvarningar. De är enkla att använda, och är en bra början. För mig är de också den lägsta nivån som är acceptabel. Program kan ha buggar, men om Valgrind gnäller så är programmet opålitligt. Då får man saker som Heartbleed.

När indatat är omvärldens önskemål blir funktionen att se hur slutanvändarna faktiskt använder systemet, hur blicken rör sig över skärmen, om det finns funktionalitet som fattas, osv. Här börjar det gränsa till psykologi och beteendevetenskap, så det är lite för långt utanför min kompetens.

Min senaste besatthet är istället området däremellan. Om specifikationerna är tillräckligt formaliserade (XML, tillståndsdiagram i UML och liknande), finns det några olika typer av verktyg man kan köra för att få ut serier med testdata. Antingen har man sedan ett annat program som tar det testdatat och matar den riktiga applikationen med, eller så har man det som protokoll för mer manuella tester. Poängen är att man får minimalt med testfall som täcker maximalt med kombinationer av indata.

Antag att man har 10 parametrar som kan vara 0 eller 1. Att testa alla kombinationer av dessa ger 1024 testfall. Med fler parametrar som kan ha fler värden, växer det där antalet snabbt. Istället börjar man med 0 överallt, så blir testfall 2-11 när man ändrar en parameter i taget till 1. På 11 testfall har man då täckt in samtliga värden av samtliga parametrar. Skapar man testfallen manuellt är det ungefär här man hamnar. Dags att levla upp.

Det finns flera verktyg som kan ge en lista med testfall där alla värden på alla parametrar minst en gång kombineras parvis med alla värden på alla andra parametrar. För 3 parametrar får man t.ex. serierna 0-0-0, 0-1-1, 1-0-0, 1-1-1, 0-0-1, och 0-1-0. För 10 parametrar blir det totalt 20 testfall. Det är fler än 11, men enormt mycket färre än 1024. Många buggar behöver bara att 2-3 variabler har en viss kombination av värden för att triggas, så effektiviteten är förvånansvärt hög. Om själva testandet kan automatiseras blir det en utmärkt testsvit att köra efter varje incheckning, varje natt eller vad som nu är lämpligt.

När kursen började sa jag till lärarna att jag ville ha nya mentala verktyg, för att kunna testa program på ett mer strukturerat sätt. Det kan man ju lugnt säga att jag har fått. Kursen pågår två månader till, men av det jag sett av det återstående innehållet är det inget som riktigt slår steget från “det kräver hallucinogena droger” till “testdata kan genereras automatiskt från kravspecifikationer”.

March 16th, 2016 Posted by Daniel Brahneborg | blogg | no comments

There and back again

Att låta ett program hoppa mellan olika programspråk var visst inte så enkelt. Från C kan man öppna filer med kompilerad C-kod och anropa funktioner där utan större problem. Funktionerna där kan använda externa bibliotek, liksom anropa funktioner i det ursprungliga programmet. Av någon konstig anledning verkar folk tyvärr inte gilla det språket, så vi ville erbjuda fler alternativ.

Jag hade kört en del Ruby, och tänkte att det kunde vara ett trevligt språk att erbjuda. Tyvärr fick jag aldrig minneshanteringen att bli rätt där, och när jag nu kollade några år senare så verkar det som om språket fortfarande är helt enkeltrådat, och inte ens fungerar som del av en multitrådad applikation.

Numera fanns även mruby, som klarade trådar. Tyvärr så använde den inte rubys normala “gem”-hantering, vilket gör den ointressant.

Det gick att anropa funktioner i Perl från C, så länge som man lät varje Perl-motor ligga i en egen tråd. Dokumentationen var ganska bra (även om det råder delade meningar om vad SvPOK() faktiskt testar), och minneshanteringen gick att få stabil. Anrop tillbaka till C var däremot en helt annan sak. Hela upplägget där bygger på att C-koden är en del av en Perl-modul, med sina egna byggregler och annat. Varianten att C-koden är en del av programmet som anropade Perl, hittar jag ingen dokumentation för. Antingen skriver man en mod_perl som anropar perl, eller så gör man en mysql-adapter. Inte båda.

Python kändes lockande, med bra api-er åt båda håll, ända tills jag såg listan med minnesläckor. Nej, tack.

För PHP hittar jag bara dokumentation för när PHP anropar C, inte tvärtom. Det lockar inte att sno källkoden till mod_php, även om den gör väldigt nära det vi vill ha. Dessutom framgår inte hur trådsäkert det är.

Det finns en reimplementation av PHP som heter PH7. Där är det enkelt att göra anrop åt båda håll, den är trådsäker, men den verkar inte ha något stöd för externa standardpaket. Allting måste därför finnas antingen i PHP-koden eller i applikationen som anropar den.

Javascript kändes också lockande, speciellt med Googles V8-motor. Den är trådsäker, man kan göra anrop åt båda håll, men så var det ju det där med externa moduler. De enda javascriptmoduler jag hittar är byggda ovanpå node.js. Att köra sådan kod skulle kräva en egen reimplementation av ungefär hela node, eller att vi skrev om hela vår app att också köras inuti node. Inget av det lockar överhuvudtaget.

Python, PH7 och V8 är onekligen en generation senare än de andra. Mycket renare API än Perl, och i V8-fallet dessutom med massor med coola features från de nyare varianterna av C++ (framför allt C++11) för att undvika minnesläckor. Det är irriterande att det verkar vara så svårt att kombinera det här med språkens övriga ekosystem, så som Perl lyckas med.

Är det något språk jag har missat, som faktiskt uppfyller alla krav? Java?

February 12th, 2016 Posted by Daniel Brahneborg | blogg | no comments

Testade Python

Ett klassiskt sätt att låta användarna göra egna tillägg till ett program är att stödja ett eller flera skriptspråk. Istället för att starta en ny process för interpretatorn som kör användarens kod, görs den till en del av huvudprogrammet. Det är så webbservrarna kör perl och php, t.ex. Jag tänkte göra detsamma nu, men för python.

För att vara säker på att mitt program inte har några minnesläckor eller klantar sig på andra sätt, testas varje ny version med Valgrind. Den hittar saker som att man läser värden innan de är skrivna, använder minne efter att det är återlämnat, och massa annat. Jag började nu med ett minimalt program som traditionsenligt bara skrev ut “Hello World”. Valgrind blev synnerligen irriterad, och skrev ut hundratals varningar. Ok, jag kanske hade missat någonting?

Jag testade med den riktiga interpretatorn, och körde samma sak där. Jo då, hundratals varningar även nu, både minne som glömts bort och som försöks återlämnas flera gånger. Det senare felet är allvarligt, för det kan göra att programmet kan krascha helt slumpmässigt. Om man råkar ha någon fil öppen så kan även innehållet där skrivas över. Det är verkligen en “all bets are off”-situation. I Unix-världen är det därför ganska vanligt att man struntar i att lämna tillbaka minne när programmet avslutas, eftersom allt ändå tas om hand av operativsystemet. Det är onödigt att flyttstäda i ett hus som ska rivas. Ändå störde det mig.

Man kan bygga python med en speciell flagga, som gör att den funkar bättre med just Valgrind. Sagt och gjort. Jo då, alla dubbla återlämningar försvann. Tyvärr fick jag då bara ännu fler varningar om bortglömt minne. Att få reda på om den läcker lika mycket oavsett vad man gör, eller om den läcker lite grand varje gång ens program körs, är inte helt lätt att få reda på. Det går säkert, men kräver större kunskap om python-källkoden än vad jag har tid och lust att skaffa mig. Att få överblick på en halv miljon rader C-kod är inte gjort i en handvändning.

Å andra sidan spelar det ingen roll. Att lämna tillbaka minne i rätt ordning är ibland väldigt svårt. Antingen glöms vissa bitar bort, eller så trampar man sig själv på tårna och lämnar tillbaka saker för tidigt. Jag har haft samma problem med min egen kod mer än en gång. Poängen är att anledningen till de problemen, är exakt alltid i samtliga fall att jag inte har haft kontroll på vad koden egentligen gör. Saker körs, men jag vet inte i vilken ordning. I ett sådant läge är det lätt att bara ge upp, eftersom man inte riktigt behöver bry sig. När programmet avslutas, kommer operativsystemet ju ändå städa upp. Om det alltid läcker lika mycket minne oavsett hur länge programmet har körts eller vad det har gjort, är det i praktiken inte ett problem.

Från mitt perspektiv är det ändå inte ok. Om problem med minneshantering kan bero på bristande kontroll, betyder det att mitt förtroende för koden minskar. Om programmerarna har problem här, har de förmodligen problem med andra saker också. Omvänt gäller också. Har man stenkoll på vad koden gör och vilken del av koden som äger vilket minne, är det en kakbit att se till att minnet återlämnas på rätt sätt och i rätt ordning.

Det hela blev ännu sämre av att flera filer måste vara skrivbara när man kompilerar python, eftersom de genereras på vägen. Ändå måste de finnas från början, annars går bygget sönder med en gång. Återigen, brist på kontroll på sakers livscykel.

Så nej, det blir ingen python just nu.

February 8th, 2016 Posted by Daniel Brahneborg | blogg | one comment

Magisterexamen

(Borde kanske ha publicerat det här inlägget för typ ett halvår sedan…)

För att få tillräckligt med poäng till min magisterexamen, tog jag under förra våren en kurs i PHP på bth.se. Det var lämpligt att sikta på några tämligen säkra poäng, eftersom det inte kändes acceptabelt att förlora examen på grund av en missad kurs i det här läget. Jag sökte flera kurser för säkerhets skull, vilket slutade med att jag även läste en grundkurs i affärsredovisning.

PHP-kursen var relativt smärtfri. Jag hade kodat en del i det under hösten innan, så grunderna hade jag redan. Däremot var det kul att få en mer heltäckande genomgång, prova fler api’er, osv. På sista uppgiften fick jag en kommentar om att “lite mer ansträngning hade kunnat lagts på layouten”. Hallå, ser jag ut som en designer kanske? Multicolor lorem ipsum på dig själv, liksom. Sammantaget fick jag betyg B, på en skala A-F. Alternativt VG, på den mer normala VG/G/U-skalan. Även om det kanske hade varit kul att få ett A, hade det krävt mer tid än vad jag tyckte var motiverat.

Ekonomikursen var klart värre. Jag lusläste varenda rad i boken flera gånger om, gjorde alla övningar, och skickade ganska många mail till läraren med funderingar. En och annan frustration nådde både Facebook och Twitter. Till slut började saker få ett sammanhang, så på inlämningsuppgifterna fick mina grupper alltid kommentaren “mycket bra”. Tentan kändes bra, och sedan kom resultatet: 16 poäng av 20, dvs VG där också.

Exjobbet som helhet var nog något av de roligaste projekt jag har gjort. Den prestandaförbättring som jag såg i början försvann när jag hade rättat buggarna, men i vilket fall som helst lärde jag mig massor om multitrådning. Jag fick svar på de frågor jag hade haft som utgångspunkt, men upptäckte även en massa aspekter som jag inte hade tänkt på innan. Jag visste av erfarenhet att det skulle hända, men att veta att något oförutsett kommer dyka upp, och att se vad det där oförutsedda faktiskt består av, är ju två helt olika saker. Vi hade en lång dialog under månaderna som gick, jag och koden. Jag påstod och frågade saker, och fick svar och ibland missnöjda muttranden tillbaka. Vissa lösningar blev å andra sidan riktigt snygga, varpå koden glatt tackade mig och tuggade på lite snabbare.

Den magisterexamen som var mitt mål hade en hård deadline på sista juni, så sista veckorna var lite stressande medan jag väntade på att godkännandena skulle trilla in. Från handläggaren i Umeå fick jag veta att det räcker att en av kurserna (PHP eller ekonomi) rapporteras in med ett godkännandedatum senast sista juni. Om det skulle dröja in i juli innan Ladok blev helt uppdaterad hade inte gjort någonting, eller om själva examensbeviset inte hade hunnat skickas iväg innan dess. Eftersom kurserna var godkända den 17:e respektive 26:e juni, var jag hemma. Sedan var det bara att vänta medan databaserna synkade ihop sig.

Att få VG på båda kurserna med 0 poängs marginal och allt klart för en examen med knappt två veckors marginal efter 20 års velande, är kanske lite väl mycket “marginaler är för fegisar” även för min smak. Däremot känner jag mig lite nöjd med att exjobbet, som alltså skulle räcka i ungefär 20 veckor gånger 40 timmar, blev klart på ungefär en tredjedel av det.

När jag ändå hade några poäng för mycket, tänkte jag att det var lika bra att fortsätta plugga. Annars gör ju de där överblivna poängen ingen nytta. I somras läste jag därför Androidprogrammering, i höstas evolutionsbiologi, och framöver tänkte jag fylla på med fler kurser inom datavetenskap och annat för att förr eller senare komma upp på en masterexamen (dvs 2 år efter kandidat, totalt 5 år, till skillnad från den 4-åriga magister som jag får nu).

January 17th, 2016 Posted by Daniel Brahneborg | blogg | no comments

Embedded perl vs php

För några år sedan lade jag till möjligheten att köra pluginer skrivna i perl, i en av våra produkter (tänk “mod_perl”, typ). På det sättet kan kunderna skriva sina egna filter och annat, utan att behöva kladda ner grundprodukten med funktioner som bara en enstaka kund använder. Implementationen blev ganska rakt på sak: Läs in perlscriptet i början av programmet, kolla vilka funktioner som är implementerade, och via diverse magiska anrop kopiera visst data till perl-strukturer, och anropa perl-koden. Med ytterligare magi plockas data tillbaka från perl-världen till C. Kunder kan skriva egen kod, ingenting behöver kompileras, och det går tämligen snabbt. Alla har varit glada.

Sedan hittade vi en motor för embedded php. Tyvärr kunde den bara köra hela filer och inte enstaka funktioner, men det löstes genom att helt enkelt låta varje funktion ligga i en separat fil. För att komma åt datat från C-världen visade det sig vara enklast att registrera en callback. När php-koden anropar funktion X, så anropas funktion Y i C-världen. Den gör det den ska, och så återvänder man till php-världen. Data kunde skickas i båda riktningar, så vi kunde få både get-funktioner och set-funktioner. Det hela fungerade klockrent, och benchmarking visade att det gick snabbare än perl. För perl-pluginer byggde man nämligen ihop allt data i förväg, medan man för php bara gjorde det vid behov.

Den uppenbara tanken blev ju då att försöka göra samma sak för perl. Hej “perl xs“. Hahaha. Nej, det blir ingen perl xs. Visst, det är svårt att hoppa mellan C och scriptspråk med garbage collection, men det finns gränser för vad jag vill utsätta mig för.

January 11th, 2016 Posted by Daniel Brahneborg | blogg | no comments

Skillnad mellan protokoll

Två av de protokoll som används för SMS är SMPP och UCP. De använder ungefär samma information, men på helt olika sätt.

UCP är ganska enkelt. Förutom lite grejer i början och slutet, så är den huvudsakliga delen av datat separerat av “/”-tecken. Man får alltså data som ser ut ungefär så här: “/avsändare/mottagare/flagga1/flagga2/text/”. Allting är text, så det är lätt att skriva ner det i loggfiler, och därifrån se precis vad som händer.

SMPP är lite besvärligare. Varje fält har där ett nummer, och skrivs med tre fält:

  1. 2 bytes med fältets nummer.
  2. 2 bytes med datats längd.
  3. Datat.

Datat som man skickar är då en bunt sådana där tripplar direkt efter varandra. Det är inte längre lika enkelt varken att skapa eller logga datat.

Två skillnader är speciellt viktiga. Med SMPP så skickar man bara de fält som faktiskt har något värde. När man ska parsa datat så slipper man därför gå igenom massor med tomma fält. Med UCP så måste det alltid vara samma antal “/”-tecken, eftersom fältens innebörd styrs av deras relativa position. Råkar man skicka ett “/”-tecken för lite, tolkas alla efterföljande fält på fel sätt, vilket kan få alla möjliga skumma effekter. Även om SMPP i sig stödjer fler fält, blir det mindre data att hantera.

Dessutom vet SMPP direkt hur mycket data varje fält innehåller. Man läser de första 4 byten, och sedan är det bara att kopiera rätt antal bytes. I UCP finns ingen sådan längd, så man måste undersöka och kopiera ett tecken i taget. Även om ett fält är tomt, kräver UCP att man lägger på ett “/” varje gång, och sedan undersöker och går förbi det när datat blir läst. Samma sak måste göras när datat blir läst, fast då får man läsa en byte i taget medan man väntar på en “end of record”-byte.

Jag gjorde några benchmarks, och med ett program som inte gör så mycket mer än att läsa paket efter paket, plocka isär dem i beståndsdelar, och sedan packa ihop och skicka iväg dem igen, gick SMPP nästan dubbelt så snabbt. Det beror alldeles uppenbart inte enbart på att UCP-koden är sämre.

December 22nd, 2014 Posted by Daniel Brahneborg | blogg | no comments

Avancerade datastrukturer

När jag fick höra talas om hashtabeller, vilket borde ha varit någon gång i gymnasiet, tyckte jag att de var det ballaste som fanns. Lite mer än ett decennium senare kom jag i kontakt med AVL-träd, som är en variant av binära sökträd. De är onekligen snäppet coolare.

Nu, ytterligare drygt ett decennium senare, var det dags för nästa steg. MIT har en massor med föreläsningar man kan titta på, bland annat för en kurs som heter “Advanced Data Structures”. Tydligen så har folk fortsatt tänka efter att jag slutade på universitet, vilket onekligen var lite otippat. På samma sätt som hashtabeller använder arrayer i botten, använder grejerna i den här kursen ofta olika varianter på binära sökträd som hjälpmedel.

Tre saker framgår extra tydligt. Det första är att i princip allting när det gäller nya datatyper handlar om att få ner ordovärdet. Har man en sorterad lista och ska hitta ett visst element, är det ju smartare att använda intervallhalvering än att göra en linjär sökning. Koden för det senare är lite enklare och går snabbare för väldigt små listor, men ju större listan blir, desto bättre är intervallhalveringen. Gränsen mellan datatyp och algoritm är lite svävande här. Själva intervallhalveringen är ju en algoritm, men samtidigt så krävs rätt datatyp i botten för att den ska fungera på rätt sätt. Man kan ju göra intervallhalvering på en länkad lista också, men det vore mest bara väldigt korkat (på “double facepalm”-nivå).

Nummer två är balansen mellan tid och plats. Redan på hemdatortiden lärde man sig att man inte räknar ut sinus i realtid, eftersom det tar för lång tid. Istället har man en tabell med lagom stor upplösning. Samma avvägning används i MIT-kursen. Genom att strukturera sitt data på rätt sätt går det exempelvis att hitta rätt punkt i två dimensioner på samma tid som den vanliga intervallhalveringen hittar rätt punkt i en dimension (nej, jag tänker inte beskriva hur man gör). Kastar man sedan massa extra minne på det hela och bygger upp en större hjälpstruktur av sitt indata, vilket ju lönar sig om datat är någorlunda konstant och man ska göra den där sökningen många gånger, kan man dessutom hitta rätt punkt även uppe i tre dimensioner. Mer data, mindre cpu-tid. I en värld på 16*16*16 (=4096) punkter, kommer man alltså till rätt ställe på bara 4 steg.

Den tredje punkten är lite speciell. Ju mer man vet om sitt problem, desto bättre val av lösning kan man göra. Man kanske vet hur pass sorterat indatat är redan från början, huruvida man vill ha tag på vilket element som helst eller bara det minsta, osv. Som belöning får man bättre ordovärde. Tänk dig en lista med 65536 element. Med linjär sökning måste man undersöka eller flytta kanske samtliga element. Intervallhalvering (hej binära sökträd) drar ner det till 16. Kan man vinna en extra “log-faktor” är man nere på 4. Vet man att man alltid bara vill ha det minsta värdet, kan man komma ner till 1. Man behöver alltså inte göra någon sökning överhuvudtaget om man väljer rätt datastruktur.

Priset för de här ballare datatyperna är mer avancerad kod. Länkade listor kan jag implementera i sömnen. Hashtabeller är klurigare, men någon sådan har jag nog fått ihop någon gång. Jag kan säkert få ihop ett binärt sökträd också om jag bestämmer mig för det, men hittills har jag aldrig varken behövt eller vågat. Det finns libbar som är tillräckligt bra. Galna saker som MIT-lärarens “tango tree” ger mig bara huvudvärk. Ballt, ja. Inspirerande, absolut. Men sannolikheten att jag skulle implementera en sådan där grej korrekt är i närheten av epsilon. Så, där måste man ju också göra någon sorts avvägning. Hur mycket kod vill man skriva själv, och hur stor är sannolikheten att det blir rätt, kontra hur supereffektiv måste den där delen av koden faktiskt vara (med tanke på storlek på indatat, tiden varje steg tar, osv)?

Det som däremot lockar, om det är så att avl-koden någon gång skulle ta en signifikant del av körtiden och jag hade ett användningsfall där det passade, är att implementera den variant som är anpassad för att utnyttja cachen så mycket som möjligt. All cache är snabbare än nivån efter, så en sådan implementation skulle piska ett vanligt avl-träds rumpa. Extrem prestanda är kul, så är det bara.

December 9th, 2014 Posted by Daniel Brahneborg | blogg | no comments

« Äldre |