Faster dictionary for k-Nucleotide

[danmoseley]

Goal is to include in the proposed corefxlab collection package a dictionary that

1. Outperforms the regular Dictionary<K,V> in k-Nucleotide and the existing top C# submission (that uses reflection tricks)
2. Is sufficiently general purpose that it fits the letter and spirit of the CLBG rules, and is useful beyond the benchmark. For example, it's a dictionary better than Dictionary<K,V> if your keys are ulong. It would be nice if it was not quite that specific (for example, possibly it is better if your keys' hashcode is cheap to calculate, so it need not be stored). Java's submission uses a dictionary that is specialized specifically <long, int> but it is part of a package that also has dictionaries specialized for every other kind of combination also.

@mikedn has a version that he found to be 40% faster than the current submission, we may want to explore taking that and making this slightly less specialized.

@Zhentar noted in another issue that K-Nuc benefits tremendously from coalesced chaining preserving insertion order locality ie., it's probably best to stick with chaining rather than open addressing.

@safern @AnthonyLloyd

[danmoseley]

@AnthonyLloyd before we look around, do you have any interest in exploring this one?

[AnthonyLloyd]

I'm happy to help. You seem to be on a great track with the @mikedn version. Not sure I understand the @Zhentar point.

It would be good if the collections were general purpose but optimized for common problem tasks e.g. int/ulong keys, ref values or aggregation. I think developers would be able to make great use of them.

[mikedn]

I don't think int/long specialization are actually needed. They're definitely needed in Java due to its generics implementation that makes boxing unavoidable. For C# you could probably get quite far with a few tweaks:

• Avoid IEqualityComparer, it's problematic due to the cost of interface calls and lack of devirtualization/inlining (this has actually been solved but only for some specific cases). Either just call object.GetHashCode (should work well for key value types) or find another way to provide hash code/equality customizations (via generic type parameters).
• Don't store the hash code in the hashtable entries. Leave to the key type to deal with hashes that are slow to compute. In such cases the actual key type can be wrapped in a struct that contains the actual key value and the cached hash code.

[Zhentar]

@AnthonyLloyd in theory, coalesced chaining is a cache unfriendly algorithm; for a large table and random access, you typically take two cache misses for a single lookup; once in the buckets array and once in the entries array. But K-Nuc is not random access; if you look up "gacgaatatatt" then there is a very high probability that the next thing you look up is "acgaatatatta". You're still doing random access into the buckets array (which being just an int32 array will have higher chances of higher level cache hits than an array holding the keys and values), but since they were added to the hashmap in that same order they are adjacent in the entries array, and you get an L1 cache hit.

This only really matters for the 12 & 16 base tasks, which have ~3-4MB maps for a reasonable capacity factor; the 6 base pair & smaller dictionaries would probably benefit from an open addressing hashmap that doesn't incur the chaining overhead costs.

[AnthonyLloyd]

@Zhentar Ah, thank you. This means it could probably be made much faster then.

[danmoseley]

@AnthonyLloyd shall I assign this to you? I'm excited to see what numbers you can get.

BTW we actually have a Q6600 based machine that gives numbers very close to the official ones if needed.

[AnthonyLloyd]

Yes, please do.

Can you give me some pointers on where the code should live and similar coding style to replicate?

[danmoseley]

@AnthonyLloyd I sent you a collaborator invite. If you accept, I can assign this. Note, it will auto-subscribe you to notifications for this repo, you may choose to switch that off.

Can you give me some pointers on where the code should live and similar coding style to replicate?

@safern will create the package shortly. That shouldn't block you from experimenting with code of course.

The coding style and practices should be the same as in corefx, eg.,
https://github.com/dotnet/corefx/blob/master/Documentation/coding-guidelines/coding-style.md (there may be other relevant info in that folder also). One example is the existing code for Dictionary: https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Collections/Generic/Dictionary.cs

Functional tests will need to go in a new folder here, looks like the same approach as corefx:
https://github.com/dotnet/corefxlab/tree/master/tests

For perf tests, they are here and also a readme:
https://github.com/dotnet/corefxlab/tree/master/tests/Benchmarks

Right now they are in xunit.perf - there's a parallel effort to convert to Benchmark.NET that should not affect you.

If it's helpful, existing perf tests for the regular Dictionary are here
https://github.com/dotnet/corefx/blob/master/src/System.Collections/tests/Performance/Perf.Dictionary.cs

[danmoseley]

I don't think int/long specialization are actually needed.

Maybe then this can be a dictionary for value type keys - that would be nicely general purpose and very much in the spirit of CLBG.

[AnthonyLloyd]

Great thanks. Looking forward to seeing what we can do.

[danmoseley]

Assigned.

[Zhentar]

@AnthonyLloyd BTW there's a minor bug the C# K-Nuc implementation - the 12 & 18 base tasks are using masks of 0x7FFFFF and 0x7FFFFFFFF, when they should be 0x3FFFFF and 0x3FFFFFFFF (unfortunately this only adds on a few hundred keys so gains from fixing it are pretty small)

[AnthonyLloyd]

@Zhentar Ok thanks

[safern]

@AnthonyLloyd I just merged a PR to create this new package, so please fill free to add your implementation under:

https://github.com/dotnet/corefxlab/tree/master/src/Microsoft.Experimental.Collections

Unit tests under:
https://github.com/dotnet/corefxlab/tree/master/tests/Microsoft.Experimental.Collections.Tests

Finally, perf tests under:
https://github.com/dotnet/corefxlab/tree/master/tests/Benchmarks/Microsoft.Experimental.Collections

We use BenchmarkDotNet to run perf tests: https://github.com/dotnet/BenchmarkDotNet