vsadov / nonblocking Goto Github PK

Method hash(...) gets the hash code from the key and applies bitmask to prevent zero hash code. It ORs the actual hashcode with 0b1100_0000_0000_0001

        protected virtual int hash(TKey key)
        {
            Debug.Assert(!(key is null));

            int h = _keyComparer.GetHashCode(key);

            // ensure that hash never matches 0, TOMBPRIMEHASH, ZEROHASH or REGULAR_HASH_BITS
            return h | (SPECIAL_HASH_BITS | 1);
        }

The problem is if two objects have two consecutive hash codes, they will end up with the same hash:

0xXXX0 -> 0xXXX1
0xXXX1 -> 0xXXX1
0xXXX2 -> 0xXXX3
0xXXX3 -> 0xXXX3
0xXXX4 -> 0xXXX5
0xXXX5 -> 0xXXX5
0xXXX6 -> 0xXXX7
0xXXX7 -> 0xXXX7
etc.

As far as I'm aware, tasks are not guaranteed to run asynchronously. Since the tests use tasks (Task.Run ...) instead of threads, it could happen (unlikely) that they run entirely in order, not in a parallel (multiple cores) or simulated-parallel (concurrent) fashion. To ensure a sufficiently adverse environment, the tests should use threads instead of tasks.

Hi,

First off, you have a really cool code here. 👍 It was an interesting exploration looking at the code.

I'm looking to use your NonBlocking collection in some connection pooling code for my RethinkDb.Driver database driver.

I was able to import most of the code but the following Delegate.CreateDelegate isn't available in CoreCLR:

https://github.com/VSadov/NonBlocking/blob/master/src/NonBlockingDictionary/ConcurrentDictionary/DictionaryImpl%602.cs#L24

var del = (Func<ConcurrentDictionary<TKey, TValue>, int, DictionaryImpl<TKey, TValue>>)Delegate.CreateDelegate(
     typeof(Func<ConcurrentDictionary<TKey, TValue>, int, DictionaryImpl<TKey, TValue>>),
     method);

Again, great work here. 👍

Thanks,
Brian

Hi,

I had to stop using the .net concurrent dictionary because of the many heap allocations happening for common operations like reading an existing value from the dictionary . I quickly profiled this implementation too and it seems that the problem is not solved. Can you confirm that you also use similar strategies where you allocate small objects for each operation?

Do you have any recommendations on how to generate those charts because I would like to know how it compares against a regular dictionary.

Hi, I have thoroughly tested the performance of your solution. It really turned out that in single-threaded mode your solution runs 25% faster. However, if you add new threads, your code starts to degrade in time and eventually starts to lose 2 times when 12 thread. At this time, the standard code looks stable regardless of the number of threads. In the tests, I measured the time of adding 10,000,000 elements using the TryAdd method.

System.Collections.Concurrent.ConcurrentDictionary:
ConcurrentDictionary 01 threads, median time - 3966
ConcurrentDictionary 02 threads, median time - 4871
ConcurrentDictionary 03 threads, median time - 4657
ConcurrentDictionary 04 threads, median time - 4514
ConcurrentDictionary 05 threads, median time - 5227
ConcurrentDictionary 06 threads, median time - 4898
ConcurrentDictionary 07 threads, median time - 5424
ConcurrentDictionary 08 threads, median time - 4906
ConcurrentDictionary 09 threads, median time - 5293
ConcurrentDictionary 10 threads, median time - 4811
ConcurrentDictionary 11 threads, median time - 4960
ConcurrentDictionary 12 threads, median time - 4859

NonBlocking.ConcurrentDictionary:
ConcurrentDictionary 01 threads, median time - 2880
ConcurrentDictionary 02 threads, median time - 4361
ConcurrentDictionary 03 threads, median time - 5846
ConcurrentDictionary 04 threads, median time - 6215
ConcurrentDictionary 05 threads, median time - 6559
ConcurrentDictionary 06 threads, median time - 6683
ConcurrentDictionary 07 threads, median time - 6845
ConcurrentDictionary 08 threads, median time - 7147
ConcurrentDictionary 09 threads, median time - 7498
ConcurrentDictionary 10 threads, median time - 8097
ConcurrentDictionary 11 threads, median time - 8478
ConcurrentDictionary 12 threads, median time - 8806

I've noticed that the dictionary has an unusually high rate of resizes even when the load factor is still in mid 50 - 55%.
Digging deeper, I found that the mixing algorithm used in the implementation is to blame:

        protected static int ReduceHashToIndex(int fullHash, int lenMask)
        {
            var h = (uint)fullHash;

            // xor-shift some upper bits down, in case if variations are mostly in high bits
            // and scatter the bits a little to break up clusters if hashes are periodic (like 42, 43, 44, ...)
            // long clusters can cause long reprobes. small clusters are ok though.
            h = h ^ h >> 15;
            h = h ^ h >> 8;
            h = h + (h >> 3) * 2654435769u;

            return (int)h & lenMask;
        }

I've attached two screenshots of GLSL shaders using the hash functions. The first screenshot is the original Wang/Jenkins hash method used by Dr. Cliff Click.

The second screenshot is the hash used by the C# implementation:

As you can clearly see, there is a lot of clustering and, as a result, erroneous resizing even moderately empty tables.

I don't get what these charts are showing. Thanks in advance.

Hello, after download I try compile code:

If you post code, it’s good to be able to compile.

Re: #13 (comment)

Such keys could use the same implementation as primitives
The question is mostly of complexity vs. how common these cases are.