# `flaque`
A fast, concurrent, lock-free, and sometimes wait-free, pool implementation.
## Quick overview
A _pool_ is a collection of _objects_ of limited size. When an object is
fetched from the pool, the number of available objects decreases by one.
Once the fetched object is dropped, it goes back into the _pool_, and the
number of available objects is increased by one.
All objects are lazily created with a _builder_. Objects are _recycled_,
i.e. when an object has been built and fetched once, it can be mutated, and
when it goes back in the pool, it stays as is, untouched.
```rust
use flaque::Pool;
// Let's define what the pool will hold.
struct T {
x: u8,
}
impl Default for T {
fn default() -> Self {
Self { x: 0 }
}
}
// Let's create the pool: capacity of 8, and the builder for the `T`s.
let pool = Pool::new(8, T::default);
// Let's try to get an object from the pool.
let object_0 = pool.try_get().unwrap();
// Or, let's wait to get an object from the pool.
let object_1 = pool.get().await;
```
The main methods are:
- `Pool::try_get` if one wants to synchronously, atomically get an object from
the pool,
- `Pool::get` if one wants to asynchronously get an object from the pool.
An object is represented by the `Object<T>` type, which `deref`s and
`deref_mut`s to `T`. When it drops, the value returns immediately to the pool.
## Features
### Lock- and wait-free
This pool implementation is lock-free and sometimes wait-free. It is
designed to be _fast_ and _consistent_.
| `Pool::try_get` | yes | yes |
| `Pool::get` | yes | no |
| `Object::drop` | yes | yes |
| `Pool::close` | yes | no |
| `Pool::reopen` | yes | yes |
If you're not familiar with these definitions, please
[read _Non-blocking algorithm_][Non-blocking algorithm].
### `Get` and `Close` futures
`Pool::get` returns a `Get` future. It resolves to `Some(object)` once one is
available in the pool, otherwise it returns to `None` if the pool is closed.
`Pool::close` returns a `Close` future. It resolves once all `Object`s are back
into the pool, i.e. when they are all dropped. `Pool::close` takes `self`, i.e.
it takes ownership of the pool. It will be returned back once the future
resolves. This guarantees that it is impossible to reopen the pool, and to fetch
new `Object`s, while waiting for all `Object`s to return back into the pool.
Thus, this is not unusual to see:
```rust
let pool = pool.close().await;
```
## Testing
This crate is tested with [`loom`](https://docs.rs/loom/) and
[`miri`](https://github.com/rust-lang/miri).
## Benchmarks
This crate has started as a hobby project, but also with the idea of replacing
[`deadpool`] inside the [Matrix Rust SDK][`matrix-rust-sdk`]. Indeed, we are
experiencing performance issues due to `deadpool`. Here are the results of the
benchmarks comparing `flaque` with `deadpool`.
<figure>
<table>
<theader>
<tr>
<th colspan="3"></th>
<th scope="col" colspan="12">Number of threads</th>
</tr>
<tr>
<th scope="col" rowspan="2">Pool size</th>
<th scope="col" rowspan="2">Number of readers</th>
<th scope="row" rowspan="2">Library</th>
<th scope="row" colspan="6">Time (ms)</th>
<th scope="row" colspan="6">Throughput (M<sub>object</sub>/sec)</th>
</tr>
<tr>
<th scope="col">1</th>
<th scope="col">2</th>
<th scope="col">4</th>
<th scope="col">8</th>
<th scope="col">16</th>
<th scope="col">32</th>
<th scope="col">1</th>
<th scope="col">2</th>
<th scope="col">4</th>
<th scope="col">8</th>
<th scope="col">16</th>
<th scope="col">32</th>
</tr>
</theader>
<tbody>
<tr>
<th scope="row" rowspan="3">16 (small)</th>
<th scope="row" rowspan="3">
8
(2<sup>3</sup>)
</th>
<th scope="row"><code>flaque</code></th>
<td>0.00203</td>
<td>0.00205</td>
<td>0.00215</td>
<td>0.00227</td>
<td></td>
<td></td>
<td>3.94</td>
<td>3.90</td>
<td>3.72</td>
<td>3.52</td>
<td></td>
<td></td>
</tr>
<tr>
<th scope="row"><code>deadpool</code></th>
<td>0.00286</td>
<td>0.00292</td>
<td>0.00322</td>
<td>0.00333</td>
<td></td>
<td></td>
<td>2.79</td>
<td>2.74</td>
<td>2.48</td>
<td>2.41</td>
<td></td>
<td></td>
</tr>
<tr>
<th scope="row"><em>speed up</em></th>
<td><em>1.4</em></td>
<td><em>1.4</em></td>
<td><em>1.5</em></td>
<td><em>1.5</em></td>
<td></td>
<td></td>
<td><em>1.4</em></td>
<td><em>1.4</em></td>
<td><em>1.5</em></td>
<td><em>1.5</em></td>
<td></td>
<td></td>
</tr>
<tr>
<th scope="row" rowspan="3">16 (small)</th>
<th scope="row" rowspan="3">
2048
(2<sup>11</sup>)
</th>
<th scope="row"><code>flaque</code></th>
<td>0.81</td>
<td>0.93</td>
<td>1.27</td>
<td>2.45</td>
<td>2.73</td>
<td>2.99</td>
<td>5.08</td>
<td>4.41</td>
<td>3.21</td>
<td>1.67</td>
<td>1.50</td>
<td>1.37</td>
</tr>
<tr>
<th scope="row"><code>deadpool</code></th>
<td>1.51</td>
<td>1.82</td>
<td>2.13</td>
<td>3.31</td>
<td>5.41</td>
<td>6.40</td>
<td>2.71</td>
<td>2.25</td>
<td>1.92</td>
<td>1.23</td>
<td>0.76</td>
<td>0.640</td>
</tr>
<tr>
<th scope="row"><em>speed up</em></th>
<td><em>1.9</em></td>
<td><em>2.0</em></td>
<td><em>1.7</em></td>
<td><em>1.4</em></td>
<td><em>2.0</em></td>
<td><em>2.1</em></td>
<td><em>1.9</em></td>
<td><em>2.0</em></td>
<td><em>1.7</em></td>
<td><em>1.4</em></td>
<td><em>2.0</em></td>
<td><em>2.1</em></td>
</tr>
<tr>
<th scope="row" rowspan="3">512 (large)</th>
<th scope="row" rowspan="3">
1'048'576
(2<sup>20</sup>)
</th>
<th scope="row"><code>flaque</code></th>
<td>363.35</td>
<td>420.59</td>
<td>588.70</td>
<td>971.94</td>
<td>976.48</td>
<td>1035.40</td>
<td>5.77</td>
<td>4.99</td>
<td>3.56</td>
<td>2.16</td>
<td>2.15</td>
<td>2.03</td>
</tr>
<tr>
<th scope="row"><code>deadpool</code></th>
<td>705.07</td>
<td>850.66</td>
<td>1030.10</td>
<td>1571.30</td>
<td>1661.30</td>
<td>1684.20</td>
<td>2.97</td>
<td>2.47</td>
<td>2.04</td>
<td>1.33</td>
<td>1.26</td>
<td>1.25</td>
</tr>
<tr>
<th scope="row"><em>speed up</em></th>
<td><em>1.9</em></td>
<td><em>2.0</em></td>
<td><em>1.7</em></td>
<td><em>1.6</em></td>
<td><em>1.7</em></td>
<td><em>1.6</em></td>
<td><em>1.9</em></td>
<td><em>2.0</em></td>
<td><em>1.7</em></td>
<td><em>1.6</em></td>
<td><em>1.7</em></td>
<td><em>1.6</em></td>
</tr>
</tbody>
</table>
<figcaption>
Each benchmark basically runs the following code: `pool.get().await;` —i.e. get
and release many objects— multiple times, on different threads,
The first group (pool size of 16, and 8 readers) represents the _no contention_
scenario: there are ½ readers per object. The second group (pool size of 16,
2048 readers) represents the _high contention on a small pool_ scenario: there
are 128 readers per object. The third group (pool size of 512, 1 million
readers) represents the _high contention on a large pool_ scenario: there are
2048 readers per object.
On average, `flaque` is 1.7 times faster than `deadpool`.
The time is in milliseconds. The throughput is in millions of objects per
second.
</figcaption>
</figure>
[`deadpool`]: https://github.com/deadpool-rs/deadpool
[`matrix-rust-sdk`]: https://github.com/matrix-org/matrix-rust-sdk
[Non-blocking algorithm]: https://en.wikipedia.org/wiki/Non-blocking_algorithm