emeryberger/heap-layers

Heap Layers: An Extensible Memory Allocation Infrastructure

Heap Layers: An Extensible Memory Allocation Infrastructure

Copyright (C) 2000 - 2021 by Emery Berger

Heap Layers is distributed under the terms of the Apache 2.0 license.

Introduction

Heap Layers provides a flexible infrastructure for composing high-performance memory allocators out of C++ layers. Heap Layers makes it easy to write high-quality custom and general-purpose memory allocators. Heap Layers has been used successfully to build a number of high-performance allocators, including Hoard and DieHard.

Using Heap Layers

For an introduction to Heap Layers, read the article Policy-Based Memory Allocation, by Andrei Alexandrescu and Emery Berger. It's a good overview. See also "Memory Allocation: Either Love It or Hate It (or just think it’s okay)", a talk by Andrei.

Heap Layers contains a number of ready-made heap components that can be plugged together with minimal effort, and the result is often faster than hand-built allocators. The PLDI 2001 paper Composing High-Performance Memory Allocators has plenty of examples.

Performance

Heap Layers can substantially outperform its only real competitor, the Vmalloc package from AT&T. The OOPSLA 2002 paper Reconsidering Custom Memory Allocation paper has more details.

Not only is Heap Layers much higher level and simpler to use, but its use of templates also improves performance. Heap Layers both eliminates the function call overhead imposed by Vmalloc layers and yields higher quality code by exposing more optimization opportunities.

Citation

To reference Heap Layers in an academic paper, please cite as follows:

@inproceedings{DBLP:conf/pldi/BergerZM01,
  author    = {Emery D. Berger and
               Benjamin G. Zorn and
               Kathryn S. McKinley},
  title     = {Composing High-Performance Memory Allocators},
  booktitle = {Proceedings of the 2001 {ACM} {SIGPLAN} Conference on Programming
               Language Design and Implementation (PLDI), Snowbird, Utah, USA, June
               20-22, 2001},
  pages     = {114--124},
  year      = {2001},
  crossref  = {DBLP:conf/pldi/2001},
  url       = {https://doi.org/10.1145/378795.378821},
  doi       = {10.1145/378795.378821},
  timestamp = {Wed, 14 Nov 2018 10:54:59 +0100},
  biburl    = {https://dblp.org/rec/bib/conf/pldi/BergerZM01},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

@proceedings{DBLP:conf/pldi/2001,
  editor    = {Michael Burke and
               Mary Lou Soffa},
  title     = {Proceedings of the 2001 {ACM} {SIGPLAN} Conference on Programming
               Language Design and Implementation (PLDI), Snowbird, Utah, USA, June
               20-22, 2001},
  publisher = {{ACM}},
  year      = {2001},
  url       = {http://dl.acm.org/citation.cfm?id=378795},
  isbn      = {1-58113-414-2},
  timestamp = {Mon, 21 May 2012 16:19:53 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/pldi/2001},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

heap-layers's Issues

heaps/special/zoneheap.h alignment problem?

class Arena {
Arena * nextArena;
char * arenaSpace;
// long long _dummy; // For alignment.
};

Why it needs a _dummy here? In codemonkey, sizeof(long long) is only 8 bytes. I guess that this works for other machines too. That actually lead to a problem of alignment. two dummys should work better.

Failing to compile on windows

Failing to compile on VS 2015. Its looking for file stdalign.h.

cl /I. /Iinclude /Iinclude/util /Iinclude/hoard /Iinclude/superblocks /IHeap-Layers /D "NDEBUG" /D "_WINDOWS" /D "_WINDLL" /D "_WINRT_DLL" /D "_UNICODE" /D "UNICODE" /Zi /Ox /MD /nologo /W1 /WX- /Ox /Oi /Oy- /Gm- /EHsc /MD /GS /Gy /Zc:wchar_t /Zc:forScope /Gd /errorReport:queue "source\libhoard.cpp" "Heap-Layers\wrappers\winwrapper.cpp" "source\wintls.cpp" /GL /link /DLL /subsystem:console /OUT:libhoard.dll libhoard.cpp d:\dev\hoard\src\heap-layers\wrappers\ansiwrapper.h(9): fatal error C1083: Cannot open include file: 'stdalign.h': No such file or directory

Compile Error: "error: 'protect' is not a member of 'HL::MmapWrapper'"

gcc version 4.4.6

consider using Mersenne primes for `myhashmap.h`

See https://ariya.io/2007/02/modulus-with-mersenne-prime

tprintf.h includes unistd.h and doesn't compile on Windows

Anything after 5808161 no longer builds on Windows as tprintf.h assumes various things that won't exist on Windows.

update to support `jemalloc` extended API

http://jemalloc.net/jemalloc.3.html

Compile Error: "error: 'protect' is not a member of 'HL::MmapWrapper'"

GCC: gcc version 4.4.6
OS: CentOS release 6.2
CPU: Intel(R) Xeon(R) CPU E5645 @ 2.40GHz
$ uname -p
x86_64

---

$ make linux-gcc-x86-64
g++ -pedantic -Wall -Wpointer-arith -Woverloaded-virtual -Werror=return-type -Wtype-limits -Wempty-body -Wno-ctor-dtor-privacy -Wno-overlength-strings -Wno-invalid-offsetof -Wno-variadic-macros -Wcast-align -Wno-long-long -pthread -pipe -DNDEBUG -W -Wall -O3 -DNDEBUG -pipe -fPIC -m64 -march=nocona -ffast-math -g -I. -Iinclude -Iinclude/layers -Iinclude/util -Iinclude/math -Iinclude/static -Iinclude/rng -Iinclude/hoard -Iinclude/superblocks -IHeap-Layers -DDIEHARD_DIEHARDER=0 -D_REENTRANT=1 -DDIEHARD_MULTITHREADED=1 -shared -D'CUSTOM_PREFIX(x)=diehard##x' Heap-Layers/wrappers/gnuwrapper.cpp source/libdieharder.cpp -Bsymbolic -o libdiehard.so -ldl -lpthread
Heap-Layers/wrappers/gnuwrapper.cpp:213: warning: unused parameter 'param'
Heap-Layers/wrappers/gnuwrapper.cpp:213: warning: unused parameter 'value'
Heap-Layers/wrappers/gnuwrapper.cpp:218: warning: unused parameter 'pad'
Heap-Layers/wrappers/gnuwrapper.cpp:231: warning: unused parameter 'ptr'
In file included from include/randomminiheap.h:25,
from include/diehardheap.h:33,
from source/libdieharder.cpp:41:
include/util/madvisewrapper.h:62: warning: unused parameter 'ptr'
include/util/madvisewrapper.h:62: warning: unused parameter 'sz'
In file included from include/dieharder-pagetable.h:13,
from include/randomminiheap-dieharder.h:7,
from include/randomminiheap.h:44,
from include/diehardheap.h:33,
from source/libdieharder.cpp:41:
include/randommmap.h: In constructor 'RandomMmap::RandomMmap()':
include/randommmap.h:37: error: 'protect' is not a member of 'HL::MmapWrapper'
include/randommmap.h: In member function 'void* RandomMmap::map(size_t)':
include/randommmap.h:77: error: 'unprotect' is not a member of 'HL::MmapWrapper'
include/randommmap.h: In member function 'void RandomMmap::unmap(void_, size_t)':
include/randommmap.h:102: error: 'protect' is not a member of 'HL::MmapWrapper'
In file included from Heap-Layers/wrappers/all.h:1,
from Heap-Layers/heaplayers.h:109,
from source/libdieharder.cpp:29:
Heap-Layers/wrappers/ansiwrapper.h: In constructor 'HL::ANSIWrapper::ANSIWrapper() [with SuperHeap = HL::LockedHeap<PosixSpinLockType, CombineHeap<DieHardHeap<8, 7, 4096, false, false>, TheLargeHeap> >]':
source/libdieharder.cpp:92: instantiated from here
Heap-Layers/wrappers/ansiwrapper.h:30: warning: unused variable 'checkAlignment'
make: *_* [linux-gcc-x86-64] Error 1

Question: how to get 16 byte aligned address using ZoneHeap?

Hi,
i'm try to build a simple memory allocator(as an assignment poject) and i found Heap layers very interesting
using Allocator = FreelistHeap<ZoneHeap<SizedMmapHeap, 1024 * 8>>;
when defining my allocator as shown above i don't get 16 byte aligned address
after reading the source code i have found :

class Arena {
  public:
    Arena() {
      static_assert((sizeof(Arena) % MallocInfo::Alignment == 0),
              "Alignment must match Arena size.");
    }

    Arena * nextArena;
    char * arenaSpace;
    size_t arenaSize;
  };

as Arena is never instantiated explicitly the static_assert fail silently i don't know if it's intentional, in my case i added a dummy
pointer to solve the problem (is there a better solution or am i using heap layer the wrong way)
thanks