Google Summer of Code (2015)

A heap profile is a description of the space usage of a program. A heap profile is concerned with the allocation, retention, and deallocation (via garbage collection) of heap data during the execution of a program. A heap profile can be used to diagnose performance problems in a functional program that arise from space leaks. This project aims to design and implement a heap profiler for MLton compiled programs.

Background:

Recommended Skills: C and SML programming experience; some experience with UI and visualization

The garbage collector plays a significant role in the performance of functional languages. Garbage collect too often, and program performance suffers due to the excessive time spent in the garbage collector. Garbage collect not often enough, and program performance suffers due to the excessive space used by the uncollected garbage. One particular issue is ensuring that a program utilizing a garbage collector "plays nice" with other processes on the system, by not using too much or too little physical memory. While there are some reasonable theoretical results about garbage collections with heaps of fixed size, there seems to be insufficient work that really looks carefully at the question of dynamically resizing the heap in response to the live data demands of the application and, similarly, in response to the behavior of the operating system and other processes. This project aims to investigate improvements to the memory behavior of MLton compiled programs through better tuning of the garbage collector.

Background:

Recommended Skills: C programming experience; some operating systems and/or systems programming experience; some compiler and garbage collector experience

Activation records (a.k.a., stack frames) are traditionally allocated on a stack. This naturally corresponds to the call-return pattern of function invocation. However, there are some disadvantages to stack-allocated activation records. In a functional programming language, functions may be deeply recursive, resulting in call stacks that are much larger than typically supported by the operating system; hence, a functional programming language implementation will typically store its stack in its heap. Furthermore, a functional programming language implementation must handle and recover from stack overflow, by allocating a larger stack (again, in its heap) and copying activation records from the old stack to the new stack. In the presence of threads, stacks must be allocated in a heap and, in the presence of a garbage collector, should be garbage collected when unreachable. While heap-allocated activation records avoid many of these disadvantages, they have not been widely implemented. This project aims to implement and evaluate heap-allocated activation records in the MLton compiler.

Background:

Recommended Skills: SML programming experience; some middle- and back-end compiler experience

The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is the de facto representation for floating-point computation. However, it is a binary (base 2) representation of floating-point values, while many applications call for input and output of floating-point values in decimal (base 10) representation. The decimal-to-binary conversion problem takes a decimal floating-point representation (e.g., a string like "0.1") and returns the best binary floating-point representation of that number. The binary-to-decimal conversion problem takes a binary floating-point representation and returns a decimal floating-point representation using the smallest number of digits that allow the decimal floating-point representation to be converted to the original binary floating-point representation. For both conversion routines, "best" is dependent upon the current floating-point rounding mode.

MLton uses David Gay’s gdtoa library for floating-point conversions. While this is an exellent library, it generalizes the decimal-to-binary and binary-to-decimal conversion routines beyond what is required by the Standard ML Basis Library and induces an external dependency on the compiler. Native implementations of these conversion routines in Standard ML would obviate the dependency on the gdtoa library, while also being able to take advantage of Standard ML features in the implementation (e.g., the published algorithms often require use of infinite precision arithmetic, which is provided by the IntInf structure in Standard ML, but is provided in an ad hoc fasion in the gdtoa library).

This project aims to develop a native implementation of the conversion routines in Standard ML.

Background:

Recommended Skills: SML programming experience; algorithm design and implementation

Debugging is a fact of programming life. Unfortunately, most SML implementations (including MLton) provide little to no source-level debugging support. This project aims to add basic to intermediate source-level debugging support to the MLton compiler. MLton already supports source-level profiling, which can be used to attribute bytes allocated or time spent in source functions. It should be relatively straightforward to leverage this source-level information into basic source-level debugging support, with the ability to set/unset breakpoints and step through declarations and functions. It may be possible to also provide intermediate source-level debugging support, with the ability to inspect in-scope variables of basic types (e.g., types compatible with MLton’s foreign function interface).

Background:

Recommended Skills: SML programming experience; some compiler experience

Region based memory management is an alternative automatic memory management scheme to garbage collection. Regions can be inferred by the compiler (e.g., Cyclone and MLKit) or provided to the programmer through a library. Since many students do not have extensive experience with compilers we plan on adopting the later approach. Creating a viable region based memory solution requires the removal of the GC and changes to the allocator. Additionally, write barriers will be necessary to ensure references between two ML objects is never established if the left hand side of the assignment has a longer lifetime than the right hand side. Students will need to come up with an appropriate interface for creating, entering, and exiting regions (examples include RTSJ scoped memory and SCJ scoped memory).

Background:

Recommended Skills: SML programming experience; C programming experience; some compiler and garbage collector experience

This project focuses on exposing real-time APIs from a real-time OS kernel at the SML level. This will require mapping the current MLton (or MultiMLton) threading framework to real-time threads that the RTOS provides. This will include associating priorities with MLton threads and building priority based scheduling algorithms. Additionally, support for perdioc, aperiodic, and sporadic tasks should be supported. A real-time SML library will need to be created to provide a forward facing interface for programmers. Stretch goals include reworking the MLton atomic statement and associated synchronization primitives built on top of the MLton atomic statement.

Recommended Skills: SML programming experience; C programming experience; real-time experience a plus but not required

This project focuses on modifications to the MLton GC to support real-time garbage collection. We will model the real-time GC on the Schism RTGC. The first task will be to create a fixed size runtime object representation. Large structures will need to be represented as a linked lists of fixed sized objects. Arrays and vectors will be transferred into dense trees. Compaction and copying can therefore be removed from the GC algorithms that MLton currently supports. Lastly, the GC will be made concurrent, allowing for the execution of the GC threads as the lowest priority task in the system. Stretch goals include a priority aware mechanism for the GC to signal to real-time ML threads that it needs to scan their stack and identification of places where the stack is shallow to bound priority inversion during this procedure.

Recommended Skills: C programming experience; garbage collector experience a plus but not required