`wee_alloc`

The Wasm-Enabled, Elfin Allocator

API Docs | Contributing | Chat

_{Built with 🦀🕸 by The Rust and WebAssembly Working Group}

About

wee_alloc: The Wasm-Enabled, Elfin Allocator.

Elfin, i.e. small: Generates less than a kilobyte of uncompressed

WebAssembly code. Doesn't pull in the heavy panicking or formatting infrastructure. wee_alloc won't bloat your .wasm download size on the Web.

WebAssembly enabled: Designed for the wasm32-unknown-unknown target and

#![no_std].

wee_alloc is focused on targeting WebAssembly, producing a small .wasm code size, and having a simple, correct implementation. It is geared towards code that makes a handful of initial dynamically sized allocations, and then performs its heavy lifting without any further allocations. This scenario requires some allocator to exist, but we are more than happy to trade allocation performance for small code size. In contrast, wee_alloc would be a poor choice for a scenario where allocation is a performance bottleneck.

Although WebAssembly is the primary target, wee_alloc also has an mmap based implementation for unix systems, a VirtualAlloc implementation for Windows, and a static array-based backend for OS-independent environments. This enables testing weealloc, and code using weealloc, without a browser or WebAssembly engine.

wee_alloc compiles on stable Rust 1.33 and newer.

Using weealloc as the Global Allocator
cargo Features
Implementation Notes and Constraints
License
Contribution

Using `wee_alloc` as the Global Allocator

extern crate wee_alloc;
// Use wee_alloc as the global allocator. #[global_allocator] static ALLOC: weealloc::WeeAlloc = weealloc::WeeAlloc::INIT;

`cargo` Features

size_classes: On by default. Use size classes for smaller allocations to

provide amortized O(1) allocation for them. Increases uncompressed .wasm code size by about 450 bytes (up to a total of ~1.2K).

extra_assertions: Enable various extra, expensive integrity assertions and

defensive mechanisms, such as poisoning freed memory. This incurs a large runtime overhead. It is useful when debugging a use-after-free or wee_alloc itself.

staticarraybackend: Force the use of an OS-independent backing

implementation with a global maximum size fixed at compile time. Suitable for deploying to non-WASM/Unix/Windows #![no_std] environments, such as on embedded devices with esoteric or effectively absent operating systems. The size defaults to 32 MiB (33554432 bytes), and may be controlled at build-time by supplying an optional environment variable to cargo, WEEALLOCSTATICARRAYBACKEND_BYTES. Note that this feature requires nightly Rust.

nightly: Enable usage of nightly-only Rust features, such as implementing

the Alloc trait (not to be confused with the stable GlobalAlloc trait!)

Implementation Notes and Constraints

wee_alloc imposes two words of overhead on each allocation for maintaining

its internal free lists.

Deallocation is an O(1) operation.

wee_alloc will never return freed pages to the WebAssembly engine /

operating system. Currently, WebAssembly can only grow its heap, and can never shrink it. All allocated pages are indefinitely kept in wee_alloc's internal free lists for potential future allocations, even when running on unix targets.

wee_alloc uses a simple, first-fit free list implementation. This means that

allocation is an O(n) operation.

Using the size_classes feature enables extra free lists dedicated to small allocations (less than or equal to 256 words). The size classes' free lists are populated by allocating large blocks from the main free list, providing amortized O(1) allocation time. Allocating from the size classes' free lists uses the same first-fit routines that allocating from the main free list does, which avoids introducing more code bloat than necessary.

Finally, here is a diagram giving an overview of wee_alloc's implementation:

+------------------------------------------------------------------------------+
| WebAssembly Engine / Operating System                                        |
+------------------------------------------------------------------------------+
                   |
                   |
                   | 64KiB Pages
                   |
                   V
+------------------------------------------------------------------------------+
| Main Free List                                                               |
|                                                                              |
|          +------+     +------+     +------+     +------+                     |
| Head --> | Cell | --> | Cell | --> | Cell | --> | Cell | --> ...             |
|          +------+     +------+     +------+     +------+                     |
|                                                                              |
+------------------------------------------------------------------------------+
                   |                                    |            ^
                   |                                    |            |
                   | Large Blocks                       |            |
                   |                                    |            |
                   V                                    |            |
+---------------------------------------------+         |            |
| Size Classes                                |         |            |
|                                             |         |            |
|             +------+     +------+           |         |            |
| Head(1) --> | Cell | --> | Cell | --> ...   |         |            |
|             +------+     +------+           |         |            |
|                                             |         |            |
|             +------+     +------+           |         |            |
| Head(2) --> | Cell | --> | Cell | --> ...   |         |            |
|             +------+     +------+           |         |            |
|                                             |         |            |
| ...                                         |         |            |
|                                             |         |            |
|               +------+     +------+         |         |            |
| Head(256) --> | Cell | --> | Cell | --> ... |         |            |
|               +------+     +------+         |         |            |
|                                             |         |            |
+---------------------------------------------+         |            |
                      |            ^                    |            |
                      |            |                    |            |
          Small       |      Small |        Large       |      Large |
          Allocations |      Frees |        Allocations |      Frees |
                      |            |                    |            |
                      |            |                    |            |
                      |            |                    |            |
                      |            |                    |            |
                      |            |                    |            |
                      V            |                    V            |
+------------------------------------------------------------------------------+
| User Application                                                             |
+------------------------------------------------------------------------------+