Detailed Feature List

Detailed Feature List

For the purposes of those evaluating this package, we provide a detailed feature list for each of the PPMalloc modules. Further below we provide a list of features not included in PPMalloc and an explanation for why they aren't present.

GeneralAllocator / GeneralAllocatorDebug

GeneralAllocator is a fully generalized allocator with no serious limitations. GeneralAllocatorDebug is a user-level debug layer over GeneralAllocator. We list GeneralAllocator and GeneralAllocatorDebug together because the latter is an extension of the former and they will almost always be used with the other in a development environment. For more information and example code, see GeneralAllocator.html. We use the term "core memory" here to refer to the large block of memory that an allocator uses as the source for user allocations.

Feature Description
Clean implementation
The header and source are very clean and include no hacks or concessions. Dependencies are minimal, as GeneralAllocator relies only on EABase. All public functionality is documented in the header in Doxygen-friendly format. Comes with a good set of heavy unit tests that test both simulation allocation behaviour and real-world allocation behaviour.
High performance and efficiency
GeneralAllocator is very fast and very efficient. The primary algorithm is based on the well-regarded dlmalloc algorithm but is futher improved. GeneralAllocator runs at 5x-20x faster than most custom allocators in use within EA. No allocator yet seen within EA has been as fast or as scalable.
High scalability
GeneralAllocator scales very well from small systems to large systems. In general, scaling is nearly constant (O(1)) with respect the amount of memory or number of allocations involved. This is unlike many other allocators which bog down once the application goes beyond a few thousand concurrent allocations, and large applications for the PC are already pushing a million concurrent allocations while console applications of the future will have similarly high requirements.
Minimal system allocation overhead
System overhead per allocation is either 4 or 8 bytes, depending on the allocation size. This is compared to 12 or 16 bytes of overhead found in most allocators. When a 'tiny block' shim is used, the overhead for small block sizes becomes zero.
Highly resistant to both internal and external fragmentation. Internal fragmentation refers to extra memory that is unused within an allocated, while external fragmentatio refers to free blocks or space that in practice become unavailable for use. GeneralAllocator's algorithm is resistant to both types of fragmentation an university studies on GeneralAllocator's brother, dlmalloc, confirm this.
Useful extra malloc variants, including MallocAligned, Realloc, MallocMultiple, Calloc.
In addition to the standard Malloc, GeneralAllocator has MallocAligned which allows for an allocation to be aligned to a user-specified value with an optional offset to the requested aligned position. GeneralAllocator also has an optimized Realloc which can very quickly shrink an allocation in place and grow in place as well if possible. MallocMultiple allows the user to request multiple guaranteed-contiguous blocks of equal or varying size in a single call that has executes almost as fast as a single allocation.
Includes high memory and end-packed memory options
High memory allocation is an allocation option that requests the allocated block be stored in a more permanent place so as to reduce external fragmentation. GeneralAllocator supports the high memory option for all malloc variants. End-packed memory is an option that requests that memory come from as low as possible or high as possible in the heap in order to reduce fragmentation at the cost of extra processing time.
Ability to create independent peer heaps and sub-heaps Unlike some allocators GeneralAllocator is not hard-wired to be a "singleton". Multiple concurrent instances of GeneralAllocator are possible and one instance of GeneralAllocator can act as a sub-heap within another instance of GeneralAllocator.
Portable to all current platforms and compilers
GeneralAllocator is portable to all current EA platforms, including PS2, PSP, XBox, GameCube, Windows, Linux (various hardware), Macintosh OSX, and others. GeneralAllocator compiles under all currently used compilers, including GCC, VC++, SN, Intel, Metrowerks, and Borland. Portability includes 64 bit platforms such as IA-64 and Power-PC64.
Savvy to platforms
GeneralAllocator isn't limited or crippled to any least-common denominator platform. For example, under Windows it will take advantage of memory mapping and virtual memory reserve and commit operations. This allows for maximum performance and flexibility on platforms that have extended functionality. It also allows for GeneralAllocator to be a completely arbitrary replacement for malloc/free new/delete for all types of uses from tools to shipping applications.
Flexible heap reporting
The heap can be walked by the user via iteration or via a function callback. Additionally, the user can take a snapshot of the heap state for storage and future analysis. Filter flags allow the user to specify the types of blocks to be iterated. Heap reporting forms the basis for the creation heap analysis tools and is invaluable for analysis of runtime memory issues.
Allocation hooking
Allocation hooks allow the user to be notified of every user-level allocation operation, such as Malloc and Free. For added flexibility, hooks come in both entry and exit form, whereby the former is called before the allocation operation is executed and the latter is called after execution. The hook gives the user all information about the call, including the return value for exit hooks.
Multi-level heap validation
The heap structure can be validated automatically every N operations or manually at any time via the ValidateHeap function. Validation has multiple levels of checking detail, from basic quick checking to fully comprehensive checking. If some piece of code is trashing the heap, automatic or manually sprinkled heap validation calls will find the culprit.
Optional thread safety
Enables use of the allocator in a thread-safe way. GeneralAllocator has special thread safety functionality which greatly improves thread-safe performance for slow platforms such as PS2, which has slow semaphore locking.
Plug-innable assertion/trace output
User can redirect assertion and trace output to the function of their choice, allowing integration with the user's debug/trace system.
Extensive leak reporting output Memory leak trace output includes detailed block information, including data preview, user debug tags, file/line, allocation call stacks, etc.
Flexible core memory
Can assign your own core memory (the source for allocation) to GeneralAllocator or let it get it from the system itself. Core memory can be added via multiple core blocks and can be added at any time. Core memory can come from independent sources and be of independent types.
Manual or automatic core expansion
The user can manually assign core; this is typically used on console and embedded platforms. Additionally, the allocator can be enabled to automatically expand core via operating system memory. This is typically used on PC, workstation, and server platforms that have more advanced memory management systems than smaller platforms.
Many compile time and runtime configurable options There are a number of compile-time options that tweak the functionality or performance of GeneralAllocator and GeneralAllocatorDebug. Additionally, there are a number of runtime options that tweak the functionality or performance of these allocators.
Automated activity recording and playback. Recording and playback of allocation activity can be valuable in studying heap behaviour. GeneralAllocator is recordable automatically via AllocationRecorder. AllocationRecorder can playback recordings via GeneralAllocator or a user-specified mechanism.
Extensive internal consistency checking
GeneralAllocator has very extensive internal consistency checking which is enabled by default in a debug build but is available if desired in a shippable build. Whether through maintainence of the code or through user-caused damage of the heap, the internal consistency very quickly finds the problem.


Flexible delayed frees

Delayed frees refer to behaviour whereby an allocator doesn't free memory when the user requests but instead delays it for some time in order to help detect certain kinds of application misbehaviour. GeneralAllocatorDebug has a configurable delayed free mechanism with multiple policies, such as count-based, time-based, and volume-based delays.
Flexible guard fills (sentinels)
GeneralAllocatorDebug has advanced guard fill (a.k.a. sentinel) functionality. Guard fills can be of constant size or scaled to the size of the allocation with clamps on min/max fill sizes. Guard fills are useful in detecting memory overruns and random memory writes by application code. 
Debug fills
GeneralAllocatorDebug implements various kinds of memory fills to aid in detecting application misbehaviour. These include including new fills, free fills, delayed free fills, and guard fills.
Constant allocations GeneralAllocatorDebug allows the user to flag a memory block as constant and will verify that the contents have not changed over the life of the allocation.
Pointer validation
GeneralAllocatorDebug has built-in pointer validation. This is particularly useful for detecting "multiple free" (whereby a block of memory is freed more than once) bugs when they occur instead of later when the heap becomes corrupted.
Arbitrary data association
GeneralAllocatorDebug allows the user to attach any data of any size to an allocation. This data can be a pointer to other data or can be a block of arbitrary size. An number of unique pieces of data can be associated with blocks; the user is not limited to a single item. The user also has the option of storing this data at any time and not just at the time that the allocation occured. The user also has the option of storing this data within the allocated block or separately from the allocated block.
Named allocations
A common technique for tracking the usage of memory is to associate a name with an allocated block. GeneralAllocatorDebug allows for named allocations. Names can be unique to each block and don't have size limits.
File/Line recording
Call stack recording
GeneralAllocatorDebug has the ability to store file/line information about an allocation as commonly done with the C __FILE__ and __LINE__ defines. It also has the ability to store full or partial call stacks for allocations as well, for extended contextual information about the allocation. Both file/line and callstack information can be done globally or just on the blocks the user chooses.
Group recording
GeneralAllocatorDebug has the optional concept of allocation groups whereby it has an assignable current group number and any allocations are assigned that group number. A primary benefit is that the user can enter a new phase of the application and change the group number and upon exiting that phase the user can verify that no allocations exist with that group number.
Other per-block information
In addition to the various items mentioned above, GeneralAllocatorDebug has the ability to optionally automatically associate other pieces of information with allocations, such as requested size, alignment, index, time, system overhead, and thread id.
Extensive metrics
GeneralAllocatorDebug has extensive metrics reporting facilities. You can query the number of allocations, volume of allocations, volume of system overhead, total historical allocation count, free count, etc.

Stack Allocator

The StackAllocator is an allocator which allocates space via a pointer increment and is very fast at the cost of not being able to free arbitrary individual blocks.

Feature Description
Clean implementation
The header and source are very clean and include no hacks or concessions. Dependencies are minimal, as StackAllocator relies only on EABase (though you can enable it to use GeneralAllocator). All public functionality is documented in the header in Doxygen-friendly format. Comes with a fairly heavy unit test.
Very fast allocation
Allocation is about as fast as an allocator can get, as it amounts to little more than an alignment check and pointer increment in fast mode.
All conventional allocation styles
Includes Malloc, MallocAligned, Realloc, and Free, just like GeneralAllocator.
Incremental allocation
With incremental allocation, you can build an allocation incrementally instead of all at once. Building an object incrementally is not the same as making multiple calls to Malloc, as the latter aligns allocations whereas the former doesn't. Also, the incremental allocation is faster as it has less to do. Incremental objects are useful for building streams of data on the fly and is also useful for building static string tables or similar tables on the fly.
Fast mode / safe mode
Allocations can be done in fast mode, whereby no bounds check is done on the allocation space, and safe mode, whereby an space check is done and core is expanded if needed.
Multiple free
Allows you to free one or more blocks off the top of the stack at a time.
Bookmarks
Allows you to record a position in the allocation stack to which you can roll back to later. This is useful for pushing and popping pools used for systems that are temporary.
Plug-innable core memory
Much like GeneralAllocator, StackAllocator lets you supply 'core' memory for the allocator to work with. Multiple blocks of core are supported; the allocator is not limited to a single contiguous core.
Same interface as GeneralAllocator
Malloc, MallocAligned, etc. are defined the same in StackAllocator as they are in GeneralAllocator, making the systems consistent with each other.The mechanism to add and free core is also the same as GeneralAllocator.

FixedAllocator

The FixedAllocator is an allocator which allocates blocks of a single size, which increases speed and eliminates block overhead at the cost of requiring some extra pool space.

Feature Description
Clean implementation
The header and source are very clean and include no hacks or concessions. Dependencies are minimal, as FixedAllocator relies only on EABase (though you can enable it to use GeneralAllocator). All public functionality is documented in the header in Doxygen-friendly format. Comes with a fairly heavy unit test.
Very fast allocation
Allocation is about as fast as an allocator can get, as it involves only a comparison and two assignments.
Templated design
For maximal runtime efficiency, FixedAllocator is a C++ template class that compiles down to the minimal code with the least possible overhead. The class is templated by allocation class type, though it can also be used to simply allocate memory of a given size.
Similar interface to GeneralAllocator
The primary functionality of FixedAllocator is the same as GeneralAllocator, for consistency. There is Malloc and Free (MallocAligned and Realloc are not applicable), as well as a mechanism to manually add core which is similar to GeneralAllocator.

NonLocalAllocator

(to do)

SmallObjectAllocator / SmallBlockAllocator

(to do)

ScratchpadAllocator

(to do)

HandleAllocator

The HandleAllocator is an allocator which implements lockable memory, resulting in very good compaction and low fragmentation at the cost of speed and ease-of-use.

Feature Description
Clean implementation
The header and source are very clean and include no hacks or concessions. Dependencies are minimal, as FixedAllocator relies only on GeneralAllocator (which itself is dependent only on EABase). All public functionality is documented in the header in Doxygen-friendly format. Comes with a fairly heavy unit test.
Conventional lock semantics
Calling Lock returns a pointer, calling Unlock undoes the Lock. Locks are cumulative, so a handle can be safely locked more than once at a time by two different entities.
All conventional allocation styles Includes Malloc, MallocAligned, Realloc, and Free, just like GeneralAllocator. The only difference is that HandleAllocator returns a handle instead of a pointer.
Mixable with GeneralAllocator
HandleAllocator is built upon GeneralAllocator and can share allocations with a GeneralAllocator heap.
Rich debugging functionality
Since HandleAllocator uses GeneralAllocator at its core, all the debug functionality of GeneralAlloator and GeneralAllocatorDebug applies to HandleAllocator as well.
Allocation-level and heap-level compaction
Individual allocations can be manually compacted or the entire heap can be manually compacted. The former is faster but the latter generally results in better packing.
Handle utilities
ValiateHandle, GetHandleFromAddress, GetLockCount, etc.
Multiple compaction levels
Multiple compaction levels allows for balancing the tradeoff between compaction and runtime speed, as better compaction requires more processing time.
Multiple compaction strategies
Multiple compaction strategies can be applied to individual allocations or to the entire heap. One such strategy is to pack high instead of pack low.
Optional thread safety
Enables use of the allocator in a thread-safe way. HandleAllocator has special thread safety functionality which greatly improves thread-safe performance for slow platforms such as PS2, which has slow semaphore locking.
Same interface as GeneralAllocator Malloc, MallocAligned, etc. are defined the same in HandleAllocator as they are in GeneralAllocator, making the systems consistent with each other. The mechanism to add and free core is also the same as GeneralAllocator.

Non-Feature List

Here we provide a list of features that PPMalloc doesn't have which you may have considered. For simplicity, the list is not broken down by module.

Feature Description
Explanation
StackAllocator and FixedAllocator thread safety
The StackAllocator and FixedAllocator classes have no option to enable thread safety. This is unlike the GeneralAllocator, GeneralAllocatorDebug, and HandleAllocator classes, which have the option to be thread safe.
Adding thread safety is a possibility for these classes and is open for consideration. In the meantime, most uses for classes like these are specialized and thread safety can often be implemented by  the user of the class around usage of the class instances. These allocators are much simpler than GeneralAllocator and HandleAllocator and there is little or no special benefit to internalizing thread safety to the class other than to simplify its usage.
Generalized Fixed Allocator
There is no FixedAllocator variant with takes an arbitrarily-sized allocation request and allocates it from a large array of fixed sized bins.
This approach is sometimes seen as an allocation strategy. It results in fast allocation speed at the cost of memory wastage due to unused pool space. Studies have been done on such allocators and they are in practice not much faster than allocators such as GeneralAllocator but have significantly higher memory usage due to the above-mentioned wastage. In a nutshell, you don't wnat one of these allocators when instead you should just use GeneralAllocator.
Ability to report X
PPMalloc doesn't have high-level reporting functionality but instead only has the core functionality upon which high-level reporting can be built.

Various users have added customized reporting to their allocation systems to support their specific needs. Each of these is unique to the team or project. PPMalloc (the GeneralAllocator module in particular) has rich support for reporting heap information to the user, but it doesn't try to solve needs that are specific to individual projects.
Advanced multi-threading support
GeneralAllocator doesn't have specialized functionality for heavy multithreaded uses. If two threads are very frequently using the same allocator, there is no advanced functionality to improve performance. An example of such an allocator is Hoard.
For the great majority of EA needs, there is little to be gained by specialized multithreading support such as this. However, if it is ever deemed necessary, GeneralAllocator can be extended to support such functionality.


End of document