The Need for Custom Memory Allocators

Memory allocators are used by dynamic data structures whose size is either known at runtime or changes during execution, e.g. std::vector, std::set, to manage dynamically changing memory requirements. The default allocation operations ("malloc", "new", "delete", etc.) provided by the C/C++ language and standard library are designed to be general-purpose. This generality comes at the cost of performance. For instance, your code could be single-threaded, but since malloc is designed to handle multi-threaded paradigms just as well, this extra functionality degrades the performance.

For thread-safe memory allocation, these functions often use a single lock on their internal heap, and, therefore, do not scale with multiple threads. As a result, parallel code that uses the default C/C++ allocators does not scale beyond a few threads. A good memory allocator is:

Fast: Dynamic allocation and de-allocation should not slow things down. They can be optimized for common allocation patterns.
Robust: They should be able to handle all the cases possible in the code and avoid memory leaks.
User-friendly: They should be easy to use.
Portable: They should be easily portable across system architectures.

Keeping these design goals in mind, in Galois, we have designed scalable parallel allocators for some of the common usage patterns. Some of them are described below.

Memory Allocators in Galois

Fixed Size Allocator

A common usage pattern is to allocate objects of the same type inside a parallel loop. Such an allocator can be implemented easily in a scalable manner. Galois provides galois::FixedSizeAllocator, which takes a template parameter as the type of object to be allocated. It only supports objects of fixed size type and always allocates the chunk of memory required to store one element of that size. Therefore, it cannot be used with STL data structures like std::vector and std::deque, which may need to allocate variable sized chunks of memory in order to keep all the elements contiguous in memory.

galois::FixedSizeAllocator can be used to allocate elements of STL data structures like std::set, and std::list, etc., which always allocate objects of fixed size type and elements are not required to be contiguous in memory. The source for galois::ThreadSafeOrderedSet shows how a fixed size allocator can be passed to std::set. Below is an example of using galois::FixedSizeAllocator:

using SetInt = std::set<int, std::less<int>, galois::FixedSizeAllocator<int>>;
SetInt s;
// use of s afterwards

Per-iteration Allocator

Per-iteration allocator galois::PerIterAllocTy can be used when dynamic data structures are defined inside the parallel loop and live for only one iteration of the loop. This allocator can be used inside the operators for galois::for_each. It can be used with STL data structures, e.g., std::vector and std::set etc., and supports variable size allocations.

To use per-iteration allocator, you need to pass galois::per_iter_alloc to galois::for_each. Here is an example of how to use it:

using Graph = /* graph type definition */;
using GNode = Graph::GraphNode;
Graph g;
galois::for_each(
    galois::iterate(graph),
    [&] (GNode n, auto& ctx) {
      // syntax for conforming to STL allocator interface
      using Alloc = galois::PerIterAllocTy::rebind<GNode>::other;
      // fast, scalable allocation for v, a per-iteration vector
      // get per-iteration allocator from ctx to initialize the v
      std::vector<GNode, Alloc> v(ctx.getPerIterAlloc());
      auto& d = graph.getData(n).data;
      std::copy(d.begin(), d.end(), std::back_inserter(v));
      // use of v below
    }
    , galois::per_iter_alloc()
    , galois::loopname("per_iter_alloc_example")
);

Power-of-2 Allocator

Power-of-2 allocator galois::Pow_2_VarSizeAlloc is a scalable allocator for dynamic data structures that allocate objects with variable size. This is a suitable allocator for STL data structures such as std::vector, std::deque, etc. It allocates blocks of sizes in powers of 2 so that insertion operations on containers like std::vector get amortized over time.

The following snippet shows how to define and use a std::vector of integers using power-of-2 allocator:

using VectorInt = std::vector<int, galois::Pow_2_VarSizeAlloc<int>>;
VectorInt v;
// use of v afterwards

Low-level Memory Interface in Galois

Types of Heaps in Galois

The allocators in Galois are implemented in a modular fashion. An allocator can take a heap implementation as its template argument. A heap implementation defines two functions:

void* allocate(size_t), and
void deallocate(void*, size_t).

Several heap implementations are just wrappers around another heap implementation to modify its interface in some way. In the following we list a few of them and show an example:

galois::runtime::SystemHeap defines the basic heap implementation used by Galois allocators, and is the source of all heap memory. It is implemented as a list of pages stored by each thread.
galois::runtime::FreeListHeap maintains a linked list of blocks of size B, where B is the size of the objects being allocated. This is a fixed size heap, and is a wrapper around a source heap implementation that is passed as a template argument.
galois::runtime::BumpHeap allows allocating different size objects within a block of memory by simply moving a pointer within the block. The size of the block is determined by the source heap implementation provided as a template argument. The memory within a block cannot be freed; however, blocks are freed only at the end of the program when the BumpHeap's destructor is called.
galois::runtime::ThreadPrivateHeap creates a per-thread instance of a source heap provided as a template argument. This is used for defining some of the parallel allocators.

Building Custom Allocators

Per-iteration allocator, from include/galois/Mem.h, shows how heap implementations can be combined together to form useful allocators:

typedef galois::runtime::BumpWithMallocHeap<
    galois::runtime::FreeListHeap<galois::runtime::SystemHeap>>
    IterAllocBaseTy;
typedef galois::runtime::ExternalHeapAllocator<char, IterAllocBaseTy>
    PerIterAllocTy;

Another example, from include/galois/runtime/Mem.h, shows how the Fixed Size allocator is defined:

typedef ThreadPrivateHeap<FreeListHeap<BumpHeap<SystemHeap>>> SizedHeap;

Plugging in 3rd Party Allocators

galois::runtime::ExternalHeapAllocator is a wrapper class that can be used to wrap any third-party heap implementation, and make it use-able by Galois and STL data structures. It takes the type-name of the heap implementation as a template parameter and a reference to it for instantiating the allocator object.

As an example, we can have a C++ memory allocator by wrapping malloc and free, from C, as follows (see file include/galois/runtime/Mem.h):

class MallocHeap {
public:
  enum { AllocSize = 0 };
  void* allocate(size_t size) { return malloc(size); }
  void deallocate(void* ptr) { free(ptr); }
};

Now we can wrap MallocHeap with galois::runtime::ExternalHeapAllocator, and use the wrapped allocator with STL containers. Below shows an example from lonestar/tutorial_examples/ThirdPartyMalloc.cpp:

  // Our 3rd-party heap
  using RealHeap = galois::runtime::MallocHeap;
  // Wrap RealHeap to conform to STL allocators
  using WrappedHeap = galois::runtime::ExternalHeapAllocator<int, RealHeap>;
  // Instantiate heaps
  RealHeap externalHeap;
  WrappedHeap heap(&externalHeap);
  // Use the wrapped heap
  std::vector<int, WrappedHeap> v(heap);
  for (int i = 0; i < 5; i++) {
    v.push_back(i);
  }
  std::cout << "Use of a std::vector with a third-party allocator wrapped by "
               "galois::runtime::ExternalHeapAllocator.\n";
  for (auto& j : v) {
    std::cout << j << std::endl;
  }

Table of Contents