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

41–50 of 67 posts

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

#41

Post by chrisseaton »

alkonaut wrote: post #23
kkokosa wrote: post #12

Earlier quoted context omitted.

In general - yes: https://github.com/dotnet/coreclr/issues/1784 . However, nothing more specific I can say...

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…

> Does java detect that this escaped the stack? How?

Well you assigned the instance to a global variable. That's how Java knows. If you can see that then so can the Java compiler.

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

#42

Post by rjbwork »

apardoe-MSFT wrote: post #32

"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.

>they'll totally forget that allocation is expensive no matter what the platform or runtime.

Well, it's easier to do in a managed language. When you literally don't have to agonize or obsess over every allocation because you aren't responsible for cleaning it up (unmanaged held resources withstanding), you tend not to do so.

P.S.: You're always free to drop down into C or C++ if you want to get some speed, but of course you need to clean up after yourself there. A friend of mine wrote a good guide on doing so, if anyone cares https://github.com/TheBlackCentipede/PlatformInvocationIndep...

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

#43

Post by dfox »

ramchip wrote: post #40
dfox wrote: post #38

Earlier quoted context omitted.

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?

That is why the "AFAIK" was there :)

Few years ago I read some paper from Ericsson that described non-moving generational GC explicitly designed for Erlang's data model which could even be implemented in terms of malloc()/free(), I'm not sure that it was relevant to how it is implemented in current BEAM.

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

#44

Post by dfox »

ridiculous_fish wrote: post #39
dfox wrote: post #38

Earlier quoted context omitted.

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 t…

Cpython has non-moving GC so this is not an issue. On the other hand CPython's hashmap implementation is probably most educational open source hashmap implementation that you can find, because it is full of wonderful and portable performance hacks (for one thing the hash values of CPython's objects is intentionally computed such that the distribution is non-uniform which allows tuning of the hashmap implementation for common cases).

As for having tight coupling between moving GC and hashmap implementation there is another reason why you want to do that: weak pointers and hashmaps that are either weak keyed or weak valued which both are things that are useful for the VM implementation itself (symbol tables, method dispatch caches, identity maps for FFI...).

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

#45

Post by vvanders »

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…

> of which there's a limit (65k in Android!)

Oh man JNI and Android.

I've never heard a developer curse up a storm like I did when one of my co-workers inadvertently stumbled across the 512 LocalRef limit(also a fun one) during an intermittent crash repro.

By the time he got done with his rant we had to talk him out of purchasing a one-way plane ticket to Mountain View.

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

#46

Post by xxs »

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…

A point of JNI - use direct byte buffers. The address remains the same within the virtual address of the process (hence non-movable).

Of course that leaves some memory management in Java, itself, but the price is usually fine for having void* access in C.

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

#47

Post by xxs »

vvanders wrote: post #45
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…

> of which there's a limit (65k in Android!) Oh man JNI and Android. I've never heard a developer curse up a storm like I did when one of my co-workers inadvertently stumbled across the 512 LocalRef limit(also a fun one) during an intermittent crash repro. By the time he got done with his rant we had to talk him out of purchasing a one-way plane ticket to Mountain View.

I've mentioned it earlier, yet - if you need native code use direct byte buffers as shared memory between java/c and hold/use no refs inside the native code.

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

#48

Post by jcdavis »

alkonaut wrote: post #37
matthewwarren wrote: post #28

Earlier quoted context omitted.

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.

FWIW, graal has partial escape analysis, which can avoid a lot of those pitfalls by allowing allocations to escape through just some of the branches. For instance, if you have

    X thing = new ...;
    if (slowpath) {
        unlikely_function(thing);
    }
    ...
Even if unlikely_function isn't inlined, it can still perform scalar replacement, and push the allocation site into the branch (reconstructing the state of the allocated object as it would've been at that point), which is a big improvement.

This in turn lets the inliner be smarter about what it does and doesn't inline, vs c2 which tries to greedily inline everything, partly to assist escape analysis

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

#49

Post by ramchip »

dfox wrote: post #43
ramchip wrote: post #40

Earlier quoted context omitted.

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?

That is why the "AFAIK" was there :) Few years ago I read some paper from Ericsson that described non-moving generational GC explicitly designed for Erlang's data model which could even be implemented in terms of malloc()/free(), I'm not sure that it was relevant to how it is implemented in current BEAM.

That’s quite possible. The GC has changed several times. There was even a unified heap fork of Erlang at some point: https://www.researchgate.net/profile/Marc_Feeley/publication...

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

#50

Post by celdon25 »

rjbwork wrote: post #42
apardoe-MSFT wrote: post #32

"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.

>they'll totally forget that allocation is expensive no matter what the platform or runtime. Well, it's easier to do in a managed language. When you literally don't have to agonize or obsess over every allocation because you aren't responsible for cleaning it up (unmanaged held resources withstanding), you tend not to do so. P.S.: You're always free to drop down into C or C++ if you want to get some speed, but of cou…

>You're always free to drop down into C or C++ if you want to get some speed

Wouldn't C# with structs and pointers do the job in many cases? I've been able to get 50-fold increases in speed through heavy optimizations, without switching to another language. Using C or C++ solely for a "speed boost" over C# is not only unnecessary, but it creates more problems than it solves. If you don't know how to optimize within C# (as a C# developer), how are you going to succeed in writing efficient C++ code?

Once you learn the nuances and limitations of making optimizations in C#, then you should start looking into how and when other languages such as C can wisely be used. To name an example, C makes it easier to micromanage assembly instructions (can be done in C# too, but not in a very practical way, and yes I mean assembly and not IL). C also contains more syntax and features which are suitable for bitwise micromanagement, whereas with C# it can be more awkward.

Post reply on HN