dlmalloc is way too big

[fitzgen]

Together, dlmalloc and alloc clock in at 10,126 bytes, or 50.98% the total Code section size in my .wasm (pre gzip).

I suspect allocation performance isn't a huge concern for Rust programs compiled into .wasm or else you could write it in JS with better/similar performance.

We could write a simple free-list allocator that focuses on tiny code size.

[fitzgen]

Sketch / brainstorm:

Two allocators:

1. Free-list allocator sourced from wasm pages using memory intrinsics. Used for large allocations.
2. For smaller/medium allocations, use separate free-lists for different size classes (dynamically populated a la BDW?)

The (2) allocator would source its free-list's blocks from the (1) allocator. If we used first-fit, then we could share free-list implementation routines (and therefore have smaller code size) between both (1) and (2) without losing the advantages of O(1) size class allocation, I think.

[anp]

A while ago I ported the musl allocator to Rust, it's pretty small and no_std. Might have time to try shoehorning it into wasm if anyone were interested.

[fitzgen]

Oh, just remembered: the other thing that a wasm allocator doesn't have to worry about (at least for now) is thread safety, which simplifies a lot. Unsure how much the musl allocator tries to do things like avoid locks with atomics or use fine grained locking.

[anp]

It has a heap-wide lock for the expand op, and then there are some internal atomics that I ported as well, but could pretty easily be replaced by a Rust type that is conditionally atomic or not (depending on target?).

[alexcrichton]

One thing I'd be interested in seeing is what happens if dlmalloc is compiled with -C opt-level=s, as right now it's compiled with -C opt-level=3. I'm not sure what kind of impact that would have but may have quite a bit?

In general this is a tough tradeoff though beause you can write an incredibly small allocator (just grow memory on all requests and never free it) but obviously that's not tenable. The allocator we choose for libstd I think needs a balance between size and speed. I sort of randomly ran across dlmalloc (and it seemed well battle tested) but if we can quantify and/or measure other allocators I think it'd be great to have a few choices.

Eventually when we have custom global allocators you can also always bring your own!

[fitzgen]

I wrote an allocator designed specifically for wasm:

• http://fitzgeraldnick.com/2018/02/09/wee-alloc.html
• https://github.com/fitzgen/wee_alloc

Only ~1K vs the ~8K of dlmalloc, but it is still an early project, ofc. I'd love some help making it robust!

[alexcrichton]

With wee_alloc I'm gonna close this as we've got a solid pretty solid default (small-ish and fast-ish) and a good option as well for "completely optimize for size"