Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Arena allocator tips and tricks

nullprogram.com

Post reply on HN
Print view View original

21–30 of 99 posts

Re: Arena allocator tips and tricks

#21

Post by [deleted] »

dellorter wrote: post #18
matheusmoreira wrote: post #17

Excellent article. > While you could make a big, global char[] array to back your arena, it’s technically not permitted (strict aliasing). Aren't char pointers/arrays allowed to alias everything? I used that technique in my programming language and its allocator. It's freestanding so I couldn't use malloc. I had to get memory from somewhere so I just statically allocated a big array of bytes. It worked perfectly but…

If you overlay a struct in your (char) buffer and dereference a pointer to it you would be accessing something with a different type than its declared type(char* as struct something *), it’s strict aliasing violation To do stay in the rules you could set up a void* to suitable region in a linkerscript

[deleted]

Re: Arena allocator tips and tricks

#22

Post by gpderetta »

bajsejohannes wrote: post #15

> Typically arena lifetime is the whole program Some other good cases for arenas are rendering of a frame in a video game and handling of a http request. The memory is contained within that context and short lived.

That's the lifetime of the objects in the arena, but wouldn't you recycle the arena itself across frames?

For requests it might make sense to have low and high water marks so that additional arenas are created during request peaks and destroyed after if you want to limit long term memory usage of your application.

Re: Arena allocator tips and tricks

#23

Post by varispeed »

corysama wrote: post #5

A very old trick for running Lua in your PlayStation 2 game (where the PS2 is a machine with 32MB of RAM and no memory paging) is to hook Lua’s realloc function into the venerable Doug Lea’s Malloc ( https://gee.cs.oswego.edu/dl/html/malloc.html ) set up to run in arena mode (ONLY_MSPACES? It’s been a decade or two…). That way Lua can fragment the arena all it wants without making a mess of the rest of the tiny addre…

I recently needed to write a memory allocator and being lazy asked ChatGPT for help. Interestingly it came up with implementation eerily similar to what is described in that document. Nonetheless everything worked like a charm from the start.

Re: Arena allocator tips and tricks

#24

Post by flohofwoe »

gpderetta wrote: post #22
bajsejohannes wrote: post #15

> Typically arena lifetime is the whole program Some other good cases for arenas are rendering of a frame in a video game and handling of a http request. The memory is contained within that context and short lived.

That's the lifetime of the objects in the arena, but wouldn't you recycle the arena itself across frames? For requests it might make sense to have low and high water marks so that additional arenas are created during request peaks and destroyed after if you want to limit long term memory usage of your application.

Typically you would have different arenas for different lifetimes ('per frame', 'per level', 'per game session' - or maybe even more specialized, like the duration of an IO operation), and 'reset' the arenas at the end of their respective lifetimes (which is basically just setting the current 'top offset' to zero). This sort-of expects that object destruction is a no-op (e.g. no destructors need to be called).

The general idea being that you don't need to track granular 'per-object lifetimes', but only a handful of 'arena lifetimes', and all objects share the lifetime of the arena they've been allocated in.

Of course it's also possible to manually call a destructor on an object in the arena without recycling its memory, but I heavily prefer using plain POD structs without owning pointers and which can be safely 'abandondend' at any time without leaking memory.

Re: Arena allocator tips and tricks

#25

Post by usrnm »

> A minority of programs inherently require general purpose allocation, at least in part, that linear allocation cannot fulfill. This includes, for example, most programming language runtimes

Interesting definition of "minority"

Re: Arena allocator tips and tricks

#26

Post by sylware »

I tend to avoid to work with data types which require to have a stable virtual address, namely a dynamic base with an offset. Because, mremap.

That said, it really depends on the data usage semantics, and one could write a much less costly allocator for such specific data. Virtual address stable generic allocators have a tendancy to be technical abominations based on statistical usage assumptions. Namely, their cost could be not worth for the improvment, even if there is a significant one.

Re: Arena allocator tips and tricks

#27

Post by dgb23 »

yxhuvud wrote: post #19
TickleSteve wrote: post #8

Earlier quoted context omitted.

also called a "bump" allocator... because all it does is bump a pointer. nice to use when you have a nicely ordered order of execution where you are guaranteed to always come back to a known position where you can free the entire heap/arena at once. (i.e. a typical main message handling loop).

You can however use bump allocation for things that are not arenas. There are some GC allocators that use the technique.

The JVM GC has a generational model.

It first allocates objects into an arena like structure. In a second step, it moves (evacuates) long lived objects into a compact region. The first region gets deallocated at once after.

Roughly speaking this leans on a heuristic that most objects are short lived. So it has arena like characteristics, but is of course managed/dynamic.

This might be one reason why managed languages like Java/C# get such good out of the box performance. You really need insight in your program and how it executes to beat this.

Re: Arena allocator tips and tricks

#28

Post by flohofwoe »

sixthDot wrote: post #3

This globally good, two remarks however: > you don’t need to write destructors I think this is not accurate. Destructors are not deallocators, they are supposed to set the object field in an invalid state. Now truth is that both are often called together, e.g `delete`. > Typically arena lifetime is the whole program, so you don’t need to worry about freeing it A technic I use is to increment a counter on `arena.alloc…

> Destructors are not deallocators, they are supposed to set the object field in an invalid state.

A typical arena allocator would just reset an offset to zero when the arena is 'freed' without calling any object destructors, and the allocator wouldn't actually have any type information about the objects allocated in the arena (of course you could also write an allocator which registers a destructor function with each allocation, and which would be called before the arena is reset):

    bla_t* bla = arena_alloc(arena, alignment, size, destructor_func);
For C++ style RAII it probably makes more sense to use placement-new, and call the destructor manually to 'invalidate' the object without recycling its memory (the memory would only be recycled once the arena allocator is reset).

Re: Arena allocator tips and tricks

#29

Post by vkazanov »

usrnm wrote: post #25

> A minority of programs inherently require general purpose allocation, at least in part, that linear allocation cannot fulfill. This includes, for example, most programming language runtimes Interesting definition of "minority"

As a share of the total number of programs written this is a minority indeed. How many pls are out there vs the number of libraries/apps?

The number of deploys is a different thing.

Re: Arena allocator tips and tricks

#30

Post by usrnm »

vkazanov wrote: post #29
usrnm wrote: post #25

> A minority of programs inherently require general purpose allocation, at least in part, that linear allocation cannot fulfill. This includes, for example, most programming language runtimes Interesting definition of "minority"

As a share of the total number of programs written this is a minority indeed. How many pls are out there vs the number of libraries/apps? The number of deploys is a different thing.

Almost every program written in some programming language depends on the runtime provided by this programming language. Very few programming languages even let you to opt out of using the runtime. Which means that if the runtime needs something, then your program also needs it. Complexity doesn't magically go away when you put it into a library
Post reply on HN