It’d be nice to be able to tune separately from compiler options such that upstream can use release-safe while zee_alloc can stay tiny:

1. Debug — enable all checks
2. External — disable internal consistency checks, but retain external checks, e.g. double free or freeing wrong memory
3. Unsafe — no checks

Note: non-release builds should keep on all debugging.

Now that we track allocated frames, we can apply a coalesce algorithm on free. Unfortunately, removing from a freelist is currently O(n) so we’ll have to do trade off analysis:

1. Don’t coalesce. This is the status quo and handles consistent allocations well, but it degenerates upon mixing between large and small allocations.

2. O(n) coalesce. This is simple and easy, but it starts degenerating when freelists are long.

3. Hybrid coalesce. Try merging but give up after a few iterations of search. Possibly a decent trade off for performance consistency at the cost of data consistency.

4. Doubly linked list. Takes extra memory space per frame and minor bookkeeping cycles but guarantees O(1) coalesce.

   Note: if implemented with packed pointers (#4), metatdata should be the same size (2x usize).

ZeeAlloc does really poorly with variable-sized jumbo allocations. We should investigate a better way to reference these frames.

Detailed problem:

1. Jumbo frames are all stuck into a (singly) linked list
2. Only specific matches will fit jumbo frames (search size == frame size)

Potential solutions:

• Make search size <= frame size — this speeds up variable reuse at the cost of hurting exact size reuse and internal fragmentation
• Increase "page size" — this only punts the problem as well as causing more internal fragmentation
• Powers of 2 for jumbo — more internal fragmentation, still poor performance for lots of simultaneous allocations

Now that we have a built-in page-based allocator in std, we should start consuming it.

Benefits:

• standardize around std — properly coordinate with any wasm allocator
• really freeing memory — this should be identical to ArenaAllocator.deinit
• potentially ignore jumbo allocations entirely

Drawbacks:

• the std allocator requires an additional 1-2 KB
• need new metadata architecture for C-like malloc()

Questions:

1. Is it possible to detect using "free()"? In theory, wasm_page_allocator can be tiny if it optimizes away the free/reuse bookkeeping, so it'd be amazing if it could detect at comptime whether free is needed.
2. Should we keep around the current dumb page allocator and only enable the new path on "deinit()"? std.WasmPageAllocator was designed to handle freeing any memory page (including ones it didn't originally allocate) so this works around question 1.

Once we have #3, we have a really nice characteristic:

• Small allocations are always align(16). The extra bits can denote the small size bitshift... which incidentally is less than 16.
• Large allocations are always align(32K) or align(64K). The extra bits can denote the total pages, which maps to 2GB or 4GB respectively.

With this type of packing, we only need a usize word (4B) for the metadata. Thus current minimum payload is expanded to 12B.

We might be able to support 4B payloads — it allows for align(8) which is not enough space to store the length, but we can possibly assume any align(8) has to be 4B allocations.
Inconsistent metadata is very hard to detect so we'll stick with 12B minimum payloads.

Alternative to #3

All payloads have natural alignment of 8. If we pad the payload by 8, we can get align 16.

This sounds simpler than shifting every block, but it wastes a lot more space.

Buddy allocation is generally pretty efficient but suffers from internal fragmentation. Can slab allocation have similar code efficiency?

Current design is reasonably simple and compact, but we have two major issues:

1. Alignment is fixed at double-usize (8 bytes). It'd be nice if we can at least align to 16 bytes, and this might give us up to 32KB alignment for "free".
2. Payload size of 2^n - 8 is super clunky. A lot of my personal usecases require 2^n exactly, and having this limitation requires an extra half page to a page.

Need to decide on a strategy for exporting the free() function. This would be for external compatibility usage and not necessarily be a guiding principle so poorer performance or efficiency is acceptable.

1. Store "extern malloc" values in a data structure — probably HashMap. This would be outside of the core allocator and probably easier to maintain, since we can use memory easier without fear of trashing the internals.
2. Each allocated block has a wrapping parent struct that can store metadata. This would also solve the "free cannot find unused node" problem... by chewing up more memory, and Zig seems to provide enough metadata from the language itself that I want to try avoiding this strategy.

Generated from twiggy

 Shallow Bytes │ Shallow % │ Item
───────────────┼───────────┼─────────────────────────────────────────────────────
           808 ┊    41.41% ┊ main.ZeeAlloc((struct main.Config constant)).realloc
           252 ┊    12.92% ┊ "function names" subsection
           173 ┊     8.87% ┊ realloc
           102 ┊     5.23% ┊ malloc
            98 ┊     5.02% ┊ data[1]
            79 ┊     4.05% ┊ main.WasmPageAllocator.realloc
            60 ┊     3.08% ┊ main.ZeeAlloc((struct main.Config constant)).shrink
            57 ┊     2.92% ┊ main.ZeeAlloc((struct main.Config constant)).free
            47 ┊     2.41% ┊ memset
            40 ┊     2.05% ┊ calloc
            29 ┊     1.49% ┊ free