Back to basics
Der er nu ikke noget som at sidde med lidt opsamlede testdata og lege med algoritmerne.
Pt. kigger jeg af forskellige årsager på hvordan Varnish finder et cache'et object.
Jeg lavede oprindeligt en klassisk hash tabel og den har klaret sig fint indtil nu, men der er folk med seriøst store antal objecter derude.
F.eks en næsten komplet samling af billeder af norske teenagere der keder sig.
Hash algoritmer er spredehagl: man kan smide dem efter stort set hvad som helst og de klarer sig fornuftigt.
Men rent multi-programmeringsmæssigt er de noget skrammel, fordi man enten får alt for mange låseoperationer, eller låser en hel hash-bucket mens roder med den.
Det er heller aldrig til at vide hvor mange hash-buckets man har brug for, før det er for sent, og det er kropumuligt at lave om på senere.
Lige nu kigger jeg på varianter af radixtræer, fordi den typiske URL har strukturer der kan udnyttes produktivt.
F.eks er det det typisk kun de nederste fire-fem bits i hver byte der indeholder information, fordi en given position i URL'en ofte kun kan være enten et ciffer eller kun kan være et bogstav.
Jeg har selvfølgelig Knuths bind tre fremme og er igang med kapitel seks.
Men der er en ting som det lader til at mesteren har overset når det kommer til opbygningen af træer:
Mange URL'er, som f.eks her på version2, har den distinktive information til sidst: /mumle/cms/etellerandet?artikel=1921243
Hvis man bygger træet op ved at tage sådan en URL forfra, skal man bane sig vej igennem 10 a 20 tegn før man kommer til noget der breder træet ud, hvis man derimod starter bagfra, får man i de første fire bits spredt træet ud med en faktor ti.
I et livetrace fra en bestemt Varnish website, reduceres dybden af et binært patricia træ fra 27 +/-6, til 21 +/- 3 hvis jeg starter bagfra istedet for forfra.
Det er langt fra alle datasæt der har denne egenskab, i et livetrace fra et andet site stiger dybden fra 28 til 32, fordi deres URL'er har en stort set konstant komponent til sidst.
Men så langt som jeg er nået og så vidt jeg erindrer har Knuth overset denne optimeringmulighed.
Er man gammel når man finder mangler i mesterens værker ?
phk
Om Poul-Henning KampPoul-Henning er selvstændig systemprogrammør, kernekoder, Varnish-forfatter, data-arkæolog og brokkehoved uden særlig portefølje.
Follow @bsdphkKommentarer (19)
Hvis vi ikke bliver dygtigere end dem der underviser, vil udviklingen gå i stå.
Udvikling medfører også at vi finder mangler og fejl i de teorier vi er blevet undervist i ellers har vi ikke hørt efter.
Engang vidste de klogeste hoveder at jorden var rund...
Hvorvidt du er gammel vil jeg lade dine nærmeste om at fortælle dig.
-
0 -
0
Engang vidste de klogeste hoveder at jorden var rund...
Det har så vidt jeg ved altid været tilfældet, det er kun religiøse nutcases der har troet andet.
Poul-Henning
-
0
-
0
Hej Poul-Henning
Jeg ved ikke om det kan hjælpe men dit indlæg minder mig om en video jeg sad og så for nogle måneder siden omkring implementationer af hashmaps i en multithreaded applikation.
http://video.google.com/videoplay?docid=2139967204534450862
Jeg håber at du finder en god løsning.
Jesper
-
0
-
0
[quote] Engang vidste de klogeste hoveder at jorden var rund...
Det har så vidt jeg ved altid været tilfældet, det er kun religiøse nutcases der har troet andet.
[/quote]
Sludder! Jorden er flad! Og det er den hele vejen rundt...
:-) Thomas
-
0
-
0
Da jeg så overskriften, tænkte jeg på hybris/NEMESIS' "Back to BASICs" (http://www.pouet.net/prod.php?which=4674).
-
0
-
0
Jeg er engang blevet belært af en af disse religøse nutcases at jorden var flad, fordi der stod i biblen at den havde 4 hjørner.
På spørgsmålet om hvorfor den så ikke kunne være et tetraeder, ville han vende tilbage, når han havde tænkt over det :)
-
0
-
0
Der er en pragtfuld gammel Science Fiction historie der leger med tanken, jeg kan ikke huske hvad den hedder, muligvis noget i stil med "cubeworld". Den afsluttende punch-line er ubetalelig.
Poul-Henning
-
0
-
0
Inden I smider den gamle Mester helt på porten, så husk lige at der i forbindelse med Patricia (og de beslægtede) algoritmer adskillige gange pointeres at analyserne kun gælder hvis nøglerne er ligefordelte.
Og det er url'er på ingen måde.
Analysen af Patricia går vist mest ud på at vise ækvivalens med radix sortering, så der er mere relevant stof i kapitlet før. Her kan man bl.a. læse de sidste par sider i afsnit 5.2.5 hvor finten med at betragte nøglerne 'bagfra' nævnes.
Generelt er det vist ret svært at analysere radix ud fra mere komplicerede fordelinger end ligefordelingen opgave 5.2.2 nr 50 har fået [HM42] i 'sværhedsgrad' (jeg har ikke prøvet den, men de eneste gange hvor jeg har synes en taocp-opgave var alt for let i forhold til dens score er når jeg har lavet fejl! :-)). Opgave 5.2.2 43 er også relevant.
Men tilbage til PHK's opgave: siden du er villig til at reversere nøgler (for at få bedre distribution i de første cifre) og dermed 'ødelægger' egenskaben om at url's der er i familie ligger tæt ved hinanden i træet kunne det måske være en ide at hash'e url'en og bruge resultatet som nøgle til dit træ?
-
0
-
0
Men tilbage til PHK's opgave: siden du er villig til at reversere nøgler (for at få bedre distribution i de første cifre) og dermed 'ødelægger' egenskaben om at url's der er i familie ligger tæt ved hinanden i træet kunne det måske være en ide at hash'e url'en og bruge resultatet som nøgle til dit træ?
Der er kun et problem: hash'en skal være kollisionsfri og det vil sige at vi kommer op i kryptografiske algoritmer som MD5 og SHA der er temmelig dyre at udregne, specielt fordi URLer kan være forholdsvist lange.
Poul-Henning
-
0
-
0
Jeg mindes i fordums tid at have haft stor glæde af splay-træer, hvor søge dybden kun er amortiseret O(ln n). Den var en forbløffende hurtig algoritme når der kom mange opslag på samme element kort efter hinanden - og sådan er det ofte med f.eks. variable i programmeringssprog, der skal parses. Så afhængigt af dit trafikmøsnster, så kunne det også være en sjov algoritme at se nærmere på.
-
0
-
0
Jeg ved ikke rigtig.... men entropien kan ligge i starten, som du anfører, men også i slutningen, som også angivet.
Men derudover kan entropien også ligge i midten.
-
0
-
0
"Engang vidste de klogeste hoveder at jorden var rund..." Det har så vidt jeg ved altid været tilfældet, det er kun religiøse nutcases der har troet andet. Poul-Henning
Hmmm, strengt taget er jorden ikke rund, men let fladtrykt, pga centrifugalkraften fra jordens rotation. Det var faktisk lidt af en kontrovers i videnskabelige kredse i 1700-tallet, at jodens form ikke var "perfekt rund". Påvisningen af dette var en stor succes for Newtons tilhængere. For en temmelig underholdende gennemgang, kan jeg anbefale Bill Brysons "A short history of nearly everything".
Ideen om, at jorden skulle være (helt) flad en nyere konstruktion i den vestlige verden, opfundet af en forvirret præst i 1800-tallet (mener jeg), der var ked af naturvidenskabens fremturden. Fra de gamle grækere, og sikkert før, har man vidst, at jorden er rund, og mig bekendt har kirken historisk ikke modsat sig dette? Om Jordens bane om solen derimod...
(PHK: Bare ærgerligt, at det ikke var en bug i hans TeX du fandt, så kunne du have tjent en dollar...:-)
-
0
-
0
Jeg mindes i fordums tid at have haft stor glæde af splay-træer, hvor søge dybden kun er amortiseret O(ln n). Den var en forbløffende hurtig algoritme når der kom mange opslag på samme element kort efter hinanden - og sådan er det ofte med f.eks. variable i programmeringssprog, der skal parses. Så afhængigt af dit trafikmøsnster, så kunne det også være en sjov algoritme at se nærmere på.
Problemet med mange af de klassiske datastrukturer er at de kræver et meget hårdhændet låsesystem i SMP sammenhæng og sekundært at de koster cache-misses til den helt store guldmedalje.
Splaytræer er meget slemme på begge punkter.
Poul-Henning
-
0
-
0
Der er kun et problem: hash'en skal være kollisionsfri og det vil sige at vi kommer op i kryptografiske algoritmer som MD5 og SHA der er temmelig dyre at udregne, specielt fordi URLer kan være forholdsvist lange.
En mulighed ville være at lade din nøgle være:
hash(url) + url
Nu kender jeg ikke størrelsen på dine datasæt, men hvis du har fx. i størrelsesordenen 100k url-agtige nøgler vil selv hurtige (fx. djb) 32-bit hashes give ganske få kollisioner (hvor den 'rene' url så bliver nødvendig). Hvis du har langt flere data, så brug to hurtige (i praksis foldet 'ind i hinanden' så du kun looper over strengen een gang) 32-bit hashes a la
hash(url) + hash2(url) + url
Men nu er vi langt fra Knuth, for der er ikke megen pæn matematik i ovenstående. Bare hackery som self. også kan være nyttigt af og til. Måske ubrugeligt -- du kender dit case bedst og kan træffe den bedste beslutning.
-
0
-
0
Et alternativ til kryptografiske hashes er funktioner som roder lidt rundt i bitsne men ikke skærer information væk.
Eg: (pseudokode, et sprog hvor man kan XORe to strenge)
[code=javascript]function messup(str url){
str part = url.left(url.len % 8)
str value = part
int lengthleft = url.len AND -8
while(lengthleft){
url = url.right(lengthleft)
part = part XOR url.left(8)
value = part + value
lengthleft = lengthleft - 8
}
return value
}[/code]
Nu er hele urlen XORet ind i de første 8 byte, med untagelse af enkelte fjollede url konstruktioner vil de første 8 byte i regelen være unikke, men der er altid den fulde mængde information at falde tilbage på.
-
0
-
0
med untagelse af enkelte fjollede url konstruktioner vil de første 8 byte i regelen være unikke, men der er altid den fulde mængde information at falde tilbage på.
Forkert antagelse for CMS systemer.
Poul-Henning
-
0
-
0
Forkert antagelse for CMS systemer.
Slet ikke, jeg tager netop forbehold for fjollede url konstruktioner, som dog har det med at opstå i forbindelse med CMS systemer (helt eksakt er der problemer hvis et id skrives to gange forskudt n*8 tegn). Man kan selvfølgelig designe et lignende system som eliminerer denne lille svaghed, jeg kan ikke lige finde på noget uden at bruge ekstra og/eller mere komplicerede instruktioner, og jeg tvivler på at den imperfektion er det værd.
-
0
-
0
Overvej hvad splay trees goer ved din cache paa en multi-core maskine :)
-
0
-
0
Hep PHK.
Checkede du LC-Tries ogsaa? De var ganske populaere i linuxkernens route-table for en stund, men de skal sandsynligvis pilles lidt i for at goere insert/delete tilstraekkeligt hurtigt. Ialdfald har de en oplagt RCU-implementation.
-
0
-
0
Tilføj kommentar
