项目作者: fengb

项目描述 :
tiny Zig allocator primarily targeting WebAssembly
高级语言: Zig
项目地址: git://github.com/fengb/zee_alloc.git
创建时间: 2019-05-21T14:23:17Z
项目社区:https://github.com/fengb/zee_alloc

开源协议:MIT License

下载


zee_alloc — zig wee allocator

A tiny general purpose allocator targeting WebAssembly.

This allocator has not been well tested. Use at your own peril.

Getting Started

In zig:

  1. const zee_alloc = @import("zee_alloc");
  2. pub fn foo() void {
  3. var mem = zee_alloc.ZeeAllocDefaults.wasm_allocator.alloc(u8, 1000);
  4. defer zee_alloc.ZeeAllocDefaults.wasm_allocator.free(mem);
  5. }

Exporting into wasm:

  1. const zee_alloc = @import("zee_alloc");
  2. comptime {
  3. (zee_alloc.ExportC{
  4. .allocator = zee_alloc.ZeeAllocDefaults.wasm_allocator,
  5. .malloc = true,
  6. .free = true,
  7. .realloc = false,
  8. .calloc = false,
  9. }).run();
  10. }

Goals

(inspired by Rust’s wee_alloc)

  1. Tiny compiled output
  2. Tiny compiled output x2
  3. Malloc/free compatibility
  4. Avoid long-term fragmentation
  5. Reasonably fast alloc and free
  6. Code simplicity — probably goes in hand with tiny output

Non-goals

  • Debugging — this library probably will never do a good job identifying errors.
    Zig has a great debug allocator
    in the works, and zig programs should be able to easily swap allocators.
  • Compact memory — fixed allocation frames are used for speed and simplicity.
    Memory usage will never be optimum unless the underlying algorithm completely changes
  • Thread performance — wasm is single-threaded

Benchmarks

  1. Benchmark Mean(ns)
  2. ----------------------------------------------------
  3. DirectAllocator.0 50842
  4. DirectAllocator.1 98343
  5. DirectAllocator.2 203980
  6. DirectAllocator.3 49908
  7. DirectAllocator.4 103635
  8. DirectAllocator.5 195941
  9. DirectAllocator.6 47367
  10. DirectAllocator.7 101733
  11. DirectAllocator.8 202697
  12. Arena_DirectAllocator.0 11837
  13. Arena_DirectAllocator.1 19591
  14. Arena_DirectAllocator.2 30689
  15. Arena_DirectAllocator.3 30916
  16. Arena_DirectAllocator.4 52425
  17. Arena_DirectAllocator.5 75673
  18. Arena_DirectAllocator.6 44874
  19. Arena_DirectAllocator.7 67557
  20. Arena_DirectAllocator.8 96276
  21. ZeeAlloc_DirectAllocator.0 15892
  22. ZeeAlloc_DirectAllocator.1 24435
  23. ZeeAlloc_DirectAllocator.2 49564
  24. ZeeAlloc_DirectAllocator.3 26656
  25. ZeeAlloc_DirectAllocator.4 52462
  26. ZeeAlloc_DirectAllocator.5 93854
  27. ZeeAlloc_DirectAllocator.6 51493
  28. ZeeAlloc_DirectAllocator.7 95223
  29. ZeeAlloc_DirectAllocator.8 250187
  30. FixedBufferAllocator.0 177
  31. FixedBufferAllocator.1 412
  32. FixedBufferAllocator.2 1006
  33. FixedBufferAllocator.3 296
  34. FixedBufferAllocator.4 785
  35. FixedBufferAllocator.5 1721
  36. FixedBufferAllocator.6 848
  37. FixedBufferAllocator.7 1546
  38. FixedBufferAllocator.8 3331
  39. Arena_FixedBufferAllocator.0 299
  40. Arena_FixedBufferAllocator.1 573
  41. Arena_FixedBufferAllocator.2 1624
  42. Arena_FixedBufferAllocator.3 1115
  43. Arena_FixedBufferAllocator.4 1868
  44. Arena_FixedBufferAllocator.5 4422
  45. Arena_FixedBufferAllocator.6 1706
  46. Arena_FixedBufferAllocator.7 3389
  47. Arena_FixedBufferAllocator.8 8430
  48. ZeeAlloc_FixedBufferAllocator.0 232
  49. ZeeAlloc_FixedBufferAllocator.1 577
  50. ZeeAlloc_FixedBufferAllocator.2 1165
  51. ZeeAlloc_FixedBufferAllocator.3 443
  52. ZeeAlloc_FixedBufferAllocator.4 907
  53. ZeeAlloc_FixedBufferAllocator.5 1848
  54. ZeeAlloc_FixedBufferAllocator.6 907
  55. ZeeAlloc_FixedBufferAllocator.7 1721
  56. ZeeAlloc_FixedBufferAllocator.8 3836

Architecture — Buddy memory allocation

Caveat: I knew nothing about memory allocation when starting this project.
Any semblence of competence is merely a coincidence.

  1. idx frame_size
  2. 0 >65536 jumbo
  3. 1 65536 wasm page size
  4. 2 32768
  5. 3 16384
  6. 4 8192
  7. 5 4096
  8. 6 2048
  9. 7 1024
  10. 8 512
  11. 9 256
  12. 10 128
  13. 11 64
  14. 12 32
  15. 13 16 smallest frame

Size order is reversed because 0 and 1 are special. I believe counting down had
slightly better semantics than counting up but I haven’t actually tested it.

Wasm only allows for allocating entire pages (64K) at a time. Current architecture is
heavily influenced by this behavior. In a real OS, the page size is much smaller at 4K.
Everything should work as expected even if it does not run as efficient as possible.

Each allocation frame consists of 2 usizes of metadata: the frame size and a pointer to
the next free node. This enables some rudimentary debugging as well as a simple lookup
when we only have the allocated data-block (especially important for C compatibility).

For allocations <=64K in size, we find the smallest usable free frame. If it’s
bigger than necessary, we grab the smallest power of 2 we need and resize the rest
to toss back as free nodes. This is O(log k) which is O(1).

For allocations >64K, we iterate through list 0 to find a matching size, O(n).
Free jumbo frames are never divided into smaller allocations.

ZeeAlloc only supports pointer alignment at 2x usize — 8 bytes in wasm. There
are a few ideas to expand this to up-to half page_size but nothing concrete yet.