All pointers stored in the arena are weak

[mumbleskates]

If any type containing a pointer is stored in the arena, the data it points to may be garbage collected if no other pointers exist because the GC cannot know about those pointers as the slabs are allocated without type information. This leads to UB when those pointers are dereferenced.

package main

import (
	"fmt"
	"runtime"

	"github.com/ortuman/nuke"
)

func main() {
	arena := nuke.NewSlabArena(256*1024, 1)
	var homes []*string
	for i := 0; i < 1000; i++ {
		home := nuke.New[string](arena)
		*home = fmt.Sprintf("this string contains the number %d in the middle", i)
		if i%10 == 0 {
			runtime.GC()
		}
		homes = append(homes, home)
	}
	// All pointers stored in the arena are weak, and do not keep the data they
	// refer to alive; any pointed-to data may be garbage collected if no "real"
	// pointers to it exist.
	for i, home := range homes {
		fmt.Printf("%d: %q\n", i, *home)
	}
}

https://go.dev/play/p/r4YNthSmv-4

[philpearl]

In case it helps - I've got what I've been calling a 'poor person's arena' in my AVRO codec, which gets around this problem by allocating data per-type (essentially per-type slabs) and using type information when allocating by calling low-level reflection functions directly. https://github.com/philpearl/avro/blob/d2f7ca4351f4676a66b6ccb901df2b81643c748b/buffer.go#L134 https://github.com/philpearl/avro/blob/master/unsafetricks.go

[mumbleskates]

yeah, that's what we have to do to make arenas safe in general; ensuring that the right type metadata is attached to every slab's allocation is the only way to make the pointers within them "real". i think it's probably the only way to make this arena usable except in extremely niche cases where all the types are pointer-free, which we can't detect or enforce.

this really calls into question how much faster the arena really is, given that it may end up doing relatively little to reduce the workload on the GC, and how resetting the arena without discarding its slabs affects that. (a major advantage of typing the slabs is that resetting the arena becomes relatively safe, because the memory from the arena will never be doled out aliased with another type; it's just a regular slot in a regular slice, and any still-living pointers into the slab will at worst just see an erased (or replaced) struct value instead of causing UB).

the main advantage: fewer small, real allocations by the allocator that need to be freed. this can mean reduced memory growth per request, exactly equal to how much memory is explicitly allocated from the arena instead of globally. unfortunately it's difficult to make this include a lot of the allocations that are actually involved. ancillary allocations are hard to move into the arena; string data in particular will live outside unless a mechanism is added to deliberately copy it into the arena somewhere. maps of any kind will never truly live inside the arena because the map's true struct is hidden from us by the runtime.

regardless, if we're able to explicitly put many, many small allocations into the arena that we would otherwise have put into the global allocator where the memory has to wait for a GC pass to become available again... that can potentially help!

[AnyCPU]

@mumbleskates I'm not sure what exactly you want to say, maybe your example is a little bit misleading.

below you can find updated example of above:

package main

import (
	"fmt"
	"runtime"
	"unsafe"

	"github.com/ortuman/nuke"
)

func main() {
	arena := nuke.NewMonotonicArena(1024*1024, 1024)

	var homes []*string

	for i := 0; i < 1000; i++ {
		s := fmt.Sprintf("this string contains the number %d in the middle", i)

		home := nuke.MakeSlice[byte](arena, len(s), len(s))

		copy(home, s)

		homes = append(homes, (*string)(unsafe.Pointer(&home)))

		if i%10 == 0 {
			runtime.GC()
		}
	}

	// All pointers stored in the arena are weak, and do not keep the data they
	// refer to alive; any pointed-to data may be garbage collected if no "real"
	// pointers to it exist.
	for i, home := range homes {
		fmt.Printf("%d: %q\n", i, *home)
	}
}

At least at the moment we have correct output in a terminal.

[AnyCPU]

In general if you have such questions in Go then you should be aware about Go memory model, GC mechanics and unsafe magic.

Unsafe is unsafe. Go's GC is not smart enough to guess what magic is going on when you touch "unsafe".

Also Go's Arenas is similar to "placement new" in C++. In order to use that you should know a little bit more than regular Go user, because arenas and custom allocators are not so simple.

[AnyCPU]

@mumbleskates I have more rudeness for you.

you do not put strings into memory managed by the arena.

if you want to have a string managed by the arena, you must allocate memory for that string inside the arena. so you should use "make slice" method.

Go's memory model does not have pointer arithmetic like in C. A lot of related features from C does not work in Go.

The arena is not aware about what Go's GC does.

Go's GC is not aware what you do in the arena.

your original example does something like following:

• "allocates" a one byte and gets its pointer
• makes a new string by fmt.Sprintf
• somehow copies string data into memory managed by a pointer (effectively one byte is managed)
• somehow overwrites strings produced on previous iterations
• runs Go's GC

in result you have:

• memory with undefined state because of code in the example;
• Go GC that want to "help" you;
• The Arena that want to "help" you;
• GC and Arena are not aware of each other.

so what do you want to get to according to above?

That's why I've provided "correct" example of your code.

Before using Go's unsafe package, it is good to read following docs:

• https://go.dev/ref/spec#Package_unsafe
• https://pkg.go.dev/unsafe

unsafe.Pointer and uintptr must be used carefully, the arena too.

Go's unsafe package is not covered by Go 1 Promise, but the package itself is used by other standard Go packages.

And a bit about the next line:
(*string)(unsafe.Pointer(&home))

this is what Go's strings.Builder does in its String method for Go versions up to 1.20, in 1.20 version it was simplified a bit.

if you are aware of Go's memory, unsafe and uintptr in theory you should not get questions like in an original message and code like in original example should be considered like a bug.

long story short: the unsafe package and memory arenas are for people that know what they do.

[mumbleskates]

your original example does something like following:

* "allocates" a one byte and gets its pointer

* makes a new string by fmt.Sprintf

* somehow copies string data into memory managed by a pointer (effectively one byte is managed)

* somehow overwrites strings produced on previous iterations

* runs Go's GC

This is entirely incorrect. If you read it closely you can see what it does, rather than guessing:

• it makes a string by fmt.Sprintf, which is naturally allocated outside the arena
• it puts the string struct into the arena, keeping a pointer to it so we can see if it is valid later
• at this point in the execution, the allocation holding the string data outside the arena should be kept alive by the arena. however, it is not: the garbage collector thinks the arena contains no pointers, and anything that is referenced only by a pointer in an arena will be garbage collected.
• the garbage collector is periodically run, causing any allocations referred to by the arena to be freed, even though the "string" struct in the arena (which we still have a pointer to) refers to that same memory.
• accessing the memory referred to by these string structs is now UB, and when we look at their contents we can see that they contain various garbage: that memory has been repeatedly freed, sometimes zeroed, and often reused for other strings produced by fmt.Sprintf.

at no point is the string data produced by fmt.Sprintf copied anywhere, explicitly or implicitly. certainly it might make more sense to put the string data into the arena, that's true. however it's already written in another allocation which must be cleaned up regardless. even more than that, i don't care: this is a demonstration of a weakness in the library that is not warned about or documented anywhere. it is simply easiest to see that these outside allocations are freely deleted and reused by the global allocator.

Once again, I am not using the unsafe package. Only your example contains unsafe, though it does use it somewhat incorrectly. There are dedicated methods for turning a []byte into a string, and you should use them instead of relying on the fact that currently the fields of string are a prefix within []byte; this is not guaranteed, and your example should create strings via unsafe.String(unsafe.SliceData(home), len(home)) rather than leaking all 3 words of the slice onto the heap and praying that the first two words will always be the same as they would be in a string struct.

The arena is not aware about what Go's GC does.

Go's GC is not aware what you do in the arena.

yes, this is what makes using this arena deeply unsafe and hazardous except in extremely limited use cases. Writing an arena for only raw byte and integer data is one thing, but there are no amenities to make that easier here, and nothing at all in any of the documentation to warn of this pointer-weakening hazard.

if the slabs for potentially pointer-bearing types are deliberately typed upon allocation instead, this hazard disappears without removing the basic utility or advantages of the arena as it is today.

If your response to all this is along the same lines you've already expressed, that you believe weaklings and losers who can't write exactly correct code and know precisely what will and won't be safe at all times should not use the library, I'm left asking who appointed you as the monarch of this repository that you don't own.

[philpearl]

I think @AnyCPU has a point - if you ensure all allocations in the arena only point to other allocations in the arena then you're fine. This should be a reasonable constraint for something like a serialisation decoder, so I think there are reasonable use-cases (and indeed if I'd twigged that for my AVRO decoder I might have made my poor arena simpler). It should also be fine for something like a JSON decoder - everything the JSON decoder allocates can come from the arena.

In terms of whether an arena approach is useful or performant if you need to do the things I did - yes, it can be very helpful. I built the AVRO decoder to handle generating ML features from data with very wide rows with lots of strings. Each row would generate a lot of garbage that could all be discarded once the row was processed.

Before adding an arena approach it was spending > 95% of CPU in garbage collection. After adding the arenas garbage collection was very low, and a process that IIRC took ~20 hours completed in more like 20 minutes.

But yes, arena approaches can be very dangerous and require extremely careful programming. The best you can hope is that when you discard the arena that accidentally referenced memory becomes invalid quickly and causes exceptions quickly. I'd hoped the Go arena was going to be an improvement on my efforts in this regard. In the meantime I'm having reasonable success just being extremely careful!

[philpearl]

Oh, I should say the key to making things performant is re-using arenas, and having arenas that gradually right-size to the task in hand.

[philpearl]

And also to be clear I don't anymore think that this is a bug - at best it's a documentation issue.

[mumbleskates]

I think @AnyCPU has a point - if you ensure all allocations in the arena only point to other allocations in the arena then you're fine.

i think if they'd bothered to say it the way you did at any point, instead of saying a lot of immediately disprovable and contradictory things about the demonstrating example and what it does and then producing a hazardous and confusing example of their own, then they would have had a point.

And also to be clear I don't anymore think that this is a bug - at best it's a documentation issue.

there's definitely an argument for this. I believe it's pretty clear something needs to happen either way: it's very, very involved in the inner workings of the (current) runtime to even realize that this happens. in my opinion, either there needs to be clear and up front documentation that this is a double ended chainsaw footgun in a language that does nothing to help make it safe; or there could be handling for this (like a switch case that creates typed slabs for anything that isn't a non-pointer primitive, a slice of such, or the user explicitly specifie the type is free of external pointers).

i would lobby for typed slabs at least as a longer-term feature goal, as an allocation saved is still an allocation saved even if it points to another allocation that isn't. the pointed-to memory is already on the heap; the best we could do by copying it into the arena is prevent the allocation from graduating to an older generation. i don't think finding the typed slabs this way would be terrible as allocating memory within the arena already has a cost approximately linear to the number of slabs, so there are already other fixes to be made.

[AnyCPU]

@mumbleskates i see you want to get another one portion of the rudeness, ok.

This is entirely incorrect. If you read it closely you can see what it does, rather than guessing:

it makes a string by fmt.Sprintf, which is naturally allocated outside the arena

this is true

it puts the string struct into the arena, keeping a pointer to it so we can see if it is valid later

who said that? did you read links above?

at this point in the execution, the allocation holding the string data outside the arena should be kept alive by the arena. however, it is not: the garbage collector thinks the arena contains no pointers, and anything that is referenced only by a pointer in an arena will be garbage collected.

who said that? it should not. GC does not thinks, it knows.

the garbage collector is periodically run, causing any allocations referred to by the arena to be freed, even though the "string" struct in the arena (which we still have a pointer to) refers to that same memory.

what do you mean when you say the string struct? a string in Go is synthetic sugar.

accessing the memory referred to by these string structs is now UB, and when we look at their contents we can see that they contain various garbage: that memory has been repeatedly freed, sometimes zeroed, and often reused for other strings produced by fmt.Sprintf.

I bet you just do not understand what is going under the hood of the arena and what is going on in that case when you do *string.

at no point is the string data produced by fmt.Sprintf copied anywhere, explicitly or implicitly. certainly it might make more sense to put the string data into the arena, that's true. however it's already written in another allocation which must be cleaned up regardless. even more than that, i don't care: this is a demonstration of a weakness in the library that is not warned about or documented anywhere. it is simply easiest to see that these outside allocations are freely deleted and reused by the global allocator.

if you do not care it is your trouble, the arena and GC just simply do their job, if you misuse it, if you do not read provided docs, if do not read what memory arenas are, nobody cares.
it is more demonstration of that you do not read docs.

Once again, I am not using the unsafe package. Only your example contains unsafe, though it does use it somewhat incorrectly. There are dedicated methods for turning a []byte into a string, and you should use them instead of relying on the fact that currently the fields of string are a prefix within []byte; this is not guaranteed, and your example should create strings via unsafe.String(unsafe.SliceData(home), len(home)) rather than leaking all 3 words of the slice onto the heap and praying that the first two words will always be the same as they would be in a string struct.

once again I can show Go's source code from official repo without any praying.

yes, this is what makes using this arena deeply unsafe and hazardous except in extremely limited use cases. Writing an arena for only raw byte and integer data is one thing, but there are no amenities to make that easier here, and nothing at all in any of the documentation to warn of this pointer-weakening hazard.

it is mentioned a lot of time, the areanas and unsafe are not for everyone.

If your response to all this is along the same lines you've already expressed, that you believe weaklings and losers who can't write exactly correct code and know precisely what will and won't be safe at all times should not use the library, I'm left asking who appointed you as the monarch of this repository that you don't own.

you have just appointed me as the monarch, this is paradox.
I never said about losers and etc, you did that, so a ball is on your side.

you have a wall, a wall has a socket, you also have two fingers, you are able to put you finger into your socket.
the trick is that socket's manufacturer is not in charge of what you do with a socket.

[AnyCPU]

@philpearl you are right.

of course it is nice to increase a number of examples how to use this library and docs too.

now i understand why exactly Go's team does not want to release their arena officially.

[AnyCPU]

@philpearl maybe it is interesting topic for you: memory ballasts.

[mumbleskates]

it puts the string struct into the arena, keeping a pointer to it so we can see if it is valid later

who said that? did you read links above?

i said that. so does the script i submitted in the original issue. that is factually what it does. if i am to give you the benefit of the doubt, i can only assume that either you did not read it at all or you suffer from a basic misunderstanding of the data types involved.

at this point in the execution, the allocation holding the string data outside the arena should be kept alive by the arena. however, it is not: the garbage collector thinks the arena contains no pointers, and anything that is referenced only by a pointer in an arena will be garbage collected.

who said that? it should not. GC does not thinks, it knows.

i said that. it is furthermore a known fact of the basic mechanism of go's garbage collector. heap allocations (and i believe stack frames) have associated metadata about the types contained within them, allowing pointers to be traversed by the garbage collector.

the garbage collector is periodically run, causing any allocations referred to by the arena to be freed, even though the "string" struct in the arena (which we still have a pointer to) refers to that same memory.

what do you mean when you say the string struct? a string in Go is synthetic sugar.

strings in golang are not merely sugar, syntactic or otherwise. string is very explicitly a defined type, a runtime struct with two fields. strings are slices of immutable data that have both a pointer and a length, not nul-terminated c-style strings with only a pointer; the mechanical difference between a string and a []byte is that []byte (and other slice types) have a third field, containing their capacity, and their referred-to data can be modified without using unsafe.

you can learn more about this by reading the documentation for string types in general, noticing that reflect.StringHeader has two fields, noticing that unsafe.String requires both a pointer and a length, noticing that golang strings can have their length measured in constant time and contain any byte, or noticing that unsafe.SizeOf("") is two words in size (16, on a 64 bit machine).

at this point it is clear that you have a very fuzzy idea of what is going on in any program that is even slightly tricky with its memory management. I strongly recommend you stick to safe golang for the time being.

[AnyCPU]

@mumbleskates

it puts the string struct into the arena, keeping a pointer to it so we can see if it is valid later

i said that. so does the script i submitted in the original issue.

no, it does not.

yes, on this line:

home := nuke.New[string](arena)

you effectively reserve 16 bytes in the arena.

on this line:

*home = fmt.Sprintf("this string contains the number %d in the middle", i)

you tries to copy whole string which is larger than reserved space, at this point the arena knows nothing about what you are trying to do. Go's GC also does know nothing on this.

after that you stress Go's GC. exact behavior at this point is not covered by Go Spec. in real life underlying memory will contain trash.

because you do not keep whole string in memory managed by arena, you will always have troubles and it does not matter what arena you will use.

yes, actually you can keep pointers in the arena, but they will kept as uintptrs and yes, you can reuse them later by casting them to unsafe.Pointer, but in the Go's GC world it is not guaranteed that they will work at all. What will work is covered by rules provided by links above.

on slice-byte-to-string-in-place-without-copy conversion you can always take a look Go's source code of strings.Builder, if you do not like it, yes you can use unsafe methods.

at this point it is clear that you have a very fuzzy idea of what is going on in any program that is even slightly tricky with its memory management. I strongly recommend you stick to safe golang for the time being.

no, it does not work this way, but i would recommend you to update a mirror.

(c) sincerely emperor.

[AnyCPU]

@mumbleskates as always you can just not to write.

[mumbleskates]

apologies, i didn't realize until now that blocking could prevent further off-topic comments. that's my bad

[mumbleskates]

@philpearl i've been toying with this general idea; were you able to quantify the improvements from using the runtime type functions directly? how's this compare to reflect.Type, and reflect.TypeFor[T]()?

[philpearl]

TBH I can't fully remember. The reflect package has a tendency to allocate unnecessarily, but I've a feeling some of those issues may have been fixed recently. I think if I started fresh I'd perhaps see what could be done directly with the reflect package or even generics, and only switch to the deeply unsafe stuff if the performance wasn't fabulous.

[mumbleskates]

@philpearl That's what I'm leaning towards yeah. from what i can see the current reflect type mechanism just cobbles together an interface object pointing to the static type info struct that those super unsafe functions give you.

The larger challenge certainly seems to be in maintaining usable safety:

1. it's maybe important to return the arena as an interface or something else trivially copyable rather than a pointer to a struct with useful fields in it as the user might otherwise unknowingly dereference and copy it around, invalidating something very important (like how map works, where it's secretly just a pointer)
2. anything that varies the arena's type and behavior, like whether it is taking concurrent locks, has to be in that object or interface; at the same time, actually allocating the underlying memory for the typed slabs has to happen at the public generic function level, outside the arena's vtable (at least if you don't want to use the reflect library to make the backing slice)

all this is doable, it's just a lot of iterating trying to find something that actually works!

[mumbleskates]

i have a branch with:

• auto-growing, auto-shrinking arena implementation
• definitely pointerless data goes into the main slabs, maybe-not-pointerless data goes into slabs containing only that type
• separate apis that skip any kind of type check and promise that the type contains no pointers, allowing some speedups
• a separate call to introspect a type completely and assert that it contains no pointers, panicking if it does; good for going alongside the latter API as a safeguard

overall, the POD path is maybe 15% slower than the monotonic arena (not a significant cost really), with the advantages of automatically growing (with exponential growth, so amortized O(1) cost to allocate) and skipping over slabs that are already full (which may degenerate in the monotonic arena implementation) and automatically shrinking over time if most of the arena is unused (shrinking incrementally if the slab group was less than 1/4 used in that cycle).

i was not able to get any kind of lite introspection to operate any better than just using reflect.Type, and i tried several different options. (for instance, types can be distinguished and looked up without reflection by their any((*T)(nil)) values, but not introspected much.) further attempts to optimize that case hit a wall and it once again became obvious that golang is not a language for low-level optimizations, as the compiler is very unsophisticated and its inlining etc. are very lacking. it does not really appear different than as if the authors of the language were just now realizing there are reasons compilers do a lot of stuff. maybe there are still savings to be had poking around with direct runtime calls, but i don't know if it matters all that much; the reflect calls aren't allocating anywhere, so most of the dead weight there is probably in the unfixable lack of inlining and function call/interface overhead.

Shaving nanoseconds that nobody is likely to notice aside, the implementation still completely saves all the outside allocations, as was the original goal of an arena. (notably, here, there was actually an aborted attempt to make userland arenas recently.) Several choices remain for this, including making individual typechecked allocations maybe 50% slower with the extra logic but making the type dispatch even more automatic, memoizing the full inspection of each type seen into something like a global sync.Map. in many situations that kind of thing would probably be desirable, but i think it's not really critical.

Major improvements other than that would look like a Sprintf-like API (that could use Fprintf into a bespoke string builder under the hood), an append() analog, maybe a "copy this string's value" call. the string writer API seems hard as i feel a desire to make it able to realloc and dealloc itself from the end of its originating slab, which adds messiness, so i've not delved into any of that.