Turn the mirrored allocation module (except for the buffer) into an Allocator

[gnzlbg]

Currently each SliceDeque is its own allocator, this means that allocating, growing and deallocating SliceDeques require system calls because we are bypassing the global allocator (which recycles memory pages across allocations to avoid system calls).

The target is probably the 0.5 release but work for this can already start. The goals I wanted for the allocator are:

• the allocator should prioritize avoiding system calls for small SliceDeques
• the allocator should avoid system calls for arbitrary large SliceDeques that are allocated and deallocated in a loop

My thoughts on how to attack small SliceDeques are:

• have a couple of free lists (of memory maps, file descriptors, etc. depending on architecture) for small multiples of the allocation granularity (1x, 2x, 4x) caching a small number N of previously freed allocations for future reuse (N ~= 10?)
• implement this as a couple of sorted stack allocated arrays of file-descriptors/memory maps, etc.

My thought on how to attack arbitrary large SliceDeques are:

• have a single sorted free list (of memory maps, file descriptors, etc.) that can be binary searched for a size
• collect the last N (~10?) deallocations that don't fit in the small lists (so this list would be rotating to adapt to patterns)
• implement this as a stack allocated array of file-descriptors/memory maps, etc. using Eytzinger layout [0, 1].

Some unknowns I have about this are:

• Maybe this allocator could implement the Alloc trait ? I don't know why we should do this, but it might be something worth toying with
• Maybe this allocator should be moved into its own crate? I'd prefer to keep it in this crate at first till "everything works", but this crate can be structured in such a way to make the transition to a workspace with sub-crates easy later on in case other parts of the ecosystem want to reuse this allocator.
• Maybe this allocator should be a bit more flexible? Currently the memory is mapped to two adjacent memory regions but @mikeash blog post does this for N regions, where the user can choose the number of regions. @mikeash why did you do this? Could you maybe comment on some applications that need three or more memory regions?

[0] : P.-V. Khuong, P. Morin, Array layouts for comparison-based searching, 2017.

pinging @bill-myers because he was interested into getting this into the library

[mikeash]

The Triplicate section of this blog post explains why my version of this needs three regions:

https://mikeash.com/pyblog/friday-qa-2012-02-17-ring-buffers-and-mirrored-memory-part-ii.html

[gnzlbg]

I've submitted a PR that implements this #33