Basic personligt

Daniel Brahneborgs blogg

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

|