Backport improvements from DictionarySlim to Dictionary

[danmoseley]

Keeping a list of changes made in DictionarySlim that could benefit Dictionary

• Instead of & 0x7FFFFFFF; to remove the sign bit on the hash code, use (uint) cast and store a uint hashcode, retaining more entropy. To store 'empty' instead of hashcode of -1 use this scheme:

            // 0-based index of next entry in chain: -1 means end of chain
            // also encodes whether this entry _itself_ is part of the free list by changing sign and subtracting 3,
            // so -2 means end of free list, -3 means index 0 but on free list, -4 means index 1 but on free list, etc.
            public int next;

• Eliminate the _freeCount field and use _freeList == -1 as a sentinel instead
• Eliminate _buckets == null check on every access, use a dummy 1-element array instead, on which reads fail and adds cause a resize into a real array

Some of these apply to HashSet<T> also.

@AnthonyLloyd @Zhentar

[benaadams]

Instead of & 0x7FFFFFFF; to remove the sign bit on the hash code, use (uint) cast.

Store uint hashcodes rather than int hashcodes?

-1 is currently used to represent empty.

[danmoseley]

@benaadams yes, clarified above

[danmoseley]

@MarcoRossignoli this may be interesting to you. It would require perf measurements using the new perf repo.

[MarcoRossignoli]

@danmosemsft interesting, I'll need some time to understand amendments and new repo organization, but if there's no rush I'm happy to try!
Plan:

1. move/merge some new slimdic tests(from corefx lab) on new perf repo.
2. amend dictionary with new improvements and do perf comparison.

Correct?

[danmoseley]

@MarcoRossignoli actually im not sure there is anything to port from corefxlab. The existing dictionary perf tests have moved from corefx repo to dotnet/performance repo. Those are the ones to run.

[MarcoRossignoli]

Ah ok perfect!So we need only amend and do comparison?

[danmoseley]

@MarcoRossignoli yes there should be enough perf test coverage already, and Adam has made it super easy to run the tests in the perf repo

Would you like me to assign this to you?

[MarcoRossignoli]

Yes I'm on it right now, https://github.com/MarcoRossignoli/marcorossignoli.github.io/compare/dicbackporting dotnet/BenchmarkDotNet#1031
I disposed some PRs, I've got only one to merge, usually I don't work on new stuff if I've more that 2/3 PR ongoing to avoid too slow reply in case of rush, this is the reason why sometimes I ask for PTAL 😊 but I'm aware that you're full of work and do your best!

[danmoseley]

😄 yes don't hesitate to ping code reviewers.

[MarcoRossignoli]

Adam has made it super easy to run the tests in the perf repo

Oh yes benchmarks_ci.py works like a charm 🚀 🚀 🚀 Adam and José are doing amazing work.

[MarcoRossignoli]

1. Is there a way to compile only managed System.Private.CoreLib?

F:\git\coreclr\src\System.Private.CoreLib (master -> origin)
λ msbuild /t:rebuild /v:m

Above fails, I would avoid build -skiptests -skipnative if possible to be faster.
I'm using a raw script to fast compile/relink and I was wondering if it could be faster coreclr managed rebuild.

2. To debug inside System.Private.CoreLib I'm using System.Diagnostic.Debugger.Launch()+ run some corefx test, is there better trick to stop on breakpoint?

/cc @jkotas @ViktorHofer

EDIT: Could we use new startups hook to find and wait IsAttacched on-the-fly?

[ViktorHofer]

Why can't you set a breakpoint in the unit test in corefx and step into the CoreLib code you are interested in? Debugging with VS 2019 >= Preview 2 should work fine again.

[MarcoRossignoli]

@ViktorHofer you mean compile coreclr in debug compile corefx with local coreclr in debug and breakpoint should work?(tried in past but with no luck)

[ViktorHofer]

It shouldn't really matter if debug or release but in debug you will get more accurate debugging results.