Title: Region-based memory management for Mercury programs
Authors: Quan, Phan
Janssens, Gerda ×
Somogyi, Zoltan #
Issue Date: Nov-2013
Publisher: Cambridge University Press
Series Title: Theory and Practice of Logic Programming vol:13 issue:6 pages:959-1024
Article number: doi = "10.1017/S1471068412000075"
Abstract: Region-based memory management (RBMM)
is a form of compile-time memory management,
well-known from the functional programming world.
In this paper we describe our work on implementing RBMM
for the logic programming language Mercury.
One interesting point about Mercury is that it is designed with
strong type, mode, and determinism systems.
These systems not only provide
Mercury programmers with several direct software engineering benefits,
such as self-documenting code and clear program logic,
but also give language implementors
a lot of information that is useful for program analyses.
In this work, we make use of this information to develop program analyses
that determine the distribution of data into regions
and transform Mercury programs by inserting into them
the necessary region operations.
We prove the correctness of our program analyses and transformation.
To execute the annotated programs, we have implemented runtime support
that tackles the two main challenges posed by backtracking.
First, backtracking can require regions
removed during forward execution to be ``resurrected'';
and second,
any memory allocated during a computation that has been backtracked over
must be recovered promptly and without waiting
for the regions involved to come to the end of their life.
We describe in detail our solution of both these problems.
We study in detail how our RBMM system performs
on a selection of benchmark programs,
including some well-known difficult cases for RBMM.
Even with these difficult cases, our RBMM-enabled Mercury system
obtains clearly faster runtimes for 15 out of 18 benchmarks
compared to the base Mercury system with its Boehm runtime garbage collector,
with an average runtime speedup of 24%,
and an average reduction in memory requirements of 95%.
In fact, our system achieves optimal memory consumption in some programs.
ISSN: 1471-0684
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
tplp.pdf Published 596KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science