Improve Density of GC heap by String Interning (de-duping) on Gen2 GC

[vancem]

It has been noted that for some applications (notably applications like MSBuild or Visual Studio) that manipulate many file paths, or deserialize large text-based payloads (e.g. JSON or XML), tend to have many duplicated strings. We could reduce the size of the GC heap by interning them (that is using the same string for all instances of a particular string value). The runtime already does this for string literals, but strings that are constructed at runtime do not benefit.

To implement this you need a table that remembers all the existing strings that is indexed by string value. While you COULD do this table lookup check when strings are first created, this is not likely to be a good approach because MANY strings have very short lifetimes, and it would slow down ALL strings creation.

Instead the idea is to do the interning check when as part of promoting the object from GC generation 1 to GC generation 2. This is a nice place to do it because

1. Most strings die before reaching Gen 2
2. However if they do make it, they are 'expensive' strings in that they are likely to live a long time.
3. Thus it makes sense to de-dup at that point

Another nice aspect of this feature is that it does not need to be perfect (you dont' HAVE to dedup everything). Thus the hash table you keep can be of fixed size with 'replace on collision' semantics, which is simple and bounded, and tends to favor younger strings (all good things).

The expectation is that typical apps have 20% of their GC heap be strings. Some measurements we have seen is that for at least some applications, 10-30% of strings all may be duplicated, so this might save 2-3% of the GC heap. Not huge, but the feature is not that difficult either.

The first step to build enough of a prototype, so that we can run it on a number of interesting apps and get a feel for how much GC space would save us and how much overhead this would add to (gen 1 and gen 2) GCs.

[sharwell]

⚠️ This would make the lock (someString) syntax subject to arbitrary and uncontrollable collisions.

[swgillespie]

I feel like we already have this problem, since you can intern arbitrary strings already with string.Intern. Though you can query whether or not a string is interned with string.IsInterned, so it's perhaps a bit less arbitrary than this, locking on interned strings can cause behavior just as surprising as this.

[sharwell]

@swgillespie That is a very different problem, which can be described as "If you are going to lock on a string, don't intern it." This is easily understandable and avoidable if locking on a string is something you intend to do. The problem this proposal would introduce is "Don't lock on a string because someone else may randomly intern it even if you don't."

⚠️ This proposal also breaks sentinel strings which serve some intentional purpose through reference equality, such as the implementation discussed in comments in antlr/stringtemplate4#132.

[danmoseley]

@sharwell presumably we could add an app-level opt out for rare cases where a library depends on that.

I note that Java interns the backing char array, not the object, and note that avoids the problem of locking on the string (http://openjdk.java.net/jeps/192). @vancem is that possible? It could reduce the locality of the string object and the char array.

[jkotas]

We do not use separate arrays for strings like Java does. The string payload is inline (it is smaller that way).

[ufcpp]

For the purpose of deserializing text-based payloads, we can parse and compare numbers and property names directly from UTF8 binary to reduce heap allocations. For instance this Utf8Json library can deserialize JSON texts with very small allocations.

[sharwell]

presumably we could add an app-level opt out for rare cases where a library depends on that.

How would a user know? The example is part of a publicly distributed library, and is an implementation detail which is never intended to be part of the public documentation/usage requirements.

[vancem]

The possibility of someone using lock on a string object that @sharwell is something we would have to at least worry about. It was already a bad idea to use strings as lock object (because of literal interning), and we would want to make that very clear by adding a compiler error (it can't be perfect, but it is likely to catch most/all real world usage of strings as lock objects). Part of the investigation would be to see how common it is (and in particular does it really ever happen that the SAME string value is used for lock objects). There are mitigations (don't intern when we notice the string has been used for a lock), but hopefully the simpler solution of enforcing 'don't do that' will be enough...

I don't think this issue should block the prototype, but if someone wantsto run an analyzer over all nuget packages looking for locks on strings, that would be useful information to have.

[benaadams]

This would make the lock (someString) syntax subject to arbitrary and uncontrollable collisions.

Locking on a string can be problematic; if you use that string in as a dictionary key, or do anything else that calls GetHashcode on it will mutate its syncblock and change from being able to have fast locks to needing slow locks (though string's syncblock is weirder than the others anyway as it stores isAscii and things, so may already be a slow lock object?)

A good candidate for a lock is a vanilla object e.g. object _lock = new object(); that's not used for anything else - unless you are string to save space; when an object that GetHashcode() definitely isn't called on works too.

This proposal also breaks sentinel strings which serve some intentional purpose through reference equality, such as the implementation discussed in comments in antlr/stringtemplate4#132.

There is no String(string s) .ctor in .NET and at compile time any string in source is interned; you need to construct it from a char[] to avoid it. e.g. new String("key".ToCharArray())

Even have some tests confirming this behaviour - to ensure object.ReferenceEquals(s0, s1) can be called on 2 different strings specified in different places in source using quotes e.g. "a string" and elsewhere "a string"

e.g.

ReferenceEquals("a string", "a string")

Will return true

[vancem]

@benaadams - just FYI, literal strings are OFTEN interned, but are not guaranteed to be interned. In particular literal strings that are precompiled but live in different modules will not be interned (since at compile time we don't know about the other and we don't want to do the extra work at runtime to make interning perfect).

For quite a while we have wanted to get off this 'locks are on object' convention. The idea is that we make up a real 'Lock' object and you use that. This avoids all the weird sync-block stuff. We should probably open an issue on that as well.

But for now, the issue @sharwell brings up is valid, but there are mitigations (although not perfect).

[FSou1]

@vancem Should the GC to remove strings from this table when they become into the 2nd generation and won't be used later?

[benaadams]

@FSou1 would do that as is normal now?

I assume the idea is to catch a string before it moves to Gen2; and either replace its reference with one already in Gen2 or one about to move to Gen2 (so only one string is promoted - rest are collected).

[vancem]

@vancem Should the GC to remove strings from this table when they become into the 2nd generation and won't be used later?

The table would hold weak handles to the strings. Thus when the strings die they naturally also die in the table (but there is logic necessary to reuse the weak handles).

[Maoni0]

The topic of string de-dup had come up before. The reasons why we didn't implement it included the following:

1. the benefit is not so obvious as folks already pointed out so far on this thread.

2. java's strings' payload is separated from the header object which allows most of the de-dup work to happen on a background thread; we can't do that because ours is inline and increasing the stop-the-world pause is something we are reluctant to do unless there is a strong justification.

[sharwell]

⚠️ This could also break code where users intentionally or unintentionally modify string contents in unsafe code. It's been a long time now, but I have seen an application before that used unsafe to turn strings mutable as part of some allocation-reducing operation that for some reason wasn't using StringBuilder.