Cheap

Cheap: a malloc/new optimizer

About Cheap

Cheap is a system that makes it easy to improve the performance of
memory-intensive C/C++ applications. Cheap works by replacing memory
allocation operations with a custom heap that can substantially
improve performance. Unlike past approaches, Cheap requires almost no
programming effort. For example, by adding just one line of code
(plus an #include), we were able to speed up the Boost JSON library
by 30-40%.

How it works

The Cheap library (libcheap.so) and its header cheap.h let you use
a custom heap with little effort. One line of code creates a custom
heap with certain characteristics and temporarily redirects all
memory allocation calls (malloc, free, new, delete) to that
heap until the heap goes out of scope.

To use Cheap, you include the file cheap.h, and then insert a line of code creating a custom heap. For example:

cheap::cheap<cheap::NONZERO | cheap::SINGLE_THREADED | cheap::DISABLE_FREE> r;

The options for the heap are passed as a series of flags, each separated by |.

Current options for the custom heap are the following:

cheap::NONZERO — no requests for 0 bytes
cheap::ALIGNED — all size requests are suitably aligned
cheap::SINGLE_THREADED — all allocations and frees are by the same thread
cheap::SIZE_TAKEN — need to track object sizes for realloc or malloc_usable_size
cheap::SAME_SIZE — all object requests are the same size; pass the size as the second argument to the constructor
cheap::DISABLE_FREE — turns free calls into no-ops

Once you place this line at the appropriate point in your program, it
will redirect all subsequent allocations and frees to use the
generated custom heap. Using cheap::DISABLE_FREE gives you the effect of a “region-style” allocator (a.k.a. “arena”, “pool”, or “monotonic
resource”); otherwise, you get a customized freelist implementation.

Once this object goes out of scope (RAII-style, like
std::lock_guard), the program reverts to ordinary behavior, using the
system-supplied memory allocator, and the custom heap’s memory is
reclaimed.

Placing a custom heap

Sometimes, placing a custom heap is straightforward, but it’s nice to
have help. We provide a tool called Cheaper that finds places in
your program where a custom heap could potentially improve
performance, and which generates the line of code to insert.

Collecting a trace with `libcheaper`

First, run your program with the Cheaper library, as follows:

LD_PRELOAD=libcheaper.so ./yourprogram

or, on Mac:

DYLD_INSERT_LIBRARIES=libcheaper.dylib ./yourprogram

This generates a file cheaper.out in the current directory. That file is a JSON file that contains information used by the cheaper.py script. NOTE: you need to compile your program with several flags to make sure Cheaper can get enough information to work. For example:

clang++ -g -fno-inline-functions -O0 yourprogram.cpp -o yourprogram

Analyze the trace with `cheaper.py`

You may need to install Rust (https://www.rust-lang.org/tools/install) the first time you
run Cheaper:

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Now run Cheaper as follows:

python3 cheaper.py --progname ./yourprogram

For a complete list of options, type python3 cheaper.py --help.

Cheaper will produce output, in ranked order from most to least
promising, corresponding to places in the code where you should insert
the cheap declaration. It outputs the line of code, which you can
then copy and paste directly into your program.