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

Allocation is cheap in .NET until it is not

tooslowexception.com

Post reply on HN
Print view View original

31–40 of 67 posts

Re: Allocation is cheap in .NET until it is not

#31

Post by kevingadd »

ridiculous_fish wrote: post #30

How does .NET support pinned pointers with a bump pointer allocator? Does it just eagerly move pinned objects out of the contiguous heap?

Pinning typically just means it is left in place and exempted from compaction. This does mean that you can end up with a performance penalty and nasty holes in your heap layout. Sometimes marshaling code will opt to make a copy of the data instead (and then perhaps pin that), it depends on the type. There's not a lot of explicit documentation on this (probably because some of it is an optimization). Pinned objects can't be moved without breaking semantics - once you get a pinned-type GCHandle to an object, you can just directly get the address and it won't ever change. (I believe once the GCHandle is freed/finalized by the GC, it will automatically unpin the object.)

Typically this isn't a big problem - pinned data structures in .NET code are either pinned for short periods of time (to pass to native code), or are reusable large big buffers that stay pinned forever. Large buffers are always allocated in the large object heap right away. You can always allocate native memory directly in which case the GC doesn't care about it.

This may be changing since recent updates to C# and the runtime have introduced the concept of interior pointers to objects, where you can have a raw pointer to a field within a GCable object. Right now those are constrained to living on the stack only, so the period of time in which the object can't be moved/compacted as a result is relatively short.

Re: Allocation is cheap in .NET until it is not

#32

Post by apardoe-MSFT »

"Managed memory is free. Not as in free beer, as in free puppy."

Dev manager of Exchange used that line in a talk. Never were more insightful words spoken. Devs will move from C++ where they obsess about every allocation to .NET and they'll totally forget that allocation is expensive no matter what the platform or runtime.

Re: Allocation is cheap in .NET until it is not

#33

Post by swgillespie »

ridiculous_fish wrote: post #30

How does .NET support pinned pointers with a bump pointer allocator? Does it just eagerly move pinned objects out of the contiguous heap?

The .NET GC hands out "allocation contexts" to every thread. An allocation context is little more than two pointers: the bump pointer and the bump pointer limit. If the runtime allocates too much and exceeds the bump pointer limit, it asks the .NET GC for a "quantum" of memory (usually a few KB). Each quantum that the GC gives out is guaranteed to be free of pinned objects - it'll find a contiguous block of memory to hand out.

Pins on the ephemeral segment are generally bad in that the quantum allocator has to be aware of them and squeeze objects between them.

The GC is not permitted to eagerly move pinned objects out of the heap. This is because there are two ways an object can be pinned: a pinning GC handle or a stack scan reports a local as pinned (e.g. the "fixed" keyword in C#). The GC does not know until a GC is already in progress that an object has been pinned and, at that point, it's not legal to move the object so it must stay where it is at the current point in time.

Re: Allocation is cheap in .NET until it is not

#34

Post by kevingadd »

kbsletten wrote: post #10
Shoothe wrote: post #6

Earlier quoted context omitted.

This pattern was also used by Java and .NET for implementing cheap String.substring calls where all substrings would use the same underlying array with just offsets changed. Unfortunately it turns out that people read entire files into a one big String and then have a reference to just a small piece of it (via substring) marking the big underlying array as reachable for the GC holding a lot of memory for no reason. T…

I know this was changed recently-ish in Java, but I hadn't heard of anybody doing the old substring trick in .NET, do you know when they cut over?

Regex's implementation in the standard library used to do this, and I think maybe still does. Bonus points because they leaked a reference to the last string you ran a regex against (????) so if it was big you'd just eat up 50 mb of heap for a while.

Re: Allocation is cheap in .NET until it is not

#35

Post by johncolanduoni »

kevingadd wrote: post #31
ridiculous_fish wrote: post #30

How does .NET support pinned pointers with a bump pointer allocator? Does it just eagerly move pinned objects out of the contiguous heap?

Pinning typically just means it is left in place and exempted from compaction. This does mean that you can end up with a performance penalty and nasty holes in your heap layout. Sometimes marshaling code will opt to make a copy of the data instead (and then perhaps pin that), it depends on the type. There's not a lot of explicit documentation on this (probably because some of it is an optimization). Pinned objects ca…

> (I believe once the GCHandle is freed/finalized by the GC, it will automatically unpin the object.)

GCHandle is a struct so you have to explicitly call GCHandle.Free().

Re: Allocation is cheap in .NET until it is not

#36

Post by kevingadd »

johncolanduoni wrote: post #35
kevingadd wrote: post #31

Earlier quoted context omitted.

Pinning typically just means it is left in place and exempted from compaction. This does mean that you can end up with a performance penalty and nasty holes in your heap layout. Sometimes marshaling code will opt to make a copy of the data instead (and then perhaps pin that), it depends on the type. There's not a lot of explicit documentation on this (probably because some of it is an optimization). Pinned objects ca…

> (I believe once the GCHandle is freed/finalized by the GC, it will automatically unpin the object.) GCHandle is a struct so you have to explicitly call GCHandle.Free().

Makes sense. I make a point of calling Free but it wasn't clear to me whether the pin was attached to the object reference (since the handle contains a reference).

Re: Allocation is cheap in .NET until it is not

#37

Post by alkonaut »

matthewwarren wrote: post #28
alkonaut wrote: post #23

Earlier quoted context omitted.

I realize it's a pretty hard problem - and hadn't java already demonstrated the feasibility of it, I would have doubted it to be possible at all without major surgery to both language and runtime (special scoped types etc). So I guess my question is: is there something about C# or .NET that makes it much harder to do escape analysis than it is in Java world? An evil example is class Something { private static readonl…

This post has a nice investigation into 'Escape Analysis' in Java, https://shipilev.net/jvm-anatomy-park/18-scalar-replacement/ Shows that the Hotspot doesn't handle it in all scenarios: > But, EA is not ideal: if we cannot statically determine the object is not escaping, we have to assume it does. Complicated control flow may bail earlier. Calling non-inlined — and thus opaque for current analysis — instance method…

Thanks that clears some of it up. It seems that java runtimes that do EA actually do this sort of crazy difficult analysis that quickly breaks down with branches and non-inlined code.

Re: Allocation is cheap in .NET until it is not

#38

Post by dfox »

ridiculous_fish wrote: post #29
dfox wrote: post #22

Earlier quoted context omitted.

The point is that you need moving GC for bump-allocation to be possible. Traditional mark-and-sweep is non-moving while semispace collector is the simplest to describe moving GC. The practical takeaway from all that is that usual generational GC constructions with semispace minor collections and mark-and-sweep/compact major collections are in the complexity/efficiency sweet spot. By the way it is possible and trivial…

Moving collectors get you best allocation throughput but impose other costs, which are hard to measure because they are design constraints. Obviously you cannot have a moving conservative collector so you must have stack maps, safe points, etc. Or interactions with native code. How can native code hold a reference to a potentially movable object? .NET allows pinned pointers (obviously hurting compaction efficiency) w…

The design space has one non-obvious but fundamental strict dividing line: if you can constrain the mutator code enough to be able to insert write barriers for generation GC you also can constrain it enough to have all the metadata to support moving GC at least to the extent of opportunistic compaction (eg. what CLR and SBCL on i386 does, both of which have conservationaly scanned stack because building stack map for register-constrained platforms like i386 is essentially impossible).

On the other hand BEAM has AFAIK non-moving generational GC implemented in the aforementioned way which is in this case trivial as you don't need any write barriers and remembered set when heap objects are inherently immutable. (In this it is somewhat relevant that Boehm GC for some time had API that allowed you to signal the time extent of mutatibility of given heap object to the GC, AFAIK it is no-op since some 6.x version and the concurrent/incremental/generational bits of it work on basis of mprotect() and handling SIGSEGV)

Re: Allocation is cheap in .NET until it is not

#39

Post by ridiculous_fish »

dfox wrote: post #38
ridiculous_fish wrote: post #29

Earlier quoted context omitted.

Moving collectors get you best allocation throughput but impose other costs, which are hard to measure because they are design constraints. Obviously you cannot have a moving conservative collector so you must have stack maps, safe points, etc. Or interactions with native code. How can native code hold a reference to a potentially movable object? .NET allows pinned pointers (obviously hurting compaction efficiency) w…

The design space has one non-obvious but fundamental strict dividing line: if you can constrain the mutator code enough to be able to insert write barriers for generation GC you also can constrain it enough to have all the metadata to support moving GC at least to the extent of opportunistic compaction (eg. what CLR and SBCL on i386 does, both of which have conservationaly scanned stack because building stack map for…

Aside from the stack, another key challenge for moving GCs is hash tables keyed on object identity. If the object can move the raw address is no longer a suitable hash.

.NET at one point stored an extra per-object word, which was either (via its LSB) a random hash code or a pointer to a metadata object that held the lock, etc.

Python did this cute thing where moved objects would get an extra word allocated to store the moved-from address, which was where the hash was stored.

Apple's plan for its (not-released) ObjC moving GC was to directly teach the GC about hash tables, so it could rehash on collection (!).

Do you know how other implementations handle this?

BEAM's GC is indeed a marvel both because of the immutability and also the enforced process isolation, so that each process can do its own GC independently. As you say, constrain the mutator...

Re: Allocation is cheap in .NET until it is not

#40

Post by ramchip »

dfox wrote: post #38
ridiculous_fish wrote: post #29

Earlier quoted context omitted.

Moving collectors get you best allocation throughput but impose other costs, which are hard to measure because they are design constraints. Obviously you cannot have a moving conservative collector so you must have stack maps, safe points, etc. Or interactions with native code. How can native code hold a reference to a potentially movable object? .NET allows pinned pointers (obviously hurting compaction efficiency) w…

The design space has one non-obvious but fundamental strict dividing line: if you can constrain the mutator code enough to be able to insert write barriers for generation GC you also can constrain it enough to have all the metadata to support moving GC at least to the extent of opportunistic compaction (eg. what CLR and SBCL on i386 does, both of which have conservationaly scanned stack because building stack map for…

The BEAM GC algorithm is explained in details here:

https://www.erlang-solutions.com/blog/erlang-garbage-collect...

I think it’s moving, unless I misunderstood something?

Post reply on HN