Ongeveer zeventig jaar geleden veranderde Hans Peter Luhn, een ingenieur bij IBM, stilletjes de koers van de informatica. Luhn had al verschillende patenten, waaronder een voor een apparaat dat het aantal draden van een doek kon meten en een ander voor een gids die bepaalde welke mixdrankjes je kon maken van de ingrediënten in je keuken. Maar in een intern IBM-artikel uit 70 stelde hij een nieuwe techniek voor voor het opslaan en ophalen van informatie die nu in vrijwel alle computersystemen is ingebouwd: de hashtabel.

Hashtabellen zijn een belangrijke klasse van datastructuren. Ze bieden een bijzonder handige methode voor het openen en wijzigen van informatie in enorme databases. Maar deze technologie brengt een onvermijdelijke wisselwerking met zich mee.

In een 1957 papier in het IBM-tijdschrift voor onderzoek en ontwikkelingidentificeerde W. Wesley Peterson de belangrijkste technische uitdaging die hashtabellen met zich meebrengen: ze moeten snel zijn, wat betekent dat ze snel de benodigde informatie kunnen ophalen. Maar ze moeten ook compact zijn en zo min mogelijk geheugen gebruiken. Deze dubbele doelstellingen zijn fundamenteel met elkaar in strijd. Het openen en wijzigen van een database kan sneller worden gedaan als de hashtabel meer geheugen heeft; en bewerkingen worden langzamer in hashtabellen die minder ruimte in beslag nemen. Sinds Peterson deze uitdaging uiteenzette, hebben onderzoekers geprobeerd de beste balans tussen tijd en ruimte te vinden.

Computerwetenschappers hebben nu wiskundig bewezen dat ze de optimale afweging hebben gevonden. De oplossing kwam van a paar van recent papieren die elkaar aanvulden. “Deze artikelen lossen de al lang bestaande open vraag op over de best mogelijke wisselwerking tussen ruimte en tijd, en leveren zeer verrassende resultaten op waarvan ik verwacht dat ze nog vele jaren een aanzienlijke impact zullen hebben,” zei Michaël Mitzenmacher, een computerwetenschapper aan de Harvard University die bij geen van beide onderzoeken betrokken was.

“Ik zou zeker zeggen dat het een groot probleem is”, voegde hij eraan toe Rasmus Pagh, een computerwetenschapper aan de Universiteit van Kopenhagen. “Veel mensen hebben aan dit probleem gewerkt, in een poging te zien hoeveel ruimte je kunt inkrimpen, terwijl je tegelijkertijd tijdbesparende bewerkingen kunt uitvoeren. Dit is degene die ik graag had willen oplossen.”

Er een hasj van maken

Hashtabellen behoren tegenwoordig tot de oudste, eenvoudigste, snelste en meest gebruikte datastructuren. Ze zijn ontworpen om drie basisbewerkingen uit te voeren: invoegingen, waardoor nieuwe items aan de database worden toegevoegd; zoekopdrachten, die toegang krijgen tot een item of controleren of het bestaat; en verwijderingen. Een hashtabel kan kortstondig zijn (slechts bestaan ​​zolang een bepaald programma actief is) of kan een permanent onderdeel zijn van het besturingssysteem van uw computer. Een webbrowser zoals Chrome of Safari kan meerdere ingebouwde hashtabellen hebben die bedoeld zijn om verschillende soorten gegevens bij te houden.

Gegevens in een hashtabel worden als paren opgeslagen, waarbij het item (de informatie zelf) is verbonden met een sleutel die de informatie identificeert. Sluit een sleutel aan op het zoekalgoritme van een hashtabel en u gaat rechtstreeks naar het item. Dit klinkt misschien niet zo bijzonder, maar voor enorme databases kan het een grote tijdsbesparing opleveren.

Om een ​​extreem vereenvoudigd voorbeeld te nemen, kijk eens naar de Oxford English Dictionary, die definities heeft voor meer dan 600,000 woorden. Als een digitale editie afhankelijk is van een hashtabel, kunt u eenvoudigweg een bepaald woord als sleutel gebruiken en rechtstreeks naar de definitie gaan. Zonder een hashtabel zou het woordenboek waarschijnlijk vertrouwen op een veel langzamer zoekmechanisme, waarbij gebruik wordt gemaakt van een eliminatieproces om uiteindelijk tot de gevraagde definitie te komen. En hoewel een hashtabel elk woord in een constante hoeveelheid tijd (meestal een kleine fractie van een seconde) kan vinden, kan de zoektijd voor andere methoden toenemen naarmate het aantal woorden in het woordenboek toeneemt. Een hashtabel biedt ook nog een ander voordeel: het kan het woordenboek dynamisch houden, waardoor het gemakkelijk wordt om nieuwe woorden in te voegen en verouderde woorden te verwijderen.

Onderzoekers hebben tientallen jaren besteed aan het bouwen van hashtabellen die proberen de snelheid te maximaliseren en het geheugen te minimaliseren. In de twintigste eeuw leverden oplossingen doorgaans aanzienlijke winst op in slechts één aspect: tijd of ruimte. Toen, in 20, onderzoekers vertoonde dat het theoretisch mogelijk was om tegelijkertijd een grote efficiëntiesprong te maken in zowel tijd als ruimte. Het zou echter nog twintig jaar duren voordat onderzoekers de ideale balans tussen beide zouden vinden.

De gegevensshuffle

De eerste grote stap in de richting van dat doel werd in 2022 gezet grote computerwetenschapsconferentie in Rome. Daar stelde een team een ​​hashtabel voor met nieuwe functies die de beste combinatie van tijd- en ruimte-efficiëntie tot nu toe zouden kunnen opleveren. De eerste auteur van het artikel (alfabetisch weergegeven) was Michael Bender van de Stony Brook University, dus het wordt gewoonlijk de Bender et al. genoemd. hash-tabel. Hoewel het team niet probeerde een functionerende hashtabel te bouwen, bewezen ze dat deze in principe kon worden geconstrueerd met de kenmerken die ze beschreven.

Om de hashtabel die ze bedachten te evalueren, produceerde de groep een trade-off curve: een grafiek die de tijd per bewerking (invoegen of verwijderen) op de ene as uitzet en de ruimte die het geheugen inneemt op de andere. Maar deze grafiek definieert ruimte op een speciale manier: vanwege de manier waarop ze zijn opgebouwd, hebben hashtabellen meer geheugen nodig dan alleen het absolute minimum dat nodig is om een ​​bepaalde set items op te slaan. Computerwetenschappers noemen deze extra ruimte 'verspilde stukjes', ook al zijn ze niet echt verspild en zijn ze tot op zekere hoogte noodzakelijk. De ruimte-as op een trade-off-curve meet het aantal verspilde bits per sleutel.

Door een trade-off curve te analyseren, kunnen onderzoekers de snelst mogelijke tijd berekenen voor een hashtabel die een bepaalde hoeveelheid ruimte in beslag neemt. Ze kunnen de vraag ook omdraaien om de kleinst mogelijke ruimte voor een bepaalde operatietijd te bepalen. Meestal zal een kleine verandering in de ene variabele leiden tot een kleine verandering in de andere Willem Kuszmaul, een theoretische computerwetenschapper aan Harvard en co-auteur van het artikel uit 2022. “Als je de tijd verdubbelt, halveer je misschien het aantal verspilde bits per sleutel.”

Maar dat is niet het geval met de hashtabel die ze hebben ontworpen. “Als je de tijd een beetje verlengt, nemen de verspilde bits per sleutel exponentieel af”, zegt Kuszmaul. De trade-off curve was zo steil dat hij letterlijk buiten de hitlijsten viel.

Het team bouwde hun hashtabel in twee delen. Ze hadden een primaire datastructuur, waarin de items worden opgeslagen zonder enige verspilde bits, en een secundaire datastructuur, waarmee een queryverzoek het item kan vinden waarnaar het zoekt. Hoewel de groep het idee van een secundaire datastructuur niet heeft uitgevonden, hebben ze wel een cruciale ontdekking gedaan die hun hyperefficiënte hashtabel mogelijk maakte: de algehele geheugenefficiëntie van de structuur hangt af van hoe de primaire structuur de opgeslagen items rangschikt.

Het basisidee is dat elk item in de primaire structuur voorkeursopslaglocaties heeft: een beste locatie, een op één na beste, een derde beste enzovoort. Als een item zich op de beste plek bevindt, wordt het nummer 1 eraan toegevoegd en dat nummer wordt opgeslagen in de secundaire datastructuur. Als antwoord op een vraag geeft de secundaire structuur alleen het getal 1 weer, dat de exacte locatie van het item in de primaire structuur aangeeft.

Als het item op de 100ste plaats staat, voegt de secundaire datastructuur het getal 100 toe. En omdat het systeem binair gebruikt, vertegenwoordigt het het getal 100 als 1100100. Het kost uiteraard meer geheugen om het getal 1100100 op te slaan dan 1. — het nummer dat aan een item wordt toegewezen wanneer het zich op de beste plek bevindt. Dergelijke verschillen worden aanzienlijk als je bijvoorbeeld een miljoen items opslaat.

Het team realiseerde zich dus dat als je voortdurend items in de primaire datastructuur verplaatst naar hun favoriete locaties, je het geheugen dat door de secundaire structuur wordt verbruikt aanzienlijk kunt verminderen zonder de zoektijden te hoeven verlengen.

“Vóór dit werk had niemand zich gerealiseerd dat je de datastructuur verder kon comprimeren door informatie te verplaatsen”, zegt Pagh. "Dat was het grote inzicht van het Bender-artikel."

De auteurs toonden aan dat hun uitvinding een nieuwe bovengrens creëerde voor de meest efficiënte hashtabellen, wat betekent dat het de beste datastructuur was die tot nu toe is bedacht in termen van zowel tijd- als ruimte-efficiëntie. Maar de mogelijkheid bleef bestaan ​​dat iemand anders het nog beter zou doen.

Gebonden om te slagen

Het jaar daarop werd een team onder leiding van Huacheng Yu, een computerwetenschapper aan de Princeton University, probeerde de hashtabel van het Bender-team te verbeteren. “We hebben heel hard gewerkt en het lukte niet”, zei hij Renfei Zhou, een student aan de Tsinghua Universiteit in Beijing en lid van Yu's team. “Toen vermoedden we dat hun bovengrens [ook] een ondergrens was” – het beste dat mogelijk kan worden bereikt. “Als de bovengrens gelijk is aan de ondergrens, is het spel afgelopen en heb je je antwoord.” Hoe slim je ook bent, geen enkele hashtabel kan het beter.

Yu's team gebruikte een nieuwe strategie om erachter te komen of dat vermoeden juist was, door op basis van de eerste principes een ondergrens te berekenen. Ten eerste redeneerden ze dat om een ​​invoeging of een verwijdering uit te voeren, een hashtabel (of eigenlijk elke datastructuur) een aantal keren toegang moet krijgen tot het geheugen van de computer. Als ze het minimumaantal keren konden berekenen dat nodig is voor een ruimtebesparende hashtabel, zouden ze dat kunnen vermenigvuldigen met de tijd die nodig is per toegang (een constante), waardoor ze een ondergrens voor de runtime krijgen.

Maar als ze niets wisten over de hashtabel (behalve dat deze ruimte-efficiënt was), hoe konden de onderzoekers dan het minimale aantal keren berekenen dat nodig was om toegang te krijgen tot het geheugen? Ze hebben het puur afgeleid uit de theorie, met behulp van een ogenschijnlijk niet-gerelateerd veld dat de theorie van communicatiecomplexiteit wordt genoemd en dat bestudeert hoeveel bits nodig zijn om informatie tussen twee partijen over te brengen. Uiteindelijk slaagde het team erin: ze kwamen erachter hoe vaak een datastructuur per bewerking toegang moet krijgen tot zijn geheugen.

Dit was hun belangrijkste prestatie. Vervolgens konden ze een ondergrens voor de runtime vaststellen voor elke ruimtebesparende hashtabel. En ze zagen dat het precies overeenkwam met de Bender-hashtabel. “We dachten eerst dat het verbeterd kon worden”, zei Zhou. “Het bleek dat we ongelijk hadden.” Dat betekende op zijn beurt dat Petersons probleem eindelijk was opgelost.

Naast het beantwoorden van de decennia-oude vraag, zei Kuszmaul, is het verbazingwekkende aan het Yu-bewijs de algemeenheid ervan. “Hun ondergrens geldt voor alle mogelijke datastructuren, ook voor de datastructuren die nog niet zijn uitgevonden.” Dat betekent dat geen enkele methode voor gegevensopslag ooit de Bender-hashtabel kan verslaan in termen van geheugen en snelheid.

Haasten naar de toekomst

Ondanks de ongekende efficiëntie van de nieuwe hashtabel zal niemand deze binnenkort proberen te bouwen. Het is gewoon te ingewikkeld om te bouwen. “Een algoritme dat in theorie snel is, is in de praktijk niet noodzakelijkerwijs snel,” zei Zhou.

Het is niet ongebruikelijk dat dergelijke verschillen tussen theorie en praktijk lange tijd blijven bestaan, zei Kuszmaul, omdat theoretici de neiging hebben constante factoren te negeren. De tijd die nodig is om een ​​bewerking uit te voeren, wordt doorgaans vermenigvuldigd met een getal, een constante waarvan de exacte waarde vanuit theoretisch oogpunt onbelangrijk kan zijn. “Maar in de praktijk doen constanten er echt toe,” zei hij. “In de echte wereld is een factor 10 het einde van het spel.”

Werkelijke hashtabellen verbeteren nog steeds op materiële manieren, ook al blijven ze ver achter bij het theoretische ideaal. Er wordt bijvoorbeeld een nieuwe hashtabel genoemd IJsbergHT, gebouwd door Bender, Kuszmaul en anderen, is veel beter dan zijn voorgangers. Volgens Kuszmaul is hij twee keer zo snel als de meest ruimtebesparende hashtafel die momenteel beschikbaar is, en gebruikt hij drie keer minder ruimte dan de snelste hashtafel.

Mitzenmacher hoopt dat het resultaat van 2023 binnenkort een ander soort voordeel kan opleveren: “Elke keer dat je een nieuwe ondergrens krijgt – vooral een die nieuwe technieken met zich meebrengt – is er altijd hoop dat je ze kunt gebruiken … voor gerelateerde problemen.”

Er is ook de intellectuele voldoening die je krijgt als je weet dat je een moeilijk en al lang bestaand probleem hebt opgelost, zei de computerwetenschapper Piotr Indijk van het Massachusetts Institute of Technology. “Als je er zeker van bent dat bepaalde datastructuren niet verbeterd kunnen worden, kan dat de onderzoeksinspanning helpen focussen.” Ten slotte kunnen dataonderzoekers hun aandacht afwenden van Petersons uitdaging en zich concentreren op nieuwe problemen in de theoretische informatica, waaraan geen gebrek bestaat.