Efficient “out of heap” pointers for multicore OCaml
Guillaume Munch-Maccagnoni (INRIA)
This paper reports an experiment with a large pages allocator for the OCaml runtime, with measured performance improvements. A large pages allocator (also known in the literature under other names: superpages, etc.) is a standard component of a memory allocator that stands between the OS and user-facing allocators (e.g. minor and major heaps) and which reserves and manages large chunks of contiguous memory. The OCaml runtime currently gives up a good amount of control by assigning this role to the system allocator. Other languages have a simple implementation from which practical lessons can be learnt (especially in terms of portability), such as the one from the Go runtime.
Control over large pages affect (traditionally) the components implementing virtual address translation (hardware-level page table, TLB), in particular by leveraging (hardware-level) huge pages. It also enables (more specifically) efficient implementations of the OCaml page table, a data structure used in various parts of the OCaml runtime to classify pointers, to distinguish for instance which blocks belong to the heaps and which ones are “out-of-heap” during the marking phase of the GC.
One goal was to evaluate the possible performance of a page table for multicore OCaml. While I did not use original techniques, some of the results are unexpected a priori based on expressed beliefs in the OCaml community.
In essence, this paper reports the good hypothetical performance, in rigorous practical terms, of embedding (borrowing) linearly-allocated values inside garbage-collected values. A companion submission to the ML workshop reports a symmetrical result: how to efficiently embed (own) garbage-collected values inside linearly-allocated values. Taken together, the broader motivation is to show the feasibility of basing linear allocation with re-use (Lafont 1988, Baker 1992) in languages that would still leverage state-of-art garbage collection for non-linear values.
