Replacing the .net Dictionary

Question

Provided (simplified description)

One of our services has many instances in memory. About 85% are unique. We need very quick access to the key elements of these elements, since they are requested very often in one stack / call. This single context is extremely optimized for performance.

So, we started putting them into the dictionary. Performance was fine.

Access to items as quickly as possible is most important in this case. Ensures no write operations while reading.

Problem

At the same time, we fall within the limits of the number of elements that the dictionary can store.

Die Arraydimensionen haben den unterstützten Bereich überschritten. bei System.Collections.Generic.Dictionary`2.Resize(Int32 newSize, Boolean forceNewHashCodes) bei System.Collections.Generic.Dictionary`2.Insert(TKey key, TValue value, Boolean add) 

What does the The array dimensions have exceeded the supported range mean.

Solutions like Memcached are too slow in this particular case. This is an isolated very specific use case encapsulated in one service.

So, we are looking for a dictionary replacement for this particular scenario.

I cannot find support at this time. Am I missing something? Can someone point me to one?

Alternatively, if no one exists, we think about their implementation.

We thought of two possibilities. Create it from scratch or wrap several dictionaries.

Wrapping multiple dictionaries

When searching for an element, we can look at the HasCode keys and use its starting number as an index for the list of wrapper dictionaries. Although this seems easy, it smells to me, and it will mean that the hash code is computed twice (once by us once in the internal dictionary) (this scenario is really really cool in performance).

I know that replacing a base type, such as a dictionary, is the last last option, and I want to avoid it. But at present, it seems like there is no way to make objects more unique or get dictionary performance from a database or save performance elsewhere.

I also know that “keep abreast of optimizations”, but lower performance will greatly affect the business requirements behind it.

Answer 1

Before I finished reading your questions, it struck me a few simple dictionaries. But you already know this solution. I assume that you are really pushing the maximum number of elements in the dictionary, and not some other limit.

I would say follow him. I don’t think you should worry about reading the hash twice. If their keys are somehow long, and obtaining a hash is really time-consuming operations (which I doubt but cannot be sure, since you did not mention what keys are), you do not need to use whole keys for your hash function. Just select any part that you are ready to process in your own hashing and distribute the element based on this.

The only thing you need to do is ensure that objects are distributed evenly among your several dictionaries. How difficult it is to achieve this really depends on your keys. If they were completely random numbers, you could just use the first byte, and everything would be fine (if you did not need more than 256 dictionaries). If they are not random numbers, you should think about the distribution in your domain and encode your first hash function in such a way as to achieve this goal of uniform distribution.

Answer 2

I looked at the implementation of .Net Dictionary and it seems that you should be able to store 2 ^ 32 values ​​in your dictionary. (Next to the list of buckets, which themselves are linked lists, there is one array in which all the elements are stored, possibly for a quick iteration, which can be a limiting factor).

If you have not added a value of 2 ^ 32, it is possible that there is a restriction on the items in the bucket (its linked list, so it is probably limited by the maximum stack size). In this case, you should double-check that your hash function evenly distributes the elements in the dictionary. See This Answer for more information. What is the best algorithm for an overridden System.Object.GetHashCode?