NDLI: An efficient non-moving garbage collector for functional languages

Please wait, while we are loading the content...

Towards a comprehensive theory of monadic effects

Just do it: simple monadic equational reasoning

Monads, zippers and views: virtualizing the monad stack

Pushdown flow analysis of first-class control

Set-theoretic foundation of parametric polymorphism and subtyping

Balanced trees inhabiting functional parallel programming

Programming assurance cases in Agda

On the bright side of type classes: instance arguments in Agda

Temporal higher-order contracts

Deriving an efficient FPGA implementation of a low density parity check forward error corrector

A hierarchy of mendler style recursion combinators: taming inductive datatypes with negative occurrences

Secure distributed programming with value-dependent types

Forest: a language and toolkit for programming with filestores

Nameless, painless

Proving the unique fixed-point principle correct: an adventure with category theory

Generalising and dualising the third list-homomorphism theorem: functional pearl

Modular verification of preemptive OS kernels

An equivalence-preserving CPS translation via multi-language semantics

Lightweight monadic programming in ML

A semantic model for graphical user interfaces

Subtyping delimited continuations

Parametric polymorphism and semantic subtyping: the logical connection

Implicit self-adjusting computation for purely functional programs

Functional modelling of musical harmony: an experience report

Parsing with derivatives: a functional pearl

Geometry of synthesis iv: compiling affine recursion into static hardware

Typed self-interpretation by pattern matching

Frenetic: a network programming language

Making standard ML a practical database programming language

Binders unbound

Linearity and PCF: a semantic insight!

Incremental updates for efficient bidirectional transformations

Characteristic formulae for the verification of imperative programs

A kripke logical relation for effect-based program transformations

Functional programming through deep time: modeling the first complex ecosystems on earth

Modular rollback through control logging: a pair of twin functional pearls

How to make ad hoc proof automation less ad hoc

An efficient non-moving garbage collector for functional languages

Using camlp4 for presenting dynamic mathematics on the web: DynaMoW, an OCaml language extension for the run-time generation of mathematical contents and their presentation on the web

Recursion principles for syntax with bindings and substitution

An efficient non-moving garbage collector for functional languages

Content Provider	ACM Digital Library
Author	Ueno, Katsuhiro Otomo, Toshiaki Ohori, Atsushi
Abstract	Motivated by developing a memory management system that allows functional languages to seamlessly inter-operate with C, we propose an efficient non-moving garbage collection algorithm based on bitmap marking and report its implementation and performance evaluation. In our method, the heap consists of sub-heaps $H_{i}$ \| c ≤ i ≤ B of exponentially increasing allocation sizes $(H_{i}$ for $2^{i}$ bytes) and a special sub-heap for exceptionally large objects. Actual space for each sub-heap is dynamically allocated and reclaimed from a pool of fixed size allocation segments. In each allocation segment, the algorithm maintains a bitmap representing the set of live objects. Allocation is done by searching for the next free bit in the bitmap. By adding meta-level bitmaps that summarize the contents of bitmaps hierarchically and maintaining the current bit position in the bitmap hierarchy, the next free bit can be found in a small constant time for most cases, and in $log_{32}(segmentSize)$ time in the worst case on a 32-bit architecture. The collection is done by clearing the bitmaps and tracing live objects. The algorithm can be extended to generational GC by maintaining multiple bitmaps for the same heap space. The proposed method does not require compaction and objects are not moved at all. This property is significant for a functional language to inter-operate with C, and it should also be beneficial in supporting multiple native threads. The proposed method has been implemented in a full-scale Standard ML compiler. Our benchmark tests show that our non-moving collector performs as efficiently as a generational copying collector designed for functional languages.
Starting Page	196
Ending Page	208
Page Count	13
File Format	PDF MP4
ISBN	9781450308656
DOI	10.1145/2034773.2034802
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-09-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Non-moving garbage collection Sml# Bitmap marking Generational collectors
Content Type	Audio Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in