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

31–40 of 99 posts

Re: Arena allocator tips and tricks

#31

Post by matheusmoreira »

gpderetta wrote: post #20
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…

char can alias everything, i.e. you can deference a char pointer with impunity, even if the actual dynamic type[1] of an object is a different type. The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type. In C++ you can just use placement new to change the dynamic type of (part of ) a char array (but beware of pointer p…

> The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type.

A limitation like that simply makes no sense to me. Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled. If we're writing C, it's because we want to do stuff like that without the compiler getting clever about it.

> you should be able to change the type of anonymous memory (for example, what is allocated with malloc) by simply writing into it

Well, in my case, I'm the one writing the malloc and the buffer is the anonymous memory. I remember months ago I scoured the GCC documentation for some kind of builtin that would allow me to mark the memory as such but there was nothing. I did add some malloc attributes to my allocation function just like TFA suggested but apparently its main purpose is to optimize based on aliasing nonsense which I disabled anyway.

Re: Arena allocator tips and tricks

#32

Post by matheusmoreira »

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

Welp. Linus Torvalds was right about this stuff.

https://lwn.net/Articles/316126/

https://lkml.org/lkml/2003/2/26/158

Re: Arena allocator tips and tricks

#33

Post by LoganDark »

matheusmoreira wrote: post #31
gpderetta wrote: post #20

Earlier quoted context omitted.

char can alias everything, i.e. you can deference a char pointer with impunity, even if the actual dynamic type[1] of an object is a different type. The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type. In C++ you can just use placement new to change the dynamic type of (part of ) a char array (but beware of pointer p…

> The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type. A limitation like that simply makes no sense to me. Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled. If we're writing C, it's because we want to do stuff like th…

> Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled.

Well, yeah. Strict aliasing is less about the incidental values of memory addresses and more about the actual semantics of what you're doing. Where writing a struct into the middle of a char array makes no sense because you have no guarantee in the type system that the array is properly sized or aligned to contain that struct.

Re: Arena allocator tips and tricks

#34

Post by gpderetta »

matheusmoreira wrote: post #31
gpderetta wrote: post #20

Earlier quoted context omitted.

char can alias everything, i.e. you can deference a char pointer with impunity, even if the actual dynamic type[1] of an object is a different type. The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type. In C++ you can just use placement new to change the dynamic type of (part of ) a char array (but beware of pointer p…

> The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type. A limitation like that simply makes no sense to me. Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled. If we're writing C, it's because we want to do stuff like th…

At some point you need to get the memory for your pool from somewhere, for example from malloc [1], hence you can safely set the type of the raw memory by writing into it. You can also change that type to some other type, by writing other stuff (so you can reuse the memory). You can also write metadata to it between uses. What you cannot do is having overlapping lifetimes for different types.

Making sure that you respect all the underspecified, obscure, and often contradicting rules is not easy, so if you prefer to disable strict-alias, you have my sympathy. For the most part is useful for high performance numerical code, and less advantageous for typical pointer chasing stuff.

From the practical point of view, the safest way to implement a custom allocator is to make sure that the compiler can't see through it, so separate compilation and no LTO and/or launder your pointers through appropriate inline asm.

[1] but other 'anonymous' sources, like mmap, would also work in practice.

Re: Arena allocator tips and tricks

#35

Post by matheusmoreira »

LoganDark wrote: post #33
matheusmoreira wrote: post #31

Earlier quoted context omitted.

> The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type. A limitation like that simply makes no sense to me. Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled. If we're writing C, it's because we want to do stuff like th…

> Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled. Well, yeah. Strict aliasing is less about the incidental values of memory addresses and more about the actual semantics of what you're doing. Where writing a struct into the middle of a char array makes no sense because you have no guarantee in the type system that t…

The compiler knows the size of statically allocated buffers and can be told about alignments with:

  __attribute__((aligned(N)))
  __builtin_assume_aligned(P, N)
Is this information sufficient for correct code generation?

Re: Arena allocator tips and tricks

#36

Post by [deleted] »

matheusmoreira wrote: post #32
dellorter wrote: post #18

Earlier quoted context omitted.

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

Welp. Linus Torvalds was right about this stuff. https://lwn.net/Articles/316126/ https://lkml.org/lkml/2003/2/26/158

[deleted]

Re: Arena allocator tips and tricks

#37

Post by neonsunset »

dgb23 wrote: post #27
yxhuvud wrote: post #19

Earlier quoted context omitted.

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…

This is correct. In .NET Gen 0 heap, if there is sufficient space, the allocation is just getting a heap address from threadlocal, bumping an offset, writing object header and methodtable, and returning the pointer (reference).

Re: Arena allocator tips and tricks

#38

Post by kgeist »

In my hobby project, I started always passing an allocator argument to every function or object which requires allocation (inspired by Zig) and I love it so far. Often I can just pass a bump pointer allocator or a stack-based allocator and do not care about deallocation of individual objects. I also wrote a simple unit testing framework to test out-of-memory conditions because it's easy to do when you're in control of allocators. Basically I inject an allocator which calculates how many allocations are done when a unit test is run, and then unit tests are later rerun again by injecting OOM at every known allocation point. A lot of bugs and crashes happen when an OOM is encountered because such paths are rarely tested. The idea of my pet project is a very resilient HTTP server with request-scoped allocations and recovery from OOM without crashes.

Re: Arena allocator tips and tricks

#39

Post by matheusmoreira »

gpderetta wrote: post #34
matheusmoreira wrote: post #31

Earlier quoted context omitted.

> The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type. A limitation like that simply makes no sense to me. Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled. If we're writing C, it's because we want to do stuff like th…

At some point you need to get the memory for your pool from somewhere, for example from malloc [1], hence you can safely set the type of the raw memory by writing into it. You can also change that type to some other type, by writing other stuff (so you can reuse the memory). You can also write metadata to it between uses. What you cannot do is having overlapping lifetimes for different types. Making sure that you res…

> For the most part is useful for high performance numerical code, and less advantageous for typical pointer chasing stuff.

Yeah. I've read that the aliasing rules and features like restrict were introduced to C because Fortran had them.

> the safest way to implement a custom allocator is to make sure that the compiler can't see through it

Makes sense.

> launder your pointers through appropriate inline asm

This is a really neat trick indeed. I learned a lot today.

Re: Arena allocator tips and tricks

#40

Post by londons_explore »

Having to decide ahead of time how much memory to allocate to the arena is... crap...

The vast majority of programmers don't want arbitrary 'out of memory in arena' errors just because the user inputted slightly more things than expected. Yes, I know that modern OS's don't actually allocate memory till you use it, but when you make widespread use of that functionality, typically your reuse of address space is poor and free'd stuff will be neither reused nor returned to the OS.

Likewise, not being able to free things within the arena is also crap - I'm sure there will be plenty of times the system is running low of RAM, but hundreds of applications have thousands of arenas, all half full of never-to-be-used again items that the OS can't reuse.

Post reply on HN