Arena Allocators in C | Hacker News Reader

Arena Allocators in C

eliasebner.com

86 pointsdimonomid38 comments

“Types.c” is dangerous code to bring to every project.

f32/64 makes assumptions about the platform.

Worse yet, the macros at the bottom are all functionally incorrect. Macros like MIN/MAX need to be contained in parentheses to avoid precedence errors.

For example, we take `Min(x,y)` from the code. Consider what happens if I write `ans = 2 * Min(3,4)` because of the way Min is defined that will expand to `ans = 2 * 3 < 4 ? 3 : 4` and while you may expect ans to be 3 it will infact resolve to 4.

Subtle bugs like these can creep into code and cause really hard to debug errors.

Finally, while u32 is a little faster to type than `uint33_t` it makes the project harder to read forcing the reader to learn the author’s personal c dialect. While it is a stylistic choice, I can’t see why anyone would want to sacrifice code highlighting and expressiveness for slightly less verbosity

It is totally fine for C code to make "assumptions about the platform".

I'm not sure where this obsession with non-existing or irrelevant target platforms is coming from that might be theoretically supported by the C standard, but are not relevant in the real world except for niche use cases which the library author might not care about (like some extremely limited embedded CPUs). E.g. not every C library needs to support every target platform just because that target platform has a C compiler, and all code (not just C code) should be considered broken anyway until it is actually tested on a specific platform (and in that case any problems that show up are trivial to fix).

You're right about the macro thing of course.

The typedef-thing is arguable, I would at least try to not let such custom typedefs over basic types leak into the public API of the library where they could collide with typedefs of other libraries (e.g. all public types of a library should have at least a prefix which makes name collisions with other libraries unlikely).

Because C is fundamentally defined for an abstract machine. People just ignoring portability and writing machine-specific code reek after actually not understanding other fundamental properties of C and are as such prune to writing a lot of undefined behaviour. C is fundamentally abstract from the machine and ignoring that will bring you in all kind of nasty situations, even if the code happens to run fine, because the compiler translated it accidentally in the naive way you expected it to.

Of course there are also the people who know what C is and make explicit choices about the compiler and the platform. But then they are often explicit about that and say that they are NOT writing C, but e.g. gnu11 on arm64. Then you also know that you can't just change the compiler and platform and happen to be fine.

> Because C is fundamentally defined for an abstract machine.

This is more like a guideline than actual rule ;) (e.g. the C standard is also full of implementation defined behaviour, and that's fine).

Instead of obsessing over theoretical C standard details, people should build their code with "-Wall -Wextra" (that's the absolute minimum), maybe -pedantic (which however disables a lot of useful non-standard extensions that are accepted by most popular compilers), run the code through a static analyzer, and test with ASAN, UBSAN and TSAN (and nowadays, also let an LLM do a bug scan over the code).

When all those things are clean, the code is in pretty good shape and will most likely survive porting to a new target platform or compiler.

UBSAN is also pragmatic enough to focus on the 'important' UB, and ignore the 'irrelevant' types of UB.

> f32/64 makes assumptions about the platform.

Indeed, but, by the way, those are assumptions that some newer languages now make about the entire world.

> forcing the reader to learn the author’s personal c dialect

If you open my codebase and understanding the u32 typedef is enough to trip you up to the point where you're now "learning a new C dialect", you're probably not well equipped to understand the actual complex stuff.

God forbid people make the slightest stylistic choice about how the code they're staring at for 10 hours a day looks.

Not to mention, s8/16/32/64, u8/16/32/64, f32/64 typedefs are all very popular for modern c/c++... and totally fine.

This is just standard gatekeeping by pearl clutching devs with PTSD from decades ago.

I don’t use code-highlighting and terseness can enable expressiveness.

Please be aware that pointer arithmetic is not defined on void * pointers, although many compilers allow it. You had better use char * for "data".

Also, your code is prone to overflow when you add data, used, alignment and size.

And finally, the realloc function could be reworked to do nothing if new_size is <= old_size.

More obvious problems with the code as shown:

- The macros doing arithmetic (KiB, MIN etc) don't put their arguments in parentheses, that is very dangerous.

- The code assumes that int and i32 are the same size.

- Don't cast the return value of malloc(). Please Google this.

I appreciated the use of structs by value, that's a nice design.

I agree there's a risk of overflow in the arithmetic around sizes/alignment, but with a 64-bit `usize` that should be mostly theoretical.

> The code assumes that int and i32 are the same size.

Tbf this is extreme nitpicking. It's very unlikely that the code will ever be built on a compiler where int is not 32 bits. Replacing the sizeof(int) with sizeof(i32) is better of course, and tbh it looks like an oversight, not intentional.

> Don't cast the return value of malloc(). Please Google this.

This is required when the code should also build in C++ mode (which some weirdos seem to prefer for "improved type safety") - in any case, the explicit cast is also entirely valid C code, so not wrong just redundant.

> The macros doing arithmetic (KiB, MIN etc) don't put their arguments in parentheses, that is very dangerous.

Agreed.

I would add though:

> Don't typedef C primitive types to your own shortcuts (like int32_t => i32), at least not when those typedefs leak into the public API, because then your i32 may collide with another library's i32.

IMO there's really not a reason to use macros in C these days.

Declare your function "static inline" in the header file and the compiler will usually inline it with -O2 level optimisations.

len also isn’t used so only 1 int’s worth of memory is allocated

> This will be used to align the data. For some reason, our computers are much better at dealing with data that is aligned at 8 bytes. This means that the start of each new allocation has to be at a multiple of 8 bytes.

Casting a pointer which is not aligned to its natural alignment has undefined behavior in C. It's not just an issue of unaligned accesses being slow; in practice, your program might also crash or access unexpected data on real platforms with real compiler implementations.

There's really no other way for a general allocation function that doesn't know the target type. I would expand the default alignment from 8 to 16 bytes though, because this is what you typically get from malloc on 64-bit targets, and a bigger 'natural alignment' should be extremely rare (maybe needed for some SIMD types, but those are outside the C standard anyway).

> It's not just an issue of unaligned accesses being slow; in practice, your program might also crash or access unexpected data on real platforms with real compiler implementations.

Unaligned accesses are fast (unless they straddle a cache line or involve SIMD registers) and work perfectly well on current mainstream CPUs (and have been working fine for a long time).

E.g. I'm really not a fan of taking every piece of C code apart because it might not work on an experimental CPU design from the 1960s which the C standard theoretically supports but no current C compiler ;) (exaggerating of course, but there's no way around testing on all expected target compilers and platforms, any target config that's not explicitly tested should be considered unsupported, and that's not even a programming language specific thing).

unaligned access is not an option on some mips cpus, which are very much still in use in 1000s of routers, for example

See Sections 5+6 in https://drh.github.io/cii/toc.html

The question is, even after so many years, why is this arena memory allocation management not part of std library ? At least for people to use it safely, given the fact that writing this safely and portably is non-trivial.

How would I handle memory fragmentation in this implementation of an Arena Allocator. If I do not need a piece of memory any more, is there a way to free it and possible use it for something else.

Arena allocator cannot free. so it's usecase is less general than a normal allocator.

But imagine creating a readonly tree, working with that tree, and then disposing of the tree. This is where a arena allocator shines. It removes fragmentation almost entirely from the main allocator.

not doing that is exactly the point.

Im not a fan of this implement. But arena allocators are awesome. Using linked blocks can make it dynamic aswell.

#define ARENA_ALIGN 8

This is unportable. You really need to pass the required alignment to the allocation function.

Or you can just use alignof(max_align_t), and your pointers will have the same alignment guarantees as malloc.

And I might be wrong, but even if you do accept a required alignment `align`, I think it's impossible in portable C to align a pointer `p` to it, unless you assume something not-strictly-portable about `(uintptr_t)p`, or `align` is less than some predetermined alignment that you used to allocate the char array.

> unless you assume something not-strictly-portable about `(uintptr_t)p`

What's not strictly portable about it?

  padding = -(uintptr_t)p & (align - 1)

The only assumption here is that align is a power of 2, which is guaranteed if it's the result of an alignof().

It'll work in reality, but I don't think C makes any guarantees about how the pointer p is represented in (uintptr_t)p, only that a roundtrip pointer -> uintptr_t -> pointer will give back p. So (as far as I know) you can't assume that the offset needed to make (uintptr_t)p a multiple of `align` is the same as the offset needed to align p to `align`.

This should definitely by a binary specification with various ISA assembly implementations.

Using the structs for return values with `[[nodiscard]]` looks so clean.

New in C23, juicy!

[[nodiscard]] is new, but returning structs worked before of course (at least since C99).

You can even integrate the struct declaration right into the return type:

https://www.godbolt.org/z/GGraK61M6

(which tbf though has limited usability)

Why redefine the stdints?

It's ok as long as the types don't leak into the public API when the code is distributed as a library. But yeah, it looks like a leftover bad habit from pre-C99 times (I suspect the author is on Windows where MSVC was very late to the C99 party), and Microsoft also recommened for a while to build C code via the C++ compiler, which is where the "cast result of malloc" habit might come from.

Typedefing uint32t to u32 etc is extremely common

They wanted shorter aliases for them to make their code clearer, I suppose.

The one thing Rust got right was inheriting the i64/u64/i32/u32/i8/u8 naming convention for types. Far more concise and unambiguously clear. No more typing unsigned long long int or uint64_t

I would have liked it more if it was U64 instead of u64, etc. It feels weird when all the other types are in PascalCase but then the primitive types are like this. Also str -> Str.

To make them easier to type and more aesthetically pleasing

Where I have landed with arenas is that the allocator is the easy part, and being honest about lifetimes is the hard part. They work beautifully when the work has a clear phase shape — parse a request, walk a tree, build a result, then throw it all away — because you stop paying for a thousand individual frees and you stop fragmenting the heap. They go wrong quietly when something that actually lives longer gets allocated in the arena and either keeps the whole block alive or gets used after a reset. The pattern that has saved me is separate scratch and long-lived arenas, plus a hard rule that nothing crosses that boundary without an explicit copy. I also want a high-water mark in debug builds, otherwise peak usage creeps up unnoticed until a large input makes it obvious all at once.

Reply on news.ycombinator.com