4 ms·

A single-file C allocator with explicit heaps and tuning knobs

57 points by enduku 7mo ago

enduku 7mo ago
I wrote this because I wanted more explicit control over heaps when building different subsystems in C. Standard options like jemalloc and mimalloc are incredibly fast, but they act as black boxes. You can't easily cap a parser's memory at 256MB or wipe it all out in one go without writing a custom pool allocator. Spaces takes a different approach. It uses 64KB-aligned slabs, and the metadata lookup is just a pointer mask (ptr & ~0xFFFF). The trade-off is that every free() incurs an L1 cache miss to read the slab header, and there is a 64KB virtual memory floor per slab. But in exchange, you get zero-external-metadata regions, instant teardown of massive structures like ASTs, and performance that surprisingly keeps up with jemalloc on cross-thread workloads (I included the mimalloc-bench scripts in the repo). It's Linux x86-64 only right now. I'm curious if systems folks think this chunk API is a pragmatic middle ground for memory management, or if the cache-miss penalty on free() makes the pointer-masking approach a dead end for general use.
- throwaway2027 7mo ago
  When dealing with memory in C defaulting to malloc or some opaque structure behind it is unless you just want to allocate and forget it for some one off program that frees memory on proc exit seems bad to me now. For any kind of sophisticated system or module you almost always want to write your own variety of slab, arena, pool, bump whatever it may be allocator.
  - hrmtst93837 7mo ago
    [flagged]
bitbasher 7mo ago
There's a single commit in the whole repository. Was this AI generated?
- sebazzz 7mo ago
  You still have things like git squash etc.
  - bitbasher 7mo ago
    That doesn't make any sense. There's 10,000+ lines of code. There shouldn't be a single commit "Initial commit". I'm fine with squashing some commits and creating a clean history, but this isn't a clean history it's obfuscated.
    - tosti 7mo ago
      I also do this. Lots of weird commit messages because fuck that, I'm busy. Commits that are just there to put some stuff aside, things like that. I don't owe it to anyone to show how messy my kitchen is.
      - Bootvis 7mo ago
        On the other hand, others don’t have to adopt, use or like your stuff which would be the reasons to publish it. One big commit definitely doesn’t help with creating confidence in this project.
      - bitbasher 7mo ago
        > I don't owe it to anyone to show how messy my kitchen is. There was once a time when sharing code had a social obligation. This attitude you have isn't in the same spirit. GitHub (or any forge) was never meant to be a garbage dumping ground for whatever idea you cooked up at 3AM.
        tosti 7mo ago
        It requires self-discipline to stay organized. A vcs is just a tool. I'm never organized, my brain just works that way. Whatever the tool, I'll create a mess with it. So as long as the project structure and its code is all good I can't care about anything else.
HexDecOctBin 7mo ago
The classic Doug Lee's memory allocator[1] has explicit heaps by the name of mspaces. OP, were you aware of that; and if yes, what does your solution do better or different than dlmalloc's mspaces? [1] https://gee.cs.oswego.edu/pub/misc/?C=N;O=D https://gee.cs.oswego.edu/pub/misc/?C=N;O=D
- enduku 7mo ago
  I am aware of dlmallc/mspaces and GNU Obstacks. Both were in a way, original inspirations for spaces. Though I hadn't looked at mspaces source in years, I remember its inline boundary tags enabling zero overhad per allocation and there were no alignment constraints on the allocator itself (and is hardened across countless archs, not just x64 :) Spaces uses 64kb aligned slabs and a metadata find is a bitop. so potentially, a buffer overflow can corrupt the heap metadata in mspaces while spaces eats a cache-line on free. mspaces was one mutex per heap for entire task (no tlc or lockfree paths). Spaces has per thread-heaps, local caches (no atomic ops on same thrad alloc/free), and a lock-free Treiber stack (ABA tagging) for cross-thread frees. mspaces doesnt track large allocs (>= 256 or 512kb) that hit mmap, so unless one knows to explicitly call mspace_track_large_chunks(...), destroy_mspace silently leaks them all (I think obstacks is good this way but is not a general fit imo). In Spaces, a chunk_destroy walks and frees all the page types unconditionally. Another small thing may matter is error callbacks: Spaces triggers a cb allowing the application to shed load/degrade gracefully. Effectively, the heap walking (inspection?) in msapces is a compile-time switch that holds the lock whole time and doesnt track mmap (direct) allocs, and shares the thresholds like mmap_threashold, etc. globally, whereas Spaces lets you tune everything per-heap. So I'd say Spaces is a better candidate for use cases mspaces bolts on: concurrent access, hard budgets, complete heap walking and per-heap tuning.
ntoslinux 7mo ago
What is the reason for the weird `{ code };` blocks everywhere and is the below code machine generated? ```c ((PageSize) (chunk->pageSize - ((PageSize) ((PageSize) ((PageSize) (sizeof(Page) + (sizeof(struct _Block))) + (PageSize) ((sizeof(double)) - 1u)) & ((PageSize) (~((PageSize) ((sizeof(double)) - 1u)))))) - ((PageSize) ((PageSize) ((PageSize) ((sizeof(FreeBlock) + sizeof(PageSize))) + (PageSize) (((((sizeof(double)) > (4)) ? (sizeof(double)) : (4))) - ```
- bitbasher 7mo ago
  There's a lot of code in the file that is questionable to say the least. There are unnecessary blocks ( { ... }; ) of code with unnecessary semicolons that don't serve any logical purpose. My hunch tells me it may be the result of macro-expansion in C (cc -E ...), etc. So it's likely there's a larger code base with multiple files and they expanded it into a one large C file (sometimes called an amalgamation build) and called it a day. By they, I mean the OP, a script or an AI (or all three).
  - motbus3 7mo ago
    Exactly my thought... This look like a clean room implementation situation
  - deleted 7mo ago
    [deleted]
- mzajc 7mo ago
  Worse yet, there's several places with empty code blocks, eg. [0] and [1]. Even without that, the formatting contains so much unnecessary whitespace, newlines, casts, etc; I'm not sure why, given the already massive source file. How do you even fit [2] on a screen? [0]: https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209aaab2e9ac19c892528d39/spaces.c#L4937-L4938 https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209a... [1]: https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209aaab2e9ac19c892528d39/spaces.c#L4834-L4835 https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209a... [2]: https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209aaab2e9ac19c892528d39/spaces.c#L5146-L5153 https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209a...
deleted 7mo ago
[deleted]
jeffbee 7mo ago
"That costs ~5 ns when the line is cold" I don't see how that could possibly be true. Sounds like a low-ball estimate. Also i wish to point out that the "tcmalloc" being used as a baseline in these performance claims is Ye Olde tcmalloc, the abandoned and now community-maintained version of the project. The current version of tcmalloc is a completely different thing that the mimalloc-bench project doesn't support (correctly; I just checked).
- enduku 7mo ago
  Fair points on both - the 5ns is the L2 hit case. I should have stated the range (30-60ns?) instead of the best case. And yes, fixing the tcmalloc case is on my list - thanks for pointing that out. And also to be clear, the goal was never to beat jemalloc or tcmalloc on raw throughput. I wanted t oshow that one doesn't have t ogive up competitive performnce to get explicit heaps, hard caps and teardown semantics.
  - jeffbee 7mo ago
    That makes sense. I have a long-standing beef with the mimalloc-bench people because they made a bunch of claims in their paper but as recently as 2022 they were apparently not aware of the distinction, and the way they tried to shoehorn tcmalloc into their harness is plain broken. That is not a problem caused by your fine project.
lstodd 7mo ago
Zig got this right to such a degree that I'm sometimes tempted to export its allocators to C via FFI. Then I sober up a bit and just rewrite it all in zig, all its instability nonwithstanding.
- dnautics 7mo ago
  <semi-self-promotion> Not only that, since there is a super-standard std allocator api, it makes itself very amenable to memory safety analysis, as long as you don't sneakily implement allocations outside of that api. https://github.com/ityonemo/clr https://github.com/ityonemo/clr
  - lstodd 7mo ago
    Now this is very interesting. Thank you for sharing.
    - dnautics 7mo ago
      thanks. i pretty much have it running in the background (watching it vibecode carefully) while im doing other work.
motters 7mo ago
As a long time C coder I checked this out, because I have my own malloc replacement. The source code is nonsensical garbage.
swetland 7mo ago
There is no way this utter pile of slop was written by a human.
xantronix 7mo ago
Brother. What is up with the Makefile rule 'test'? I don't mean to be harsh but is this performance art? Edit: Homie. Why is bench.sh fetching external resources? Call me old fashioned, but it would be nice if when I cloned the repository (and checked out any submodules that may exist), I've got everything I need, right there.

57 points by enduku 7mo ago

I wrote this because I wanted more explicit control over heaps when building different subsystems in C. Standard options like jemalloc and mimalloc are incredibly fast, but they act as black boxes. You can't easily cap a parser's memory at 256MB or wipe it all out in one go without writing a custom pool allocator. Spaces takes a different approach. It uses 64KB-aligned slabs, and the metadata lookup is just a pointer mask (ptr & ~0xFFFF). The trade-off is that every free() incurs an L1 cache miss to read the slab header, and there is a 64KB virtual memory floor per slab. But in exchange, you get zero-external-metadata regions, instant teardown of massive structures like ASTs, and performance that surprisingly keeps up with jemalloc on cross-thread workloads (I included the mimalloc-bench scripts in the repo). It's Linux x86-64 only right now. I'm curious if systems folks think this chunk API is a pragmatic middle ground for memory management, or if the cache-miss penalty on free() makes the pointer-masking approach a dead end for general use.

throwaway2027 7mo ago
When dealing with memory in C defaulting to malloc or some opaque structure behind it is unless you just want to allocate and forget it for some one off program that frees memory on proc exit seems bad to me now. For any kind of sophisticated system or module you almost always want to write your own variety of slab, arena, pool, bump whatever it may be allocator.
- hrmtst93837 7mo ago
  [flagged]

bitbasher 7mo ago

There's a single commit in the whole repository. Was this AI generated?

sebazzz 7mo ago
You still have things like git squash etc.
- bitbasher 7mo ago
  That doesn't make any sense. There's 10,000+ lines of code. There shouldn't be a single commit "Initial commit". I'm fine with squashing some commits and creating a clean history, but this isn't a clean history it's obfuscated.
  - tosti 7mo ago
    I also do this. Lots of weird commit messages because fuck that, I'm busy. Commits that are just there to put some stuff aside, things like that. I don't owe it to anyone to show how messy my kitchen is.
    - Bootvis 7mo ago
      On the other hand, others don’t have to adopt, use or like your stuff which would be the reasons to publish it. One big commit definitely doesn’t help with creating confidence in this project.
    - bitbasher 7mo ago
      > I don't owe it to anyone to show how messy my kitchen is. There was once a time when sharing code had a social obligation. This attitude you have isn't in the same spirit. GitHub (or any forge) was never meant to be a garbage dumping ground for whatever idea you cooked up at 3AM.
      - tosti 7mo ago
        It requires self-discipline to stay organized. A vcs is just a tool. I'm never organized, my brain just works that way. Whatever the tool, I'll create a mess with it. So as long as the project structure and its code is all good I can't care about anything else.

HexDecOctBin 7mo ago

The classic Doug Lee's memory allocator[1] has explicit heaps by the name of mspaces. OP, were you aware of that; and if yes, what does your solution do better or different than dlmalloc's mspaces? [1] https://gee.cs.oswego.edu/pub/misc/?C=N;O=D https://gee.cs.oswego.edu/pub/misc/?C=N;O=D

enduku 7mo ago
I am aware of dlmallc/mspaces and GNU Obstacks. Both were in a way, original inspirations for spaces. Though I hadn't looked at mspaces source in years, I remember its inline boundary tags enabling zero overhad per allocation and there were no alignment constraints on the allocator itself (and is hardened across countless archs, not just x64 :) Spaces uses 64kb aligned slabs and a metadata find is a bitop. so potentially, a buffer overflow can corrupt the heap metadata in mspaces while spaces eats a cache-line on free. mspaces was one mutex per heap for entire task (no tlc or lockfree paths). Spaces has per thread-heaps, local caches (no atomic ops on same thrad alloc/free), and a lock-free Treiber stack (ABA tagging) for cross-thread frees. mspaces doesnt track large allocs (>= 256 or 512kb) that hit mmap, so unless one knows to explicitly call mspace_track_large_chunks(...), destroy_mspace silently leaks them all (I think obstacks is good this way but is not a general fit imo). In Spaces, a chunk_destroy walks and frees all the page types unconditionally. Another small thing may matter is error callbacks: Spaces triggers a cb allowing the application to shed load/degrade gracefully. Effectively, the heap walking (inspection?) in msapces is a compile-time switch that holds the lock whole time and doesnt track mmap (direct) allocs, and shares the thresholds like mmap_threashold, etc. globally, whereas Spaces lets you tune everything per-heap. So I'd say Spaces is a better candidate for use cases mspaces bolts on: concurrent access, hard budgets, complete heap walking and per-heap tuning.

ntoslinux 7mo ago

What is the reason for the weird `{ code };` blocks everywhere and is the below code machine generated? ```c ((PageSize) (chunk->pageSize - ((PageSize) ((PageSize) ((PageSize) (sizeof(Page) + (sizeof(struct _Block))) + (PageSize) ((sizeof(double)) - 1u)) & ((PageSize) (~((PageSize) ((sizeof(double)) - 1u)))))) - ((PageSize) ((PageSize) ((PageSize) ((sizeof(FreeBlock) + sizeof(PageSize))) + (PageSize) (((((sizeof(double)) > (4)) ? (sizeof(double)) : (4))) - ```

bitbasher 7mo ago
There's a lot of code in the file that is questionable to say the least. There are unnecessary blocks ( { ... }; ) of code with unnecessary semicolons that don't serve any logical purpose. My hunch tells me it may be the result of macro-expansion in C (cc -E ...), etc. So it's likely there's a larger code base with multiple files and they expanded it into a one large C file (sometimes called an amalgamation build) and called it a day. By they, I mean the OP, a script or an AI (or all three).
- motbus3 7mo ago
  Exactly my thought... This look like a clean room implementation situation
- deleted 7mo ago
  [deleted]
mzajc 7mo ago
Worse yet, there's several places with empty code blocks, eg. [0] and [1]. Even without that, the formatting contains so much unnecessary whitespace, newlines, casts, etc; I'm not sure why, given the already massive source file. How do you even fit [2] on a screen? [0]: https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209aaab2e9ac19c892528d39/spaces.c#L4937-L4938 https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209a... [1]: https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209aaab2e9ac19c892528d39/spaces.c#L4834-L4835 https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209a... [2]: https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209aaab2e9ac19c892528d39/spaces.c#L5146-L5153 https://github.com/xtellect/spaces/blob/422dbba85b5a7e9a209a...

deleted 7mo ago

[deleted]

jeffbee 7mo ago

"That costs ~5 ns when the line is cold" I don't see how that could possibly be true. Sounds like a low-ball estimate. Also i wish to point out that the "tcmalloc" being used as a baseline in these performance claims is Ye Olde tcmalloc, the abandoned and now community-maintained version of the project. The current version of tcmalloc is a completely different thing that the mimalloc-bench project doesn't support (correctly; I just checked).

enduku 7mo ago
Fair points on both - the 5ns is the L2 hit case. I should have stated the range (30-60ns?) instead of the best case. And yes, fixing the tcmalloc case is on my list - thanks for pointing that out. And also to be clear, the goal was never to beat jemalloc or tcmalloc on raw throughput. I wanted t oshow that one doesn't have t ogive up competitive performnce to get explicit heaps, hard caps and teardown semantics.
- jeffbee 7mo ago
  That makes sense. I have a long-standing beef with the mimalloc-bench people because they made a bunch of claims in their paper but as recently as 2022 they were apparently not aware of the distinction, and the way they tried to shoehorn tcmalloc into their harness is plain broken. That is not a problem caused by your fine project.

lstodd 7mo ago

Zig got this right to such a degree that I'm sometimes tempted to export its allocators to C via FFI. Then I sober up a bit and just rewrite it all in zig, all its instability nonwithstanding.

dnautics 7mo ago
<semi-self-promotion> Not only that, since there is a super-standard std allocator api, it makes itself very amenable to memory safety analysis, as long as you don't sneakily implement allocations outside of that api. https://github.com/ityonemo/clr https://github.com/ityonemo/clr
- lstodd 7mo ago
  Now this is very interesting. Thank you for sharing.
  - dnautics 7mo ago
    thanks. i pretty much have it running in the background (watching it vibecode carefully) while im doing other work.

motters 7mo ago

As a long time C coder I checked this out, because I have my own malloc replacement. The source code is nonsensical garbage.

swetland 7mo ago

There is no way this utter pile of slop was written by a human.

xantronix 7mo ago

Brother. What is up with the Makefile rule 'test'? I don't mean to be harsh but is this performance art? Edit: Homie. Why is bench.sh fetching external resources? Call me old fashioned, but it would be nice if when I cloned the repository (and checked out any submodules that may exist), I've got everything I need, right there.