Corefxlab: 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

[AnthonyLloyd]

@safern thanks. Will start to put these in tonight.

[danmoseley]

I tried reordering the chain to bring the hit to the front of the chain. This hurts k-Nuc substantially (3.7s->6.1s) because k-Nuc hits are not clustered.

Here is some logging from 25M -- there are 7 dictionaries. 5 are small or tiny, 2 have 138K items, but all are used for 125M lookups. Essentially every lookup is a hit - which would be good for reordering - but nevertheless ~50% of lookups result in a reorder in the large dictionaries (the small ones have few or no collisions so aren't impacted).

[7244] ###found 100.000% reordered 0.000% of total 124999999; maxSize 0 maxCount 16 adds 16 collisionsOnAdd 0.000%
[7244] ###found 100.000% reordered 0.000% of total 124999998; maxSize 0 maxCount 64 adds 64 collisionsOnAdd 0.000%
[7244] ###found 99.997% reordered 0.000% of total 124999995; maxSize 4096 maxCount 4096 adds 4096 collisionsOnAdd 18.506%
[7244] ###found 100.000% reordered 0.000% of total 125000000; maxSize 0 maxCount 4 adds 4 collisionsOnAdd 0.000%
[7244] ###found 100.000% reordered 0.000% of total 124999997; maxSize 0 maxCount 256 adds 256 collisionsOnAdd 0.000%
[7244] ###found 99.889% reordered 52.050% of total 124999989; maxSize 262144 maxCount 138822 collisionsOnAdd 59.076%
[7244] ###found 99.888% reordered 47.195% of total 124999983; maxSize 262144 maxCount 139912 adds 139912 collisionsOnAdd 55.925%

If I log reorders but don't actually reorder (ie., just count how often the hit is not first in the chain)

[16640] ###found 99.888% would reorder 26.890% of total 124999983; maxSize 262144 maxCount 139912 
[16640] ###found 99.889% would reorder 30.487% of total 124999989; maxSize 262144 maxCount 138822 

so the hit is first in the chain about 70% of the time, without reordering; but about 50% with reordering: reordering makes it worse.

For reordering to be helpful the lookups need to be dominated by hits, there needs to be plenty of collisions (high load factor), Equals needs to be relatively expensive, and the hits need to be heavily clustered. k-Nuc has the first two but not the last two (keys are longs).

[danmoseley]

I also experimented with different initial sizes (as shown above, some of the dictionaries stay small or tiny, but the large ones resize 7 times (from 1024 to 262,144). It made no measurable difference at best, at worse, large initial sizes made perf worse: the resizing cost itself is negligible, and small arrays have a locality benefit. BTW, the benchmark requires that the dictionaries have a fixed reasonable initial size.

[danmoseley]

I also did some simple investigation of whether the 7 tasks are packed well onto the 4 CPU.

Here is a trace of a typical run on the Q6600 (the loading from file is about 240ms and initializing about 315ms before these start)

ID 1  started 00:58.89   took 1,792ms ended 01:00.69
ID 6  started 00:58.89   took 2,171ms ended 01:01.07
ID 18 started 00:58.89   took 4,106ms ended 01:03.00
ID 12 started 00:58.89   took 4,303ms ended 01:03.20
ID 2  started 01:00.69   took 1,767ms ended 01:02.46
ID 3  started 01:01.07   took 2,134ms ended 01:03.20
ID 4  started 01:02.46   took 1,845ms ended 01:04.31

This shows the default scheduler starts the first 4 tasks immediately, then the next 3 in turn each time one finishes.

Running them sequentially to see how much work they are:

ID 1  started 34:25.66   took 1,825ms ended 34:27.48
ID 6  started 34:25.66   took 2,038ms ended 34:27.70
ID 3  started 34:27.70   took 1,843ms ended 34:29.54
ID 2  started 34:27.48   took 2,105ms ended 34:29.59
ID 4  started 34:29.54   took 1,960ms ended 34:31.50
ID 12 started 34:25.66   took 6,062ms ended 34:31.72
ID 18 started 34:25.66   took 6,538ms ended 34:32.20

(I am not sure why the long tasks are 4 sec above and 6 sec here - guess I changed something..)

Any 2 of the shorter 5 tasks take less time than the 2 slower tasks each take. So the fastest packing is to put the 3 shortest tasks (the 5th, 6th and 7th) on the same thread, and everything else will be finished earlier. This is what the current ordering in the code already does. Clearly @AnthonyLloyd already went through this thought process!

Naively reordering from slowest to fastest tasks ("LPT algorithm") will give a poorer result, because the 4th and 5th longest tasks will be on the same thread, whereas we want the 5th, 6th, and 7th.