libualloc - microlib for special allocation sequences
This library is intended to supplement (and not replace) standard libc malloc
by providing a modular set of allocators that can speed up and/or decrease
memory footprint of algorithms that have a specific sequence of allocations.
Key features:
- the code is real tiny; small enough to be easily audited
- portability:
- depends only on C89
- no assumption about operating system, libc, etc.
- does not try to be smart:
- simple, modular source code
- does exactly what the caller requests
- flexible connection to host program:
- can be used either as inlines with #includes
- or as a static linked library
- flexible install:
- install: can be system or user installed (make install)
- embed: can be svn:extern'd
- embed: can be simply included as a single subdirectory in a host program
- code size is so small that embedding won't have too much overhead
- flexible interface to the host operating system:
- low level access to memory is done through replaceable callback functions
- example callbacks provided for malloc and static heap/stack array backend
Motivation
The malloc in the libc needs to be generic. It either tries to be simple
but then it will have relatively high memory/CPU overhead. Or it tries to
be smart and do different things "detecting" how the application is making
allocations - but then it needs to be complex and at the end it may still
fail to figure how to minimize overhead in a specific case. For a portable
application it is also impossible to assume the libc will have a smart
allocator.
But even if the specific libc under the application is smart, using a
generic allocator which then tries to figure how to optimize allocation
run-time is sort of thinking backwards. Instead, the applaction programmer
may anticipate allocation pattern of specific parts of the code in advance
and use an allocator algorithm that performs best for that pattern. Libualloc
is a microlib offering a framework and a range of different allocators for
that.
Typical examples where a custom allocator may reduce memory/CPU overhead:
- a large number of allocations and frees with the same small size ->
slab-allocator.
- a large number of allocations with the same small size, but no free
until the end when the whole thing is freed at once; typical
for parsers when building an AST or when loading a tree of data
from a file -> stack-allocator.
- algorithm that needs temporary data for variable input size; for
reasonable sized input (95% of the cases) temp data should use the
stack (e.g. an array as local variable); but when temp grows too large
it needs to seamlessly expand using malloc().
License, author, contact
- Author: Tibor 'Igor2' Palinkas (contact)
- Source code from VCS: svn://svn.repo.hu/libualloc/trunk
- Source code from Release tarballs
Documentation - ToC