bias_shared_arena/lib.rs
1// #![forbid(missing_docs)]
2// #![forbid(missing_doc_code_examples)]
3
4//! Memory pools are usefull when allocating and deallocating lots of
5//! data of the same size.
6//! Using a memory pool speed up those allocations/deallocations.
7//!
8//! This crate provides 3 memory pools:
9//!
10//! 
11//!
12//! # Performance
13//!
14//! On my laptop, with Intel i7-10750H, running Clear Linux OS 33840,
15//! an allocation with `shared_arena` is 6 to 8 times faster than the
16//! system allocator:
17//!
18//! ```ignore
19//! SingleAlloc/SharedArena time: [12.153 ns 12.423 ns 12.724 ns]
20//! SingleAlloc/Arena time: [9.2267 ns 9.4895 ns 9.7559 ns]
21//! SingleAlloc/Pool time: [8.8624 ns 8.9305 ns 9.0033 ns]
22//! SingleAlloc/Box (System Allocator) time: [71.042 ns 72.995 ns 74.442 ns]
23//! ```
24//!
25//! Performances with more allocations:
26//!
27//! 
28//!
29//! The graphic was generated with criterion, reproducible with `cargo bench`
30//!
31//! # Implementation details
32//!
33//! `SharedArena`, `Arena` and `Pool` use the same method of allocation,
34//! derived from a [free list](https://en.wikipedia.org/wiki/Free_list).
35//!
36//! They allocate by pages, which include 63 elements, and keep a list
37//! of pages where at least 1 element is not used by the user.
38//! A page has a bitfield of 64 bits, each bit indicates whether or
39//! not the element is used.
40//!
41//! In this bitfield, if the bit is set to zero, the element is
42//! already used.
43//! So counting the number of trailing zeros gives us the index of an
44//! unused element.
45//! Only 1 cpu instruction is necessary to find an unused element:
46//! such as `tzcnt`/`bsf` on `x86` and `clz` on `arm`
47//!
48//! ```ignore
49//! [..]1101101000
50//! ```
51//! With the bitfield above, the 4th element is unused.
52//!
53//! 
54//!
55//! The difference between `SharedArena`/`Arena` and `Pool` is that
56//! `Pool` does not use atomics.
57//!
58//! # Safety
59//!
60//! `unsafe` block are used in several places to dereference pointers.
61//! The code is [100% covered](https://codecov.io/gh/sebastiencs/shared-arena/tree/master/src)
62//! by the [miri](https://github.com/rust-lang/miri) interpreter,
63//! valgrind and 3 sanitizers: address, leak and memory, on each commit.
64//! See the [github actions](https://github.com/sebastiencs/shared-arena/actions)
65//!
66//! [`SharedArena`]: ./struct.SharedArena.html
67//! [`Arena`]: ./struct.Arena.html
68//! [`Pool`]: ./struct.Pool.html
69
70mod arena;
71mod arena_arc;
72mod arena_box;
73mod arena_rc;
74mod block;
75mod cache_line;
76mod common;
77mod page;
78mod pool;
79mod shared_arena;
80
81pub use {
82 self::shared_arena::SharedArena,
83 arena::Arena,
84 arena_arc::ArenaArc,
85 arena_box::ArenaBox,
86 arena_rc::ArenaRc,
87 block::Block,
88 pool::{Pool, PoolBox},
89};