Discover the dark secrets of your OCaml programs with this new memory profiler, Spacetime, designed to identify hard-to-find memory leaks and excessive memory consumption. Spacetime, which can instrument industrial-scale applications, records how your program executes so it can reliably tell you the full stack backtrace at every point in the program that caused an allocation. Spacetime is not a statistical profiler. It is capable of recording allocations that happened in C stubs together with allocations that happened in code loaded via natdynlink.

We have a version of this pull request based on 4.03 which can be tried out:

opam remote add mshinwell git://github.com/mshinwell/opam-repo-dev
opam update mshinwell

To profile a program:

• opam switch 4.03.0+spacetime
• build your program
• run your program with the OCAML_SPACETIME_INTERVAL environment variable set to an integer giving a time interval in milliseconds. This interval controls how often Spacetime examines the memory usage of the program.
• make sure your program exits normally.

The profiling information is currently written into a file called spacetime (this will be given a more satisfactory name in due course). As an alternative, you can not set the environment variable, and use the new Spacetime module in the stdlib instead.

To read the profiling information there are new libraries provided in otherlibs/ in the compiler source tree: Spacetime_lib and Raw_spacetime_lib. @lpw25 however has written an embryonic web-based UI for visualising the output. It is probably faster to use a different switch for this (see note on cross-compilation below):

opam switch 4.03.0+spacetime+disabled
git clone https://github.com/lpw25/prof_alloc
opam pin add prof_alloc $(pwd)/prof_alloc

Then in the directory containing the Spacetime file, run the binary produced (prof_alloc/bin/prof_alloc.exe) which will start a web server bound to localhost on port 8080. Then visit this in your browser. (There are command-line options to change the port, etc.) The x-axis is time and the y-axis is the number of words found in the heap at the given time, classified by the point at which they were allocated. If you mouse-over a particular slice of the graph you will see a source location (a few of these may still appear as integers, which can be decoded with gdb, although they will display properly once we finish the code). So for example you might see that the largest slice, 30% of the memory came from List.map. If you then click that slice, the graph will change to show what the callers of List.map were. For example we might find that out of that 30% of memory allocated by List.map, 20% came from function X.foo calling List.map and the remaining 80% came from function Y.bar.

The browser-based visualisation can be slow to display the graph, so have patience; we hope to rectify this shortly. We may also produce a curses-based interface and some kind of query language associated with Spacetime_lib.

There is not yet support for visualising the total number of words allocated at each program point across the lifetime of the program, although the instrumentation code for this is complete. We plan to fix this deficiency pretty soon.

We propose the compiler patch shown on this GPR for inclusion in trunk. Our intention is that only basic support for reading the profiles is provided within the compiler distribution; complicated visualisation can live outside. The compiler patch is largely orthogonal to existing code. The vast majority of changes not in the backend are actually related to propagating extra location information, which we also need for enhanced debugging information. A (slightly modified) version of these changes will be presented shortly by @lpw25 . Subject to those being accepted this diff will be greatly simplified.

Spacetime works by instrumenting OCaml code such that it builds the dynamic call graph of the program, outside of the OCaml heap, at runtime. The majority of nodes in this graph usually correspond to invocations of OCaml functions. An edge from one node to another indicates a function call. A path from the root to one of these nodes gives the stack backtrace at that function invocation. (There may be multiple nodes for a given function, of course.) Nodes that correspond to OCaml functions that might allocate have space within them for the recording of the number of times that allocation point has been passed. They also contain space for unique identifiers that will be written into spare space in values' headers; these identifiers are read from the heap and correlated with the graph to produce the human-readable profile. (The technique of using extra bits in the header was independently discovered some years ago by myself and Fabrice Le Fessant's team.)

If building the call graph of an OCaml program one has to be careful about tail calls. Spacetime is careful about this, and will correctly form cycles in the graph corresponding to tail calls. Self-recursive calls (i.e. recursive calls to the function currently being defined) are also treated as tail calls to simplify the graph. The information loss here is minimal.

Each thread has its own graph. There is also a single distinguished graph used for asynchronous execution of finalisers and signal handlers.

Nodes in the graph not corresponding to OCaml functions correspond to C functions. Spacetime uses the libunwind library to extract stack backtraces at allocation points in C code and generate the necessary nodes in the call graph. At present, the notion of backtrace does not quite match up with the notion used in OCaml, but we will rectify that in due course. (If libunwind is not available, recording of allocations from C is disabled, but all other functionality remains.)

Spacetime does not rebuild the call graph if it already exists: if a given function in a given backtrace context has already been called, the nodes will be reused. This means that whilst programs may see an initial performance penalty (running maybe about half of normal speed), programs that run for longer periods of time should substantially speed up once the graph of hot paths has been built.

The instrumentation code is partially emitted directly as assembly and partially implemented in C. An extra register (to keep track of where in the graph we are) is required when functions are called, which makes it imperative that all parts of a program using Spacetime are compiled with such. The emission of instrumentation is cunning: it requires information (specifically as to whether calls will be tail or non-tail) only deduced during instruction selection---yet we do not want to write Mach code when describing the instrumentation. Instead, there are callbacks that generate more Cmm code on the fly from Selectgen, run instruction selection on that generated code, and splice it in. To avoid some difficult list manipulation we have changed the next field in Mach instructions to be mutable.

The call graph has a compact representation which is not uniform: each OCaml function generates a different shape of node depending on its pattern of call and allocation points. These representations are described in shape tables, which parallel the frame tables. For decoding locations, Spacetime uses the frame tables when possible, which helps with cross-platform portability. However resolution of symbols in C stubs is going to require platform-dependent code; it is proposed to use the owee library due to Bour in the first instance for this. Likewise, there is a certain transformation on the C backtraces that we will need to perform as a post-processing step, which will require platform/binary-format-dependent code (specifically to find the top-of-function address given an address somewhere in that function).

The backend changes required for Spacetime, which are fairly minor, have only currently been implemented for x86-64. It works very well on Linux; on the Mac, it may be rather slow (we suspect this is due to libunwind, and we may either need to emit compact unwind info or write a frame-pointer-based unwinder instead). As it stands, it should function on Windows (although without support for recording allocations in C), but we have not yet tested it. 32-bit platforms are not supported at all, as there is insufficient space in values' headers for the profiling information words.

Code to snapshot the heap is currently quite naive (there is at least one extant bug relating to the "hole in the minor heap"): in particular it performs a linear scan of the minor heap rather than traversing from roots (we intend to fix this now that we have support for recording total allocations across the lifetime of the program; previously it was important to scan rather than work from roots on the minor heap or some very short-lived values might continually be missed out of the profile). It may also record values in the major heap that are about to be swept up. However neither of these deficiencies appears to hinder its usefulness.

Spacetime's instrumentation, possibly extended, may well be useful for other analyses. Two such might be analysis of write barrier hits, and profile-directed feedback for optimisation.

This is still a work in progress, although mostly finished. One major item remaining relates to the lack of cross-compilation support in the compiler. At present, if you configure with -spacetime, the whole compiler is built with instrumentation. This is unsatisfactory for performance, and I am going to investigate ways of fixing that. The most likely outcome is to try to integrate with some of the cross-compilation work being done elsewhere such that multiple copies of the stdlib and other libraries can be built with different options (e.g. with and without Spacetime instrumentation) and then correctly located when the compiler is run.

I imagine there will be a number of questions about this work, so I will leave it at that for now.