[WIP] Remove reflection in ValueType.Equals/GetHashCode #5226

MichalStrehovsky · 2018-01-08T10:38:44Z

My weekend project. Contributes to #5013.

This adds support for emitting new data structures that describe instance field layout of valuetypes that can't be memcompared. The data structure enables us to iterate over fields at runtime and compare them individually.

Adds 7 kB to hello world. The cost of the new blob is about 2 kB and the rest of the diff is a mixed bag of regressions and improvements.

On the improvements side:

The part of the reflection stack that reads fields using reflection is gone from the image
We now generate some new code and EETypes for valuetypes we didn't previously generate. E.g. we now generate an EEType for System.EETypePtr since OpenMethodResolver has a field of that type.

We can get some decent size back if we do some extra work around reflection blocking (to make sure various internal (but "public" in the assembly) valuetypes are not considered reflectable, and therefore boxed, and therefore needing this extra data).

Contributes to dotnet#5013. This adds support for emitting new data structures that describe instance field layout of valuetypes that can't be memcompared. The data structure enables us to iterate over fields at runtime and compare them individually.

MichalStrehovsky · 2018-01-08T10:41:25Z

This is marked as WIP due to the various TODOs.

The major missing thing is runtime support in the type loader. The compiler already emits the native layout data I'm expecting will be sufficient to implement this, but we don't parse the data yet. The type loader support is needed for the annoying case of:

struct Foo<T> { }
struct Bar<T>
{
    Foo<T> _field;
}

Where we dynamically load a e.g. Foo<string>.

mikedn · 2018-01-08T12:10:42Z

src/ILCompiler.Compiler/src/Compiler/DependencyAnalysis/InstanceFieldLayoutNode.cs

+            // would mean we no longer need this information, but we have seen customer code
+            // that does:
+            //
+            // public override bool Equals(object obj) => base.Equals(obj);


Funny. This make me wonder: can't the compiler simply replace the base.Equals(obj) call with code that does the right thing?

What would it replace it with though? It would have to be something that also works for annoying things like:

class Program { struct Foo { public Func<int> CreateDelegate() => base.GetHashCode; public override int GetHashCode() => 0; } static void Main() { Console.WriteLine(default(Foo).GetHashCode()); Console.WriteLine(default(Foo).CreateDelegate()()); } }

What would it replace it with though?

With code that does the same thing as base.Equals(object o) but without needing to know the field layout at runtime.

In your new example you show a struct that doesn't even override Equals. I don't know if it's possible but it would be interesting if ILC could automatically override Equals.

ProjectN does roughly that. However, the generated method bodies can add up to a lot of space in return for the increased efficiency. That compiler actually includes a bit of analysis of which types are likely to have Equals/GetHashCode called and generates bodies for them and then falls back to the base class for cases that it doesn't think are likely (and for cases where it can prove there's no call, it doesn't generate code or metadata). Hopefully we could use something like that here at some point.

ProjectN also needs to rewrite direct calls to System.ValueType::Equals/GetHashCode to call the injected method, but that code is sketchy and we would need to port it into RyuJIT (and all the other codegen backends) if we ever wanted to take the path of synthesizing the overloads in the compiler (like we do in Project N). I'm not a huge fan.

I haven't measured it yet, but I think the code I'm adding is going to be faster than CoreCLR (except for the part where CoreCLR caches the "can use memcmp?" part and we don't). I'm generally fine with everything that is at least as fast as CoreCLR.

jkotas · 2018-01-08T19:52:07Z

I am wondering what this gives us an interesting option. ValueType.Equals/GetHashCode is just one of the many places that use reflection. You will pick up the reflection stack really easily through other paths.

I think that if we want to have lean and mean config without reflection stack - such as for small WebAssembly apps or other experiements, we should have it as an explicit option and you need to make sure that you do not actually use any reflection. ValueType.Equals/GetHashCode won't work in that config and that's expected. The no-reflection config can be implemented by providing an alternative implementation of System.Private.Reflection.Execution/System.Private.Reflection.Core that just wraps runtime types, and pretends that there are no methods, field, attributes, etc. Maybe even drop type names if we want to be really extreme.

morganbr · 2018-01-08T21:31:46Z

...Private.TypeLoader/src/Internal/Runtime/TypeLoader/TypeLoaderEnvironment.ValueTypeSupport.cs

+                if (!typeHandle.Equals(tentativeType))
+                    continue;
+
+                // Found the entry - find the first non-null field


I believe this is only supposed to return the hashcode of the first field, whether or not it's null (yes, it's not a good hash code).

I believe this is only supposed to return the hashcode of the first field, whether or not it's null

That's not how CoreCLR does it:

https://github.com/dotnet/coreclr/blob/4e6435be1f5a77abb875f946fa7bd5dbeb5c3864/src/vm/comutilnative.cpp#L2158-L2159

On closer inspection, you're right on both counts.

If we have to match CoreCLR's behavior, we would also need to incorporate a type differentiator that gets XORed in. While eeTypePtr would be an easy one, I'd have concerns about leaking pointers. The CoreCLR code is:

// To get less colliding and more evenly distributed hash codes, // we munge the class index with two big prime numbers hashCode = typeID * 711650207 + 2506965631U;

Yup, that's why I have a TODO 24 lines above. I would probably use the type's stable hashcode that we include as a field of each EEType but I didn't think about how to combine it yet:

https://github.com/MichalStrehovsky/corert/blob/eee4c66cec59f3e93aa2e476b8e0cae1fa5af223/src/System.Private.TypeLoader/src/Internal/Runtime/TypeLoader/TypeLoaderEnvironment.ValueTypeSupport.cs#L120

morganbr · 2018-01-08T21:32:13Z

...Private.TypeLoader/src/Internal/Runtime/TypeLoader/TypeLoaderEnvironment.ValueTypeSupport.cs

+            int size = RuntimeAugments.GetValueTypeSize(type);
+            int hashCode = 0;
+
+            for (int i = 0; i < size / 4; i++)


Same comment -- just the first field.

Same comment -- just the first field.

That's not how CoreCLR does it either:

https://github.com/dotnet/coreclr/blob/4e6435be1f5a77abb875f946fa7bd5dbeb5c3864/src/vm/comutilnative.cpp#L2070-L2089

Is size guaranteed to be a multiple of 4? If not, we're including random memory here.

If not, we're including random memory here.

Are you sure? i goes from 0 to size / 4 - we discard the remaining bytes. Again, this is not something I invented, I just stole it from CoreCLR.

Whoops, you're right about that. No danger of reading extra memory, though I wonder if it means all 1-3 byte structs end up with 0. This hash code is really really poor. I wonder if we should consider adopting the new HashCode type at some point.

morganbr · 2018-01-08T21:38:33Z

@MichalStrehovsky, how does the size for this contrast to generating method bodies for them? I recall the reflection path saved a bit of space, but it wasn't that large.

@jkotas, while I appreciate the WebAssembly thought, I think we're unlikely to have apps so simple that we don't support ValueType.Equals/GetHashCode -- Dictionaries are pretty popular!

jkotas · 2018-01-08T22:16:03Z

Pretty much everybody overrides ValueType.Equals/GetHashCode because of the built-in implementation is slow and otherwise broken.

There are two features that this is about:

Reflection (full reflection stack code is part of the app)
Non-overriden ValueType.Equals/GetHashCode

I believe that supporting 2 without 1 is not that interesting combination.

Any random larger app or library out these depends on 1, that will make the current implementation of 2 work without much extra cost.

This change makes 2 work without 1 at the cost of introducing extra complexity. If you have an app that is small enough or that you went out of your way to not depend on full reflection stack, avoiding dependency on built-in implementation of ValueType.Equals/GetHashCode should not be a big deal for you.

MichalStrehovsky · 2018-01-08T22:42:30Z

I am wondering what this gives us an interesting option. ValueType.Equals/GetHashCode is just one of the many places that use reflection. You will pick up the reflection stack really easily through other paths.

#5013 has the full list of places that we need to address to have a system where the various non-essential services of the runtime are pay-for-play - the list is not so long. When people are evaluating various platforms, they often look at the size of hello world to get a sense how "bloated" the platform is (it's easy to compare). Investing into a small default configuration for app that essentially does nothing has potential to positively affect perception of the platform - this work is more motivated by that than technical reasons. Switches described deep in the documentation (and that break things when enabled) won't be used much. Console apps that don't use NuGet packages is how people who are new to the platform (or new to the programming in general) write code.

Pretty much everybody overrides ValueType.Equals/GetHashCode because of the built-in implementation is slow and otherwise broken.

Yet in Project N we had to scale back on usage of the reflection code path in favor of the path that overrides the methods at compile time because the reflection based code path on CoreRT is slower than CoreCLR's and the customer just really didn't want to bother to override Equals/GetHashCode.

There are two features that this is about:
1 .Reflection (full reflection stack code is part of the app)
2. Non-overriden ValueType.Equals/GetHashCode
I believe that supporting 2 without 1 is not that interesting combination.

I think it's exactly the kind of small one-off tools that I would want to be tiny where I wouldn't want to bother with overriding Equals/GetHashCode.

@MichalStrehovsky, how does the size for this contrast to generating method bodies for them? I recall the reflection path saved a bit of space, but it wasn't that large.

Codegen version of just an Equals for a struct with a single field is around 80+ bytes of code if we talk about is check, a null check, an unbox call for other, etc. (and on top of that there's relocs, alignment overhead, GC info, etc.). The data structures introduced in this PR are: 2 bytes for an indirection to owning type + 1 byte for field count + 1 byte for field offset + 2 bytes indirection for field type (and 8 bytes for the data indirections point to, assuming they're not shared). So about 14 bytes plus hashtable overhead since this is in a static hashtable. This also includes data we need to do GetHashCode. Codegen needs extra bytes for that too that I didn't measure.

jkotas · 2018-01-09T00:11:24Z

Since you have to be able to generate these at runtime for the dynamic case anyway, can we always use that path to generate the descriptor and not persist it into the image at all?

It would make it less spread through the whole system at least.

MichalStrehovsky · 2018-01-09T09:55:34Z

can we always use that path to generate the descriptor and not persist it into the image at all

Sure, I will look into that.

MichalStrehovsky · 2018-02-23T13:38:05Z

Since you have to be able to generate these at runtime for the dynamic case anyway, can we always use that path to generate the descriptor and not persist it into the image at all?
It would make it less spread through the whole system at least.

I looked at that, but while less code, it wasn't a great improvement (having to put non-generic types into the template map started to make everything pretty hard to reason about). Superseded by #5436.

mikedn reviewed Jan 8, 2018

View reviewed changes

morganbr reviewed Jan 8, 2018

View reviewed changes

MichalStrehovsky mentioned this pull request Feb 23, 2018

Remove reflection in ValueType.Equals/GetHashCode #5436

Merged

MichalStrehovsky closed this Feb 23, 2018

MichalStrehovsky deleted the valuetypeGetHashCodeEquals branch March 21, 2019 15:53

[WIP] Remove reflection in ValueType.Equals/GetHashCode #5226

[WIP] Remove reflection in ValueType.Equals/GetHashCode #5226

Uh oh!

Conversation

MichalStrehovsky commented Jan 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

MichalStrehovsky commented Jan 8, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jkotas commented Jan 8, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

morganbr commented Jan 8, 2018

Uh oh!

jkotas commented Jan 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

MichalStrehovsky commented Jan 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jkotas commented Jan 9, 2018

Uh oh!

MichalStrehovsky commented Jan 9, 2018

Uh oh!

MichalStrehovsky commented Feb 23, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

MichalStrehovsky commented Jan 8, 2018 •

edited

Loading

jkotas commented Jan 8, 2018 •

edited

Loading

MichalStrehovsky commented Jan 8, 2018 •

edited

Loading