Expand description
Description
Onsen provides hot Pools for objects. In most cases allocation from such a Pool is faster and offers better locality than the standard allocator. For small to medium sized objects the performance improvement is around 20% or better. For large objects the gains become smaller as caching effects even out. These improvements cover operating on objects because of locality, not just faster allocation speeds.
Details
Onsen pools allocate blocks with exponentially growing sizes. Allocations are served from these blocks. Freed entries are kept in a double linked cyclic freelist. This freelist is kept in weakly ordered and the entry point always point close to where the last action happend to keep the caches hot.
Box, Rc and Sc
Onsen comes with its own Box
and Rc
/Weak
implementations that wrap the underlying
RcPool
in a safe way. A Sc
reference counted box without weak reference support is
available as well and provides an advantage for small objects where the weak count would add
some weight.
For each of these a variant that uses static global pools is avaialble as well.
Slots
Allocating from a pool returns Slot
handles. These are lightweight abstractions to memory
addresses, they do not keep a relation to the pool they are allocated from. The rationale for
this design is to make them usable in a VM that uses NaN tagging.
Slot Policies
Slots are guarded by typestate policies which prevent some wrong use at compile time.
Slots and Safety
Because of this slots need to be handled with care and certain contracts need to be
enforced. The library provides some help to ensure correctness. Few things can not be asserted
and are guarded by unsafe functions. Higher level API’s (Such as Box
, Rc
and Sc
above) can
easily enforce these in a safe way.
- Slots must be given back to the pool they originate from.
- Slots must not outlive the pool they are allocated from.
- When a Pool gets dropped while it still has live allocations it will panic in debug mode.
- When a pool with live allocations gets dropped in release mode it leaks its memory. This is unfortunate but ensures memory safety of the program.
- There is
pool.leak()
which drops a pool while leaking its memory blocks. This can be used when one will never try to free memory obtained from that Pool. - This applies to u64 NaN tags as well.
- Slots must be freed only once.
- This is always asserted. But the assertion may fail when the slot got allocated again.
- Slots are not ‘Copy’ thus one can not safely free a slot twice but there is an explicit ‘copy()’ function used by the reference count implementations and the NaN tagging facilities can copy an ‘u64’ and try to attempt to free this multiple times. These are ‘unsafe’ functions becasue of that.
- References obtained from slots must not outlive the freeing of the
Slot
.- This is the main reason that makes the
Slot
freeing functions unsafe. There is no way for a pool to know if references are still in use. One should provide or use a safe abstraction around references to enforce this.
- This is the main reason that makes the
Features
Onsen provides a singlethreaded Pool
, a singlethreaded reference counted RcPool
and a
multithreaded TPool
. Additional features are gated with feature flags.
- parking_lot use parking_lot for the
TPool
(insteadstd::sync::Mutex
). This makes sense when parking lot is already in use. There is no significant performance benefit from this in onsen. - stpool Makes
STPool
available, a singlethreaded pool that uses aThreadCell
which is much faster than mutex protected pools. This pools can be moved cooperatively between threads with acquire/release semantics. - tbox Adds the API for
TBox
,TRc
,TSc
that use a global pool per type. The advantage is that the box does not need to store a reference to its pool which saves a bit memory and improves locality for small objects. - st_tbox use
STPool
for the tbox API, this enables tbox and stpool as well.
st_tbox is the default. This enables the most complete API with best performance.
Performance Characteristics
-
Onsen pools are optimized for cache locality and with that to some extend for singlethreaded use. It is best to have one pool per type per thread.
-
The
TPool
adds a mutex to be used in multithreaded cases but its performance is significantly less than the singlethreaded pools but in many cases still better than the std allocator. One will still benefit from locality though. -
The
STPool
is singlethreaded but can be cooperatively passed between threads, its performance is on par with the other singlethreaded pools. This is especially important when one usesTBox
,TRc
orTSc
.
Benchmarking
Onsen uses criterion for benchmarking, since onsen is made for singlethreaded application its best to be tested when locked on a single CPU core and lock the core to some frequency well below the max to give more consistent results. At higher priority so it wont be disturbed as much from other programs. On Linux you may do something like:
sudo renice -15 $$
sudo cpupower -c 1 frequenc-set -f 2.8GHz
taskset 2 cargo bench
Will produce target/criterion/report/index.html
.
Macros
For each type that shall be allocated with TBoxes
there must be an associated global
memory pool. This is defined with this macro.
For each type that shall be allocated with TRcs
there must be an associated global
memory pool. This is defined with this macro.
For each type that shall be allocated with TScs
there must be an associated global
memory pool. This is defined with this macro.
Structs
A Box for pool allocated objects. This wraps Slots in a safe way. Dropping a Box will
ensure that the destructor is called and the memory is given back to the pool. Uses a RcPool<T>
to keep the backing pool alive as long any Box<T>
is still in use.
A single threaded, interior mutable memory Pool holding objects of type T.
The error returned when a STPool
can not be acquired or released.
A reference counted smart pointer for pool allocated objects. This wraps Slots in a safe
way. Rc’s need a RcPool<RcInner<T>>
as pool.
Data including reference counters
A single thread, interior mutable memory Pool backed by a reference count. This allows objects to hold references back to the pool to keep it alive without carrying a lifetime.
A single thread, interior mutable memory Pool holding objects of type T that can cooperatively moved between threads.
A reference counted smart pointer for pool allocated objects. This wraps Slots in a safe
way. Sc’s need a RcPool<ScInner<T>>
as backing pool. Sc’s do not have a Weak
counterpart. When no Weak functionality is required this can give a space advantage
for small objects and be slightly faster.
Data including reference counter
Handle to allocated memory. This wraps an internal pointer to the allocation and provides
an API for accessing the content. To free memory slots must eventually be given back to
the pool they belong to by pool.free()
, pool.forget()
or pool.take()
. Slots do not
track which Pool they belong to. It is the responsibility of the user to give them back to
the correct pool and ensure that they do not outlive the pool they belong to. In debug
mode it asserted that a slot belongs to the pool when it is given back. Safe abstractions
should track the slots pool.
A TBox
for Pool allocated objects. This wraps Slots in a safe way. Dropping a TBox
will ensure that the destructor is called and the memory is given back to the pool. TBoxes
use a TAG to discriminate. This can be any user defined type, preferably a ZST made only
for this purpose. See the assoc_static
documentation for details.
A threadsafe, interior mutable memory Pool holding objects of type T. The whole pool is protected by a single lock, thread safety is not meant to scale here. When scalability over many threads is needed then onsen is not the right tool.
A reference counted smart pointer for Pool allocated objects. This wraps Slots in a safe
way. A TRc
need a Pool holding RcInner<T>
, not T
.
A reference counted smart pointer for Pool allocated objects. This wraps Slots in a safe
way. A TSc
need a Pool holding ScInner<T>
, not T
.
TWeak
references do not keep the object alive.
Weak
references do not keep the object alive.
Enums
Holds an initialized value.
Initialized, mutable references are permitted.
Initialized, NaN tagged identifier API.
Initialized, pinned references are permitted.
Holds uninitialized memory.
Traits
Permits getting a immutable reference to the value.
Permits destroying the Slot by taking the Value out of it.
Implements how/if the content of a slot shall be dropped.
Base of the typestate policies.
The API for a Pool. This trait takes care for the locking the interior mutable pools and default implements all its methods. It is not intended to be implemented by a user.
Unions
Entries within a Pool. This can either hold user data (potentially uninitialized) or the freelist node.