Region-based memory management for Mercury programs

DOI10.1017/S1471068412000075MaRDI QIDQ5398287zbMATH OpenFDO

Authors Quan Phan, Gerda Janssens, Zoltan Somogyi

Publication date 27 February 2014

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.1392

zbMATH Keywords

backtrackinglogic programmingMercuryregion analysisregion-based memory managementruntime support

Mathematics Subject Classification ID

Theory of programming languages (68N15) Logic programming (68N17)

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 large amount 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.

Recommendations

• Towards Region-Based Memory Management for Mercury Programs
• Static Region Analysis for Mercury
• Region-based memory management in Prolog
• A constraint-based region inference algorithm
• scientific article; zbMATH DE number 2090526

Cites work

• A retrospective on region-based memory management
• A type system with usage aspects
• Region-based memory management
• The execution algorithm of mercury, an efficient purely declarative logic programming language

Cited in

(9)

• A retrospective on region-based memory management
• Region-based memory management in Prolog
• scientific article; zbMATH DE number 1696867 (Why is no real title available?)
• Static Region Analysis for Mercury
• scientific article; zbMATH DE number 2090526 (Why is no real title available?)
• Towards Region-Based Memory Management for Mercury Programs
• Programming Languages and Systems
• A constraint-based region inference algorithm
• Region-based memory management

Describes a project that uses

Uses Software

• Mercury

This page was built for publication: Region-based memory management for Mercury programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5398287)