maskerad_object_pool 0.2.0

A collection of object pools, for more efficient dynamic memory allocation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

# Maskerad Object Pool

[![codecov](https://codecov.io/gh/Maskerad-rs/Maskerad_object_pool/branch/master/graph/badge.svg)](https://codecov.io/gh/Maskerad-rs/Maskerad_object_pool)
[![Build status](https://ci.appveyor.com/api/projects/status/cda7vb6lc6uqjn3t?svg=true)](https://ci.appveyor.com/project/Malkaviel/maskerad-memory-allocator)
[![Build Status](https://travis-ci.org/Maskerad-rs/Maskerad_object_pool.svg?branch=master)](https://travis-ci.org/Maskerad-rs/Maskerad_object_pool)

[![Crates.io](https://img.shields.io/crates/v/maskerad_object_pool.svg)](https://crates.io/crates/maskerad_object_pool) [![Docs](https://docs.rs/maskerad_object_pool/badge.svg)](https://docs.rs/maskerad_object_pool)

[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT) [![License](https://img.shields.io/badge/License-Apache%202.0-blue.svg)](https://opensource.org/licenses/Apache-2.0)

**A collection of object pools, for more efficient dynamic memory allocation.**

This library provides 2 data structures to deal with dynamic memory allocation more efficiently :
- An object pool for **single-threaded** contexts
- An object pool for **multi-threaded** contexts

Usage
-----
### Installation

This library is available on [crates.io](https://crates.io/crates/maskerad_object_pool)

## What is an object pool ?
An **Object Pool** is a structure maintaining a collection of **reusable** objects.

When the pool is instantiated, a given number of objects are allocated on the Heap. Those
objects manage an **usage-state**, this state have the value **not used** when the objects are
instantiated.

When the user want to **create** a new object, he asks the pool for one. The pool will return the
first *not used* object in its pool, and set the object as *used*.

When the object is **dropped**, the object return to its original state and is set to *not used*. 

### Potential benefices compared to heap allocation
It *can* be **faster**: Allocations have been made in advance, when the user create objects 
with an object pool, a pointer to a pre-allocated non-used object is returned. When an object
is dropped, the pointer is dropped and the object (which is not dropped) goes back to a non-used
state.

It prevents **memory fragmentation**: We allocate a big chunk of memory full of ready-to-use objects. Even though
the user is creating and dropping/destroying objects, no allocations and *frees* are occurring.



Context
---------------------------------------
### Purpose of custom allocators

Time-constrained programs, like video-games, need to be as fast as possible.

A video-game, in its game loop, needs to :
- Read the player's input at frame **n**.
- Update the world state (AI, physics, object states, sounds...) at frame **n**.
- Draw the scene at frame **n** in the back buffer.
- Swap the back buffer (frame **n**) with the current buffer (frame **n - 1**).

In order to display **60** frames per second, this loop needs to be completed in **16** milliseconds (**0.016** seconds).

### Problems about general-purpose memory allocators
One possible bottleneck is **dynamic** memory allocation (allocation on the **heap**). Even though Rust *sometimes* uses **[jemalloc](http://jemalloc.net/)**, a fast
general-purpose memory allocator (see this [RFC](https://github.com/rust-lang/rfcs/blob/master/text/1974-global-allocators.md)),
heap memory allocation *can* be a **slow** operation.

Moreover, memory can become **fragmented** over time :

Even though we have enough **total** memory, this memory is not **contiguous** so we can't
 allocate anything.
![memory fragmentation illustration](readme_ressources/memory_fragmentation.svg)


Custom memory allocators can help with both problems.

We can distinguish 3 types of memory allocation :
- **Persistent** memory allocation: data is allocated when the program is started, and freed when
the program is shut down. The [arena crate](https://doc.rust-lang.org/1.1.0/arena/) is perfect for that.

- **Dynamic** memory allocation: data is allocated and freed during the lifetime of the program, but
we can't predict *when* this data is allocated and freed. This library deals with this type of
memory allocation

- **One-Frame** memory allocation: Data is allocated, consumed and freed in a loop.
**[stack-based allocators](https://github.com/Maskerad-rs/maskerad_stack_allocator)** can be a good
solution to this type of allocation.


## More informations on the subject
[Game Engine Architecture, chapter 5.2](http://gameenginebook.com/toc.html)

[Stack Overflow answer about memory fragmentation](https://stackoverflow.com/questions/3770457/what-is-memory-fragmentation#3770593)

[Stack Overflow answer about stack-based allocators](https://stackoverflow.com/questions/8049657/stack-buffer-based-stl-allocator)

[SwedishCoding blogpost about custom memory allocators](http://www.swedishcoding.com/2008/08/31/are-we-out-of-memory/)

[Game Programming Patterns, Chapter 19, about Object Pools](http://gameprogrammingpatterns.com/object-pool.html)

[Wikipedia article about Object Pools](https://en.wikipedia.org/wiki/Memory_pool)

[Wikipedia article about free lists](https://en.wikipedia.org/wiki/Free_list)

## License

Licensed under either of

 * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
 * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)

at your option.

### Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted
for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any
additional terms or conditions.