Fri 30 Oct 2015 14:37 - 15:00 at Grand Station 1 - 11. Programming Language Design Chair(s): Gary Leavens

The data structures under-pinning collection API (e.g. lists, sets, maps) in the standard libraries of programming languages are used intensively in many applications. The standard libraries of recent Java Virtual Machine languages, such as Clojure or Scala, contain scalable and well-performing immutable collection data structures that are implemented as Hash-Array Mapped Tries (HAMTs). HAMTs already feature efficient lookup, insert, and delete operations, however due to their tree-based nature their memory footprints and the runtime performance of iteration and equality checking lag behind array-based counterparts. This particularly prohibits their application in programs which process larger data sets. In this paper, we propose changes to the HAMT design that increase the overall performance of immutable sets and maps. The resulting general purpose design increases cache locality and features a canonical representation. It outperforms Scala’s and Clojure’s data structure implementations in terms of memory footprint and runtime efficiency of iteration (1.3–6.7x) and equality checking (3–25.4x).

Fri 30 Oct
Times are displayed in time zone: Eastern Time (US & Canada) change

13:30 - 15:00
11. Programming Language DesignOOPSLA at Grand Station 1
Chair(s): Gary Leavens University of Central Florida
13:30
22m
Talk
Remote-Scope Promotion: Clarified, Rectified, and VerifiedOOPSLA Artifact
OOPSLA
John WickersonImperial College London, Mark BattyUniversity of Cambridge, Bradford M. BeckmannAdvanced Micro Devices, Inc, Alastair DonaldsonImperial College London
DOI Media Attached
13:52
22m
Talk
Incremental Computation with NamesOOPSLA Artifact
OOPSLA
Matthew HammerUniversity of Maryland, College Park, Jana DunfieldUniversity of British Columbia, Canada, Kyle HeadleyUniversity of Maryland, College Park, Nicholas LabichUniversity of Maryland at College Park, USA, Jeffrey S. FosterUniversity of Maryland at College Park, USA, Michael HicksUniversity of Maryland at College Park, USA, David Van HornUniversity of Maryland at College Park, USA
DOI
14:15
22m
Talk
Checks and Balances: Constraint Solving without Surprises in Object-Constraint Programming LanguagesOOPSLA Artifact
OOPSLA
Tim FelgentreffHPI, Germany, Todd MillsteinUniversity of California at Los Angeles, USA, Alan BorningUniversity of Washington, USA, Robert HirschfeldHPI
DOI
14:37
22m
Talk
Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM CollectionsOOPSLA Artifact
OOPSLA
Michael SteindorferCWI, Netherlands, Jurgen VinjuCWI, Netherlands
Link to publication