Datastrukturerna under-pinning insamling API (t.ex. Listor, uppsättningar, kartor) i de vanliga biblioteken för programmeringsspråk används intensivt i många tillämpningar. Standardbiblioteken för de senaste språken i Java Virtual Machine, t.ex. Clojure eller Scala, innehåller skalbara och väl fungerande oföränderliga datainsamlingsstrukturer som implementeras som Hash-Array Mapped Tries (HAMTs). HAMTs har redan effektiv uppslagning, infoga och ta bort operationer, men på grund av sin trädbaserade natur deras minnesavtryck och körtiden prestanda av iteration och jämlikhet kontroll släpar efter array-baserade motparter. Detta förbjuder särskilt deras tillämpning i program som behandlar större datamängder. I detta dokument föreslår vi ändringar i HAMT-designen som ökar den totala prestandan för oföränderliga uppsättningar och kartor. Den resulterande allmänna syftet design ökar cache lokalisering och har en kanonisk representation. Det överträffar Scalas och Clojures implementeringar av datastrukturen när det gäller minnesavtryck och iteration (1.3-6.7 x) och jämlikhetskontroll (3-24.4 x).
I tidigare arbete introducerade vi den komprimerade Hash-Array Mapped Prefixtree (CHAMP) REF, en cache-oblivious och kanoniska HAMT variant som förbättrar körtiden effektivitet i iteration (1.3-6.7 x) och jämlikhet kontroll (3-25.4 x) över sin föregångare, samtidigt minska minnesavtryck.
Optimizing hash-array mapped tries for fast and lean immutable JVM collections
{'venue': 'OOPSLA 2015', 'journal': None, 'mag_field_of_study': ['Computer Science']}